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

graph ices s cv abset of to some U 3 u2 U2 1VV)-V∈v|u∈,uv∈EU丿 A={v1,v3},N(A)={v2,v6,v4} A1={vl,v4},N(A1)={v2,v6,v4,v3, V5, V1) vs

▪ Definition 40: Given a bipartite graph G(V1;V2), and a subset of vertices S V, the neighborhood N(S) is the subset of vertices of V that are adjacent to some vertex in S, i.e. ▪ N(S) ={vV|uS,{u,v}E(G)} A={v1,v3},N(A)={v2,v6,v4} A1={v1,v4},N(A1 )={v2,v6,v4,v3, v5,v1}

Theorem 5.26: Let G(Vi, v2) be a bipartite graph with Vil=V2. Then a complete matching of G from Vi to v2 is a perfect matching

▪ Theorem 5.26: Let G(V1 ,V2 ) be a bipartite graph with |V1 |=|V2 |. Then a complete matching of G from V1 to V2 is a perfect matching

Theorem 5.27(Hall's Theorem) Let G(vi; V2) be a bipartite graph with visv2l Then G has a complete matching saturating every vertex of Vi iff SEN(S) for every subset scv Example: Let g be a k-regular bipartite graph. Then there exists a perfect matching of g, where k0 regular For acv,erele incident a vertex ofa, eisele incident a vertex ofN(a) For ve∈E1,eeE2 Thus e1∈E2. Therefore e1E2 Because KA|=E1≤E2=kN(A川,N(A)A By Halls theorem, g has a complete matching M from VI to V2. Because vi=val, Thus M is a perfect matching

▪ Theorem 5.27 (Hall's Theorem) Let G(V1 ; V2 ) be a bipartite graph with |V1 |≤|V2 |. Then G has a complete matching saturating every vertex of V1 iff |S|≤|N(S)| for every subset SV1 ▪ Example: Let G be a k-regular bipartite graph. Then there exists a perfect matching of G, where k>0. ▪ k-regular ▪ For AV1 ,E1={e|e incident a vertex of A}, E2={e|e incident a vertex of N(A)} ▪ For eE1 , eE2 . Thus E1E2 . Therefore |E1 |≤|E2 |. ▪ Because k|A|=|E1 |≤|E2 |=k|N(A)|, |N(A)|≥|A|. ▪ By Hall’s theorem, G has a complete matching M from V1 to V2 . ▪ Because |V1 |=|V2 |, Thus M is a perfect matching

5.9 Planar Graphs 59.1 Euler’ s Formula Definitions 41: Intuitively, a graph G is planar if it can be embedded in the plane, that is, if it can be drawn in the plane without any two edges crossing each other. If a graph is embedded in the plane, it is called a planar graph

5.9 Planar Graphs ▪ 5.9.1 Euler’s Formula ▪ Definitions 41: Intuitively, a graph G is planar if it can be embedded in the plane, that is, if it can be drawn in the plane without any two edges crossing each other. If a graph is embedded in the plane, it is called a planar graph