◆周二下午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