◆周二下午1:304:15在软件楼4楼密码与信 息安全实验室答疑 周三下午1:15到3:15期中测验
❖ 周二下午1：30—4：15在软件楼4楼密码与信 息安全实验室答疑 ❖ 周三下午1：15到3：15期中测验
X X 4 5 K K 2.3 3.3 nsects either two (b) in v2). The symbol V1={x 142543,44J520y1,2,3,4,y55 or Vi=(x1,x2,. 4.35, V2=y1..y3 x43, contains all edges joining vertices in VI k3,3 K 23°
❖5.2.4 Bipartite graph ❖ Definition18: A simple graph is called bipartite if its vertex set V can be partioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 . (so that no edge in G connects either two vertices in V1 or two vertices in V2 ).The symbol Km,n denotes a complete bipartite graph: V1 has m vertices and contains all edges joining vertices in V2 , and V2 has n vertices and contains all edges joining vertices in V1 . ❖ K3,3 , K2,3。 V1={x1 ,x2 ,x3, x4 }, V2={y1,y2,y3,y4,y5 }, or V'1={x1 ,x2 ,x3,y4,y5 }, V'2={y1,y2,y3, x4 }
&o The graph is not bipartite .o Theorem 5.5: A graph is bipartite iff it does not contain any odd simple circuit .o Proof: (1)Let G be bipartite, we prove it does not contain any odd simple circuit Let C=(vo, v1,.,Vm Vo) be an simple circuit of G
❖ The graph is not bipartite ❖ Theorem 5.5:A graph is bipartite iff it does not contain any odd simple circuit. ❖ Proof:(1)Let G be bipartite , we prove it does not contain any odd simple circuit. ❖ Let C=(v0 ,v1 ,…,vm,v0 ) be an simple circuit of G
&(2)G does not contain any odd simple circuit, we prove G is bipartite Since a graph is bipartite iff each component of it is, we may assume that G is connected Pick a vertex uE Vand put V=xl(u, x) is even simple path, ,and v2=yl(u, y is odd simple pathy oo 1)We prove v(G=ViUV2, Vinv2=D Letv∈v1nV2 there is an odd simple circuit in G such that these edges of the simple circuit cp, U p2 s each edge joins a vertex of v to a vertex of va
❖ (2)G does not contain any odd simple circuit, we prove G is bipartite ❖ Since a graph is bipartite iff each component of it is, we may assume that G is connected. ❖ Pick a vertex uV,and put V1={x|l(u,x) is even simple path} ,and V2={y|l(u,y) is odd simple path} ❖ 1)We prove V(G)=V1∪V2 , V1∩V2 = ❖ Let vV1∩V2 , ❖ there is an odd simple circuit in G such that these edges of the simple circuit p1∪p2 ❖ each edge joins a vertex of V1 to a vertex of V2
8 2) we prove that each edge of g joins a vertex of VIand a vertex v2 o If it has a edge joins two vertices yi and y2 of v g odd simple path 令(uF=u02u1,u2,…,U2n2yY1y2), even path 令y2≠u(0≤2n There is u; so that y2=U; The path(u, u1,,.,U;-1 y23Uj+15., U2n,,y2) from u to y2 25 s Simple path(u, u1,u23.,U,y2), simple circuit 2,u+1…,u2ny1,y %j is odd number ☆ i is even number
❖ 2) we prove that each edge of G joins a vertex of V1 and a vertex V2 ❖ If it has a edge joins two vertices y1 and y2 of V2 ❖ odd simple path ❖ (u=u0 ,u1 ,u2 ,,u2n,y1 ,y2 ),even path ❖ y2ui (0i2n) ❖ There is uj so that y2=uj . The path (u,u1 ,u2 ,,uj-1 , y2 ,uj+1,,u2n,y1 ,y2 ) from u to y2 , ❖ Simple path (u,u1 ,u2 ,,uj-1 ,y2 ),simple circuit (y2 ,uj+1,,u2n,y1 ,y2 ) ❖ j is odd number ❖ j is even number
5.3Euler and Hamilton paths ☆53.1 Euler paths o Definition 19: A path in a graph G is called an Euler path if it includes every edge exactly once An Euler circuit is an Euler path that is a circuit Theorem 5.6: A connected multigraph has an Euler circuit if and only if each of its vertices has even degree
5.3Euler and Hamilton paths ❖ 5.3.1 Euler paths ❖ Definition 19: A path in a graph G is called an Euler path if it includes every edge exactly once. An Euler circuit is an Euler path that is a circuit ❖ Theorem 5.6: A connected multigraph has an Euler circuit if and only if each of its vertices has even degree
s Proof: (l)Let connected multigraph G have an Euler circuit. then each of its vertices has even degree. ☆(VaV 09V19°·9i.9Vk9v0k First note that an Euler circuit begins with a vertex Vo and continues with an edge incident to Vo, say & V1. The edge (vo, v1 contributes one to d(vo) 8. Thus each of g's vertices has even degree
❖Proof:(1)Let connected multigraph G have an Euler circuit, then each of its vertices has even degree. ❖ (v0 ,v1 ,…,vi , …,vk ),v0=vk ❖First note that an Euler circuit begins with a vertex v0 and continues with an edge incident to v0 , say {v0 ,v1 }. The edge {v0 ,v1 } contributes one to d(v0 ). ❖ Thus each of G’s vertices has even degree
4(2)Suppose that G is a connected multigraph and the degree of every vertex of g is even o Let us apply induction on the number of edges of G 令1)e=1,oop The graph is an Euler circuit. The result holds 2)Suppose that result holds for esm e=m+1,δ(G)≥2. By the theorem 5.4, there is a simple circuit C in the graph G
❖ (2)Suppose that G is a connected multigraph and the degree of every vertex of G is even. ❖ Let us apply induction on the number of edges of G ❖ 1)e=1,loop The graph is an Euler circuit. The result holds 2) Suppose that result holds for em e=m+1， (G)≥2. By the theorem 5.4, there is a simple circuit C in the graph G
The degree of ≤m tive hypothesis ed. h has l components, The degree of every vertex of components is even and the number of edges less than m. By the inductive hypothesis, each of components has an Euler circuit. H .G is connected
❖ If E(G)=E(C), the result holds ❖ If E(G)-E(C), Let H=G-C, The degree of every vertex of H is even and e(H)m ❖ ①If H is connected, by the inductive hypothesis, H has an Euler circuit C1， ❖ C=(v0 , v1 ,…,vk-1 , v0 ) ❖ ② When H is not connected, H has l components, The degree of every vertex of components is even and the number of edges less than m. By the inductive hypothesis,each of components has an Euler circuit. Hi ❖ G is connected
the puzzle of the seven bridge in the Konigsberg d(A)=3 The graph is no Euler circuit. c Theorem 5.7: A connected multigraph 只 has an Euler path but not an circuit if and only if it has exactly two vertices (b) of odd degree d(A)=d(D)=d(C)=3,d(D)=5 The graph is no Euler path
the puzzle of the seven bridge in the Königsberg d(A)=3. The graph is no Euler circuit. Theorem 5.7: A connected multigraph has an Euler path but not an circuit if and only if it has exactly two vertices of odd degree. d(A)=d(D)=d(C)=3, d(D)=5 The graph is no Euler path