Example: biology

Graph Theory, Part 2 - Princeton University

GraphTheory, Part27 ColoringSupposethatyouareresponsiblefors chedulingtimesforlecturesin a University . Youwantto make surethatany two lectureswitha commonstudent occurat di erent timesto avoidacon couldputthevariouslecturesona chartandmarkwithan\X"any pairthathasstudents in common:LectureACGHILMPSA stronomyXXXXC hemistryXXGreekXXXXXH istoryXXXXI talianXXXL atinXXXXXXM usicXXXXP hilosophyXXSpanishXXXXA moreconvenient representationof thisinformationis a graphwithonevertexforeach lectureandin which two verticesarejoinedif thereis a con ictbetweenthem:GMLIAPSCHNow, we cannotscheduletwo lecturesat thesametimeif thereis a con ict,butwe wouldliketo useas fewseparatetimesas possible,subjectto thisconstraint. How many di erent timesarenecessary?We cancode each timewitha color,forexample11:00-12:00might be given thecolorgreen,andthoselecturesthatmeetat thistimewillbe ictrulethenmeansthatwe needto colortheverticesof ourgraphin such a way thatnotwo adjacent vertices(representingcourseswhich con ictwitheach other)have make a de nition:De nition15(Proper Coloring,k-Coloring,k-Colorable).

