复旦大学：《离散数学》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

2: A planar embedded of a the plane into connected luding an unbounded region nded region is called outside other regions are called inside

▪ Definition 42:A planar embedded of a graph splits the plane into connected regions, including an unbounded region. The unbounded region is called outside region, the other regions are called inside regions

Theorem 5.28(Eulers formula) If G is a connected plane graph with n vertices, e edges and f regions, then n-e+f-2. Proof. Induction on e, the casee=0 being as in this case n=le=0 and f=1 n-e+f=1-0+1=2

▪ Theorem 5.28(Euler’s formula) If G is a connected plane graph with n vertices, e edges and f regions, then n -e+f= 2. ▪ Proof. Induction on e, the case e = 0 being as in this case n = 1, e = 0 and f =1 ▪ n-e+f=1-0+1=2

Assume the result is true for all connected plane graphs with fewer than e edges, e21, and suppose g has e edges. If g is a tree. then n=e+l and f=1. so the result holds If g is not a tree. let e be an edge of a cycle of g and consider g-e Clearly, G-e is a connected plane graph with n vertices, e-l edges and f-1 regions, so by the induction hypothesis, n- (e-1)+(f-1)=2, from which it follows that n -e +f=2

▪ Assume the result is true for all connected plane graphs with fewer than e edges, ▪ e ≥ 1, and suppose G has e edges. ▪ If G is a tree, then n =e+1 and f= 1, so the result holds. If G is not a tree, let e be an edge of a cycle of G and consider G-e. Clearly, G-e is a connected plane graph with n vertices, e-1 edges and f-1 regions, so by the induction hypothesis, n- (e-1) + (f- 1) = 2, from which it follows that n -e +f = 2

If G is a plane graph with n vertices, e onents and f regions, then n-e +f=1+k If g is a connected planar simple edges and n vertices where n >3, then e<3n-6 Proof: A connected planar simple graph drawn in the plane divides the plane into regions, say f of them. The degree of each region is at least three(since the graphs discussed here are simple graphs, no multiple edges that could produce regions of degree two, or loops that could produce regions of degree one, are permitted). The degree of a region is defined to be number of edges on the boundary of this region We denoted the sum of the degree of the regions by S

▪ Corollary 5.1 If G is a plane graph with n vertices, e edges, k components and f regions, then n-e +f= 1+k. ▪ Corollary 5.2: If G is a connected planar simple graph with e edges and n vertices where n ≥ 3, then e≤3n-6. Proof: A connected planar simple graph drawn in the plane divides the plane into regions, say f of them. The degree of each region is at least three(Since the graphs discussed here are simple graphs, no multiple edges that could produce regions of degree two, or loops that could produce regions of degree one, are permitted). The degree of a region is defined to be number of edges on the boundary of this region. We denoted the sum of the degree of the regions by s