Number of Triangles in an Undirected Graph - GeeksforGeeks
Given an Undirected simple graph, We need to find how many triangles it can have. For example below graph have 2 triangles in it.
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
// 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])
{
int
aux2[V][V];
// To Store graph^2
int
aux3[V][V];
// To Store graph^3
// 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;
}
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.
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
Number of Triangles in Directed and Undirected Graphshttp://www.d.umn.edu/math/Technical%20Reports/Technical%20Reports%202007-/TR%202012/yang.pdf
Number of Triangles in Directed and Undirected Graphs
We have discussed a method based on graph trace that works for undirected graphs. In this post a new method is discussed with that is simpler and works for both directed and undirected graphs.
The idea is to use three nested loops to consider every triplet (i, j, k) and check for the above condition (there is an edge from i to j, j to k and k to i)
However in an undirected graph, the triplet (i, j, k) can be permuted to give six combination (Seeprevious post for details). Hence we divide the total count by 6 to get the actual number of triangles.
In case of directed graph, the number of permutation would be 3 (as order of nodes becomes relevant). Hence in this case the total number of triangles will be obtained by dividing total count by 3. For example consider the directed graph given below
However in an undirected graph, the triplet (i, j, k) can be permuted to give six combination (Seeprevious post for details). Hence we divide the total count by 6 to get the actual number of triangles.
In case of directed graph, the number of permutation would be 3 (as order of nodes becomes relevant). Hence in this case the total number of triangles will be obtained by dividing total count by 3. For example consider the directed graph given below
// function to calculate the number of triangles in a simple
// directed/undirected graph.
// isDirected is true if the graph is directed, its false otherwise
int
countTriangle(
int
graph[V][V],
bool
isDirected)
{
int
count_Triangle = 0;
// Initialize result
// Consider every possible triplet of edges in graph
for
(
int
i=0; i<V; i++)
{
for
(
int
j=0; j<V; j++)
{
for
(
int
k=0; k<V; k++)
{
// check the triplet if it satisfies the condition
if
(graph[i][j] && graph[j][k] && graph[k][i])
count_Triangle++;
}
}
}
// if graph is directed , division is done by 3
// else division by 6 is done
isDirected? count_Triangle /= 3 : count_Triangle /= 6;
return
count_Triangle;
}
Comparison of this approach with previous approach:
Advantages:
Advantages:
- No need to calculate Trace.
- Matrix- multiplication is not required.
- Auxiliary matrices are not required hence optimized in space.
- Works for directed graphs.
Disadvantages:
- The time complexity is O(n3) and can’t be reduced any further.