Definition 11: The complement of a graph g is the graph(denoted G) with the same vertex set but whose edge set consists of the edges not present in G(i.e, the complement of the edge set of G with respect to all possible edges on the vertex set of g) K
Definition 11: The complement of a graph G is the graph (denoted G ) with the same vertex set but whose edge set consists of the edges not present in G (i.e., the complement of the edge set of G with respect to all possible edges on the vertex set of G)
8G-v, or G-iv .o When we remove a vertex v from a graph, we must remove all edges incident with the vertex v When a edge is removed from a graph, without removing endpoints of the edge G
❖ G-v, or G-{v} ❖ When we remove a vertex v from a graph, we must remove all edges incident with the vertex v. ❖ When a edge is removed from a graph, without removing endpoints of the edge
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