1Albert R Meyer, March 15, 2010 Graph Coloring Bipartite Matchinglec 7M.1 Mathematics for Computer Science MIT 6.042J/18.062JAlbert R Meyer, March 15, 2010 Flight Gatesflights need gates, buttimes overlap.how many gates needed? lec 7M.2 Albert R Meyer, March 15, 2010 Airline Schedule 122145 67 257306 99 Flightstimelec 7M.3 Albert R Meyer, March 15, 2010 Conflicts Among 3 Flights 99145306Needs gate at same time lec 7M.4 Albert R Meyer, March 15, 2010 Model all Conflicts with a Graph 2576799145306122lec 7M.5 Albert R Meyer, March 15, 2010 Color the vertices so that adjacent vertices have different colors. min # distinct colors needed = min # gates neededColor the vertices lec 7M.62Albert R Meyer, March 15, 2010 Coloring the Vertices 257, 67 122,145993064 colors 4 gates assigngates:2576799145306122lec 7M.7 Albert R Meyer, March 15, 2010 Better coloring 3 colors3 gates2576799145306122lec 7M.8 Albert R Meyer, March 15, 2010 Final Exams subjects conflict if studenttakes both, so need different time slots. how short an exam period? lec 7M.9 Albert R Meyer, March 15, 2010 Model as a Graph 6.0426.00118.023.0918.02M 9am M 1pm T 9am T 1pm assigntimes:4 time slots (best possible) lec 7M.10 Albert R Meyer, March 15, 2010 Map Coloring lec 7M.12 Albert R Meyer, March 15, 2010 Planar Four Coloring any planar map is 4-colorable. 1850’s: false proof published (was correct for 5 colors). 1970’s: proof with computer 1990’s: much improvedlec 7M.14 © Source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.3Albert R Meyer, March 15, 2010 Chromatic Number min #colors for G ischromatic number, (G)lemma:(tree) = 2 lec 7M.15 Albert R Meyer, March 15, 2010 Pick any vertex as “root.” if (unique) path from root is even length:odd length: Trees are 2-colorable rootlec 7M.16 Albert R Meyer, March 15, 2010 Simple Cycleslec 7M.17 (Ceven) = 2(Codd) = 3Albert R Meyer, March 15, 2010 Complete Graph K5lec 7M.18 (Kn) = nAlbert R Meyer, March 15, 2010 The Wheel Wnlec 7M.19 (Weven) = 3(Wodd) = 4W5Albert R Meyer, March 15, 2010 Bounded Degreeall degrees k, impliesvery simple algorithm…lec 7M.20 (G) k+14Albert R Meyer, March 15, 2010 “Greedy” Coloring …color vertices in any order. next vertex gets a color different from its neighbors. k neighbors, so k+1 colors always work lec 7M.21 Albert R Meyer, March 15, 2010 coloring arbitrary graphs 2-colorable? --easy to check 3-colorable? --hard to check (even if planar) find (G)? --theoretically no harder than 3-color, but harder in practice lec 7M.24 Albert R Meyer, March 15, 2010 Bipartite Matching lec 7M.25 Albert R Meyer, March 15, 2010 Compatible Boys & Girls GBcompatiblelec 7M.26 Albert R Meyer, March 15, 2010 GBmatch each girl to a unique compatible boy lec 7M.27 Compatible Boys & Girls Albert R Meyer, March 15, 2010 GBa matchinglec 7M.28 Compatible Boys & Girls5Albert R Meyer, March 15, 2010 GBsuppose this edge was missing lec 7M.29 Compatible Boys & Girls Albert R Meyer, March 15, 2010 GBlec 7M.30 Compatible Boys & Girls suppose this edge was missing Albert R Meyer, March 15, 2010 GBlec 7M.31 3Compatible Boys & Girls Albert R Meyer, March 15, 2010 GBlec 7M.32 32like only 2 boys3 girlsCompatible Boys & Girls Not enough boys for these girls! Albert R Meyer, March 15, 2010 GBlec 7M.33 32like only 2 boys3 girlsNo match is possible! SN(S)|S| = 3> 2 = |N(S)|Albert R Meyer, March 15, 2010 No match is possible! a bottleneckGBlec 7M.34 SN(S)|S| > |N(S)|6Albert R Meyer, March 15, 2010 Bottleneck Lemma If there is a bottleneck,then no match is possible, obviously. lec 7M.36 Albert R Meyer, March 15, 2010 Conversely, if there areno bottlenecks, then there is a match.Hall’s Theorem lec 7M.37 Albert R Meyer, March 15, 2010 If |S| |N(S)| for allsets of girls, S, then there is a match.Hall’s Theorem lec 7M.38 Hall’s condition (proof in Notes) Albert R Meyer, March 15, 2010 How to verify no bottlenecks? fairly efficient matching procedure is known (explained in algorithms subjects) lec 7M.47 …but there is a special situation which ensures a match: Albert R Meyer, March 15, 2010 How to verify no bottlenecks? If every girl likes d boys, and every boy likes d girls, then no bottlenecks. proof: say set S of girls has e incident edges:d|S| e |S| |N(S)|so no bottleneck dN(S)|lec 7M.48 Albert R Meyer, March 15, 2010 How to verify no bottlenecks? If every girl likes d boys, and every boy likes d girls, then no bottlenecks. lec 7M.49 a degree-constrained bipartite graph7Albert R Meyer, March 15, 2010 lec 6M.50 Team Problems Problems 1—4MIT OpenCourseWarehttp://ocw.mit.edu6.042J / 18.062J Mathematics for Computer ScienceSpring 2010For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...