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 + A + .... + A[V-1][V-1] Count of triangles = trace(A3) / 6
Below is implementation of above formula.
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.
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.
This article is attributed to GeeksforGeeks.org