Número de triángulos en un gráfico no dirigido

Dado un gráfico simple no dirigido, necesitamos encontrar cuántos triángulos puede tener. Por ejemplo, el siguiente gráfico tiene 2 triángulos.
 

triangle2

C++

// A C++ program for finding
// number of triangles in an
// Undirected Graph. The program
// is for adjacency matrix
// representation of the graph
#include <bits/stdc++.h>
using namespace std;
  
// Number of vertices in the graph
#define V 4
  
//  Utility function for matrix
// multiplication
void multiply(int A[][V], int B[][V], int C[][V])
{
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            C[i][j] = 0;
            for (int k = 0; k < V; k++)
                C[i][j] += A[i][k]*B[k][j];
        }
    }
}
  
// Utility function to calculate
// trace of a matrix (sum of
// diagonal elements)
int getTrace(int graph[][V])
{
    int trace = 0;
    for (int i = 0; i < V; i++)
        trace += graph[i][i];
    return trace;
}
  
//  Utility function for calculating
// number of triangles in graph
int triangleInGraph(int graph[][V])
{
    // To Store graph^2
    int aux2[V][V];
  
    // To Store graph^3
    int aux3[V][V];
  
    //  Initialising aux
    // matrices with 0
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            aux2[i][j] = aux3[i][j] = 0;
  
    // aux2 is graph^2 now  printMatrix(aux2);
    multiply(graph, graph, aux2);
  
    // after this multiplication aux3 is
    // graph^3 printMatrix(aux3);
    multiply(graph, aux2, aux3);
  
    int trace = getTrace(aux3);
    return trace / 6;
}
  
// driver code
int main()
{
  
    int graph[V][V] = {{0, 1, 1, 0},
                       {1, 0, 1, 1},
                       {1, 1, 0, 1},
                       {0, 1, 1, 0}
                      };
  
    printf("Total number of Triangle in Graph : %d\n",
            triangleInGraph(graph));
    return 0;
}

Java

// Java program to find number
// of triangles in an Undirected
// Graph. The program is for
// adjacency matrix representation
// of the graph
import java.io.*;
  
class Directed
{
    // Number of vertices in
    // the graph
    int V = 4;
   
   //  Utility function for
   // matrix multiplication
   void multiply(int A[][], int B[][],
                            int C[][])
   {
       for (int i = 0; i < V; i++)
       {
           for (int j = 0; j < V; j++)
           {
               C[i][j] = 0;
               for (int k = 0; k < V; 
                                   k++)
               {
                   C[i][j] += A[i][k]*
                              B[k][j];
               }
           }
       }
   }
   
   // Utility function to calculate
   // trace of a matrix (sum of
   // diagonal elements)
   int getTrace(int graph[][])
   {
       int trace = 0;
  
       for (int i = 0; i < V; i++)
       {
           trace += graph[i][i];
       }
       return trace;
   }
   
   // Utility function for
   // calculating number of
   // triangles in graph
   int triangleInGraph(int graph[][])
   {
       // To Store graph^2
       int[][] aux2 = new int[V][V];  
  
       // To Store graph^3
       int[][] aux3 = new int[V][V];
   
       // Initialising aux matrices
       // with 0
       for (int i = 0; i < V; ++i)
       {
           for (int j = 0; j < V; ++j)
           {
               aux2[i][j] = aux3[i][j] = 0;
           }
       }
   
       // aux2 is graph^2 now
       // printMatrix(aux2)
       multiply(graph, graph, aux2);
   
       // after this multiplication aux3
       // is graph^3 printMatrix(aux3)
       multiply(graph, aux2, aux3);
   
       int trace = getTrace(aux3);
  
       return trace / 6;
   }
   
   // Driver code
   public static void main(String args[])
   {
       Directed obj = new Directed();
         
       int graph[][] = { {0, 1, 1, 0},
                         {1, 0, 1, 1},
                         {1, 1, 0, 1},
                         {0, 1, 1, 0}
                       };
  
       System.out.println("Total number of Triangle in Graph : "+
              obj.triangleInGraph(graph));
   }
}
  
// This code is contributed by Anshika Goyal.

Python3

# A Python3 program for finding number of 
# triangles in an Undirected Graph. The 
# program is for adjacency matrix 
# representation of the graph 
  
# Utility function for matrix 
# multiplication 
def multiply(A, B, C):
    global V
    for i in range(V):
        for j in range(V):
            C[i][j] = 0
            for k in range(V):
                C[i][j] += A[i][k] * B[k][j]
  
# Utility function to calculate 
# trace of a matrix (sum of 
# diagonal elements) 
def getTrace(graph):
    global V
    trace = 0
    for i in range(V):
        trace += graph[i][i] 
    return trace
  
# Utility function for calculating 
# number of triangles in graph 
def triangleInGraph(graph):
    global V
      
    # To Store graph^2 
    aux2 = [[None] * V for i in range(V)]
  
    # To Store graph^3 
    aux3 = [[None] * V for i in range(V)]
  
    # Initialising aux 
    # matrices with 0
    for i in range(V):
        for j in range(V):
            aux2[i][j] = aux3[i][j] = 0
  
    # aux2 is graph^2 now printMatrix(aux2) 
    multiply(graph, graph, aux2) 
  
    # after this multiplication aux3 is 
    # graph^3 printMatrix(aux3) 
    multiply(graph, aux2, aux3) 
  
    trace = getTrace(aux3) 
    return trace // 6
  
# Driver Code
  
