here is my question Recall that an adjacency matrix for a graph can be made by u
ID: 2983706 • Letter: H
Question
here is my question
Recall that an adjacency matrix for a graph can be made by using a 1 in column i and row j if there is an edge connecting vertices i,j and a 0 otherwise. Let G be a graph and A(G) by the adjacency matrix of G. In a matrix we recognize the main diagonal, which is all elements in the matrix such that if an element is in row j and column i and in the main diagonal, then i = j. The trace(A) is the sum of all main diagonal elements. Show the following. The number of edges in a graph G is trace(A2(G)). The number of 3-cycles or 'triangles' in a graph G is trace(A3(G)). Explain why this same technique cannot be used to count the number of 4-cycles or 'squares'. Give an example.Explanation / Answer
a) The values along the principal diagonal of a matrix=1 only if there are self loops else=0
Hence when we multiply it by itself, All the edges in a given column get added and get stored in the given diagonal element. Example: In [0,0] of A^2 we will have the sum of the first column of A.
Hence, The trace or sum of diagonal elements will give the no.of edges in G.
b)ij th entry of X^3= dot product of ith row of X^2 and jth column of X
= summation of ikth entry of X^2 and kjth entry of X
=summation of all different edge sequences of three edges from ith to jth vertex via kth vertex
=no. of 3 cycles or triangles.
C) No.of 4 cycles will need 4 edges but here we are considering only 3 edges i,j and k. Hence only 3cycles will be formed.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.