1lec 5f.1October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphs;Bipartite MatchingMathematics for Computer ScienceMIT 6.042J/18.062Jlec 5f.2October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar GraphsMathematics for Computer ScienceMIT 6.042J/18.062Jlec 5f.3October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphslec 5f.4October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar GraphsA graph is planar if thereis a way to draw it in the plane without edges crossing.lec 5f.5October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.General connected planar graphs may havedonglesPlanar Graphscross barsMaps are 2-connected planar graphslec 5f.6October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph12341234(wait! also the outer face)with 3 faces42lec 5f.7October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsdraw it edge by edge:lec 5f.8October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.(the outer face)Planar Graphsfacesand record faces while drawinggraphlec 5f.9October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.(the outer face)Planar Graphsfacesand record faces while drawinggraphlec 5f.10October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.(the outer face)Planar Graphsfacesand record faces while drawinggraphlec 5f.11October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.If you like curves…With same faces, you can draw the graph in the plane big or small, curvy or straight:4321lec 5f.12October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.“Planar Drawing” = FacesAn (abstract) planar drawingis defined to be its set of faces.The same planar graph may have different drawings.3lec 5f.13October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Team ProblemProblem 1lec 5f.14October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Euler's FormulaIf a connected planar drawing has v vertices,e edges, and f faces, thenv–e+f = 2lec 5f.15October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Euler's FormulaProof by induction on # edges in drawing:base case: no edgesconnected, so v = 1outside face only, so f = 1e = 01−0+1 = 2lec 5f.16October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Adding an edge to a drawingInductive step: any n+1 edge drawing comes from adding an edge to some nedge drawing.(not a buildup error: it’s the definition of drawing edge by edge)So can assume Euler for n edge drawing and see what happens tov–e+f when 1 edge is added.lec 5f.17October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Two cases for connected graph:1) Attach edge from vertex on a face to a new vertex.2) Attach edge between vertices on a face.Adding an edge to a drawinglec 5f.18October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Face Creation Rules1) choose facewvold face vxvpath xadd edge to new vertex4lec 5f.19October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvnew face is wvxvw1) choose faceadd edge to new vertexFace Creation Rulespath xlec 5f.20October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.new face is wvxvw1) choose faceadd edge to new vertexFace Creation Rulesnothing else changeslec 5f.21October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Euler’s Formulav increases by 1e increases by 1f stays the sameso v–e+f stays the samelec 5f.22October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvxyFace Creation Rules2) choose faceold face: wxvywadd edge across itlec 5f.23October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvxyFace Creation Rules2) choose faceadd edge across itsplits into 2 faces:lec 5f.24October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvvywx, vywvFace Creation Rules2) choose faceadd edge across itwxvwsplits into 2 faces:5lec 5f.25October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved., vywvFace Creation Rules2) choose faceadd edge across itwxvwsplits into 2 faces:nothing else changeslec 5f.26October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Euler’s Formulav stays the samee increases by 1f increases by 1so v–e+f stays the samelec 5f.27October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Euler’s FormulaInductive step:lec 5f.28October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Team ProblemsProblems2 & 3lec 5f.29October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Bipartite Matching:Hall’s TheoremMathematics for Computer ScienceMIT 6.042J/18.062Jlec 5f.30October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Compatible Boys & GirlsGBcompatible6lec 5f.31October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Compatible Boys & GirlsGBmatch each girl to aunique compatible boylec 5f.32October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Compatible Boys & GirlsGBa matchinglec 5f.33October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Compatible Boys & GirlsGBsuppose this edge was missinglec 5f.34October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Compatible Boys & GirlsGBno match possiblelec 5f.35October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.No match possibleGBbecause of bottlenecklec 5f.36October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Bottleneck conditionGBSN(S)|S|=3|N(S)|=27lec 5f.37October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Bottleneck LemmaIf there is a bottleneck, then no match is possible.bottleneck: not enough boys forsome set of girls.{}, N( ):: | adjacent to a ,|||N()|SG S bb gSSS⊆= ∈>lec 5f.38October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Hall’s TheoremThere is a perfect match iffthere are no bottlenecks.Proof in Notes: clever strong induction on #girls.(Better proof using duality principlegoes beyond 6.042)lec 5f.39October 7, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Hall’s TheoremThere is a perfect match iffthere are no bottlenecks.Lots of elegant use in applications & proofslec 5f.40October 7, 2005Copyright © Albert R. Meyer, 2005. All rights
View Full Document
Unlocking...