复旦大学：《离散数学》PPT教学课件（赵一鸣）12/28

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 nn 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 nm 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

5.2 Paths and circuits .8.5.2.1 Paths and circuits % Definition 14: Let n be a nonnegative integer and g be an undirected graph. A path of length n from u to y in G is a sequence of edges elsey,en of G such that e=vo=u, V1, e2=v1,V2,,en=vn-1,Vn=v), and no edge occurs more than once in the edge sequence. When G is a simple graph, we denote this path by its vertex sequence u=vo V1.Vn-V. A path is called simple if no vertex appear more than once. A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices V1,V2,.,Vn-I are all distinct

5.2 Paths and Circuits ❖5.2.1 Paths and Circuits ❖ Definition 14: Let n be a nonnegative integer and G be an undirected graph. A path of length n from u to v in G is a sequence of edges e1 ,e2 ,…,en of G such that e1={v0=u,v1 }, e2={v1 ,v2 },…,en={vn-1 ,vn=v}, and no edge occurs more than once in the edge sequence. When G is a simple graph, we denote this path by its vertex sequence u=v0 ,v1 ,…,vn=v. A path is called simple if no vertex appear more than once. A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices v1 ,v2 ,…,vn-1 are all distinct

6,e7,8904,e7)Is not a circuit (e1,e6,e,, eg, e4s es)is a circuit e6 1,es,e4, e&) is a simple circuit e 2 6(e6,e,) is a simple circuit e7 4 国e U3 4 (e6se, eg,, e,,e, is not a path; %(e6,e,e1) is a path of from v2 to VI o(eg,e4, es) is a simple path of from v2 to vi

❖ (e6 ,e7 ,e8 ,e4 ,e7 ,e1 ) is not a path; ❖ (e6 ,e7 ,e1 ) is a path of from v2 to v1 ❖ (e8 ,e4 ,e5 ) is a simple path of from v2 to v1 (e6 ,e7 ,e8 ,e4 ,e7 ) is not a circuit; (e1 ,e6 ,e7 ,e8 ,e4 ,e5 ) is a circuit (e1 ,e5 ,e4 ,e8 ) is a simple circuit (e6 ,e7 ) is a simple circuit

Theorem 5.4: Let 8(G22, then there is a simple circuit in the graph G Proof: If graph G contains loops or multiple edges, then there is a simple circuit.(a, a)or(e, e"). Let g be a simple graph For any vertex vo of G, god(vo22, next vertex, adjacent, Pigeonhole pl rinciple

❖ Theorem 5.4:Let  (G)≥2, then there is a simple circuit in the graph G. ❖ Proof: If graph G contains loops or multiple edges, then there is a simple circuit. (a,a) or (e,e'). ❖ Let G be a simple graph. For any vertex v0 of G, ❖ d(v0 )≥2, next vertex, adjacent, Pigeonhole principle

☆5.2.2 Connectivit %s Definition 15: A graph is called connectivity if there is a path between every pair of distinct vertices of the graph. Otherwise, the graph is disconnected

❖5.2.2 Connectivity ❖ Definition 15: A graph is called connectivity if there is a path between every pair of distinct vertices of the graph. Otherwise , the graph is disconnected