Grado mínimo de tres Nodes formando un triángulo en un Gráfico dado

Dado un grafo no dirigido que consta de N vértices y M aristas y una array edge [][] , en la que cada fila representa dos vértices conectados por una arista, la tarea es encontrar el grado mínimo de tres Nodes que forman un triángulo en el gráfico . Si no existe ningún triángulo en el gráfico , imprima «-1» .

Ejemplos:

Entrada: N = 7, Bordes = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6] , [3, 7]]
Salida: 4
Explicación: A continuación se muestra la representación del gráfico anterior:

Hay dos triángulos conectados:

  1. Uno formado por los Nodes {1, 2, 3}. Grado del triángulo = 5.
  2. Segundo triángulo formado por los Nodes {2, 3, 7}. Grado del triángulo = 4.

El grado mínimo es 4.

Entrada: N = 6, Bordes = [[1, 2], [1, 3], [2, 3], [1, 6], [3, 4], [4, 5]]
Salida: 2

Enfoque: El problema dado se puede resolver encontrando el grado de cada triplete de Nodes que forman un triángulo y contando el grado de cada Node en ese triángulo. Siga los pasos a continuación para resolver el problema:

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum degree
// of a connected triangle in the graph
int minTrioDegree(int N,
                  vector<vector<int> >& Edges)
{
    // Store the degree of each node
    // in the graph
    int degree[N + 1] = { 0 };
 
    // Stores the representation of
    // graph in an adjancency matrix
    int adj[N + 1][N + 1] = { 0 };
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.size(); i++) {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u->v and v->u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = INT_MAX;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == INT_MAX ? -1 : ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > Edges;
    Edges = { { 1, 2 }, { 1, 3 },
              { 2, 3 }, { 1, 4 },
              { 2, 5 }, { 2, 7 },
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    cout << minTrioDegree(N, Edges);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N,int [][]Edges)
{
    // Store the degree of each node
    // in the graph
    int degree[] = new int[N + 1];
 
    // Stores the representation of
    // graph in an adjancency matrix
    int adj[][] = new int[N + 1][N + 1];
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.length; i++) {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = Integer.MAX_VALUE;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = Math.min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == Integer.MAX_VALUE ? -1 : ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int [][]Edges = { { 1, 2 }, { 1, 3 },
              { 2, 3 }, { 1, 4 },
              { 2, 5 }, { 2, 7 },
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    System.out.print(minTrioDegree(N, Edges));
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
import sys
 
# Function to find the minimum degree
# of a connected triangle in the graph
def minTrioDegree(N, Edges):
 
    # Store the degree of each node
    # in the graph
    degree = [0] * (N+1)
 
    # Stores the representation of
    # graph in an adjancency matrix
    adj = []
 
    for i in range(0, N+1):
        temp = []
        for j in range(0, N+1):
            temp.append(0)
 
        adj.append(temp)
 
    # Create the adjacency matrix and
    # count the degree of nodes
    for i in range(len(Edges)):
 
        # u & v are the endpoint of
        # the ith edge
        u = Edges[i][0]
        v = Edges[i][1]
         
        # Mark both edges i.e.,
        # edge u->v and v->u
        adj[u][v] = adj[u][v] = 1
 
        # Increment degree by 1
        # of both endnodes
        degree[u] += 1
        degree[v] += 1
 
    # Stores the required result
    ans = sys.maxsize
 
    # Traverse for the first node
    for i in range(1, N+1, 1):
 
        # Traverse for the second node
        for j in range(i + 1, N+1, 1):
 
            # If there is an edge between
            # these two nodes
            if adj[i][j] == 1:
 
                # Traverse all possible
                # third nodes
                for k in range(j + 1, N+1, 1):
 
                    # If there is an edge
                    # between third node
                    # and the previous two
                    if (adj[i][k] == 1) and (adj[j][k] == 1):
 
                        # Update ans
                        ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
 
    # Return the result
    if ans == sys.maxsize:
        return -1
    return ans
 
# Driver Code
Edges = [[1, 2], [1, 3], [2, 3], [1, 4], [2, 5], [2, 7], [3, 6], [3, 7]]
N = 7
 
print(minTrioDegree(N, Edges))
 
# This code is contributed by Dharanendra L V.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
// Function to find the minimum degree
// of a connected triangle in the graph
static int minTrioDegree(int N, int [,]Edges)
{
   
    // Store the degree of each node
    // in the graph
    int []degree = new int[N + 1];
 
    // Stores the representation of
    // graph in an adjancency matrix
    int [,]adj = new int[N + 1, N + 1];
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (int i = 0; i < Edges.GetLength(0); i++)
    {
 
        // u & v are the endpoint of
        // the ith edge
        int u = Edges[i, 0];
        int v = Edges[i, 1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u, v] = adj[u, v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    int ans = int.MaxValue;
 
    // Traverse for the first node
    for (int i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (int j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i,j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (int k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i,k] == 1
                        && adj[j,k] == 1) {
 
                        // Update ans
                        ans = Math.Min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == int.MaxValue ? -1 : ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]Edges = { { 1, 2 }, { 1, 3 },
              { 2, 3 }, { 1, 4 },
              { 2, 5 }, { 2, 7 },
              { 3, 6 }, { 3, 7 } };
    int N = 7;
 
    Console.Write(minTrioDegree(N, Edges));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// javascript program for the above approach
 
// Function to find the minimum degree
// of a connected triangle in the graph
function minTrioDegree(N,Edges)
{
    // Store the degree of each node
    // in the graph
    var degree = Array.from({length: N+1}, (_, i) => 0);
 
    // Stores the representation of
    // graph in an adjancency matrix
    var adj = Array(N+1).fill(0).map(x => Array(N+1).fill(0));
 
    // Create the adjacency matrix and
    // count the degree of nodes
    for (var i = 0; i < Edges.length; i++) {
 
        // u & v are the endpovar of
        // the ith edge
        var u = Edges[i][0];
        var v = Edges[i][1];
 
        // Mark both edges i.e.,
        // edge u.v and v.u
        adj[u][v] = adj[u][v] = 1;
 
        // Increment degree by 1
        // of both endnodes
        degree[u]++;
        degree[v]++;
    }
 
    // Stores the required result
    var ans = Number.MAX_VALUE;
 
    // Traverse for the first node
    for (var i = 1; i <= N; i++) {
 
        // Traverse for the second node
        for (var j = i + 1; j <= N; j++) {
 
            // If there is an edge between
            // these two nodes
            if (adj[i][j] == 1) {
 
                // Traverse all possible
                // third nodes
                for (var k = j + 1;
                     k <= N; k++) {
 
                    // If there is an edge
                    // between third node
                    // and the previous two
                    if (adj[i][k] == 1
                        && adj[j][k] == 1) {
 
                        // Update ans
                        ans = Math.min(ans,
                                  degree[i]
                                      + degree[j]
                                      + degree[k] - 6);
                    }
                }
            }
        }
    }
 
    // Return the result
    return ans == Number.MAX_VALUE ? -1 : ans;
}
 
// Driver Code
var Edges = [ [ 1, 2 ], [ 1, 3 ],
              [ 2, 3 ], [ 1, 4 ],
              [ 2, 5 ], [ 2, 7 ],
              [ 3, 6 ], [ 3, 7 ] ];
    var N = 7;
 
    document.write(minTrioDegree(N, Edges));
 
// This code is contributed by 29AjayKumar
</script>
Producción: 

4

 

Complejidad de Tiempo: O(N 3
Espacio Auxiliar: O(N 2 ) 

Publicación traducida automáticamente

Artículo escrito por sumukh_bhardwaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *