Adjacency matrices and Incidence matrices 4 Definition 12: Let G(V,E) be a graph of non-multiple edge where vn. Suppose that v1,v2,,n are the vertices. The adjacency matrix A of G, with respect to this listing of the vertices, is the nxn zero-one matrix with 1 as its (i,jth entry when vi and vi are adjacent, and 0 as its (i,jth entry when they are not adjacent. In other words, If its adjacency matrix is A=lail, then 扩f, v is an edge of g otherwise
Adjacency matrices and Incidence matrices ❖ Definition 12: Let G(V,E) be a graph of non-multiple edge where |V|=n. Suppose that v1 ,v2 ,…,vn are the vertices. The adjacency matrix A of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i,j)th entry when vi and vj are adjacent, and 0 as its (i,j)th entry when they are not adjacent. In other words, If its adjacency matrix is A=[aij], then = otherwise i f v v i s an edge of G a i j i j 0 1 { , }
g Let G(v,E) be an undirected graph. Suppose that v1 v2,-.,Vn are the vertices and el, e2,.,e are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nxm matrix M=miil, where when edge e is incident with y otherwise
❖ Let G(V,E) be an undirected graph. Suppose that v1 ,v2 ,…,vn are the vertices and e1 ,e2 ,…,em are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nm matrix M=[mij], where = otherwise when edge e i s incident withv m j i i j 0 1
00 0 010100 011010 图C 000000 e3 et es e6e, e8 1000 000 1000111 00000 011000 v00011110 aoe3
0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 5 4 3 2 1 1 2 3 4 5 6 7 8 v v v v v e e e e e e e e
Quotient graph Definition 13: Suppose G(VE) is a graph and R is a equivalence relation on the set V. we construct the quotient graph gR in the follow way. The vertices of GR are the equivalence classes of v produced by r If v and w are the equivalence classes of vertices v and w of G, then there is an edge in g between v and w if some vertex in v] is connected to some vertex in w in the graph G
❖Quotient graph ❖ Definition 13: Suppose G(V,E) is a graph and R is a equivalence relation on the set V. We construct the quotient graph GR in the follow way. The vertices of GR are the equivalence classes of V produced by R. If [v] and [w] are the equivalence classes of vertices v and w of G, then there is an edge in GR between [v] and [w] if some vertex in [v] is connected to some vertex in [w] in the graph G