The Adjacency matrix A=[a_ ij] of a graph G=(V, E) is defined as a_ ij= {10 If t
ID: 1721286 • Letter: T
Question
The Adjacency matrix A=[a_ ij] of a graph G=(V, E) is defined as a_ ij= {10 If there is an edge between vertices i and j otherwise The degree of a vertex in a graph G=(V, E) is defined as the number of edges incident to it. The Laplacian matrix is defined as the matrix L=D-A where D=[d_ ij] is a diagonal matrix whose entries are d_ ij= the degree of vertex i, and d_ij =0 if the i j. L=(2 -1 -1 0 0 0 0 0 -1 2 -1 0 0 0 0 0 -1 -1 2 0 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 2 -1 -1 0 0 0 0 0 -1 2 -1 0 0 0 0 0 -1 -1 2) : Draw and label the graph represented by the Laplacian L. : Find a basis for the ker(L) := {: L = } : What feature of the graph is encoded in your basis?Explanation / Answer
The given matrix consists of three independent blocks 3x3 , 2x2 and 3x3. The graph above is the union of the three components ABC, DE and FGH respectively.
It is easy to verify that the given matrix is the Laplacian of the graph drawn above.
If we denote a vector by [x,y,z,k,l, p,q,r] , it belongs to the kernel iff
2x-y-z=0, -x+2y-z=0,-x-y+2z=0
k=l
2p-q-r=0, -p+2q-r=0,-p-q+2r=0
A basis is given by (1,1,1,0,0,0,0,0), (0,0,0,1,1,0,0,0) and (0,0,0,0,0,1,1,1)
The information that the graph has three connected components is encoded .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.