Given an Undirected simple graph, We need to find how many triangles it can have. For example below graph have 2 triangles in it.
Let A[][] be adjacency matrix representation of graph. If we calculate A3, then the number of triangle in Undirected Graph is equal to trace(A3) / 6. Where trace(A) is the sum of the elements on the main diagonal of matrix A.
Trace of a graph represented as adjacency matrix A[V][V] is, trace(A[V][V]) = A[0][0] + A[1][1] + .... + A[V-1][V-1] Count of triangles = trace(A3) / 6
Below is implementation of above formula.
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 // diagnonal 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
" , 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 // diagnonal 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 # diagnonal 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 // diagnonal 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. |
Output:
Total number of Triangle in Graph : 2
How does this work?
If we compute An for an adjacency matrix representation of graph, then a value An[i][j] represents number of distinct walks between vertex i to j in graph. In A3, we get all distinct paths of length 3 between every pair of vertices.
A triangle is a cyclic path of length three, i.e. begins and ends at same vertex. So A3[i][i] represents a triangle beginning and ending with vertex i. Since a triangle has three vertices and it is counted for every vertex, we need to divide result by 3. Furthermore, since the graph is undirected, every triangle twice as i-p-q-j and i-q-p-j, so we divide by 2 also. Therefore, number of triangles is trace(A3) / 6.
Time Complexity:
The time complexity of above algorithm is O(V3) where V is number of vertices in the graph, we can improve the performance to O(V2.8074) using Strassen’s matrix multiplication algorithm.
References:
http://www.d.umn.edu/math/Technical%20Reports/Technical%20Reports%202007-/TR%202012/yang.pdf
Number of Triangles in Directed and Undirected Graphs
leave a comment
0 Comments