and those lectures that meet at this time will be colored green. The no-con ict rule then means that we need to color the vertices of our graph in such a way that no two adjacent vertices (representing courses which con ict with each other) have the same color. This motivates us to make a de nition: De nition 15 (Proper Coloring, k-Coloring, k ...

Tags:

  Lecture, Princeton, Part, Theory, Graph, Part 2, Graph theory

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Graph Theory, Part 2 - Princeton University

1 GraphTheory, Part27 ColoringSupposethatyouareresponsiblefors chedulingtimesforlecturesin a University . Youwantto make surethatany two lectureswitha commonstudent occurat di erent timesto avoidacon couldputthevariouslecturesona chartandmarkwithan\X"any pairthathasstudents in common:LectureACGHILMPSA stronomyXXXXC hemistryXXGreekXXXXXH istoryXXXXI talianXXXL atinXXXXXXM usicXXXXP hilosophyXXSpanishXXXXA moreconvenient representationof thisinformationis a graphwithonevertexforeach lectureandin which two verticesarejoinedif thereis a con ictbetweenthem:GMLIAPSCHNow, we cannotscheduletwo lecturesat thesametimeif thereis a con ict,butwe wouldliketo useas fewseparatetimesas possible,subjectto thisconstraint. How many di erent timesarenecessary?We cancode each timewitha color,forexample11:00-12:00might be given thecolorgreen,andthoselecturesthatmeetat thistimewillbe ictrulethenmeansthatwe needto colortheverticesof ourgraphin such a way thatnotwo adjacent vertices(representingcourseswhich con ictwitheach other)have make a de nition:De nition15(Proper Coloring,k-Coloring,k-Colorable).

2 Aproper coloringis anas-signment of colorsto theverticesof a graphso thatnotwo adjacent verticeshave a graphis a proper coloringinvolvinga graphthathasak-coloringis saidto seekis ak-coloringof ourgraphwithkas smallas a 4-coloringof thegraph:GMLIAPSCHQ uestion:Is therea proper coloringthatuseslessthanfourcolors?Clear lywe cannotgetbywithlessthanthreecolors,since G,H, andLarealladjacent to each :Canwe nda 3-coloring?Theanswer is shallsupposethatwe canproperlycolorthegraphwithonlythreecol ors,andshow thatthisleadsto a coloringG,H, andLthreedi erent colors,as we might as well assumetheyarethecolorsas shownabove. ThenMmustbe thesamecolorasH, sinceMis adjacent colorMblueas shownabove. In a likemanner,Imustbe coloredgreensinceit is adjacent toLandM, which we have determinedto be adjacent toH,L, andI, andso it mustbe a di erent cannotmake needto have at leastfourdi erent now a verynaturalconcept:De nition16(ChromaticNumber).

3 Thechromaticnumberof a graphis theminimumnumber of colorsin a proper coloringof dowe determinethechromaticnumber of a Graph ?In thelastexample,we didit by rst ndinga 4-coloring,andthenmakinganintricateargum ent thata may be quitedi cultto computethechromaticnumber of at leastmake anupper boundonthenumber of colorswe need,evenif wecannot ndtheminimumnumber?Thereis analgorithm(procedure)forproperlycolorin gverticesthatdoes notalways useas fewcolorsas possible,butat leastgives us anupper boundonthenumber of ColoringVerticesThealgorithmis calledgreedybecauseit is a rathershort-sightedway of tryingto make a propercoloringwithas fewcolorsas does notalwayssucceedin ndingtheminimum2number (thechromaticnumber),butat leastprovidessomeproper number consecutivelythecolorsthatwe use,so each timewe introducea newcolor,we number it theprocedure:1.

4 Colora Pick anuncoloredvertexv. Colorit withthelowest-numberedcolorthathasnotbee nusedon any previously-coloredverticesadjacent tov. (If all previously-usedcolorsappearonverticesadj acent tov, thismeansthatwe mustintroducea newcolorandnumber it.)3. Repeatthepreviousstepuntil , thisproducesa proper coloring,sincewe arecarefulto avoidcon ictseach timewecolora many colorswillbe used?It is hardto say in advance,andit dependsonwhatorderwe chooseto example,supposewe decideto colorthecoursecon ictgraphusingtheGreedyColoringAlgorithm, andwe decideto colortheverticesin orderG,L,H,P,M,A,I,S,C. ThenwewouldcolorGwithcolor1 (green),Lwithcolor2 (red)sinceadjacencywithGprevents itfromreceivingcolor1 (green),andwe colorHwithcolor3 (blue)sinceadjacencywithGandLprevents it fromreceivingcolors1 and2 (greenandred).Sowe haveGMLIAPSC color 1color 2color 3 HPandMalsocannotreceive colors1 and2 (greenandred),so theyaregivencolor3 (blue):GMLIAPSC color 1color 2color 3H3 ThenAcannotreceive colors1 and3 (greenandblue),so we give it color2 (red),whileIcannotreceive colors2 and3 (redandblue),so we give it color1 (green).

5 GMLIAPSC color 1color 2color 3 HVertexScannotreceive color1, 2, or 3, andso we give it color4 (say, yellow).VertexCcannotreceive color2 or 4 (redor yellow),so we give it color1 (green).We obtainthesamecoloringwe hadproposedearlier:GMLIAPSC color 1color 2color 3color 4H4 Ontheotherhand,we couldimaginechoosinga di erent choseto colortheverticesin theorderA,I,P,M,S,C,H,L,G. Firstwe colorAwithcolor1 (green) 1 HThenwe colorMandSwithcolor2 (red),becausetheycannotbe 1color 2 Thenwe colorCandHwithcolor3 (blue),becausetheycannotbe coloredgreenor 1color 2color 35We colorLwithcolor4 (yellow),becauseit cannotbe coloredwithgreen,red,or 1color 2color 3color 4We colorGwithcolor5 (light blue),becauseit cannotbe coloredwithany of 1color 2color 3color 4color 5 Sowe seethatthequality of ourcoloring(withfewer colorsbeingconsideredbetter)fromtheGreed yColoringAlgorithmis dependent ontheorderin which we ,thereis a certainminimumquality we get,which we candetermineby thefollowingtheoreticalargument.

6 Supposethatdis thelargestdegreeof any vertexin ourgraph, ,allverticeshavedor fewer edgesattached,andat goaboutcoloring,whenwe colorany particularvertexv, it is attachedto atmostdothervertices,of which somemay alreadybe mostdcolorsthatwe usesomecolornumberedd+ 1 or lower,becauseat leastoneof thecolors1, 2,: : :,d+ 1 never needto useany colornumberedhigherthand+ us thefollowingtheorem:6 Theorem4 (GreedyColoringTheorem).Ifdis thelargestof thedegrees of thevertices ina graphG, thenGhasa proper coloringwithd+ 1or fewercolors, ,thechromaticnumberofGis at mostd+ anupper boundonthechromaticnumber,buttherealchro maticnumber maybe below thisupper example,in ourcoursecon ictgraphabove, thehighestdegreeisd= 6 (vertexLhasthisdegree),so theGreedyColoringTheoremstatesthatthechr omaticnumber is nomorethan7. In fact,thechromaticnumber is 4, anda 4-coloringcanbe obtainedby employingtheGreedyColoringAlgorithm(aswe saw above) if oneis nottoo unluckyinpickingtheorderto di cultproblemthatwas addressedby graphtheoristsis theanswer to themaximumnumber of colorsyouneedto colora mapso thatadjacentterritoriesaregivendi erent colors?

7 For us,a territoryis a connectedmassof ,theKaliningradexclave is partof Russia,althoughit is notconnectedto themainpartof Russia.(Kaliningradis themodernnamegiven to thecity onceknownas K onigsberg.)Althoughwe posethisproblemin termsof coloringmaps,realcartographersareseldomv eryinterestedin knowingtheminimumnumber of ,thisproblem,likeothercoloringproblems,h asrami ,supposewe want to minimizethenumber of radiofrequencieswe usewhilenotusingthesamefrequenciesin nearby regions(toprevent interference).Thencolorscouldrepresentfr equencies,verticescouldrepresent regions, want to assignfrequencies( ,colorthevertices)withnocon icts( ,noadjacent verticeshave thesamecolor)usingas fewfrequencies( ,colors)as we shouldbe usedto abstractingrelationsinto canmake eachterritorya vertex,andjointwo verticeswithanedgewhentheterritoriesthey represent areadjacent.

8 Thencoloringtheverticesof thegraphso thatnotwo adjacent verticesreceive thesamecoloris equivalent to coloringtheoriginalmapso thatnotwo adjacent example,if we want to abstracta portionof thefollowingmapof Europe1we might producethefollowinggraph:1 Allthegeographicalmapsin thesenotesarefromthePerry-Casta~nedaLibr aryMapCollectionattheUniversity of Texas, fromthemapand exingit a littleto make it easierto lookat,weobtainAndorraSpainPortugalFranc eMonacoBelgiumGermanyPolandCzech RepublicAustriaItalySloveniaCroatiaSan MarinoVatican CityLuxembourgSwitzerlandLiechtenstein9W e notethatthisgraphcannotbe coloredwithlessthanfourcolors:Belgium,Lu xembourg,France,andGermany alltouch each other,so ,fourcolorsaresu cient to colorthegraph,as RepublicAustriaItalySloveniaCroatiaSan MarinoVatican CityLuxembourgSwitzerlandLiechtensteinIf youtrycoloringothermaps,andmake shrewdchoices,youwill ndthatit seemsthatfourcolorsarealways su shallshow in thesenotesis thefollowing:Theorem5 (SixColorTheorem).

9 Any mapcan be colored withsixor fewercolorsin sucha waythatno whichwouldrequiremoretimeandcarethanwe candevoteto thisproblemin thelecture,onecanshow thatthesixthcolorisn' (Five ColorTheorem,P. J. Heawood, 1890).Any mapcanbe colored with veor fewercolorsin sucha waythatno seemsto reallyneedthe fthcolorif oneis longtime,sometimesproducing awedproofsthatfourcolorssu , a solutionwas announced:Claim1 (Appel andHaken,1976).Anymapcanbe colored withfouror fewercolorsinsucha andHaken usedmathematicaltheoryto reducetheproblemfroma problemaboutallpossiblemaps(andtherearei n nitelymany of these)to checkinga largebut nitenumber thatreducesto casesis hundredsof pageslong,andthecase-checkingis notwrittenout(itis too longfora personto workout),buthadto be carriedoutwitha bugs,so somemathematiciansdonotacceptit as a have alsousedcomputers,andtheyverystronglycon rmtheclaimof ,it somewhatunsatisfactorythatthereis noproof intendprove theSixColorTheorem, ,thatallmapscanbe convertmapsinto graphsandthentryto colortheirverticeswithsixcolors,such thatnoadjacent verticeshave minute!

10 We needto thinkaboutthis:somegraphscannotbe example,thegraphbelow hassevenverticesandeach oneis connectedto wouldneedsevencolorsto properlycolorit!Whatwent wrong?In fact,now thatwementionit,we canalways draw a graphwithNverticesandjoineach vertexto everyothervertex,so thatNdi erent colorsareneededto as bigas contradictallthetheoremsmentionedabove. Butthecontradictionis onlyapparent. In fact,graphslike theonethatrequiressevencolorscannotarise as graphthatcomesfroma maphassomeconstraints onit thatmake canwe gureouttheintellectualcontent of theseconstraints?Thekey factis thefollowing:Principle:A grapharisingfroma mapcanbe drawnin theplaneso thatnotwo edgescrossover each o erthefollowingintuitive justi want to startmakinga graphforEurope. Firstwe placea dotinsideeach country:12 Then,countryby country, we draw linesfromthedotinsidethecountryto each of example,we startwithGermany here:Theserays arelike thenpick anothercountry, say, theCzech draw rays fortheCzechRepublic,andwe jointhehalf-edgesthatstrike pick anothercountry, Poland,andjoinitshalf-edgesto thoseof Germany andtheCzech thisfashion,we wouldgeta graphforthisportionof themapof Europe, andnoedgeswouldcross!


Related search queries