# Number of vertices in the graph 
V = 4
graph = [[0, 1, 1, 0], 
         [1, 0, 1, 1], 
         [1, 1, 0, 1], 
         [0, 1, 1, 0]]
  
print("Total number of Triangle in Graph :",
                    triangleInGraph(graph))
  
# This code is contributed by PranchalK

C#

// C# program to find number
// of triangles in an Undirected
// Graph. The program is for
// adjacency matrix representation
// of the graph
using System;
  
class GFG
{
// Number of vertices 
// in the graph
int V = 4;
  
// Utility function for
// matrix multiplication
void multiply(int [,]A, int [,]B,
                        int [,]C)
{
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            C[i, j] = 0;
            for (int k = 0; k < V; 
                              k++)
            {
                C[i, j] += A[i, k]*
                           B[k, j];
            }
        }
    }
}
  
// Utility function to 
// calculate trace of 
// a matrix (sum of 
// diagonal elements)
int getTrace(int [,]graph)
{
    int trace = 0;
  
    for (int i = 0; i < V; i++)
    {
        trace += graph[i, i];
    }
    return trace;
}
  
// Utility function for
// calculating number of
// triangles in graph
int triangleInGraph(int [,]graph)
{
    // To Store graph^2
    int[,] aux2 = new int[V, V]; 
  
    // To Store graph^3
    int[,] aux3 = new int[V, V];
  
    // Initialising aux matrices
    // with 0
    for (int i = 0; i < V; ++i)
    {
        for (int j = 0; j < V; ++j)
        {
            aux2[i, j] = aux3[i, j] = 0;
        }
    }
  
    // aux2 is graph^2 now
    // printMatrix(aux2)
    multiply(graph, graph, aux2);
  
    // after this multiplication aux3
    // is graph^3 printMatrix(aux3)
    multiply(graph, aux2, aux3);
  
    int trace = getTrace(aux3);
  
    return trace / 6;
}
  
// Driver code
public static void Main()
{
    GFG obj = new GFG();
          
    int [,]graph = {{0, 1, 1, 0},
                    {1, 0, 1, 1},
                    {1, 1, 0, 1},
                    {0, 1, 1, 0}};
  
    Console.WriteLine("Total number of " + 
                   "Triangle in Graph : "+
              obj.triangleInGraph(graph));
}
}
  
// This code is contributed by anuj_67.

Javascript

<script>
  
// Javascript program to find number
// of triangles in an Undirected
// Graph. The program is for
// adjacency matrix representation
// of the graph
  
// Number of vertices in the graph
let V = 4;
  
//  Utility function for matrix
// multiplication
function multiply(A, B, C)
{
    for(let i = 0; i < V; i++)
    {
        for(let j = 0; j < V; j++)
        {
            C[i][j] = 0;
            for(let k = 0; k < V; k++)
                C[i][j] += A[i][k] * B[k][j];
        }
    }
}
  
// Utility function to calculate
// trace of a matrix (sum of
// diagonal elements)
function getTrace(graph)
{
    let trace = 0;
    for(let i = 0; i < V; i++)
        trace += graph[i][i];
          
    return trace;
}
  
//  Utility function for calculating
// number of triangles in graph
function triangleInGraph(graph)
{
      
    // To Store graph^2
    let aux2 = new Array(V);
  
    // To Store graph^3
    let aux3 = new Array(V);
  
    // Initialising aux
    // matrices with 0
    for(let i = 0; i < V; ++i)
    {
        aux2[i] = new Array(V);
        aux3[i] = new Array(V);
        for(let j = 0; j < V; ++j)
        {
            aux2[i][j] = aux3[i][j] = 0;
        }
    }       
  
    // aux2 is graph^2 now  printMatrix(aux2);
    multiply(graph, graph, aux2);
  
    // After this multiplication aux3 is
    // graph^3 printMatrix(aux3);
    multiply(graph, aux2, aux3);
  
    let trace = getTrace(aux3);
    return (trace / 6);
}
  
// Driver code 
let graph = [ [ 0, 1, 1, 0 ],
              [ 1, 0, 1, 1 ],
              [ 1, 1, 0, 1 ],
              [ 0, 1, 1, 0 ] ];
  
document.write("Total number of Triangle in Graph : " +
               triangleInGraph(graph));
                 
// This code is contributed by divyesh072019     
  
</script>

C++

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
  
using namespace std;
  
#define V 4
  
int main()
{
    // Graph represented as adjacency matrix
    int graph[][V] = {{0, 1, 1, 0},
                      {1, 0, 1, 1},
                      {1, 1, 0, 1},
                      {0, 1, 1, 0}};
  
    // create the adjacency list of the graph (as bit masks)
    // set the bits at positions [i][j] & [j][i] to 1, if there is an undirected edge between i and j
    vector<bitset<V>> Bitset_Adj_List(V);
    for (int i = 0; i < V;i++)
        for (int j = 0; j < V;j++)
            if(graph[i][j])
                Bitset_Adj_List[i][j] = 1,
                Bitset_Adj_List[j][i] = 1;
  
    int ans = 0;
  
    for (int i = 0; i < V;i++)
        for (int j = 0; j < V;j++)
              
            // if i & j are adjacent
            // compute the number of nodes that are adjacent to i & j
            if(Bitset_Adj_List[i][j] == 1 && i != j){
                bitset<V> Mask = Bitset_Adj_List[i] & Bitset_Adj_List[j];
                ans += Mask.count();
            }
  
   // divide the answer by 6 to avoid duplicates
   ans /= 6;
  
   cout << "The number of Triangles in the Graph is : " << ans;
    
    // This code is contributed
    // by Gatea David
}

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *