Facultatea de Matematic i Informatic Universitatea din Bucureti lucrare de licen Grafuri Planare autor Slavic Sorin ndrumtor tiinific conf. dr. DragoRadu Popescu Bucureti, iunie 2010 2 Cuprins 1 Prefa 4 1.1 Coninutul tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 4 1.2 Repere istorice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Problema podurilor din Knigsberg . . . . . . . . . . . . . . . . . . .6 1.2.2 Teorema poliedral a lui Euler . . . . . . . . . . . . . . . . . . . . . . .8 1.2.3 Problema celor patru culori . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Planaritate12 2.1 Introducere . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 13 2.2 Teorema poliedral a lui Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 2.3 Graf planar maximal. Triangulri . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 2.3.1 Algoritm de triangulare greedy . . . . . . . . . . . . . . . . . . . . . .21 2.4 Teorema lui Kuratowksi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 2.5 Algoritmi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5.1 Algoritmul Hopcroft-Tarjan . . . . . . . . . . . . . . . . . . . . . . . . .30 2.5.2 Algoritmul lui Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32 2.5.3 Algoritmul lui Schnyder . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 3 Colorri 363.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 1-, 2- i 3-Colorare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 3.3 Teorema celor 5 culori. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 3.4 Teorema celor 4 culori. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46 3.4 Algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 3.4.1 Algoritm Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.2 Algoritm Dsatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55 3 4 Descrierea Aplicaiei 57 4.1 Observaii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Implementare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5 Concluzii 61 Anexe63 Bibliografie 64 4 Prefaa Ideea de start pentru aceast lucrare poate fi redus la urmtoarea ntrebare: Pot s gsesc o hart corect desenat pentru un graf planar? Acuma vreau s o i colorez.. Primaparteaproblemeiamobservat-odecurndpetelefonulmobilalunuicoleg, care se juca cu o aplicaie foarte simpl [1]. Scopul era rearanjarea vrfurilor unui graf astfel nct reprezentarea acestuia s fie planar. A doua parte, cea de colorare a grafurilor este una din cele mai vechi i cunoscute probleme din teoria grafurilor. 1.1 Coninutul tezei Tezaarelabazdoutemevechiicomplexedinteoriagrafurilorpentrucareabia recent s-au realizat progrese teoretice i practice semnificative: grafuri planare i probleme de colorare.Lalucrulcugrafuri,caresuntpurisimplustructuricudouelemente,unsetde vrfurisiorelaientreacestea,suntemajutaimultattnpracticctinteoriedac realizm o proiectare a acestuia n plan. Ideal ar fi ca aceast desenare s fie ct mai aranjat i ordonat pentru a ne ajuta n executarea diferitelor operatii. Desenareaunuigrafestefoartesimpl,esteunadinprimeleoperaiicarepotfi aplicate acestuia ns nu exist un algoritm evident care s fie eficient pentru mai multe tipuri de grafuri. Pentru un graf planar o reprezentare corecta acestuia n plannu trebuie sa aibe intersecii de muchii.Aceastreprezentaresenumetehartagrafuluiiestecaracterizatdefeele sale(regiunile delimitatede muchiile grafului. Evident, oricegraf plan areun numr finit de fee, dintre care una singur este nemrginit i se numete faa exterioar a lui G. Primateoremsemnificativdescoperitpentruacestetipuridegrafuriesteteorema lui Euler. n una din primele lucrri care aveau ca interes grafurile planare acesta a propus o relaientrenumruldefee,muchiiivrfuridintreungraf.Multealteobservaiisi proprietiauurmat,toatecusperanadeadaocaracterizaresimpliuoardeverificat pentruplanaritateaunuigraf.Pentruadeduceplanaritateaesteaproapeimposibildetestat toate metodele n care un graf poate fi aezat n plan i un avantaj semnificativ a fost adus de 5 Kuratowskicareapropusometodrelativesimpldeverificareaplanaritiiunuigraf.O subcategoriecuoseriedeproprietiimportanteestealctuitdingrafurileplanare maximale, adic triangulrile unei hri. Acestea au aplicaii importante att n practic dar i laaplicareaunoralgoritmiidemonstrareaunorteoreme.nultimiianis-apusaccentpe gsirea unei metode de verificare dar mai ales de generare a unei desenri planare pentru un graf, cu o serie de algoritmi foarte complicai. nurmtoareaseciunefacemtrecerealaunadintrecelemaicunoscuteifolosite aplicaiialeunuigraf,anumecolorarea.Deinuestespecificgrafurilorplanare,folosim noiuneadecolorarenrelaiecuacesttipdegrafuridatorit,nmareparte,uneiteoreme celebre ce abia recent a fostdemonstrat, teorema celor patru culori.Pentruungrafdefinimcolorareacaoasignareaunorvalorinumericediferitelor elementedingrafastfelnctsverificmoseriedeproprieti.Colorrilesefolosescn multe domenii, la probleme de optimizare, de verificare sau la gruparea de elemente pe baza proprietilor.ncapitolsefacrefeririiseprezintproprietipentrufunciiledecolorare folosind un numr specific de culori. Prezentm iniial diferitele tipuri de grafuri sau structuri pentrucareputemaplicaocolorarecuunnumrlimitatdeculori.Metodafolositla demonstrarea colorrii cu 5 culori a fost iniial crezut corespunztoare pentru demonstrarea problemei celor 4 culori. n cele din urm s-a descoperit c problema celor patru culori este mult mai complex i a necesitat folosirea unui calculator pentru demonstraie. A fost prima problemmajorpentrucareodemonstraienuapututfiprezentatfrajutorul calculatorului. Referitorlaaceastmetoddedemonstraiefolosit,nutoimatematicieniiau acceptatdemonstraiaargumentndctesteleicalculelepentrucareaufostnecesare calculatoarele nu pot fi verificate manual. Urmtorul citat dintr-o lucrare de Saaty i Kainen pune n eviden aceste probleme : Tousethecomputerasanessentialtoolintheirproofs,mathematicianswillbe forced to give up hope of verifying proofs by hand, just as scientific observations made with a microscopeortelescopedonotadmitdirecttactileconfirmation.Bythesametoken, however,computer-assistedmathematicalproofcanreachamuchlargerrangeof phenomena. There is a price for this sort of knowledge. It cannot be absolute. But the loss of 6 innocence has always entailed a relativistic world view; there is no progress without risk of error (Kainen and Saaty, 98). Calaprimaparte,sprefinalulacestuicapitolsuntprezentatecivaalgoritmipentru colorarea vrfurilor unui graf. Lucrareadelicen,pelngaceastpartescrisaredezvoltatnparalelio aplicaieJava.Utilizatorulpracticsejoaccunoiuniledegrafplanaripoatesapliceo colorare unui graf. 1.2 Repere Istorice 1.2.1 Problema podurilor din Knigsberg OraulKnigsberg(pevremurinPrussia,acumafacapartedinRusiaisenumete Kaliningrad)estempritderulPregelnmaimulteregiuni(inclusiveinsulaKniephof) unite de apte poduri. Figura 1.1 Localnicii erau curioi s afle un drum care s nceap i s se termine n acelai punct i s parcurgtotoraulastfelnctstreacpestefiecarepodosingurdat.Aceastaera considerat o problem dificil la vremea respectiv deoarece erau multe rute posibile, dar pe altpartedacaifigsitundrumcorectproblemaerarezolvat.n1736matematicianul LeonardEulerapublicatnrevistaComentariiAcademiaeScientarmImperialisunarticol 7 considerat actul de natere a unei ramuri ale matematicii numit Teoria Grafurilor. Acesta a demonstrat c este imposibil de gsit un drum prin ora care s ndeplineasc aceste condiii. ndemonstraienefolosimdenoiuniabstracteiextragemdinproblemdoar informaiilerelevante.nfigursuntpatruzonesimaimultepoduricareleleag.Putem reducefiecareregiunelaunpunctdeoarecenusunteminteresaideeventualeledate suplimentaredinaceasta.Traversndoanumitregiuneesteechivalentcuavizitanodul adugat. Adugm linii de legtur ntre noduri, cte una singur pentru fiecare pod. Figura.1.2 Sunteminteresaidoardeconectivitatedintrenoduriinudedireciadedeplasaresaude distan. Problema este de a trece din punct n punct trecnd peste o muchie o singur dat i ajungnd napoi la punctual de start. Presupunem c pornim de la vrful din partea dreapt a imaginii.Avemdealesunadinceletreiposibilitidedeplasareceeacenseamncne rmndoumuchiicetrebuietraversatelaunmomentdat.Singurulcazncareputems folosimomuchieesteacelancarenentoarcemlapunct.nacestmomenttrebuies prsim nodul pentru a traversa i ultima muchie rmas dar nu vom aveam posibilitate de a nentoarcelanoduldestartpentruacompletadrumul.Poatecnutrebuiasancepem cltoriadinacestpunct.Nealegemaltpunctdestartdarinemcontctotvatrebuisa ajungem si la acest punct la un moment dat. La prima vizit folosim un pod pentru intrare i nc unul la ieire. A rmas o singura muchie neparcurs ataat nodului deci trebuie s mai vizitm o data nodul. Am folosit toate cele trei poduri care sunt conectate punctului i nu mai 8 avem cum sa l prsim. Drumul obinut nu este corect ntruct punctual de sfrit nu a fost i cel de nceput. S-ademonstratcpentruaparcurgetoatemuchiiledintr-ungraftrebuiecafiecare nod s aibe un numr par de muchii, indiferent de pozitia acestuia n drum(de nceput/sfrit sau n interior). Dup ce am intrat ntr-o zon trebuie neaprat s o prsim iar pentru nodul de nceput dup ce am pornit la drum trebuie s ne ntoarcem.n onoarea lui Euler, care a demonstrat aceste proprieti, un drum care viziteaz toate vrfurileiparcurgefiecaremuchieosingurdatestenumitciclueulerian.Ungrafeste eulerian dac acesta conine un ciclu eulerian. 1.2.2 Teorema poliedral a lui Euler Euler a fcut a doua mare contribuie la teoria grafurilor n 1758, la dou decenii dup cea rezolvat problema podurilor din Knigsberg. Acesta a enunat o formul pentrugrafuri planare. Un graf planar este un graf care poate fi trasat n plan astfel nct muchiile sale s nu se intersecteze n interior. Figura 1.3 O caracteristic evident a acestui tip de graf este c mparte planul n regiuni nchise deunciclunumitefee.DeexemplunFigura1.3sunttreifeeinterioaresiunaexterioar infinit.Eulerademonstratecapentruoreprezentareaunuigrafplanarnumruldevrfuri minus numrul muchiilor plus numrul feelor este ntotdeauna egal cu doi. Pe scurt n e + f =2,undenestenumruldevrfuri,enumruldemuchiisifnumrulfeelor.Pentru exemplul de mai sus avem n = 4, e = 6 i f = 4, valori care verfic egalitatea. Acest teorem 9 poart numele aceluiai Euler, n plus pentru orice reprezentare n plan al unui graf valoarea pentru n e + feste cunoscut ca si caracteristica Euler. Multedintrecorolareleacesteiteoremeconstituieobazpentruomarepartedin teoriadezvoltatreferitoarelagrafuriplanare.ntructverificareaprinreprezentria planaritiiunuigrafestefoartedificildatoritnumruluimaredeposibiliticriteriilede planaritate des folosite se bazeaz pe relaii dintre numrul de muchii i numrul de vrfuri a unui graf. Aceste relaii se deduc foarte uor pornind de la teorema lui Euler. 1.2.3 Problema celor patru culori Alt problem specific grafurilor planare a fost enunat aproape o sut patruzeci de anidupEuler.n1852,ntimpcencercascolorezehartainuturilordinAnglia,Francis Guthrie a observat c patru culori sunt suficiente pentru a desena o hart oarecare astfel nct oricare dou ri care au o frontier comun s fie reprezentate cu o culoare diferit. Guthrie l-a ntrebat pefratele su dac poate s demonstreze aceast afirmaiesi acesta a trimis mai departe conjectura profesorului su DeMorgan, n1878apareprimareferirenscrislaproblemacelorpatruculorintr-olucrarede Arthur Cayley care se interesa dac a fost dovedit conjectur. La doar un an distan Kempe alansatdemonstraiasa.Unsprezeceanimaitrziu,Heawoodaevideniatgreelin argumenteleluiKempedarareuitsverificecorectitudineapentruocolorarecucinci culori.n1880Taitaenunatoaltdemonstraiebazatpepresupunereaincorectcorice graf planar 3-conex este Hamiltonian(la eliminarea a dou muchii adiacente unui vrf graful ipierdeconectivitatea,ungrafHamiltoniancontineunciclucareviziteaztoatevrfurile sale exact o singur dat). n anul 1891 Peteresen a observat eroarea din demonstraia lui Tait i a dedus c problema celor patru culori este echivalent cu o patru colorare a muchiilor unui graf. n 1898 Heawood a mai descoperit o teorem important: dac numrul de muchii care delimiteazoregiuneestemultiplude3atuncitoateregiunilesunt4-colorabile.Pentruo reprezentare a unui graf putem s obinem o triangulare(fiecar fa s fie delimitat de doar 3muchii)adugndmuchiicarempartoricefanon-triangularntriunghiuri.O configuraieesteparteauneitriangulriconinutentr-unciclu.Unsetinevitabil(debaz) esteunsetdeconfiguraiicuproprietateacoricealttriangulareaunuigraftrebuies 10 coninunadinconfiguraiiledinset.Oconfiguraieestereductibildacpoatsfie mprit n mai multe triangulri din setul de baz. Pebazaacestorinformaiin1904anceputcutareapentruconfiguraiiiseturi evitabile prin lucrrile lui Weinicke. Noiunea de reductibilitate a fost introdus deBirkhoff. n1922Frankilnapublicatmaimulteexempledeseturiinevitabileiafolositideealui Birkhoffdereductibilitatepentruademonstracaoricehartcumaipuinde25deregiuni poateficoloratcupatruculori.Alimatematicieniaunceputsadaugelanumrulde regiuni care pot fi patru colorabile.Reynold a demonstrat pentru 27 de regiuni n 1926, Winn pentru 35 n 1940 iar Ore i Stemple au ridicat numrul de regiuni la 39 n 1970. AltecontribuiiimportanteincludteoremaluiBrooksdin1941ncaredefineao limitpentrunumrulcromaticalunuigraf(numrulminimdeculoricucarepoatefi desenat un graf) i lucrrile lui Hadwiger.Interesul n problema celor patru culori a crescut, lafel ca n teoria grafurilor n totalitate. Konig a publicat prima carte despre teoria grafurilor n 1936. Au mai fost publicate cteva textegeneralereferitoare la acest subiect de Berge(n 1961i1973),BusackeriSaaty(1965),Harray(1969),Ore(1961i1963),etc.Numrulde regiuniacontinuatscreascntretimpajungndla52infinalla95n1976datorit lucrrilor lui Mayer. Ideilefinalenecesaresoluieiproblemicelorpatruculoriaufostintrodusenc dinaintea lucrrilor lui Mayer. n 1969 Heesch a dedus metoda de descrcare, asignarea unui vrfdegradivaloarea6i.FolosingformulaluiEulerputemdeducecsumavalorilor ncrcate trebuie s fie 12. Un set de configuraii este inevitabil dac pentru o triangulare care nuconineoconfiguraiedinsetputemredistribuincrcrile(framodificasumatotal) astfelnctniciunvrfsnuaibeosarcinpozitiv.Heeschconsideracproblemacelor patru culori poate fi rezolvat folosind unset de 8900 de configuraii. n1976apareorezolvarecompletaproblemeicelorpatruculori,cndafost enunatsiteoremacorescpunztoarea.DemonstraiaaparineluiAppeliHakencareau folosit metode de reductibilitate i s-au bazat pe ideile lui Heesch, construind un set iniial de 1936 de configuraii. Au limitat numrul de muchii pentru faa exterioar la 14, lucru care a simplificat calculele pentru cazurile lui Heesch. Ei au fost ajutai de Koch i au folosit 1200 deoredelucrupecalculator.Afostprimateoremmajordemonstratfolosindun calculator, Appel i Haken au folosit un program special pentru a demonstra c toate hrile 11 dinsetverificproblema.Lucrarealornuafostacceptatdetoimatematicieniintruct demonstraiabazatpetesterealizatecucalculatorulesteaproapeimposibildeverficat manual.nc se caut o demonstraie mai eficient pentru aceast problem care s nu necesite lucrul pe calculator. n 1997 Robertson, Sanders, Seymour i Thomas au simplificat ideile lui Appel i Haken cnd au folosit calcule mai uoare pentru a demonstra teorema dar s-au bazat tot pe calculator. 12 Capitolul 2 Planaritate Dei este format doar din dou seturi de elemente este greu s ne gndind la noiunea de graffr a avea n minte o desenare pe hrtie a sa. O expunere vizual n plan al unui graf aconstituitunpunctdeinterespentruteoreticienidefoartemulttimp,nparticularpentru grafuriplanaresaugrafuricaresuntaproapeplanare.Odefinitiepentruungrafplanareste unulcarepoatefidesenatfrcamuchiilesalesseintersecteze.ntimpcelucrala problemacelorpatruculori,Wagner(1936)afostprimulcareaartatcoricegrafplanar poatefidesenatfolosinddoarliniidrepte.naintedeaceasta,ncdinanul1758Eulera enunatoformulcareprezentaoegalitatespecificgrafurilorplanare.Altcontribuie semnificativladezvoltareateorieilegatedegrafurileplanareaavut-on1930Kazimierz Kuratowskiprincaracterizareasetuluidegrafurilorplanarenasocierecudougrafuri simplecarenundeplinesccondiiadeplanaritate(K5 -grafulcompletcu5vrfuriiK3,3 graf bipartit cu 6 vrfuri cu 2 diviziuni pentru care fiecare vrf se unete cu celelalte 3). ntimpceteoriagrafurilorafostiniialoramuramatematiciiadevenitacum relevantnmaimultedomeniicaunmijlocpentrurezolvareaproblemelorsaua reprezentrii de date. Nuedificilsdescriemunalgoritmpentruafiareaunuigraf,putemconsiderao aezare aleatoare a vrfurilor ntr-un spaiu finit. Muchiile poate fi desenate ca o linie dreapt de lungime minim ntre vrfuri sau ca segmente de curb pentru e evita eventuala intersecie cu un alt vrf.Ali algoritmi la felde uor pot sprezinte o expunere circulara vrfurilor de-a lungul perimetrului unui cerc iar muchiile traversnd cercul sau plasarea vrfurilor pe un grid ptratic aezate pe diagonala principal . Calitatea sau utilitatea unei desenri particulare pentru un graf depinde n principal de domeniul de aplicare. Ideal este ca un algoritm pentru desenarea grafurilor s respecte cteva criterii estetice:-minimizarea numrului de intersecii dintre muchii; 13 -desenarea ct mai dreapt a muchiilor: -vrfurile s fie distribuite uniform; -majoritatea muchiilor direcionate s fie n acelai sens; -minimizarea ariei zonei de acoperire a grafului; -utilizarea de element simetrice; Algoritmidedesenarepentruungrafplanarauevoluatmultnultimiianiavnd aplicaii din ce n ce mai multe n diferite domenii, reele de drumuri sau plci de circuitei alte domenii care folosesc structuri definite pe suprafee. 2.1 Introducere Definiie: UngrafesteoperecheG=(V,E),undeVesteomulimefinitnevid,numit muimeavrfuriloriarEesteosubmulimeaprodusuluicarteziandintreViV(perechide vrfuri),numitmulimeamuchiilor.OrdinulunuigrafG=(V,E)estereprezentatde numrul de elemene din V iar dimensiunea sa de numrul perechilor din E. Figura 2.1 Definiie: UngrafG=(V,E)senumetegrafplanardacadmiteoreprezentarenplanastfel nct segmentele de curb asociate muchiilor sale s nu se intersecteze n interior(considerm cacesteaseintersecteaznvrfuripentruunnod).Pentruoricegrafsepotconstruimai multereprezentrinplan,obinndmaimultehri.OreprezentareM=(V,E,F)care ndeplinete condiiile de planaritate se numete hart, iar graful asociat este graful suport la 14 hriiM.LanotailedindefiniiagrafuluiseadaugmulimeaFdefee(componentele delimitate de muchiile grafului).

Figura 2.2 Definiie: Grafuldualpentruoanumithrtalunuigrafplanaresteungrafncarevrfurile suntasociatefiecreifeedingraf(inclusivfaaexterioar,infinit)iarmuchiilesunt construite unind feele care au o grani comun, fr a mai intersecta o alta muchie. Propoziie: Proprietateadedualitateaunuigrafestesimetric,dacG'estegrafdualpentruG atunci i G este graf dual pentru G'. n plus duala hrii duale este izomorf cu harta iniial. Figura 2.3 Feeleunuigrafauungradcarereprezintnumruldemuchiidinciclulcarele delitmiteaz.Dimensiunea(numrulmuchiior)pentruungrafdualesteaceeaicu dimensiunea grafului suport iar gradul unei fee se pstreaza n gradul noului nod din graful dual.Evident,dupconstruireahriidualenumruldenoduriesteegalcunumruldefee 15 dingrafuliniialiinvers:numruldefeedingrafuldualesteegalcuordinulgrafului suport(putem considerac fiecare nod se afl la intersescia mai multor regiuni iar muchiile careledespartpeaceasteavorfiapoitiatedeonouamuchieladesenareahriiduale, formndunnouciclucarenchidefaa).Acesteegalitisepstreazladesenareauneialte hridualepentrunouahartformat.Astfelobinemungrafncarefiecarevrfaregradul egal cu gradul vrfurilor iniiale deci cele doua grafuri sunt izomorfe. 2.2 Teorema poliedral a lui Euler Teorem(Euler, 1758): ConsidermungrafplanarconexG=(V,E)iohartM=(V,E,F)alacestuia, atunci se verific urmtoarea ecuaie:|V| - |E| + |F| = 2 Demonstraie: Existmaimultevariantepentruademonstraaceastafirmaie.Vomprezentatrei metode de demonstraie care au la baz construcia grafului dup numrul de fee, vrfuri i muchii.1.Considerm c un graf conex cu o singur fa reprezint de fapt un arbore. Pentru un arbore cu nodurile V si mulimea muchiilor E avem |V| = |E| + 1, reprezentarea sa n plan determin |F| = 1 rezult c |V| - |E| + |F| = 2 |E| + 1 - |E| + 1 = 2 2 = 2.

Pentruaadugaofatrebuiesnchidemunciclu.Estesuficentsadugmo singurmuchiepentruarealizaacestlucru.Astfelcreteattnumrulmuchiilorcti numrul feelor cu 1, ceea ce pstreaz egalitatea. 16 Figura 2.4 2.Dacungrafareunsingurvrfatuncitoatemuchiilereprezintocurb Jordan(segmentdecurbnchisfrautointersecii)iarfiecarefainterioareste determinat de o muchie. Deducem |F| = |E| + 1 iar |V| = 1 de unde : |V| - |E| + |F| = |E| + 1 - |E| + 1 = 2 Considerm o muchie care unete dou vrfuri i o contractm astfel nct cele dou vrfurissesuprapun,formndunnounod.Numruldevrfuriscadecu1lafelca numrulmuchiilor.Dupeliminareatuturormuchiilordintr-unciclurmnemcuunsingur nou nod i o singur muchie curb Jordan. Aceasta determin o fa corespunztoare regiunii cuprinsencicluliniial.Totgrafulsereducelaostructurcuunsingurnodcutoate muchiile curbe Jordan. Figura 2.5 3.Ungrafconexfrmuchiiestedefaptunsingurnodizolat.Pentruacestaavemo singur fa: |V| - |E| + |F| = 1 - 0 + 1 = 2 Porninddelaungrafeliminmmuchiiinoduripnsajungemlaungraffr muchii. Dac o muchie unete doua vrfuri atunci o contractm reducnd numrul de vrfuri 17 simuchiicu1.DacamuchiaestereprezentatdeocurbJordanoeliminmreducndde aceastdatnumrulfeelorsimuchiilorcu1.Sepstreazvaloareaexpresieinambele cazuri ajungnd la final la un singur nod izolat. Figura 2.6 Corolar 1: Pentru orice graf conex planar cu mai mult de trei vrfuri(implic mai mult de dou muchii) avem urmtoare inegalitate: |E| 3|V| - 6 Demonstraie: Pentru a demonstra aceast proprietat considerm un graf cu o singur fa(arbore) i maimultenoduri.|V|=|E|+1pentruarbori.nacestecondiiiinegalitateaseverific. Presupunem c graful are mai mult de dou fee atunci fiecare fa are ca frontier un ciclu C din graf. Fiecare muchie dintr-un astfel de ciclu aparine exact la dou fee iar ciclul are mai mult de trei muchii. Deducem c 2|E| este mai mare sau egal dect numrul total de muchii dinciclurilecarenconjoarfiecarefadingraf.Cumfiecarefaarecelputin3muchii obinem: 2|E| 3|F| Graful ales este planar deci putem aplica teorema lui Euler din carededucem: |F| = 2 - |V| + |E| 2|E| 3(2 - |V| + |E|) 2|E| 6 3|V| + 3|E| |E| 3|V| - 6 18 AltconsecinimportantlateoremaluiEulerseaplicpentrugrafuriplanare bipartite(ungraf este bipartit dac mulimea vrfurilor sale poate fi desprit n dou seturi astfel nct s nu existe muchie comun ntre doua vrfuri din acelai set) i anume: Corolar 2: Dac G este un graf planar, conex i bipartit cu mai mult de doua muchii atunci are loc urmtoarea inegalitate: |E| 2|V| - 4 Demonstraie: Raionamentulpentrudemonstraieestelafelcalaprimulcorolarcumeniuneac ntr-un graf bipartit ciclul minim care separ o fa are 4 muchii: 2|E| 4|F| |E| 2(2 - |V| + |E|) |E| 4 2|V| + 2|E| |E| 2|V| - 4 Corolar 3: Oricegrafplanarconexarecelpuinunvrfdegrad(numruldemuchiiadiacente lui) mai mic sau egal de 5. Demonstraie: Notm prin vi numrul vrfurilor de grad i(1 i |V| - 1) . tim ca ntr-un graf suma gradelor vrfurilor este egal cu de doua ori numrul muchiilor(pentru fiecare muchie aparine ladouvrfuri).Ansumatoategradelevrfuriloresteacelailucrucuansumapentru fiecare i produsul dintre gradul i numrul de vrfuri cu aceste grad. 19 E n iVii21 | |1= -= Folosim inegalitatea din primul corolar: |E| 3|V| - 6 ( ) 12 6 6 3 2111 | |1 - = s - ==ViiViin V n i Dac adunm numrul de vrfuri cu un anumit grad pentru toate gradele grafului obinem n final numrul total de vrfuri. 0 12 ) 6 (1 | |1s + - =Viin i Cumpentrui6toitermeniisumeisuntpozitivirezultcexistunimaimicsauegal dect 5 astfel nct ni > 0. Exist un vrf cu gradul mai mic dect cinci. 2.3 Graf planar maximal.Triangulri Definiie: Un graf se numete planar maximal dac adugnd o muchie se anuleaz proprietatea de planaritate. Definiie: Otriangulareesteungrafplanarncaretoatefeete,inclusivceaexterioar,sunt mrginite de 3 muchii. 20 Figura 2.7 Teorem: Considerm un graf oarecare G = (V,E), urmtoarele afimaii sunt echivalente

1. Graful este planar maximal.2. Graful este o triangulare. 3. 3|V| - |E| = 6 i G este planar. Demonstraie: Demontrmmaintiprimaimplicaie,dacungrafesteplanarmaximalatunci acestaesteotriangulare.Presupunemcexistohartpentrugrafulplanarmaximalales astfel nct s conin o fa mrginit de 4 sau mai multe muchii. Exist dou vrfuri n acest ciclu pentru care s nu fie trasat o muchie ntre ele. Cum faa nu este strbtut de nici o alt muchie putem unui cele dou vrfuri fr s modificm planaritatea grafului. O triangulare a unui graf implic prin definiie c toate feele sunt mrginite de doar 3 muchii.Fiecaremuchiereprezintfrontieradintredoufeedeciseverificurmtoarea egalitate: 3|F| = 2|E| Aplicm formula lui Euler: |V| - |E| + |F| = 2/*3 3|V| - 3|E| + 3|F| = 6 3|V| - 3|E| + 2|E| = 6 21 3|V| - |E| = 6 S-a dovedit anterior c pentru orice graf planar |E| 3|V| - 6. n cazulde fa avem egalitateadeciadugareauneisinguremuchiioanuleazfaptcedefineteungrafplanar maximal. 2.3.1 Algoritm triangulare Triangularea unei hri are multe aplicaii, printre care i aplicarea lor n rezolvarea unorproblemeteoreticecugrafuri.Existoseriedealgoritmipentrutriangulareaunuigraf care in cont i de distane sau unghiuri ntr-un graf. Noi suntem interesai doar de construirea unui graf planar maximal. Ideea unui astfel de algoritm este adugarea de muchii astfel nct fiecare fa nou construit s fie mrginit de trei muchii. Pentru fiecare regiune a unei hri trebuie s trecem un numr, preferabil ct mai mic, de muchii prin interiorul acesteia pentru a satisface aceast condiie. Am precizat c nu suntem interesai de mrimea muchiei adugate sau de faptul c s-ar putea s nu existe un drum drept ntre dou muchii astfel nct s nu anuleze planaritatea grafului.Oricemuchiepoatefidesenatcaocurb,ocolindprininterioralteelementeale grafului. Distingem2metodeevidenteisimplepentruadugareademuchiipentrufiecare regiune. Alegem un vrf i trasm muchii ntre acesta i toate celelalte vrfuri din ciclul care delimiteaz faa. Aplicndalgoritmulobinempentruofadelimitatdeunciclucunnoduri, indiferentdevrfuldepornire,unnougrafplanarncareamadugatn-3muchii.Grania unei fee este evident reprezentat de un ciclu. Pentru un nod avem deja doi vecini i astfel ne rmn n-3 vrfuri care trebuie legate printr-o muchie. Singura observaie este la triangularea feeiexterne. Pentru aceasta muchiile vorfi subformaunorcurbeinuvorfitrasatepentrutoatenodurile.Lafelpentruunnodales 22 parcurgem ntr-o ordine ciclul care delimiteaz regiunea trasnd muchiile astfel nct acestea s ocoloeasc graful. 2.4 Teorema lui Kuratowski naintedeaformulaaceastteoremdecaracterizareagrafurilorplanaretrebuies avem n vedere cteve definiii i proprieti folosite. Definiie: Spunem c dou grafuri G = (V,E) i G = (V,E) sunt izomorfe dac exist o bijecie f:VVdefinitntremulimeavrfurilorcelordougrafuricarepstrezrelaiilede adiacent i neadiacen dintre vrfuri. ' ) ( ) ( : , E y f x f E xy V y x e e e Observm c mulimea gradelor vrfurilor este aceeai pentru ambele grafuri. Definiie: UngrafG=(V,E)estesubgrafalluiG=(V,E)daceliminndmuchiiivrfuri din G putem ajung la o reprezentare a lui G.V_ V i E_ E Definiie: Se numete graf p-conex un graf n care prin eliminarea oricrui set de p-1 vrfuri nu se anuleaz proprietatea de conexitate. Definiie: Un graf complet este un graf simplu n care toate perechile de vrfuri distincte sunt unite de o unic muchie. Graful complet de ordin n notat Kn este graful cu |V| = n. ( )21 =V VE Figura 2.8 Definiie: 23 DougrafuriGiGsunthomeomorfedacGsepoatetransformanGdup aplicareaunuinumrfinitdesubdiviziunisimpleieliminareadevrfuricugradulegalcu doi astfel nct muchiile adiacente vrfului s fie unite. Figura 2.9 Definiie: Ungrafestebipartitdacmulimeavrfurilorpoatefimpritndousubseturi disjunctenenuleastfelnctoricemuchieuneteunvrfdintr-unsetcuunvrfdincellalt set.Pentru un graf bipartit complet fiecare vrf din primul set este unit prin muchii de toate vrfurile din al doilea set.Notm Kn,mgraful bipartit complet pentru care V = V1 V 2 . |E| = |V1| * |V2| Figura 2.10 n teorema lui Kuratowski se face referire la dou grafuri n deosebi: unul complet K5 i unul bipartit complet K3,3 , amndou neplanare. PentruademonstraacesteafirmaiiapelmlateoremaluiEuler,maiexactla primele dou corolare: 1.Pentruoricegrafplanarconexcumaimultdetreivrfuri(implicmaimultde dou muchii) avem urmtoare inegalitate: |E| 3|V| - 6 2. Pentru orice graf planar, conex i bipartit cu mai mult de dou muchii atunci are loc urmtoarea inegalitate: |E| 2|V| - 4 24 Figura 2.11 Teorem: K5nu este planar. Demonstraie: Putem aplica primul corolar: |V| = 5. ( )21 =V VE= 10 10 = |E| 3|V| - 6 = 15 6 = 9 10 9 fals Teorem: K3,3 nu este planar. Demonstraie: Pentru K3,3 putem apela la dou metode n a demonstra c nu este planar: 1. aplicm al doilea corolar:|V| = 6. |E| = 3*3 = 9. 9 = |E| 2|V| - 4 = 10 4 = 6 9 6 fals 2.Prinreducerelaabsurdprespunemcgrafularfiplanar.Pentruungrafbipartit lungimea minim posibil pentru un ciclu este 4 de unde rezul ca fiecare fa a oricrei hri aregradulcelpuin4.Pentrufiecarefafconsidermd(f)valoareapentrunumrulde muchiicareformeazciclulceomrginete.Fiecaremuchieaparelacalculareavalorilor pentru d de dou ori: n cazul n care aceasta separ dou fee se consider pentru amndou 25 iar dac este o muchie care nu este pe frontiera feei atunci se adaug dedou ori pentru c prin ea se va trece n ambele sensuri la selectarea ciclului. ( ) 18 9 * 2 2 4 = = = seE f d FF f |F| 4 Din teorema poliedral a lui Euler deducem inegalitatea: 2 = |V| - |E| + |F| = 6 - 9 + |F| 6 9 + 4 = 1. fals Avndnvederetoateacestedefiniiisiobservaiiputemsenunmteoremalui Kuratowski: Teorem(Kuratowski, 1930): Un graf finit este planar dac i numai dac acesta nu conine un subgraf care este o subdiviziune a lui K5(graful complet cu 5 vrfuri) sauK3,3 (graf bipartit cu 6 vrfuri cu 2 diviziuni pentru care fiecare vrf se unete cu celelalte 3). Alt formulare pentru aceast teorem folosete conceptul de graf homeomorfic. Un graf finit este planar dac si numai dac acesta nu conine un subgraf care este homeomorfic cu sau . Demonstraie: ImplicaiainversesteevidentdeoareceK5i K3,3suntneplanare.Dacgraful conineunsubgrafcareestehomeomorfcuunuldintreacestedougrafuriatuncieleste neplanar, deci i graful este neplanar. Presupunem c teorema este fals. Trebuie s gsm un set de contra-exemple cu un numr ct mai mic de muchii care s nu conin o subdiviziune a lui K5 sau K3,3 i nici s nu fie planar. Notm cu n numrul de muchii E(G) i v numrul de vrfuri V(G) pentru un astfel de graf G din set. Urmtoarele trei afirmaii sunt adevrate: 1. G este conex. PresupunemcGnuesteconex.ExistatunciomprirealuiGnmaimulte componente conexe care evident au mai puine muchii dect G. Putem elimina cazul n care existvrfurifrmuchiinGdeoarececumamafirmatanteriorcGapainesetuluide 26 grafuricunumrulminimdevrfuricaresnuverificeteorema.DacGnuconine subgrafurihomeomorfecuK5sau K3,3atuncinicicomponentelesaleconexenulevor include. Numrul de vrfuri pentru o component conex a lui G este mai mic dect V(G) de underezultctoateacestecomponentesuntplanare.TrebuiecaiGsfieplanarntruct toate componentele sale conexe sunt deci presupunerea fcut este fals iar G este conex. 2. G nu conine noduri critice. Un nod este critic dac prin eliminarea sa din graf acesta nu mai este conex.PresupunemcGconineunvrfcriticinotmcuG*grafuldeconectatprin eliminarea acestui vrf. G* nu este conex deci la fel ca la demonstraia anterioar poate s fie mpritnmaimultecomponenteconexeci.Fiecarecinupoatesconinunsubgraf homeomorfcuK5sau K3,3deoareceniciGnuconinea.DeoareceE(ci) 3|V| - 6 2. dac nu exist cicluri de lungime impar i |E| > 2|V| - 4 2.5.1 Algoritmul Hopcroft-Tarjan n1974HopcroftiTarjanapropusprimulalgoritmntimplineardetestarea planaritii. Acest algoritm, cunoscut i sub numele de path-addition algorithm pornete de launcicluiadaugcteocalelafiecarepas.Deoareceestefoartecomplexidificilde implementat au fost fcute mai multe contribuii la dezvoltarea sa. Un exemplu evident este 31 lucrareascrisdeMehlhorniMutzeln1996careauevideniatometodprincaresse construiascdesenulnplanpentruungrafcareafostgsitplanarprinalgoritmuliniialal lui Hopcroft i Tarjan. Pentruanelegealgoritmultrebuiemaintisintroducemctevedefiniiiisclarificm informaii legate de parcurgerea n adncime a unui graf, depth first search. Ungrafestebiconexdacprineliminareaoricruivrfgrafulrmneconex.O componentbiconectesteunsubgrafmaximalbiconex.Oricegrafconexsepoate descompunecaunarboredecomponentebiconexecaresuntconectateprinnoduricese numesc puncte de articulaie. Exist dou metode clasice de parcurgere a unui graf: parcurge n lime(breadth first, search BFS) sau parcurgere n adncime(depth first search, DFS).nalgoritmullor,HopcroftiTarjanapeleazlaadouametoddeparcurgerea nodurilor unui graf DFS. Parcurgerea pornete de la un vrf oarecare i continu trecnd de la nodul curent la urmtorul ct timp exist vecini nevizitai pentru nod. Cnd nodul curent nu maiarevecinineexplorainentoarcempeacelaidrumpngsimunnodconectatla vrfuri nevizitate. procedure DFS(nod n) viziteaz(n); for i : vecini(n) if(i : nevizitat) DFS(i) end Algoritmul lui Hopcroft i Tarjan este bazat pe o cutare a unei reprezentri planare a grafului dar fr s fie precizat cum s se deseneze aceast reprezentare. Etapele pe care este bazat algortimul sunt urmtoarele: -Testeaz dac numrul de muchii din graf nu depete condiia din corolarele teoremei luiEuler(dac depete atunci nu e planar). -mparte graful n componente biconexe. -Folosete o cutare n adncime pentru a gsi un ciclu n graf. 32 -Eliminareaciclurilormpartegrafulnmaimultecomponenteconexenumite poduri.Pentru fiecare pod individual testm dac mpreun cu ciclul formeaz ungrafplanar.Folosimacelaialgoritmlafiecaretestinndcontcfiecare podestemaimicdectgrafuldincareafostseparatiastfelevitm posibilitatea apelrii la infinit a recursivitii. -Dac ciclul este aezat n plan atunci fiecare pod trebuie s se afle n ntregime fieninteriorsaunexterior.Uneleperechidepodurisepotintersectai trebuie aezate pe pri opuse ale ciclului. Cheiaimplementriieficienteaalgoritmuluiesterealizareatuturorcalculelori testelor(inclusiv a subgrafurilor) printr-o singur parcurgere n adncime. Figura 2.15 nexempluldinfigura2.15avemconstruciaarboreluiobinutdinparcurgereaDFS pentrugrafulalturat.Liniilepunctatereprezintramurilepentoarcere,carenuaufost traversate n parcurgerea grafului. Ciclul gsit pentru al doilea pas din algoritm este: 1 -- 2 -- 4 -- 3 -- 6 5 1 n al 5-lea pas, testul de verificare, observm c cele 3 muchii neparcurse pot fi asezate pe o parte si pe alta a ciclului astfel nct s nu se intersecteze, adic reprezentarea s fie planar pentru subgraful obinut.Am artat c graful este planar. AlgoritmulHopcraft-Tarjanreducetestuldeplanaritatelaverificaredacarborele obinutdupparcurgereaDFmpreuncumuchiiledentoarcereformeazostructur planar.Aceastverficarepoatefifcutfoarteeficientasignndpentrufiecaremuchiede 33 ntoarcereovaloarecarenespunepeceparteacicluluiseafl:LEFT-RIGHT.Pentruo muchie de ntoarcere dintre dou vrfuri trebuie ca n ordinea de parcurgere a ciclului acestea snufieseparatedeunnodconectatprinoaltmuchiedentoarceredenodaflatnafara setului delimitat de cele dou noduri. 2.5.2 Algoritmul lui Tutte n 1963 Tutte a dezvoltat un algoritm bazat pe idea de corzi elastice pentru desenarea unui graf planar 3-conex n plan. Prin aceast metod vrfurile ciclului care delimiteaz faa externagrafuluiestesuntfixatentr-unpolygonstrictconvexntimpcecelelaltevrfuri suntintroduseninterioriconectateprinmuchiicroralevomasignavaloripentru elasticitate.Coeficientuldeelasticitatei,jarevaloristrictpositiveiestecalculatepentru muchia dintre nodul i i nodul j doar dac nu se afl amndou pe ciclul exterior. Considermpipoziianplanavrfuluii.Pentrui=k+1,..,naceastpoziieeste fixat(n reprezint numrul de noduri din graf). Celalalte poziii urmeaz s fie calculate i se aflundevaninteriorulpoligonuluideterminat.Sistemulformatdintr-unpoligonrigid consideratsuportimuchiielasticeestenechilibrudacseverficurmtorulsistemde ecuaii:( ) 0 = eE iji j ijp p e Evident pentru muchia ij considerm vrful i n interiorul poligonului iar vrful j care poziia fixat. Sistemul fixeaz fiecare nod interior n centrul geometric al corpului construit de vecinii si. Laaplicareaalgoritmuluifixmpoziiilevrfurilordinciclulexteriorpeunpoligon convexnplan.Asignmvalorialeatoareninteriorulpoligonuluipentrucelelaltevrfurii repetm paii: -pentrufiecarevrficalculmforaFipentrutoatecoeficienteledeelasticitate pentru muchiile adiacente nodului; -mutm fiecare vrf i pentru vectorul Fiunde > oeste un numr real fixat;34 Repetmacetidoipaipncnddeplasareavrfurilorestesuficientdemicpentrua aproxima sistemul de ecuaii. 2.5.3 Algoritmul lui Schnyder Scopul algoritmului lui Schnyder este de a determina o hart cu muchii drepte pentru ungrafplanarcepoatefireprezentatpeungrid.Pentruungrafplanarcunvrfuri algoritmulvagsiodesenareagrafuluintr-ungriddedimensiunen-2Xn-2ntimplinear. AceastareprezintombuntireaalgoritmuluiconstruitdeDeFraysseix,PachiPollack care folosea un grid de dimensiune 2n-4Xn-2. GrafuldeintrarepentruacestalgoritmesteungrafplanarfrmuchiicurbeJordan sauvecintimultiplentredoufee.nplusestedatioreprezenareasanplan aproximativ, referitor la o ordonare n sensul acelor de ceas a muchiilor pentru fiecare vrf. Altelementesenialestefaptulcgrafulesteplanarmaximal,evidentfiecarefaare3 muchii. Selectm o fa agrafului cafiind extern i restul ca interne. O muchiesau un vrf sunt considerai interni dac nu aparin feei externe.Metoda lui Schnyder depinde de dou caracteristiciaunuigrafplanartriangulat:etichetareaunghiurilorinterneidirecia muchiilor.Dupcumspuneinumele,etichetareaunghiurilorinterneasigneazovaloare dintre 1, 2 sau 3 fiecrui col al unui triunghi astfel nct fiecare triunghi are toate etichetele n ordinea acelor de ceas. Pentru setarea direciei muchiilor trebuie la fel o etichetare cu 1, 2 sau3,dedataaceastaamuchiilor.Fiecarevrfareexactomuchiedeplecareetichetatcu fiecare numr i acestea apar n ordinea acelor de ceas. Muchiile poziionate ntre dou dintre aceste muchii va fi etichetat cu 6-i-j, unde i i j reprezint etichetare celor dou muchii. Etichetarea unghiurilor interne are o serie de proprieti specifice: 1. Pentru fiecare triunghi exist un col etichetat cu 1, al doilea cu 2 i al treilea cu 3. 2. Unghiurile fiecrui triunghi sunt etichetate n ordinea acelor de ceas cu 1, 2 i 3. 3.Pentrufiecarevrfinterior,etichetrilecolurilorpentrufiecaretriunghiadiacentsunt construite ca serii de 1 urmate de 2 i 3. 4. Toate unghiurile unui vrf exterior au aceeai etichet. 35 5. Vrfurile triughiului exterior pentru care toate unghiurile adiacente sunt etichetate doar cu o singur valoare apar i ele n ordinea acelor de ceas. Selecia etichetrii unei muchii se face pe baza etichetrii vrfurilor adiacente. Fiecare muchiifacelegturantredouvrfuricuctepatruunghiuriadiancenteetichetatecudou dintrecele3valoriodaticucealaltvaloareademaimulteori.Setmetichetarea muchieie ca fiind valoarea setului de etichetare care se repet la vrful de intrare din direcia muchiei.Schnyderdescrieometodfolositladeterminareaetichetrilorvrfurilori muchiilorfolosindcontraciialemuchiilor.Omuchieinterioaraunuigraftriangulareste contractabildacceledouvrfuridincapeteauexactdoivecinincomun.Rezultatul contractrii este eliminarea muchiei respective i se adaug muchii ntre un vrf i toi vecinii celuilalt.Deoarececontraciauneimuchiiaunuigraftriangularducelaformareaunuialt graftriangularcuunvrfmaipuin,Schnyderconsidercsteposibilconstruciaunei etichetriporninddelaordineainversncareaufostfcuteoseriedecontraciia triunghiului exterior.Pentruunvrfintern,dacmergempelanulconstruitdemuchiileetichetatecu aceeaivaloareajungemlavrfultriunghiuluiexteriorcorespunztor.Pentrufiecarevrf internceletreilanurideterminomprireagrafuluintreiregiuni.Folosimnumrulde triunghiuridintr-oregiunepentrudeterminareaunuisetdecoordonatetrei-dimensionale pentru un vrf. Pentru orice set de coordonate (x,y,z) verificm egalitatea x+y+z = 2n-5 astfel ncttoatecoordonatelesfieaezatenacelaiplan.Pentrudeterminareauneiaezrimai compacte Schnyder folosete o numrare a vrfurilor dintr-o regiune, inclusiv din drumul ce mrginete o regiune vecin pe partea acelor de ceas dar nu pe partea opus. Dupceamdeterminatcoordonatepentrufiecarevrfalgrafuluitriangular,prin folosirea uneia din metode de numrare descrise mai sus, trebuie doar aplicarea lor pe un grid de dimensiune 2n-5X2n-5 sau n-2Xn-236 Capitolul 3 Colorri Princolorareaunuigrafnelegemprocesuldeasignareaunorculori(reprezentate prinvalorinumericedistincte),diferitelorcomponentealegrafului(vrfuri,feesaumuchii) astfelnctsfiendepliniteoseriedeconstrngeri.ncontinuarevomconsideraproblema colorriipentruvrfurileunuigraf,acestafiindcazulcelmaiimportantdeoarecesepoate replicantr-oformechivalentpentrualtetipuridecolorri.Colorareamuchiilorsepoate rezolvaprincolorarealinie-grafuluiasociat,iarpentruoreprezentareagrafuluicolorarea feelor acestuia se poate realiza prin colorarea vrfurilor grafului dual asociat. Colorarea cu un numr redus de culori nu poate fi aplicat tuturor tipurilor de grafuri. Vomprezentatipuriledegrafuriihriiproprietiloracestoracarelepermitsfie colorare cu 1,2 sau 3 culori.Teorema celor 5 culori a fost demonstrat nc dinaintea anului 1900 de Kempe care erancutareademonstraieiproblemeicelorpatruculori.Ideeasadedemonstraieafost demonstrateronatdeHeawoodcareadedusdinaceastmetodinformaiilesuficiente demontraiei problemei celor 5 culori. Auurmatapoiaproape70deanidencercriaunoradintreceimaimare matematicienidedemonstrareaproblemeicelorpatruculori.AppeliHakenauaplicat metodeleluiHeeschdereducereidescrcareagrafurilorpentruademonstra.Ideeade demonstraieestearhicunoscutdatoritnprincipalfolosiriicalculatoarelorpentru verificarea i testarea unor configuraii. 3.1 Introducere Definiie: FieG=(V,E)ungraf,op-colorarevrfurilorluiG,unde e p ip>0,poatefi definit ca o funcie c : V -> {1, 2, .., p} cu proprietatea c: 37 ( ) ( ) j c i c = , E ij e Definiie: NumrulcromaticalgrafuluiG,notat(G),esteceamaimicvaloarealuie p * pentru care G admite o p-colorare proprie. O p-colorare a vrfurilor poate fi considerat ca o partiionarearevrfurilornpseturiindependentenumiteclasedecolorare.Unexemplu evidentestereprezentatdesetulgrafurile2-colorabilecareesteacelaicusetulgrafurilor bipartite. Figura 3.1 Definiie: Op-colorareamuchiilorunuigrafG=(V,E)esteoaplicaiec:E->{1,2,..,p} pentru care oricare dou muchii adiancente au culori diferite: () ( ) f c e c = , E f e e ,Definiie: Indicele cromatic al grafului G, notat(G),este cea mai mic valoare a luie p * pentrucareGadmiteop-colorareamuchiilorsale.Observmcindicelecromaticeste calculate foarte uor ca fiind gradul maxim al vrfurilor din G. 38 Figura 3.2 Definiie: Colorareafeeloruneihripoateficonsideratcaop-colorareavrfurilorgrafului dualasociat.ConsidermpentruofafeF,C(f)mulimeamuchiilordinciclulcareo delimiteaz. O p-colorare a feelor este o funcie c : F -> {1,2,..,p} astfel nct: () ( ) f c e c =F f e e ,unde ( ) () | = e C f C Figura 3.3 39 3.2 1-, 2-, i 3Colorare naceastseciuneneinteresmdecolorareagrafurilorfolosindunnumrctmai mic de culori. Aceste rezultate se obin foarte uor i logic i reprezint un pas semnificativ pentru a nelege celelalte probleme de colorare i importana lor. O culoare: Pentruacoloraohartcuosingurculoaretrebuiecareprezentareaeisconino singur fa nemrginit. Dac harta ar conine o fa mrginit atunci atunci muchiile sale ar trebui s o separe de alt regiune i astfel trebuie s fie colorate folosind dou culor diferite. Presupunndcgrafulconineuncicluastanseamncplanuldereprezentareeste mpritndouregiuni.Deducemcohartpoateficoloratcuosingurculoaredac graful nu conine niciun ciclu. Un astfel de graf este n mod evident un arbore.Regiunile unei hri sunt 1-colorabile dac graful pentru acea hart este un arbore. Pentru colorarea vrfurilor unui graf ideea este mult mai simpl ntruct dac exist o muchieconectoarentredouvrfuriatunciacesteatrebuiecoloratediferit.Observmc vrfurilegrafuluipotficoloratecuosingurculoaredoardacacestanuconinenicio muchie.Colorareavrfurilorunuigrafconexnecesitosingurculoaredacinumaidac acestaesteformatdintr-unsingurvrf.Dinaceastobservaieputemsfacemlegturacu colorarea unei hri ntruct aceasta are o singur regiune. Pentru o hart M ce are o singur fa nemrginit obinem graful dual asociat ca un graf cu un singur vrf. Acest vrf poate fi colorat cu o singur culoare deci i harta M are aceeai proprietate. Dou culori: Colorareauneihricudouculoriesteunpicmaidificildarlafelestespecific unui anumit tip de grafuri. Un exemplu clasic pentru colorarea unei hri cu dou culori este tabladeah.nsaceastalegereestegreitntructtrebuiesavemnvedereifaa exterioar,careintrncontacticusuprafeealbesaunegre.Putemsconsidermotabl 40 deahinfinitnsaceastanuajutlanelegereacondiiilornecesarepentruafi2-colorabil. Figura 3.4 Teorem: Ohartpoatefi2-colorabildacinumaidacoricevrfalgrafuluiaregradul parmaimaresauegaldectdoi.Aceastteorempoatefidoveditprininduciedup numrul de muchii. Demonstraie: Pentru a genera o hart 2-colorabil putem s imprim planul n dou trasnd o linie infinit.Fiecareregiuneseparatdeaceastlinievaficoloratcuunadinceledouculori. Repetmprocesulconsiderndfiecarefacaunplannumaicdedataaceastainversm culorile care se afl pe o singur parte a liniei.. Aceeai idee o putem aplica pentru generarea unei hri folosind cercuri. Zona interioar va ficoloratcu o culoarea iar cea exterioar cu alta. Cnd adugm un nou cerc ntr-o zon colorat ntr-un fel inversm culoarea din interior lsnd cea din exterior la fel. n cazul interseciei dintre dou cercuri zona de interseciei va aveaculoareaschimbatpecndinteriorulrmaspentrualdoileacercvaaveaculoarea primului. Evident ambele metode determin o colorare corect folosind doar 2 culori. 41 Teorema enunat este evident pentru un graf cu doar dou muchii deoarece acestea nuformeazuncicluidecinuavemmaimulteregiuni.Presupunemteoremaadevarat pentruoricehartcummuchiiitoatevrfuriledegradpar.Considermohartcum+1 muchiiitoatevrfuriledegradpar.ncepemoparcurgeredelaunnodAoarecarepn ajungem napoi la un alt nod B pe care deja l-am parcurs. Drumul de la prima apariie a lui B pnlantoarcerealaelesteunciclunchispecareputemsltergem.ntructciclulare maimultdeomuchie,obinemonouhartpentrucarecondiiadinipotezainduciesunt verificate,adiceste2-colorabil.Adugndciclulnapoindesenputemsinversm culorile de pe o parte a zonei nchise i obinem o 2-colorare corect. Pentrucolorareavrfurilorunuigraftrebuiesavemnvederenprimulrnd dimensiunea ciclurilor sale. Teorem: Vrfurile unui graf pot fi 2-colorate dac i numai dac acesta nu conine un ciclu cu un numr impar de vrfuri. Demonstraie: Demonstraiapentruaceastteoremestefoartesimplipornetedelaconstrucia ciclului.Dounodurilegateprintr-omuchietrebuiesfiecoloratediferitedecioricedou vrfuridincicluauculoridiferite.Porninparcurgereacicluluiisetmoculoarepentru primulvrf.Colormtoatevrfurileadiacenteluicucealaltculoare,inclusivceledou vrfuricareaparinciclului.Ciclulareunnumrpardevrfiastfeldacfacemsimultan cte un pas din fiecare vrfurile colorate, mergnd n ambele sensuri vom colara vrfurile la fel pentru fiecare nou muchie traversat. Ajungem la final cnd avem dou vrfuri alturate dar care au aceeai culoare.Aceast afirmaie este echivalent cu faptul c graful 2-colorabil este bipartit. Un graf este bipartit dac setul de vrfuri poate fi mprit n dou submulimi astfel nct s nu existe o muchie ntre dou vrfuri din aceeai submulime. Aplicarea unei 2-colorri pentru un graf bipartit este evident ntruct fiecare submulime de vrfuri va avea o culoare diferit. 42 Pentru un arbore o funcie de 2-colorare este la fel de intuitiv, ideea de baz este ca fiecare nivel s aibe o alt culoare. Pentru un nod colorat ntr-un anumit fel trebuie s alegem pentru copiii si cealalt culoare. Evident un arbore nu conine cicluri deci nu putem obine o contradicie cu prima teorem. Trei Culori: La aplicarea unei 3-colorri nu mai exist din pcate astfel de caracterizri uoare. Oteoremdecaracterizarepentrugrafurile3-colorabileseaplicgrafurilorcuhri cubice. Numim o hart cubic dac fiecare vrf are gradul 3. Teorem: Ohartcubiceste3-colorabildacinumaidacfiecareregiuneestemrginit de un numr par de muchii. Demonstraie: Primaimplicaieestefoartelogicsipornetedelaconstruciauneihricubice.O colorareauneihricubicepresupunecanumruldemuchiidinciclurilecaredelimiteaz fiecare regiune s fie par. Putem colora o fa cu o anumit culoare iar regiunile sale vecine alternativecucelelaltedouculorirmase.Pentrufiecarehartputemsconstruimungraf dualastfelnctobinemuncicluasociatfeelorvecine.Cumamartatnparagrafele anterioarelungimeaunuiciclucoloratcudoardouculoritrebuiesfiepar.Caurmare fiecar fa a unei hri cubice 3-colorabile trebuie s fie delimitat de un numr par de fee vecine.Pentru a arta c dac fiecare regiune dintr-o hart cubic este delimitat de un numr pardemuchiiatuncihartaeste3-colorabilpornimdemonstraiaprintr-oinduciedup numrul de regiuni din harta respectiv. Pentru ohartcu 3 regiuni colorareaeste evident, fiecare regiune are o alt culoare.Presupunem teorema adevrat pentru o hart cu mai puin der regiuni. Considerm o hart cubic M cu r+1 regiuni unde fiecare fa are un numr par de muchii. Cum am vzut n teoria pentru grafurile planare, fiecare graf planar poate fi considerat ca un graf dual pentru o alt hart. Evident graful pentru o hart cubic este planar deci putem s construim graful 43 dual asociat. Al treilea corolar al teoremei lui Euler limita gradul unui vrf oarecare din graf astfel nct acesta s fie mai mic sau egal cu 5. Trecnd napoi la o hart rezult ca trebuie s existe o fa mrginit de mai puin de 5 muchii. Cum numrul de muchii pentru fiecare fa esteparobinemdoucazuripentruregiunearespectiv,dousaupatruregiunicareo nconjoar.Daceliminmaceastfaobinemohartcurregiunicareampresupusn ipoteza de inducie c este 3-colorabil. Rmne de artat ca prin eliminarea feei numrul de muchii care mrginesc celelalte regiuni rmne par. Pentruprimulcaz,ncarefaaeliminatare2muchii.PentruaeliminaregiuneaR estesufficientstergemosingurmuchie.Astfelaceastfaiceadecareeraseparatprinmuchiaeliminat,R,seunesc.Celelaltefeenusuntafectatedeaceastmodificare ntruct marginile au rmas n aceleai poziii iar noua fa are acelai numr de muchii ca si regiunea R: a fost eliminat o muchie dar i adugat cealalt care desprea regiunea R de cealaltfa.Numruldemuchiicaremrginescfiecarefaarmaspardeciseverific inducia i harta este 3-colorabil. n cazul n care harta are o regiune cu 4 muchii, selectm regiunile vecine acesteia i lenotmR1,R2,R3iR4nsensulacelordeceas.Evidentacesteregiunitrebuiesfie conectate dar trebuie ca dou dintre ele s nu fie separate de o muchie. Presupunem c R2 iR4 nu au muchie comun deci pot fi colorate la fel pecnd celelalte 2 regiuni suntcolorate diferit.EliminmmuchiiledintreRiR2,respectivRiR4,obinndastfelohartcur-1 regiuni.Folosindacelairaionamentcanprimulcazregiunilepentrunouahartauun numrpardemuchii.NotmcuRnouafaformatdinreuniuneadintreR,R2iR4. AmintimcnconstruciahriiRaveadoar4muchii,cteunapentrufiecaredincele4 regiuni vecine. Att pentru R2 ct i pentru R4 trebuie deci s fie un numr impar de muchii n contact cu exteriorul. Astfel orice ciclu care ocolete noua fa R pentru a ajunge din R1n R3trebuiesparcurgunnumrimpardemuchii,delimitndlafelunnumrimparde regiuni.Cumammaiartat,pentruo2-coloraredupparcurgereaunuinumrimparde vrfuri obinem o aceeai culoare pentru vrful de nceput ct i pentru cel de la final. Aadar R1 i R3 trebuie s fie colorate la fel pentru ca aceast hart cu r-1 regiuni s fie 3-colorabil. AdugmdinnouregiuneatearsRpentrucolorndceledouregiunivecineR2iR4cu aceeaiculoareiarpeRcuoculoaredistinct.Obinemo3-colorarecorectpentruharta cubic cu r+1 regiuni. 44 n ambele cazuri putem afirma c o hart cubic cu regiunile mrginite de un numr par de muchii este 3-colorabil. 3.3 Teorema celor 5 culori Cumafostexemplificatanteriorproblemeledecoloraresepotreducelaosingur aplicaiedefinitpemulimeavrfurilor.Considermo5-colorareauneihricafiind5-colorarea vrfurilor grafului suport. Teorem: Pentru orice hart M = (V,E,F) avem c numrul cromatic (M) 5. Demonstraie: Amintim din teorema lui Euler c pentru un graf planar conex G = (V,E) i o hart = (V,E,F) al acestuia, atunci se verific urmtoarea ecuaie: |V| - |E| + |F| = 2 Pentru un graf planar cu mai mult de trei vrfuri aceast teorem implic: |E| 3|V| - 6 FieungrafGcu|V|>=6i|E|numruldemuchii.Oricegrafcumaipuinde|V|vrfuri poateficoloratcu5culori.Afirmaiaesteevidentdeoareceputemscolormfiecarevrf cu o culoare diferit. Aceasta este pasul de inducie. Folosim urmtoare notaie pentru media gradelor nodurilor grafului G: ( ) ( )e=V vv d G dV1 unde evident d(v) reprezint gradul vrfului respectiv. ( )eV vv d= 2|E| Putem s aplicm corolarul de la teorema lui Euler i obinem inegalitatea: ( )( )66 3 2 2