If G = (V, E) is an undirected graph with |V|-n and |E| = k, the following matrices are used to represent G. Let V = {v1, v2, . . . , Define the adjacency matrix A = (aI j)n×n where aIJ = 1 if {vI, vj] ˆˆ E, otherwise alj = 0.
If E = {e1, e2, . . . . , ek), the incidence matrix I is the n × k matrix (blJ)n × k where bIJ = 1 if vI is a vertex on the edge ej, otherwise bIJ = 0.
(a) Find the adjacency and incidence matrices associated with the graph in Fig. 11.46.
(b) Calculating A2 and using the Boolean operations where 0 + 0 = 0,0+l = l+ 0= l + l = 1,and 0 ˆ™ 0 = 01 = 10 = 0, 1-1 = 1, prove that the entry in row j and column j of A2 is 1 if and only if there is a walk of length 2 between the ith and jth vertices of V.
(c) If we calculate A2 using ordinary addition and multiplication, what do the entries in the matrix reveal about G?
(d) What is the column sum for each column of A? Why?
(e) What is the column sum for each column of I? Why?

Transcribed Image Text:

ез e2 e7 e1 Vs eg es V Figure 11.46