Fakulta Informatiky Masarykova Univerzita Základy Teorie Grafů pro (nejen) informatiky Doc. RNDr. Petr Hliněný, Ph.D. hlineny@fi.muni.cz 19. března 2010 N^tis mPo % '^AS u^ Obsáhlý úvod do většiny základních oblastí teorie grafů, s (přiměřeným) důrazem na algoritmické a informatické aplikace a doplněný bohatým procvičením látky a úlohami k samostatnému řešení Základní český výukový text pro předmět MA010 na FI MU od roku 2006. Verze 1.20 (2010) © 2005 2010 Petr Hliněný, FI MU. Předmluva Vážení čtenáři, dostává se vám do rukou výukový text Teorie grafů, který je primárně zaměřený pro potřeby studentů informatických oborů na vysokých školách (je ale dobře přístupný i ne-informatikům). Hloubkou teoretického záběru je tento text směřován spíše do magisterské úrovně studia, ale při vynechání některých více teoretických pasáží dobře poslouží i jako základní přehled oblasti na bakalářské úrovni. Diskrétní matematika a Teorie grafů jako její prominentní součást jsou moderními a rychle se rozvíjejícími oblastmi matematiky, které mají mnohé úzké vazby na teoretickou i aplikovanou informatiku. Kořeny diskrétní matematiky (kombinatoriky) sahají k velkým matematikům 18. a 19. století, z nichž si zaslouží jmenovat především Leonard Euler. Byl to však až nástup počítačů a rozvoj informatiky jako vědní disciplíny v druhé polovině 20. století, které přinesly nové teoretické pojmy a otázky a vtiskly tak diskrétní matematice její moderní tvář, spojenou dosti specificky s pojmy relací a grafů. Náš text vás seznámí jak s přehlednými základy klasické teorie grafů, tak i se hlavními grafovými pojmy užitečnými pro aplikace, především ty informatické, a závěrem rozvede některé zajímavé nové směry vývoje. Je koncipován jako soběstačný celek, který od čtenáře nevyžaduje o mnoho více než běžné středoškolské matematické znalosti, k tomu základní formalismy matematického dokazování (matematickou indukci) a diskrétní matematiky (množiny, relace, kombinatorické počítaní) a chuť do studia. Části věnované algoritmickým aplikacím navíc předpokládají jistou znalost algoritmizace a zběhlost v programování. Svým rozsahem látka odpovídá jednomu semestru běžné VS výuky včetně cvičení. Tento výukový text vychází ve svých základech z vynikající moderní učebnice [5] Kapitoly z Diskrétní Matematiky [5] autorů J. Matouška a J. Nešetřila z MFF UK. (Tato kniha se kromě českého vydání dočkala i úspěšných vydání ve světových jazycích, jako například [6]. Vřele ji doporučujeme všem zájemcům o rozšíření svých diskrétních matematických obzorů.) Záběr našeho textu není tak široký jako u zmíněné učebnice, ale zaměřujeme se především na ty oblasti grafů, které nacházejí nejčastější použití v informatické praxi. Na druhou stranu se zde více věnujeme přímým algoritmickým aplikacím uváděné látky a zmiňujeme také některé důležité detaily programátorské implementace. Ve stručnosti se zde zmíníme o struktuře naší učebnice. Přednášený materiál je dělený do jednotlivých lekcí (kapitol), které zhruba odpovídají obsahu týdenních přednášek v semestru. Lekce jsou dále děleny tematicky na oddíly. Výklad je strukturován obvyklým matematickým stylem na definice, tvrzení, případné důkazy, poznámky a neformální komentáře. Každá lekce má v závěru uvedeny bohaté odkazy na případné rozšiřující (samo)studium. Výukový text je dále proložen řadou vzorově řešených příkladů navazujících na vykládanou látku a doplněn dalšími otázkami a úlohami. (Otázky a úlohy označené hvězdičkou patří k obtížnějším a nepředpokládáme, že by na ně všichni studující dokázali správně odpovědět bez pomoci.) Každá lekce je zakončena zvláštním oddílem určeným k dodatečnému procvičení látky. Správné odpovědi k otázkám a úlohám jsou shrnuty na konci textu. Věříme, že příklady vám budou užitečným vodítkem při studiu a pro pochopení přednesené teorie. Mnoho zdaru. n O výuce Teorie grafů MA010 na FI MU Teorie grafů MA010 je jedním ze stěžejních teoretických magisterských předmětů na Fakultě informatiky MU, ale jeho výuka je bez problémů přístupná i bakalářským studentům se zájmem o obor. Paralelně k MA010 je na FI MU vyučován předmět Grafové algoritmy MA015. Autor pak dále přednáší několik navazujících výběrových předmětů pokročilé teorie grafů - MA051, MA052 a MA053. V rámci e-learningu Informačního systému (IS) MU je k předmětu vytvořena obsáhlá interaktivní osnova Teorie grafů (v anglickém jazyce), odpovídající struktuře výukového textu a s mnoha odkazy na přístupné webové zdroje k předmětu a procvičování. Osnova je veřejně přístupná na adrese http://is.muni.cz/el/1433/podzim2010/MA010/index.qwarp. O historii našeho učebního textu Původní výukový text vznikal v průběhu let 2003 až 2005 na základě autorových přednášek a cvičení předmětu Diskrétní matematika na FEI VSB - TUO. Tento text byl pak autorem upraven a druhotně (především v teoretické oblasti) výrazně rozšířen pro potřeby výuky magisterského předmětu MA010 Teorie grafů na FI MU Brno od roku 2006. Za přípravu některých příkladů a zvláště za pečlivou kontrolu celého textu patří díky také mnohým zúčastněným cvičícím - za FEI VSB-TUO Martinu Kotovi, Ondřeji Kohútovi, Michalu Kolovratovi a Pavlu Moravcovi a za FI MU Brno Janu Boudovi, Robertu Ganianovi, Janu Obdržálkovi a Pavlíně Vařekové. Vzhledem k tomu, že od roku 2009 je předmět MA010 na FI MU vyučován v angličtině, tento učební text poněkud ztrácí své výsadní postavení primárního studijního materiálu (kterým se stává výše odkázaná interaktivní osnova MA010 v IS MU), ale zůstává plnohodnotným českým studijním zdrojem pro tento předmět. A slovo závěrem. . . Přejeme vám mnoho úspěchů při studiu teorie grafů a budeme potěšeni, pokud se vám náš výukový text bude líbit. Jelikož nikdo nejsme neomylní, i v této publikaci zajisté jsou nejasnosti či chyby, a proto se za ně předem omlouváme. Pokud chyby objevíte, dejte nám prosím vědět e-mailem mailto:hlineny@fi.muni.cz. Autor m Obsah I Základní Pojmy Teorie Grafů 1 1 Pojem grafu 1 1.1 Definice grafu.................................. 1 1.2 Stupně vrcholů v grafu............................. 3 1.3 Podgrafy a Isomorfismus............................ 4 1.4 Orientované grafy a multigrafy........................ 7 1.5 Implementace grafů............................... 8 1.6 Cvičení: O základech grafů a isomorfismu.................. 9 2 Souvislost grafů 14 2.1 Spojení vrcholů, komponenty......................... 14 2.2 Prohledávání grafu............................... 16 2.3 Vyšší stupně souvislosti............................ 17 2.4 Jedním tahem: Eulerovské grafy ....................... 19 2.5 Cvičení: Procházení grafů, souvislost a isomorfismus............ 21 3 Vzdálenost a metrika v grafech 27 3.1 Vzdálenost v grafu............................... 27 3.2 Výpočet metriky................................ 29 3.3 Vážená (ohodnocená) vzdálenost....................... 30 3.4 Hledání nejkratší cesty............................. 31 3.5 Cvičení: Nejen o grafových vzdálenostech .................. 34 II Další Užitečné Oblasti a Problémy 39 4 Stromy a les 39 4.1 Základní vlastnosti stromů........................... 39 4.2 Kořenové stromy................................ 41 4.3 Isomorfismus stromů.............................. 44 4.4 Kostry grafů .................................. 47 4.5 Cvičení: Příklady o stromech a kostrách................... 48 5 Minimální kostry, Hladový algoritmus 51 5.1 Hledání minimální kostry ........................... 51 5.2 Hladový algoritmus v obecnosti........................ 53 5.3 Pojem matroidu ................................ 54 5.4 Kdy hladový algoritmus (ne)pracuje správně ................ 56 5.5 Cvičení: Příklady o stromech, kostrách a hladovém postupu........ 58 6 Toky v sítích 61 6.1 Definice sítě................................... 61 6.2 Hledání maximálního toku........................... 63 6.3 Zobecnění definice sítí............................. 66 6.4 Speciální aplikace sítí.............................. 67 6.5 Cvičení: Příklady toků v sítích ........................ 70 IV 7 Barevnost a další těžké problémy 73 7.1 Barevnost grafu................................. 73 7.2 Variace na barevnost a jiné.......................... 77 7.3 WP-ůplnost grafových problémů....................... 78 7.4 Příběh problému vrcholového pokrytí..................... 82 7.5 Cvičení: Příklady o barevnosti grafů..................... 83 7.6 Apendix: Další MV-úplné grafové problémy................. 84 8 Rovinnost a kreslení grafů 90 8.1 Rovinné kreslení grafu............................. 90 8.2 Eulerův vztah o počtu stěn.......................... 91 8.3 Rozpoznání rovinných grafů.......................... 93 8.4 Barvení map a rovinných grafů........................ 95 8.5 Praktické „pružinové" kreslení grafů..................... 96 8.6 Cvičení: Příklady na rovinnost grafů..................... 97 III Vybrané Pokročilé Partie 99 9 Krátké povídání o průnikových grafech 99 9.1 Průnikové a intervalové grafy.........................99 9.2 Chordální grafy.................................101 9.3 Třídy průnikových grafů............................102 9.4 Průnikové grafy křivek a úseček........................103 10 Dekompozice grafů, algoritmy a minory 106 10.1 Obtížné problémy na speciálních grafech...................106 10.2 Tree-width - čtyři definice...........................107 10.3 Některé další parametry............................109 10.4 Efektivní algoritmy na dekompozicích ....................111 10.5 Minory v grafech................................112 11 Něco více o kreslení grafů 114 11.1 Co jsou to plochy................................114 11.2 Kreslení grafů na plochy............................115 11.3 Překážky kreslení na plochy..........................116 11.4 O průsečíkovém čísle grafů...........................117 11.5 O problému rovinného pokrytí ........................119 IV 122 Klíč k řešení úloh 122 Literatura.......................................130 v Část I Základní Pojmy Teorie Grafů 1 Pojem grafu Úvod Třebaže grafy jsou jen jednou z mnoha struktur v diskrétní matematice, vydobyly si svou užitečností a názorností tak důležité místo na slunci, až se dá bez nadsázky říci, že teorie grafů je asi nejvýznamnější součástí soudobé diskrétní matematiky. Znalost teorie grafů se jeví nezbytná ve většině oblastí moderní informatiky, včetně těch aplikovaných. Proto se náš základní kurz teorie grafů bude ve velké míře zaměřovat právě na jejich informatické aplikace (ale vcelku bez nutnosti informatiku ovládat, tj. naše látka bude přístupná i ne-informatikům). Neformálně řečeno, graf se skládá z vrcholů (představme si je jako nakreslené puntíky) a z hran, které spojují dvojice vrcholů mezi sebou. (Pozor, nepleťme si graf s grafem funkce!) Takový graf může vyjadřovat souvislosti mezi objekty, návaznosti, spojení nebo toky, atd. Své důležité místo v informatice si grafy získaly dobře vyváženou kombinací svých vlastností -snadným názorným nakreslením a zároveň jednoduchou zpracovatelností na počítačích. Díky těmto vlastnostem se grafy prosadily jako vhodný matematický model pro popis různých, i komplikovaných, vztahů mezi objekty. Cíle Prvním cílem této lekce je formálně deßnovat, co je to graf a jaké jsou nejzákladnější grafové pojmy (třeba hrany a stupně). Také jsou zde uvedeny některé obvyklé typy grafů, jako cesty, kružnice, či úplné grafy. Především je však důležité, aby čtenář pochopil pojem isomorfismu grafů a dobře si jej procvičil v následujících cvičeních, od jednoduchých malých grafů (postupně) až po poměrně náročné „velké" příklady. 1.1 Definice grafu Hned na úvod přistoupíme k formální definici grafu. Bude se jednat o základní definici tzv. obyčejného grafu; přičemž možné rozšiřující definice zmíníme krátce v závěru, ale stejně se budeme převážně zabývat obyčejnými grafy. V základní definici popisujeme hrany mezi dvojicemi vrcholů pomocí dvouprvkových podmnožin těchto vrcholů. Definice 1.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů & E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů. Značení: Hranu mezi vrcholy u a v píšeme jako {u,v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední Na množinu vrcholů známého grafu G odkazujeme jako na V(G), na množinu hran E(G). 1 Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. Poznámka: Grafy se často zadávají přímo názorným obrázkem, jinak je lze také zadat výčtem vrcholů a výčtem hran. Například: F = {1,2,3,4}, E= {{1,2}, {1,3}, {1,4}, {3, 4}} Běžné typy grafů Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami: 4 3 Cr 7 ' ' ' n Cesta délky n má n + 1 vrcholů spojených za sebou n hranami: 1 4 ... n n+1 Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem (™) hran): 2 Kr Úplný bipartitní graf nam> lan>l vrcholech má m+n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m-n dvojice z různých skupin: m Kr n 2 Úlohy k řešení (1.1.1) Zapíšeme graf výčtem vrcholů {a, 5, c, d, e} a zkráceným výčtem hran {ac, ba, be, cd, de}. Nakreslete si jej! O jaký typ grafu se jedná? (1.1.2) Pro jakou hodnotu n je úplný graf Kn zároveň cestou? (1.1.3) Pro jakou hodnotu n je úplný graf Kn zároveň kružnicí? (1.1.4) Pro jaké hodnoty m, n > 0 je úplný bipartitní graf Km^n zároveň kružnicí? (1.1.5) Pro jaké hodnoty m,n > 0 úplný bipartitní graf Kmn neobsahuje žádnou kružnici? (1.1.6) Kolik hran musíte přidat do kružnice délky 6, aby vznikl úplný graf na 6 vrcholech? (1.1.7) Má více hran úplný graf Kg nebo úplný bipartitní graf Kqq? 1.2 Stupně vrcholů v grafu Máme-li graf, často nás zajímá, kolik z kterého vrcholu vychází hran-spojnic, neboli kolik má vrchol „sousedů". Proto je jedním z prvních definovaným pojmů stupeň vrcholu v grafu. Definice 1.2. Stupněm vrcholu v v grafu G rozumíme počet hran vycházejících z v. Stupeň v v grafu G značíme dc(v). Komentář: Slovo „vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana vychází z obou svých konců zároveň. Například v nakreslené ukázce jsou stupně přímo zapsány u vrcholů. Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d. Značení: Nejvyšší stupeň v grafu G značíme A(G) a nejnižší 5 {G). Věta 1.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát -jednou za každý její konec. Proto výsledek vyjde sudý. □ Vlastnosti stupňů Jelikož v obyčejném grafu zvlášť nerozlišujeme mezi jednotlivými vrcholy, nemáme dáno žádné pořadí, ve kterém bychom stupně vrcholů měli psát (pokud je nepíšeme přímo do obrázku grafu). Proto si stupně obvykle seřazujeme podle velikosti. Zajímavou otázkou je, které posloupnosti stupňů odpovídají vrcholům skutečných grafů? (Například posloupnost stupňů 1,2,3,4,5,6,7 nemůže nastat nikdy.) Věta 1.4. Nechť d\ < cfe < • • • < dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupňů d\, c?2, • • •, dn právě tehdy, když existuje graf s n — 1 vrcholy stupňů d\, d,2,---, dn-dn-ly dn-dn ~ 1; • • • > dn-2 ~ 1, dn-\ — 1. 3 Komentář: K použití Věty 1.4: Mírně nepřehledný formální zápis věty znamená, že ze seřazené posloupnosti odebereme poslední (největší) stupeň dn a od tolika dn bezprostředně předchozích stupňů odečteme jedničky. Zbylé stupně na začátku posloupnosti se nezmění. (Nezapomeňme, že posloupnost je třeba znovu seřadit dle velikosti.) Příklad 1.5. Existuje graf se stupni vrcholů: (1,1,1,2,3,4) ? Dle Věty 1.4 upravíme posloupnost na (1, 0, 0,1, 2), uspořádáme ji (0, 0,1,1, 2), pak znovu vše zopakujeme na (0,0, 0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? (Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2 spojený se dvěma z nich a další vrchol stupně 4 takto: (1,1,1,1,2,3,4,6,7) ? Podobně upravíme tuto posloupnost na (1,0,0,0,1,2,3,5) a uspořádáme ji (0,0,0,1,1,2,3,5), pak znovu upravíme na (0,0,-1,0,0,1,2), ale to už přece nelze -stupně v grafu nejsou záporné. Proto takový graf neexistuje. Úlohy k řešení (1.2.1) Kolik hran má graf se 17 vrcholy stupňů 4? (1.2.2) Existuje graf se stupni 4, 2, 3, 5, 3, 2, i? Nakreslete jej. (1.2.3) Existují dva „různé" grafy se 6 vrcholy stupňů 2? (1.2.4) Proč má každý (jednoduchý) graf aspoň dva vrcholy stejného stupně? 1.3 Podgrafy a Isomorfismus Podgraf je, jednoduše řečeno, část grafu. Avšak tato slova musíme definovat poněkud přesněji, abychom předešli situacím, kdy by nám zbyly „hrany bez vrcholů". Dále si definujeme tzv. indukovaný podgraf, který (na rozdíl od běžného podgrafu) z původního grafu přebírá všechny hrany mezi vybranými vrcholy. Definice: Podgraf em grafu G rozumíme libovolný graf H na podmnožině vrcholů V(H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V(H). Píšeme H C G, tj. stejně jako množinová inkluze (ale význam je trochu jiný). Komentář: Na následujícím obrázku vidíme zvýrazněné podmnožiny vrcholů hran. Proč se vlevo nejedná o podgraf? Vpravo už podgrafem je. Definice: Indukovaným podgrafem je podgraf H (Z G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H). „Různost" grafů Pozorný čtenář si možná již při čtení předchozího textu položil otázku: Co když vezmeme jeden graf (třeba kružnici délky 5) a nakreslíme jej jednou tak, podruhé zase jinak - je to stále tentýž graf nebo ne? Přísně formálně řečeno, každé nakreslení jistého grafu, třeba té kružnice C5, je jiným grafem, ale přitom bychom rádi řekli, že různá nakreslení téhož grafu jsou „stále stejná". Už jen proto, že grafy mají modelovat vztahy mezi dvojicemi objektů, ale tyto vztahy přece vůbec nezávisí na tom, jak si grafy nakreslíme. Pro tuto „stejnost" grafů se vžil pojem isomorfní grafy. Pro správné pochopení a využití teorie grafů je tedy třeba nejprve dobře chápat pojem isomorfismu grafů. Definice 1.6. Isomorfismus grafů G a H je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u, v € V(G) je spojená hranou v G právě tehdy, když je dvojice /(«), f (v) spojená hranou v H. Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píšeme G ~ H. Fakt: Isomorfní grafy mají stejný počet vrcholů (i hran). ik O ® Komentář: * ^ ^-»-^ ^-4—^ Z nakreslených tří grafů jsou první dva isomorfní - jsou to jen různá nakreslení téhož grafu, kružnice délky 5. (Určitě snadno najdete isomorfismus mezi nimi. Pro jednoduchost isomorfismus zakreslete do obrázku tak, že vrcholy prvního očíslujete čísly f až 5 a vrcholy druhého stejnými čísly v pořadí odpovídajícím jeho bijekci.) Třetí graf jim isomorfní není, neboť, například, má vrcholy jiných stupňů. Fakt: Pokud je bijekce / isomorfismem, musí zobrazovat na sebe vrcholy stejných stupňů, tj. do{v) = du{f{v))- Naopak to však nestačí! Příklad 1.7. Jsou následující dva grafy isomorfní? Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého. Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že nejlevější vrchol prvního grafu, označme jej f, se zobrazí na nejlevější vrchol ľ v druhém grafu (taky stupně tři), vrchol označený 5 1 se zobrazí na ľ. Očíslujme zbylé vrcholy prvního grafu 2,..., 6 v kladném smyslu, jak je ukázáno na následujícím obrázku. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu (pravý spodní). Pak je již jasně vidět, že další sousedé 2, 6 vrcholu f se zobrazí na analogické sousedy 2', 6' vrcholu ľ v druhém grafu, a stejně je to i se zbylými vrcholy 3, 5. Výsledný isomorfismus vypadá v odpovídajícím značení vrcholů takto: D Abychom mohli s isomorfismem grafů přirozeně pracovat, je potřeba vědět následující fakt: Věta 1.8. Relace „být isomorfní" ~ na třídě všech grafů je ekvivalencí. Důkaz. Relace ~ je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením. Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně obrátit. Tranzitivnost ~ se snadno dokáže skládáním zobrazení-isomorfismů. □ Důsledkem je, že všechny možné grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfismu, tj. nezáleží nám na konkrétní prezentaci grafu. Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice v G. • Speciálně říkáme trojúhelník kružnici délky 3. • Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G. • Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika v G. (Někdy se za kliku považuje pouze takový úplný podgraf, který je maximální vzhledem k inkluzi.) • Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G. • Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G. Komentář: První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4 taktéž. První graf obsahuje cestu délky 4 na vrcholech 1, 2, 3, 4, 5, ale ta není indukovaná. Indukovaná 6 cesta délky 4 v něm je třeba 2, 3, 4, 5, 6. Druhý graf tyto cesty také obsahuje, ale naopak žádná z nich není indukovaná. První graf má největší kliku velikosti 2 -jedinou hranu, kdežto druhý graf má větší kliku na vrcholech 3,4, 5. Největší nezávislá množina u obou grafů má 3 vrcholy 2, 4, 6. Příklad 1.9. Jsou následující dva grafy isomorfní? Postupovat budeme jako v Příkladě 1.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. D Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a zatím platí, že jediná vždy fungující cesta pro nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu vyzkoušejte všechny možnosti bijekcí mezi vrcholy těchto grafů. (Těch je, jak známo, až n!) V hierarchii výpočetní složitosti však problém isomorfismu leží docela nízko, jen „kousek nad" třídou polynomiálních problémů, takže je jistá naděje na nalezení univerzálního efektivního algoritmu. Úlohy k řešení (1.3.1) Je nějaká cesta indukovaným podgrafem kružnice? (1.3.2) Jaká je velikost největší nezávislé množiny v tomto grafu? (Tj. největší podmnožiny vrcholů, mezi kterými není žádná hrana.) Vyznačte tuto množinu. (1.3.3) Jaká je délka nejkratší kružnice obsažené v grafu z Úlohy 1.3.2? (1.3.4) Jaká je délka nejdelší cesty obsažené v grafu z Úlohy 1.3.2? * (1.3.5) Jaká je délka nejdelší indukované cesty obsažené v grafu z Úlohy 1.3.2? (1.3.6) Dokážete najít ke grafu z Úlohy 1.3.2 neisomorfní graf, který má stejnou posloupnost stupňů? Proč nejsou isomorfní? * (1.3.7) Kolik existuje jednoduchých neisomorfních grafů se všemi vrcholy stupně 2 na a) 5 vrcholech; b) 6 vrcholech; c) 9 vrcholech? 1.4 Orientované grafy a multigrafy V některých případech (například u toků v sítích) potřebujeme u každé hrany vyjádřit její směr. To vede na definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.) 7 Definice: Orientovaný graf je uspořádaná dvojice D = (V, E), kde E C V x V. Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické. Značení: Hrana (u,v) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v,u) je různá od (u,v)! Navíc někdy můžeme mluvit o tzv. multigrafech, ve kterých padají téměř všechna omezení na hrany... V multigrafu může mezi dvojicí vrcholů vést libovolný počet hran - tzv. násobné hrany, a některé z nich mohou být i orientované. Také jsou povoleny hrany, které mají oba konce totožné - tzv. smyčky. Definice: Multigraf je uspořádaná trojice M = (V, E,e), kde V D E = 0 a e : E —> (2) U V U (V x V) je incidenční zobrazení hran. Komentář: Značení (2) v definici reprezentuje neorientované hrany, V neorientované smyčky a V x V orientované hrany a smyčky. Smyčky a paralelní hrany (oproti běžné hraně) lehce ilustruje následující obrázek: Multigrafy zmiňujeme jen okrajově pro úplnost, nebudeme se jimi dále příliš zabývat. Úlohy k řešení (1.4.1) Zorientujte hrany úplného grafu Kj tak, aby z každého vrcholu vycházely nejvýše 3 šipky. (1.4.2) Proč v orientaci z úlohy 1.4.1 musí z každého vrcholu vycházet právě 3 šipky? 1.5 Implementace grafů Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly V(G) = {0,1,... , n — 1}. Pro počítačovou implementaci grafu G se nabízejí dva základní způsoby: • Maticí sousednosti, tj. dvourozměrným polem g[] [], ve kterém g [i] [j]=l znamená hranu mezi vrcholy i a j. • Výčtem sousedů, tj. použitím opět dvourozměrné pole h[] [] a navíc pole d[] stupňů vrcholů. Zde prvky h [i] [0] ,h[i] [1] , . . . ,h[i] [d[i]-l] udávají seznam sousedů vrcholu i. 8 Poznámka: Dávejte si pozor na symetrii hran v implementaci! To znamená, že pokud uložíte hranu g [i] [j]=l, tak musíte zároveň uložit i hranu g [j] [i]=l, jinak se dočkáte nepříjemných překvapení. Totéž se týká i seznamů sousedů. Komentář: Implementace maticí sousednosti je hezká svou jednoduchostí. Druhá možnost se však mnohem lépe hodí pro grafy s malým počtem hran, což nastává ve většině praktických aplikací. (Navíc je implementace výčtem sousedů vhodná i pro multigrafy.) Ke grafům lze do zvláštních polí přidat také ohodnocení vrcholů a hran libovolnými čísly či značkami... Rozšiřující studium Rozsáhlý matematický úvod do teorie grafů je zahrnut v [5, Kapitola 4] a navazují na něj i další části naší učebnice. Co se týče implementace grafů v programátorské praxi, najdete asi nejlepší zdroje na Internetu, třeba http://en.wikipedia.org/wiki/Graph_Cdata_structure) nebo http://www.mozart-oz.org/mogul/doc/smiele/graph/ a mnoho jiných stránek... Hezké, ale poněkud pokročilé pojednání o grafových algoritmech lze volně nalézt také v [4]. V našem textu se sice budeme dále zabývat mnoha zajímavými grafovými algoritmy, ale již je abstrahujeme od otázek praktické implementace. Co se týče praktického zjišťování iso-morßsmu grafů a dalších podobných grafových počítačových úloh, nejlépe je se podívat na http://es.anu.edu.au/~bdm/nauty/. Studenti MU si také mohou vyzkoušet množství „online" základních příkladů o grafech (na isomorfismus, stupně vrcholů, běžné vlastnosti grafů, atd.) ve formě odpovědníků v IS pod učebními materiály předmětu MA010 na FI MU od roku 2007. Někomu sice může připadat zbytečné trávit čas mechanickým řešením takových základních (a nudných?) příkladů, ale autor toto považuje za velmi přínosné zejména s ohledem na získání potřebného nadhledu nad grafy a „citu" pro řešení složitějších grafových úloh v budoucnu. 1.6 Cvičení: O základech grafů a isomorfismu Začneme se skutečně snadnou ukázkou. Příklad 1.10. Existuje graf s posloupností stupňů 1,1, 3, 3, 3, 4, 4, 4, 6, 6, 6, 7? Daná posloupnost je již setříděná, jinak bychom ji nejprve vzestupně setřídili. Podle Věty 1.4 budeme posloupnost upravovat, přičemž vždy v řádku vypíšeme setříděnou posloupnost před odečtením a po odečtení (nesetříděnou). 1,1,3,3,3,4,4,4,6,6,6,7 -»■ 1,1,3,3,2,3,3,3,5,5,5 1,1,2,3,3,3,3,3,5,5,5 -»■ 1,1,2,3,3,2,2,2,4,4 1,1,2,2,2,2,3,3,4,4 -+ 1,1,2,2,2,1,2,2,3 1,1,1,2,2,2,2,2,3 -+ 1,1,1,2,2,1,1,1 1,1,1,1,1,1,2,2 -+ 1,1,1,1,1,0,1 0,1,1,1,1,1,1 zřejmě tento graf existuje (3 samostatné hrany). K poslední posloupnosti snadno sestrojíme graf, proto i graf s původní posloupností stupňů existuje. Zpětným přidáváním vrcholů sestrojíme i původní graf: 9 D Velmi důležitou součástí učiva první lekce je zjišťování isomorfismu jednoduchých grafů. Jednoduché příklady tohoto typu se vyskytly už v předchozím a další jsou v následujících úlohách k řešení. Nyní si ukážeme jeden ze složitějších příkladů (a další obtížnější příklady na isomorfismus budou následovat po příští lekci, neboť se jedná o „běh na dlouhou trať"). Komentář: Procvičování s isomorfismy grafů není samoúčelná činnost, nýbrž pomáhá studujícím grafy a jejich vnitřní strukturu lépe „uchopit", také pomocí vhodně zvolených obrázků. Všímejte si v dalších příkladech, jak významnou roli v řešení hraje vhodné nakreslení zkoumaného grafu! Příklad 1.11. Najděte všechny isomorfní dvojice grafů v následujících obrázcích tří 10-vrcholových grafů. Isomorfní dvojice odpovídajícím způsobem očíslujte, u neisomorfních toto zdůvodněte. Postupujme systematicky: Všechny tři grafy mají po 10 vrcholech a všechny vrcholy stupňů 3. Takto jsme je tedy nijak nerozlíšili. Podívejme se třeba na trojúhelníky v nich - opět si nepomůžeme, neboť žádný z nich trojúhelníky neobsahuje. Co se tedy podívat na obsažené kružnice C4? Graf C jich jasně obsahuje pět, graf A po chvíli zkoumání také, ale v grafu B najdeme i při vší snaze jen tři kružnice délky 4. (Obdobného rozdílu si můžeme všimnout, pokud se zaměříme na kružnice C5, zkuste si to sami.) Takže co z dosavadního zkoumání plyne? Graf B nemůže být isomorfní žádnému z A, C. Nyní tedy zbývá najít (očekávaný) isomorfismus mezi grafy A a C. To se nám skutečně podaří poměrně snadno - stačí „prohozením" prostředních dvou vrcholů u grafu A získat lepší obrázek A / 1------- ---------1 \ } 1 ŕ—-----1 1------ --------1 1------—^ X --------1 1------- / c t—------1 1------ --------1 1-------—* a odpovídající bijekce je na pohled zřejmá. (Doplňte si ji společným očíslováním vrcholů obou grafů.) □ Příklad 1.12. Jaká je nejdelší kružnice a nejdelší indukovaná kružnice obsažená v následujícím grafu? Zdůvodněte. 10 Co se týče nejdelší kružnice, ta nemůže být z principu delší než počet všech vrcholů, tedy 10. Přitom kružnici délky 10 v zadaném grafu snadno najdeme. Co se týče indukované kružnice, ta musí s vybranými vrcholy podgrafu obsahovat i všechny hrany mezi nimi (a přesto to musí stále být jen kružnice). To zřejmě žádnou kružnicí délky 10 splněno není. Nenajdeme dokonce ani takové kružnice délky 9 a 8, nejdelší při troše snahy najdeme indukovanou kružnici délky 7, jako třeba na následujícím obrázku: Závěrem se zamysleme, proč vlastně delší indukovanou kružnici (než 7) nelze v našem grafu nalézt. Pokud bychom, pro spor, nalezli indukovanou kružnici délky 8, tak by musela použít jak ze spodního, tak z horního pětiúhelníku po čtyřech vrcholech. (Nemůže totiž být všech 5 vrcholů z jednoho pětiúhelníku, neboť to by uz byla kružnice délky jen 5.) Sami však snadným pokusem zjistíme, že v takové kružnici budou ještě hrany navíc, tudíž nebude indukovaná. □ Příklad 1.13. Kolik vzájemně neisomorfních jednoduchých grafů na 8 vrcholech existuje s posloupností stupňů 1,1,2,2,2,2,2,2? Nejprve si uvědomme, že graf musí obsahovat sudý počet vrcholů lichých stupňů, takže dva vrcholy stupně 1 musí být „u sebe", neboli musí být součástí jedné cesty. Mimo to jedinými grafy se všemi stupni 2 jsou soubory kružnic, takže naše požadované grafy se skládají z jedné cesty a žádné až několika kružnic. Použijeme-li k zápisu disjunktního sjednocení grafů symbol +, můžeme všechny možnosti systematicky vypsat: P\ + C3 + C3, P\ + Ce, P2 + C5, P3 + C4, P4 + C3, Pj. Existuje tedy právě 6 požadovaných grafů. □ Úlohy k řešení (1.6.1) Existuje graf s posloupností stupňů 1,1,1,3,3,3,4,4,4? (1.6.2) Existuje graf s posloupností stupňů 1,1,1,1,1,1,1,1, 6, 6? (1.6.3) Pro která přirozená x existuje graf s posloupností stupňů 4,4,4,8,9,10,10,10, 11,12,12,12,13, x? (1.6.4) Kolik existuje neisomorfních grafů s 6 vrcholy, všemi stupně 3? Nakreslete je. Návod: Podívejte se místo těchto grafů na jejich doplňky - dejte hrany právě tam, kde je původní graf nemá. Tím vzniknou grafy se všemi stupni 5 — 3 = 2. (1.6.5) Kolik hran má graf s touto posloupností stupňů? A: 1,1, 2, 2, 3, 3, 4,4,4, 4, 5, 6, 7 5:1,1,2,2,2,2,4,4,4,5,6,7 C: 1,1, 2, 2, 2, 3, 3,4,4, 4, 5, 6, 7 11 (1.6.6) Najděte a vyznačte isomorfismus mezi následujícími dvěma grafy na 7 vrcholech. (1.6.7) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: (1.6.8) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: (1.6.9) Najděte mezi následujícími grafy všechny isomorfní dvojice a zdůvodněte svou odpověď. (Isomorfní dvojice stejně očíslujte, u neisomorfních najděte odlišnosti.) A B C A A / ' \ , X , A A k . ./ Návod: Pokud vám třeba jedno očíslování pro isomorfismus nevyjde, musíte zkoušet další a další a probrat tak všechny možnosti. (1.6.10) Existují dva neisomorfní grafy s posloupnostmi stupňů J~í. tj .tj .tj .tj .tj .tj. B: 2,2,3,3, C: 2,3,3,3,3 ? U možnosti, kde dva neisomorfní grafy existují, je nakreslete. Pokud neexistují, pokuste se to správně zdůvodnit. (1.6.11) Jaká je nejdelší kružnice a nejdelší indukovaná kružnice obsažená v grafech A a B z Úlohy 1.6.9? "(1.6.12) Kolik podgrafů následujícího grafu je isomorfních kružnici Cg ? "(1.6.13) Kolik podgrafů úplného grafu K\q je isomorfních kružnici C4? "(1.6.14) Najděte ručně všechny neisomorfní grafy se stupni 3, 3, 3, 3, 2, 2, 2. 12 Návod: Uvědomte si, že vrcholy stupně 2 lze „zanedbat" - nahradit hranami. Ve výsledku pak zbudou 4 vrcholy stupňů 3, ale mezi nimi mohou být násobné hrany nebo i smyčky. Kreslete si obrázky. (1.6.15) Vraťte se zpět k příkladům a úlohám z Oddílu 1.3 a zkuste, zda je se znalostí nových metod jste schopni řešit lépe a elegantněji. (1.6.16) Kolik nejvíce vrcholů může obsahovat nezávislá množina v nakreslených grafech? Tuto největší nezávislou množinu si v grafech vyznačte. (1.6.17) Jakou největší kliku obsahují grafy z Úlohy 1.6.16? (1.6.18) Najděte mezi následujícími grafy všechny isomorfní dvojice a zdůvodněte svou odpověď. * (1.6.19) Kolik navzájem neisomorfních jednoduchých grafů lze získat z grafu A v úloze 1.6.18 přidáním jedné hrany? 13 2 Souvislost grafů Úvod Pokud máme graf, který modeluje nějaká spojení či sít, přirozeně nás zajímá, jakou máme možnost se dostat odněkud někam v tomto grafu. To má množství praktických motivací -například počítačové, dopravní, telefonní či potrubní sítě. Je pochopitelné, že v takových sítích chceme mít možnost se dostat z každého místa do každého jiného. Grafům s takovou vlastností říkáme souvislé. (Abychom si ujasnili terminologii, když mluvíme o souvislosti, nejedná se o žádné „hledání souvislostí grafů s něčím jiným", ale o možnost procházení mezi vrcholy jednoho grafu po jeho hranách.) Pro ukázku se podívejme na následující obrázky tří grafů: Poznáte, který z nich je nesouvislý? Všechny tři vypadají „spojeně", ale podívejte se důkladně na ten prostřední- v něm není žádné propojení mezi vrchním a spodním vrcholem po hranách (křížení se nepočítají). Další potřebnou dovedností je umět celý souvislý graf algoritmicky procházet. Zde si uvedeme obecnou kostru algoritmu pro procházení grafu a zmíníme některé konkrétní variace tohoto algoritmu. (Znáte nějaký algoritmus pro procházení bludiště? V grafech je to v obecnosti podobné.) Také se později zmíníme i o vyšších stupních souvislosti grafu - jako třeba zálohování spojení v sítích pro případy výpadku. Cíle Tato lekce definuje pojmy souvislosti a komponent grafu. Cílem je ukázat, jak se souvislostí grafu pracovat a jak algoritmicky graf procházet po jeho hranách. Zmíněny jsou i vyšší stupně souvislosti. 2.1 Spojení vrcholů, komponenty Nejprve bychom si měli přesně ujasnit, jak se pohybujeme grafem, tedy co je vlastně procházkou v grafu. Tento pojem by měl postihnout základní věc, že v grafu procházíme hranami vždy z vrcholu do sousedního vrcholu, a přitom ponechat dostatek volnosti pro vracení se a zacyklení procházek. Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran vo,ei,vi,e2,V2,...,en,vn, ve které vždy hrana e» má koncové vrcholy v i- \, v i. Komentář: Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). Lema 2.1. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy u ~ v právě když existuje v G sled začínající v u a končící ve v. Pak ~ je relací ekvivalence. Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou sledem délky 0. Symetrická je také, protože sled z u do v snadno obrátíme na sled z v do u. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. □ 14 Definice: Třídy ekvivalence výše popsané (Lema 2.1) relace ~ na V(G) se nazývají komponenty souvislosti grafu G. Jinak se taky komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence. Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů. Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Důkaz. Nechť u = vq, ei, V\,..., en, vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu wq = u, který už bude cestou: - Předpokládejme, že nový sled W už má počátek wq, ei, w\,..., Wi (na začátku i = 0, tj. jen wo bez hran), kde Wi = v j pro některé j € {0,1,... , n}. - Najdeme největší index k > j takový, že Vk = v j = Wi, a sled W pokračujeme krokem ..., w_i = Vj = vk, efc+i, wi+i = vk+i,.... - Zbývá dokázat, že nový vrchol Wí+\ = vu+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo Wi = Wj+i, l < i, pak bychom na vrchol Wí+\ „přeskočili" už dříve z vrcholu wi, spor. - Nakonec skončíme, když Wi = v. Komentář: Ačkoliv uvedený důkaz vypadá složitě, je to jen jeho formálním zápisem. Ve skutečnosti se v důkaze neděje nic jiného, než že se původní sled zkracuje o opakované vrcholy, až nakonec zákonitě vznikne cesta. Jeho výhodou je konstruktivnost - vidíme, jak cestu získat. Důkaz kratší, ale nekonstruktivní, pro Větu 2.2: Ze všech sledů mezi vrcholy u a v v G vybereme sled W s nejmenší délkou. Je snadno vidět, že pokud W zopakuje některý vrchol grafu G, můžeme W ještě zkrátit, a to je spor s předpokladem. Proto je W cestou vG. □ Závěrem se dostáváme k nejdůležitější definici souvislého grafu: Definice 2.3. Graf G je souvislý pokud je G tvořený nejvýše jednou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou (dle Věty 2.2). Poznámka: Prázdný graf je souvislý a má 0 komponent. Komentář: Podívejte se, kolik komponent souvislosti má tento graf: Vidíte obě dvě komponenty? Úlohy k řešení (2.1.1) Který z těchto dvou grafů je souvislý? 15 (2.1.2) Kolik komponent souvislosti má tento graf? 2.2 Prohledávání grafu Když se lidé dívají na grafy, obvykle je vnímají jako obrázky a jejich pohled je jakoby globální. Pokud je však graf zpracováván v počítači (a obzvláště pokud se jedná o skutečně velký graf), tento globální pohled nemáme k dispozici a graf musíme prohledávat lokálně. Z toho důvodu se potřebujeme seznámit, jako vůbec s prvním grafovým algoritmem, s obecným postupem lokálního prohledávání grafu. Tento algoritmus není složitý a víceméně zobecňuje dobře známý postup procházení všech cest v bludišti. Pro vytvoření co nejobecnějšího schématu algoritmu pro procházení grafu vystačíme s následujícími datovými stavy a pomocnou strukturou: • Vrchol: má stavy ... — iniciační - dostane na začátku, — nalezený - poté, co jsme jej přes některou hranu nalezli, — zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející. • Hrana: má stavy ... — iniciační - dostane na začátku, — zpracovaná - poté, co už byla probrána od jednoho ze svých vrcholů. • Úschovna: je pomocná datová struktura (množina), — udržuje nalezené a ještě nezpracované vrcholy. Poznámka: Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu. V prohledávaných vrcholech a hranách se pak provádějí konkrétní programové akce pro prohledání a zpracování našeho grafu. Algoritmus 2.4. Procházení souvislé komponenty grafu Algoritmus projde a zpracuje každou hranu a vrchol souvislého grafu G. Konkrétní programové akce potřebné ke zpracování grafu jsou uvedeny v pomocných funkcích ZPRACUJ(). vstup < graf G; stav (všechny vrcholy a hrany G ) = iniciační; úschovna U = {libovolný vrchol Vo grafu G}; stav(vo) = nalezený; // zpracování vybrané komponenty G while (U je neprázdná) { vybrat v € U; U = U\{v}; ZPRACUJ(v); foreach (e hrana vycházející z v) { if (stav(e) ==iniciační) ZPRACUJ (e); 16 w = opačný vrchol hrany e = vw; if (stav (w) ==iniciační) { stav(w) = nalezený; U = UU{w}; } stav(e) = zpracovaná; } stav (v) = zpracovaný; II případný přechod na další komponentu G } G zpracovaný; K průchodu nesouvislého grafu dochází po jednotlivých komponentách, po projití jedné komponenty algoritmem se libovolně přejde na vrchol další komponenty. Příklady aplikací schématu Algoritmu 2.4 jsou uvedeny dále například v Důsledku 3.4 a v Algoritmu 3.10. Konkrétní postup algoritmu procházení bude ilustrován ve Cvičení 2.4. Způsoby implementace procházení grafu • Procházení „do hloubky" - úschovna U je implementovaná jako zásobník, tj. dále prohledáváme od posledních nalezených vrcholů. • Procházení „do šířky" - úschovna U je implementovaná jako fronta, tj. dále prohledáváme od prvních nalezených vrcholů. • Dijkstrův algoritmus pro nejkratší cestu - z úschovny vybíráme vždy vrchol nejbližší k počátečnímu vq. (Toto je dost podobné prohledávání do šířky, ale obecnější i pro případy, kdy hrany nejsou „stejně dlouhé".) Tento algoritmus bude popsán v příští lekci. 2.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním „vyšších" stupňů souvislosti grafu. Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných nejvýše k — 1 hran z G zůstane výsledný graf souvislý. Definice: Graf G je vrcholově k-souvislý, k > 1, pokud i po odebrání libovolných nejvýše k — 1 vrcholů z G zůstane výsledný graf souvislý. Speciálně úplný graf Kn je vrcholově {n — l)-souvislý. Pokud mluvíme jen o fc-souvislém grafu, máme (obvykle) na mysli vrcholově fc-souvislý graf. Komentář: Stručně řečeno, vysoká hranová souvislost znamená vysoký stupeň odolnosti sítě proti výpadkům spojení-hran, neboli síť zůstane stále dosažitelná, i když libovolných k — \ spojení bude přerušeno. Vysoká vrcholová souvislost je mnohem silnějším pojmem, znamená 17 totiž, že síť zůstane dosažitelná i po výpadku libovolných k — 1 uzlů-vrcholů (samozřejmě mimo těch vypadlých uzlů). #■» Na ilustračním obrázku má první graf vrcholovou souvislost 4 a snadno vidíme, že po odebrání tří vrcholů či hran zůstává souvislý. Z druhého grafu bychom museli odebrat nejméně 3 hrany, aby se stal nesouvislým, a proto je jeho hranová souvislost 3. Na druhou stranu však stačí odebrat 2 vrcholy, aby mezi jeho levým a pravým krajním vrcholem žádné spojení nezůstalo. (Vidíte, které dva?) A jak je tomu u třetího grafu? Vrcholově 2-souvislé grafy mají následující jednoduchou konstruktivní chrakterizaci, která se vám může hodit například při dokazování vlastností 2-souvislých grafů. Věta 2.5. Libovolný obyčejný graf je 2-souvislý, právě když jej lze vytvořit z kružnice „přidáváním uší"; tj. iterací operace, kdy libovolné dva stávající vrcholy grafu jsou spojeny novou cestou libovolné délky (ale ne paralelní hranou). Komentář: Ilustrací tohoto hezkého tvrzení jsou třeba následující obrázky... (Dívejte se na postup přidávání uší zprava doleva.) Důkaz: V jednom směru snadno nahlédneme, že graf G vzniklý z kružnice přidáváním uší je 2-souvislý. V druhém směru zvolíme maximální 2-souvislý podgraf G' v G, který lze sestrojit z nějaké kružnice přidáváním uší. G' je neprázdný, neboť 2-souvislý G obsahuje aspoň kružnici. Pokud V(G') = V(G), pak lze jako uši přidávat všechny zbylé hrany G, tudíž z maximality plyne G' = G. Takže existuje vrchol x € V (G) \ V(G'). Pak lze dokázat, že z a; vedou dvě vnitřně disjunktní cesty do různých dvou vrcholů G', které tvoří další ucho přidané k G'. (Existence těchto dvou cest plyne třeba z Věty 2.6, ale elementární krátký argument zatím v této lekci nemáme.) Opět máme spor s maximalitou G', tudíž opět G' = G. □ Mengerova věta Důkaz následujícího důležitého výsledku by nebyl jednoduchý při použití stávajících znalostí, proto jej ponecháme na pozdější Lekci 6. Věta 2.6. Graf G je hranově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k hranově-disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k disjunktních cest (různých až na ty dva spojované vrcholy). Komentář: Věta nám vlastně říká, že stupeň souvislosti grafu se přirozeně rovná stupni redundance spojení vrcholů. Na výše uvedeném obrázku mezi každými dvěma vrcholy prvního grafu můžeme vést až 4 disjunktní cesty. U druhého grafu třeba mezi levým a pravým 18 koncern lze vést jen 2 (vrcholově) disjunktní cesty, ale mezi každými dvěma vrcholy lze vést 3 hranově-disjunktní cesty. V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky. Věta 2.7. Nechť G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici. Důkaz: Nechť e, / € E(G). Sestrojíme graf G' podrozdělením obou hran e, / novými vrcholy ve, Vf. Je zřejmé, že i G' je vrcholově 2-souvislý graf, takže podle Věty 2.6 existují v G' dvě disjunktní cesty spojující ve s Vf, tvořící spolu kružnici C Nakonec C" indukuje v G kružnici C procházející elf. □ Rozšířením předchozí úvahy lze dokonce dokázat: Věta 2.8. Nechť G je vrcholově k-souvislý graf, k > 1. Pak pro každé dvě disjunktní množiny Ui,U2 C V (G), \Ui\ = | C/21 = k v G existuje k po dvou disjunktních cest z vrcholů U\ do vrcholů U2- Úlohy k řešení (2.3.1) Jaký stupeň souvislosti má úplný bipartitní graf Knn? (2.3.2) Kolik nejméně vrcholů mimo x, y musíme vypustit z nakresleného grafu, aby v něm nezbyla žádná cesta mezi vrcholy x a y? Zdůvodněte. (2.3.3) Sestrojte graf Ks „přidáváním uší". (2.3.4) Kolik nejméně hran musíte přidat k cestě délky 7, aby vznikl vrcholově 2-souvislý graf? (2.3.5) Kolik nejvíce hran může mít nesouvislý graf na n vrcholech? * (2.3.6) Dokažte sami toto tvrzení: Každý 2-souvislý graf G na alespoň čtyřech vrcholech, který má všechny stupně ostře větší než 2, obsahuje hranu e takovou, že G — e je 2-souvislý. 2.4 Jedním tahem: Eulerovské grafy Snad nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera - jedná se o problém slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningradě. Tuto část 19 o kreslení grafů jedním tahem tak zařazujeme na závěr především z historických důvodů. KoKlHOr*! «tA O jaký problém se tehdy jednalo? Městští radní chtěli vědět, zda mohou suchou nohou přejít po každém ze sedmi vyznačených mostů právě jednou. Rozbor tohoto problému vede k následující definici a odpovědi. Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Otevřený tah je tahem, který končí v jiném vrcholu, než ve kterém začal. Nejstarší výsledek teorie grafů od Leonarda Eulera poté zní: Věta 2.9. Graf G lze nakreslit jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně. Důsledek 2.10. Graf G lze nakreslit jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně. Důkaz: Dokazujeme oba směry ekvivalence. Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. Naopak zvolíme mezi všemi uzavřenými tahy T v G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' = G—E(T), o kterém předpokládejme, že je neprázdný. Jelikož G' má taktéž všechny stupně sudé, je (z indukčního předpokladu) libovolná jeho hranově-neprázdná komponenta C C G' nakreslená jedním uzavřeným tahem Tq- - Vzhledem k souvislosti grafu G každá komponenta C C G' protíná náš tah T v některém vrchole w, a tudíž lze oba tahy Tc a T „propojit přes w". To je spor s naším předpokladem nejdelšího možného T. Důkaz důsledku: Nechť u,v jsou dva vrcholy grafu G mající lichý stupeň, neboli dva (předpokládané) konce otevřeného tahu pro G. Do G nyní přidáme nový vrchol w spojený hranami s u a v. Tím jsme náš případ převedli na předchozí případ grafu se všemi sudými stupni. □ 20 Úlohy k řešení (2.4.1) Lze tento graf nakreslit jedním otevřeným tahem? (2.4.2) Kolik hran musíte přidat ke grafu z předchozí otázky, aby se dal nakreslit jedním uzavřeným tahem? Rozšiřující studium Základní souvislosti grafů se blíže teoreticky věnují [5, Oddíly 4.2,8] a Eu-lerovským grafům [5, Oddíl 4.5]. Algoritmy pro procházení grafu jsou podrobně popsány (včetně netriviálních aplikací) v [3] a demonstrovány třeba v http://kam.mff.cuni.cz/~ludek/Algovision/Algovision.html. Za zmínku stojí i [4, Kapitola 3]. Pro hlubší teoretické poznatky a aplikace vyšší souvislosti grafů odkazujeme čtenáře na [1, Chapter 3]. Mnohá spíše implementačně zaměřená pojednání o grafových algoritmech lze v dnešní době snadno nalézt ve Wikipedii. Konkrétní odkazy lze získat třeba ze stránky http://en.wikipedia.org/wiki/Connected_component_(graph_theory). Pro čtenáře by mohly být užitečné třeba algoritmy pro nalezení silně souvislých komponent orientovaného grafu http://en.wikipedia.org/wiki/Strongly_connected_components nebo 2-souvislých komponent (bloků), které oba vycházejí z prohledávání do hloubky. Opětovně připomínáme, že studenti MU si také mohou vyzkoušet množství základních příkladů o grafech „online" ve formě odpovědníků v IS pod učebními materiály předmětu MA010 na FI MU. 2.5 Cvičení: Procházení grafů, souvislost a isomorfismus Příklad 2.11. Ukázka průchodu následujícím grafem do hloubky z vrcholu a. /*: 9 f; ------* e \ ~lf d / a *-- ■ Ví V této ukázce budeme obrázky znázorňovat stavy Algoritmu 2.4 v jednotlivých krocích takto: Neprohledane hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / *--------* e 9 *=,--------« j ^> d '' i — --* c ----• b 21 d g ^ c h d g c h Tímto zpracování zadaného grafu skončilo. Mimo jiné jsme zjistili, že graf má jedinou komponentu souvislosti. □ Příklad 2.12. Ukázka průchodu následujícím grafem do šířky z vrcholu a. /*: 9 *; -----i*, e "-AN \ \ '■* d h *- —_ { ,''\ Si--* c \ ~~~-ff-"\ / l a *-- \ -Vb V této ukázce budeme obrázky znázorňovat stavy Algoritmu 2.4 stejně jako v předchozím příkladě. 22 Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu příkladu? □ Příklad 2.13. Mějme graf H3, jehož vrcholy jsou všechny podmnožiny množiny {1, 2, 3} a hrany spojují právě disjunktní dvojice podmnožin. (Tj. H3 má 8 vrcholů.) Rozhodněte, zda je H3 souvislý graf, a napište, kolik má H3 hran. Vrchol 0 odpovídající prázdné množině je spojený se všemi sedmi ostatními vrcholy, takže graf je souvislý. Nakreslete si jej! Každý vrchol í-prvkové podmnožiny je pak spojený s 23_t disjunktními podmnožinami doplňku. Celkem tedy máme součtem všech stupňů |(7 + 3 • 22 + 3 • 21 + 2°) = 13 hran. D Příklad 2.14. Dokažte, že hrany každého 6-regulárního grafu lze zorientovat tak, aby z každého vrcholu vycházely právě 3 šipky. Myšlenka řešení je krátká, ale poměrně triková: Náš 6-regulární graf G je kreslitelný jedním uzavřeným tahem T podle Věty 2.9. Tento tah T si prostě zorientujeme - zvoleným směrem všechny jeho hrany. Jelikož T do každého vrcholu přichází třikrát a také odchází třikrát, dostaneme tři příchozí a tři odchozí šipky. □ Závěrem se ještě jednou vrátíme k pokročilé problematice isomorfismu z minulé lekce, která si zasluhuje důkladnější procvičení než by odpovídalo rozsahu jedné přednášky. Opět si všímejte, jak důležitou roli v úspěšném vyřešení příkladu hraje nakreslení „hezkého" obrázku. 23 Příklad 2.15. Dány jsou následující čtyři jednoduché grafy na 12 vrcholech každý. Vašim úkolem je mezi nimi najít všechny isomorfní dvojice a zdůvodnit svou odpověď. Zadané grafy si překreslíme například takto: Jak jsme přišli zrovna na tato nakreslení? To nelze jednoduše vysvětlit, prostě si musíme několikrát každý graf zkoušet kreslit a představovat, až najdeme ten pravý pohled. (Ověřte si sami očíslováním, že nové obrázky jsou isomorfní zadaným... Chce to jen trochu cviku s kreslením grafů.) Ihned tak vidíme, že B ~ D. Pozor, nelze však nyní jen tak říci, že obrázky A a C vypadají jinak a tudíž nejsou s B isomorfní! Musíme najít jednoznačné zdůvodnění rozdílu mezi grafy. Grafy A i C například oba obsahují 6 kružnic délky 4 (vyznačte je v obrázku), ale v A existují vrcholy náležející zároveň do tří kružnic délky 4 (opět vyznačte), kdežto v C každým vrcholem procházejí právě dvě kružnice délky 4. Proto A cf± C. Dále zdůvodníme v obrázku, že B ~ D obsahují celkem jen 4 kružnice délky 4, a tudíž A^éBaC^éBa stejně s D. Tím jsme hotovi, existuje právě jedna isomorfní dvojice B ~ D. □ Příklad 2.16. Kolik navzájem neisomorfních jednoduchých grafů lze získat z následujícího grafu vlevo přidáním jedné hrany? 24 7 6 Prvním krokem k řešení příkladu jako tento je nalézt „co nejlepší" obrázek našeho grafu. V tomto případě nalezneme isomorfní obrázek vpravo. (Jak, to lze jen těžko algoritmicky popsat, je k tomu potřeba zkušenost s grafy a fantazie...) Nyní vidíme, že všechny vrcholy našeho grafu jsou si navzájem symetrické, takže stačí uvažovat přidání hrany z jednoho z nich, třeba z 1. Nechť Gs je graf vzniklý přidáním hrany {1, 3}, G4 přidáním hrany {1, 4} a G5 přidáním hrany {1, 5}. Pak žádné dva z nich nejsou isomorfní, neboť G3 obsahuje 2 trojúhelníky, G5 obsahuje 1 trojúhelník a G4 nemá žádný trojúhelník. Naopak přidáním hrany {1,6} vznikne graf isomorfní G4, přidáním hrany {1,7} vznikne graf isomorfní G5 a přidáním hrany {1,9} vznikne graf isomorfní Gs- (Kterému z našich tří grafů jsou tyto nové grafy isomorfní snadno odhadneme opět podle počtu trojúhelníku v nich, isomorfismus pak už najdeme standardním přístupem.) Takže odpověď je 3 vzájemně neisomorfní grafy. □ Úlohy k řešení (2.5.1) Kolik nejvýše komponent může mít graf s 15 vrcholy, všemi stupně 2? (2.5.2) Kolik nejvýše komponent může mít graf s 30 vrcholy, všemi stupně 4? (2.5.3) Mějme graf H5, jehož vrcholy jsou všechny dvouprvkové podmnožiny množiny {1,2,3,4,5} a hrany spojují právě disjunktní dvojice podmnožin. (Tj. H5 má 10 vrcholů.) Rozhodněte, zda je H5 souvislý graf, a napište, kolik má H5 hran. (2.5.4) Kolik nejméně hran musí mít graf na 12 vrcholech, aby stupeň jeho souvislosti byl 3 (tj. aby se nestal nesouvislým odebráním dvou vrcholů) ? (2.5.5) Kolik nejvíce hran může mít graf na 10 vrcholech, a) který se skládá ze tří komponent souvislosti, b) jehož každá komponenta souvislosti má nejvíce tři vrcholy? Tento graf také nakreslete. (2.5.6) Existují dva neisomorfní jednoduché grafy se stejnou posloupností stupňů A: 2,2,2,3,3, H: 2737373737 C: 2,2,2,1,1 ? U možnosti, kde dva neisomorfní grafy existují, je nakreslete. U zbylé možnosti pak správně zdůvodněte, proč dva takové neisomorfní grafy neexistují. (2.5.7) Existují dva neisomorfní jednoduché grafy se stejnou posloupností stupňů A: 2,2,2,2,2, B: 1,1,3,3,3,3 ? * (2.5.8) Najděte mezi následujícími grafy všechny isomorfní dvojice a zdůvodněte svou odpověď. 25 * (2.5.9) Kolik navzájem neisomorfních jednoduchých grafů lze získat z grafu B v úloze 2.5.8 přidáním jedné hrany? * (2.5.10) Pokud vezmeme libovolný jednoduchý graf na 6 vrcholech, tak v něm najdeme trojúhelník nebo nezávislou množinu velikosti 3. Dokažte. (2.5.11) Hamiltonovská kružnice v grafu G je takový podgraf, který je isomorfní kružnici a obsahuje všechny vrcholy G. (Neboli je to kružnice procházející všemi vrcholy G právě jednou.) Najděte a nakreslete jednoduchý neorientovaný graf, který zároveň je vrcholově 3-souvisIý a přitom neobsahuje Hamiltonovskou kružnici. (2.5.12) Lze tento graf nakreslit jedním tahem? A uzavřeným? (Uprostřed není vrchol, jen se tam kříží hrany) (2.5.13) Dokažte, že každý ^-regulární graf obsahuje 2-regulárnípodgraf. *(2.5.14) Dokažte, že každý 4-regulární graf se dá rozložit na dva 2-regulární grafy. (Rozklad je opakem operace množinového sjednocení, tj. sjednocením jejich množin hran i množin vrcholů dostaneme původní graf) (2.5.15) Vezměme kostky klasického domina, kde na políčcích jsou všechny polo-uspořádané dvojice čísel od 0 do 6. Pokud ze všech kostek poskládáme „hada", dokažte, že pak první a poslední číslo jsou stejné. 26 3 Vzdálenost a metrika v grafech Úvod V minulé lekci jsme mluvili o souvislosti grafu, tj. o možnosti procházení z jednoho vrcholu do jiného. Někdy je prostá informace o souvislosti dostačující, ale většinou bychom rádi věděli i jak je to z jednoho vrcholu do druhého „daleko". Proto se nyní podíváme, jak krátká či dlouhá taková procházka mezi dvěma vrcholy grafu je. V jednodušším případě se při zjišťování grafové vzdálenosti díváme jen na minimální počet prošlých hran z vrcholu do vrcholu. Tak například v našem ilustračním obrázku je vzdálenost mezi a, b rovna 2, vzdálenost mezi a, c je rovna oo a vzdálenost mezi c, x je rovna 3. Navíc vidíme, že vrchol d má „ centrální" pozici v pravém grafu - každý další vrchol je od něj ve vzdálenosti nejvýše 2, kdežto vrchol c má „okrajovou" pozici. Z obecného pohledu při určování grafové vzdálenosti bereme do úvahy délky jednotlivých hran podél cesty (pro nás pouze nezáporné). Mimo potřebné definice si jako hlavní náplň lekce si uvedeme dva klasické algoritmy pro výpočty vzdáleností v grafu: Floyd-Warshallův a Dijkstrův. Dijkstrův algoritmus je, mimo jiné aplikace, třeba základem programů vyhledávajících vlaková/autobusová spojení a ve vylepšené podobě i dnes populárních GPS navigací. Dodáváme, že většina tvrzení a algoritmy obsažené v této přednášce jsou beze změny aplikovatelné i na orientované grafy (tj. když nás zajímá i směr procházení hran). Cíle Prvním cílem této lekce je deßnovat vzdálenost v grafech a probrat její základní vlastnosti. Dalším je ukázat a správně pochopit dva klasické postupy; Floyd-Warshallův a Dijkstrův algoritmus pro hledání nejkratších cest v grafu. 3.1 Vzdálenost v grafu Vzpomeňme si, že sledem délky n v grafu G rozumíme posloupnost vrcholů a hran vo,ei,vi,e2,V2, ■ ■ ■ ,en,vn, ve které hrana e» má koncové vrcholy Ví-i,Ví. Definice 3.1. Vzdálenost do{u,v) dvou vrcholů u, v v grafu G je dána délkou nejkratšího sledu mezi u a v v G. Pokud sled mezi u,v neexistuje, je vzdálenost do{u,v) = oo. Komentář: Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme projít, pokud se chceme dostat z u do v. Speciálně do(u,u) = 0. Uvědomme si, že nejkratší sled je vždy cestou (vrcholy se neopakují) - Věta 2.2. Grafová vzdálenost se chová dosti podobně běžné vzdálenosti, jak ji známe z geometrie, což bude vidět z následujících tvrzení. Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. do{u,v) = dc(v,u). Lenia 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: Vti,ti,ii)£ľ(G) : do{u,v) + do{v,w) >do{u,w). Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky dc(u,v) mezi u,v lze navázat sled délky do{v,w) mezi v,w, čímž vznikne sled délky do{u,v) + do{v,w) mezi u,w. Skutečná vzdálenost mezi u,w pak už může být jen menší. □ 27 Zjištění vzdálenosti Věta 3.3. Nechť u, v, w jsou vrcholy souvislého grafu G takové, že dc(u,v) < dc(u,w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w. Důkaz. Postupujeme indukcí podle vzdálenosti do{u,v): Pro do{u,v) = 0, tj. u = v je tvrzení jasné - vrchol u jako počátek prohledávání byl nalezen první. Proto nechť do{u,v) = d > 0 a označme v' souseda vrcholu v bližšího k u, tedy do{u,v') = d — 1. Obdobně uvažme libovolného souseda w' vrcholu w. Pak dc(u,«/) > dc(u, w) — 1 > dc(u, v) — 1 = dc(u, v'), a tudíž vrchol v' byl nalezen v prohledávání do šířky dříve než vrchol w' podle indukčního předpokladu. To znamená, že v' se dostal do fronty úschovny dříve než «/. Proto sousedé v' (mezi nima v) jsou při pokračujícím prohledávání také nalezeni dříve než sousedé w' (mezi nima w). □ Důsledek 3.4. Algoritmus procházení grafu do šířky lze použít pro výpočet grafové vzdálenosti z daného vrcholu u. Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu u přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu v přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého jsme jej právě nalezli. Podle Věty 3.3 se totiž nelze později dostat k v z vrcholu bližšího k počátku u. Komentář: Důsledek 3.4 funguje jen pro "vzdálenost" s jednotkovou délkou všech hran. My si dále ukážeme obecnější Dijkstrův algoritmus, který obdobným postupem počítá nejkratší vzdálenost při libovolně kladně ohodnocených délkách hran. Další pojmy a fakta Definice. Mějme graf G. Definujeme (vzhledem k G) následující pojmy a značení: - Excentricita vrcholu exc(v) je nejdelší vzdálenost z v do jiného vrcholu grafu; exc(v) = m?otxeV(G)dG(v,x). - Průměr diam(G) grafu G je největší excentricita jeho vrcholů, naopak poloměr rad(G) grafu G je nejmenší excentricita jeho vrcholů. - Centrem grafu je množina vrcholů U C V (G) takových, jejichž excentricita je rovna poloměru rad(G). - Steinerova vzdálenost mezi vrcholy libovolné podmnožiny W C V (G) je rovna minimálnímu počtu hran souvislého podgrafu v G obsahujícího všechny vrcholy W. Komentář: Prostudujte si výše uvedené pojmy na různých příkladech (obrázcích) grafů. Zamyslete se třeba nad příklady grafů, ve kterých tvoří centrum všechny jejich vrcholy. Promyslete si také, jak by se naše pojmy související se vzdáleností v grafech zobecnily na Steinerovu vzdálenost. Úlohy k řešení (3.1.1) Jaká je největší vzdálenost dvou různých vrcholů v úplném grafu? (3.1.2) Jaká je největší vzdálenost dvou různých vrcholů v úplném bipartitním grafu K^z^aa ? (3.1.3) Jaká je největší vzdálenost dvou různých vrcholů na kružnici C\\ ? (3.1.4) Jaká je největší Steinerova vzdálenost tří různých vrcholů na kružnici C\\? 28 (3.1.5) Jaká je Steinerova vzdálenost všech vrcholů souvislého grafu s n vrcholy? (3.1.6) Jaká je největší vzdálenost mezi dvěma vrcholy v následujícím grafu? # (3.1.7) Určete poloměr a centrum grafu z předchozího obrázku. (3.1.8) Umíte nalézt graf na 8 vrcholech se všemi stupni 3 a průměrem 2? *(3.1.9) Zjistěte vztah mezi průměrem a poloměrem grafu a dokažte jej. 3.2 Výpočet metriky Než se podíváme na samotný postup výpočtu obecné vzdálenosti Dijkstrovým Algoritmem 3.10, uvedeme si ještě „globální" pohled na soubor všech vzdáleností v grafu, tedy metriku grafu. Přínosem tohoto pohledu je především fakt, že pro výpočet celé metriky existuje velice jednoduchý tzv. dynamický Algoritmus 3.7 Floyda a Warshalla, jehož chytrá základní myšlenka je užitečná i v jiných oblastech a na jinak zadaných problémech. Definice: Metrikou grafu myslíme soubor vzdáleností mezi všemi dvojicemi vrcholů grafu. Jinak řečeno, metrikou grafu G je matice (dvourozměrné pole) d [, ], ve kterém prvek d [i, j] udává vzdálenost mezi vrcholy i a j. Metoda 3.5. Dynamický výpočet metriky skládáním cest • Na počátku nechť d[i,j] udává 1 (případně délku hrany {i,j}), nebo oo pokud hrana mezi i, j není. • Po každém kroku t > 0 nechť d [i, j] udává délku nejkratší cesty mezi i,j, která jde pouze přes vnitřní vrcholy z množiny {0,1, 2,... , t — 1}. • Při přechodu z í na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů - jsou vždy pouhé dvě možnosti: - Buď je cesta délky d [i, j] z předchozího kroku stále nejlepší (tj. nově povolený vrchol t nám nepomůže), — nebo cestu vylepšíme spojením přes nově povolený vrchol t, čímž získáme menší vzdálenost d[i,t]+d[t, j]. (Nakreslete si obrázek.) Věta 3.6. Metoda 3.5 v poli d[i, j] správně vypočte vzdálenost mezi vrcholy i,j. Důkaz povedeme matematickou indukcí podle t. Báze je snadná - v kroku t = 0 udává d [i, j] vzdálenost mezi i a j po cestách, které nemají vnitřní vrcholy (tj. pouze hranu). Přejdeme-li na krok t + 1, musíme určit nejkratší cestu P mezi i a j takovou, že P používá pouze vrcholy {0,1,2,... ,t — l,í}. Tuto nejkratší cestu P si hypoteticky představme: Pokud i ^ V{P), pakd[i, j] již udává správnou vzdálenost. Jinakí € V(P) a označíme P\ podcestu v P od počátku í do í a obdobně P2 podcestu od t do konce j. Podle indukčního předpokladu je pak délka P rovna d[i,t]+d[t, j]. V kroku t = n + 1 jsme hotovi. Poznámka: V praktické implementaci pro symbol 00 použijeme velkou konstantu, třeba MAX-INT/2. (Nelze použít přímo MAX_INT, neboť by pak došlo k aritmetickému přetečení.) 29 Algoritmus 3.7. Výpočet metriky grafu; Floy d-Warshall Tento algoritmus, pro vstupní graf G s N vrcholy zadaný svou maticí sousednosti, vypočte celou jeho metriku d[ ] podle postupu Metody 3.5. input: matice sousednosti G[] [] grafu na N vrcholech (číslovaných 0. . .N-lj, kde G [i, j ] =1 pro hranu mezi i, j a G [i, j ] =0 jinak; for (i=0; i IR. Kladně vážený grafG,w je takový, že 10(e) > 0 pro všechny hrany e. Definice: Mějme (kladně) vážený graf G,w. Délkou váženého sledu S = Vo,ei,V\,-e-2, V2, ■ ■ ■, en, vn v G myslíme součet ď£(S) = io(ei) + w(e2) + ■■■ + w(en). Váženou vzdáleností v G,w mezi dvěma vrcholy u, v pak myslíme da(u, v) = min{dg(S*) : S je sled s konci u, v} . Obdobně Oddílu 3.1 snadno dokážeme: Lema 3.9. Vážená vzdálenost v kladně vážených grafech také splňuje trojúhelníkovou nerovnost. Komentář: Podívejme se na následující ohodnocené grafy. (Čísla u hran udávají jejich váhy-délky.) Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi b, c. Co ale mezi a, cl Je jejich vzdálenost 6? Kdepak, vzdálenost a, b je 5, cesta vede po „horních" vrcholech. A jaká je v našem druhém grafu vzdálenost mezi x, y? Je to 3 nebo 1? Ne, ta vzdálenost je —oo (sled může zápornou hranu libovolně krát opakovat...). To je nakonec dobrý důvod, proč zaRazat záporné hrany. Úlohy k řešení (3.3.1) Jaká je nejdelší vzdálenost mezi dvěma vrcholy v předchozím obrázku vlevo? (3.3.2) O kterém vrcholu v předchozím obrázku vlevo se dá říci, že má „centrálnípozici", tj. že je z něj do všech ostatních vrcholů nejblíže? Jaká je z něj největší vzdálenost do ostatních vrcholů? (3.3.3) Zamyslete se, jak by bylo třeba deßnovat vzdálenost v grafu obsahujícím i záporné hrany, abychom neměli problém s „nekonečně malou" vzdáleností? 3.4 Hledání nejkratší cesty Pro nalezení nejkratší (vážené) cesty mezi dvěma vrcholy kladně váženého grafu se používá tradiční Dijkstruv algoritmus či jeho vhodná vylepšení. Takové algoritmy se například používají při vyhledávání vlakových spojení. Pravděpodobně se i vy někdy dostanete do situace, kdy budete nejkratší cestu hledat, proto si popsaný algoritmus včetně jeho vylepšení A* zapamatujte. Poznámka: Dijkstruv algoritmus je sice poněkud složitější než Algoritmus 3.7, ale na druhou stranu je výrazně rychlejší, pokud nás zajímá jen nejkratší vzdálenost z jednoho vrcholu místo všech dvojic vrcholů. Dijkstruv algoritmus • Je variantou procházení grafu (skoro jako do šířky), kdy pro každý nalezený vrchol ještě máme proměnnou udávající vzdálenost - délku nejkratšího sledu (od počátku), kterým jsme se do tohoto vrcholu zatím dostali. • Z úschovny nalezených vrcholů vždy vybíráme vrchol s nejmenší vzdáleností (mezi uschovanými vrcholy) - do takového vrcholu se už lépe dostat nemůžeme, protože všechny jiné cesty by byly dle výběru delší. • Na konci zpracování tyto proměnné vzdálenosti udávají správně nejkratší vzdálenosti z počátečního vrcholu do ostatních. Algoritmus 3.10. Dijkstruv pro nejkratší cestu v grafu Tento algoritmus nalezne nejkratší cestu mezi vrcholy u a v kladně váženého grafu G, daného seznamem sousedů vrcholů. input: graf na N vrcholech daný seznamem sousedů sous [] [] a del [] [], kde sous [i] [0] , . . . ,sous [i] [st [i]-l] jsou sousedé vrcholu i stupně st [i] 31 a hrana z i do sous [i] [k] má délku del [i] [k] >0; input: u, v, kde hledáme cestu z n do v; // stav [i] udává zpracovanost vrcholu, vzdal [i] zatím nalezenou vzdálenost for (i=0; i<=N; i++) { vzdal [i] = MAX_INT; stav [i] = 0; } vzdal [u] = 0; while (stav [v]==0) { for (i=0, j=N; i pv{x) —pv{y)- • Upravená délka libovolného sledu S z u do v pak je cÍq (S) = cÍq(S) +pv{v) —pv(u), což je konstantní rozdíl oproti původní délce S. Takže S je optimální pro původní délkové ohodnocení w, právě když je optimální pro nové «/. Komentář: Čtenář nechť si povšimne, že algoritmus A* každý graf implicitně zorientuje -upravené délkové ohodnocení totiž nebude symetrické w'(xy) ^ w'(yx). Pro (časté) použití při navigaci v mapě může potenciál pv(x) udávat přímou (Euklidovskou) vzdálenost z bodu x do bodu v. Tento potenciál je vždy přípustný podle trojúhelníkové nerovnosti. Dijkstrův algoritmus pro délkové ohodnocení w' takto upravené potenciálnem přímé vzdálenosti do v pak bude „silně preferovat" hrany vedoucí ve směru k cíli v; délka takových hran bude téměř nulová, kdežto délka hran vedoucích od cíle se téměř zdvojnásobí. Výsledkem bude výrazně menší počet prohledávaných vrcholů grafu (do nalezení cesty do cíle v) a také menší potřebná velikost úschovny vrcholů. Úlohy k řešení (3.4.1) Co konkrétně selže v Dijkstrově algoritmu při vstupu grafu se záporně ohodnocenou hranou? (3.4.2) Bude Dijkstrův algoritmus pracovat správně, pokud sice graf obsahuje hrany záporné délky, ale každý jeho cyklus má kladnou délku ? (3.4.3) Dokažte matematicky nezápornost w'(xy) v algoritmu A*, pokud pv(x) udává přímou vzdálenost z bodu x do v. (3.4.4) Jaký problém nastane, pokud v algoritmu A* bude hodnota pv(x) vyšší, než vzdálenost z vrcholu x do cíle v? (pv nebude dolním odhadem vzdálenosti do v) Rozšiřující studium Vzdálenostem v grafech se teoreticky věnuje [5, Oddíl 4.2]. Floyd-Warshallův algoritmus http://en.wikipedia.org/wiki/Floyd-Warshall_algorithmje dobře známou ukázkou paradigmatu dynamického programování a jeho modifikace mohou počítat nejen nejkratší cesty či tranzitivní uzávěry, ale třeba i odvozovat regulární výraz (viz klasická učebnice Hopcroft-UUman: Introduction to automata theory, languages, and computation, Addison-Wesley, 1979). Dijkstrův algoritmus je navíc velmi oblíbeným 33 tématem mnoha učebnic programování, a proto jej není třeba nijak složitě hledat, na Internetu například http://en.wikipedia.org/wiki/Dijkstra's_algorithm a dále http://en.wikipedia.org/wiki/A*_search_algorithm. Naše krátké pojednání se z časových důvodů vůbec nevěnuje problematice výpočtu nejkratších cest za přítomnosti negativních hran. Tento problém lze řešit třeba Bellman-Fordovým algoritmem, http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, podobným Dijkstrovu, ale pomalejším. Sofistikovanější kombinované řešení nabízí John-sonův algoritmus http://en.wikipedia.org/wiki/Johnson's_algorithm. Problematice výpočtu vzdálenosti za přítomnosti záporných hran se na MU do větší hloubky věnuje sesterský předmět MA015 Grafové algoritmy. 3.5 Cvičení: Nejen o grafových vzdálenostech Příklad 3.12. Ukázka běhu Dijkstrova Algoritmu 3.10 pro nalezení nejkratší cesty mezi vrcholy u, v v následujícím grafu. i v oo ^----------------^ / \ ^ / °°\ / / \ \ \ oo f oo < \ / - \ / 2 5 V ^/ \ / >^ \3 ' / ^^ \ / / 3\^^ / / \ / ^ ■> oo \ / A \ ■* OO \ / \ 2 \ / \ / 2 \0/ \/ V---------------V oo u i / U tohoto algoritmu se vlastně jedná a specifickou variantu procházení grafu. Proto použijeme stejné obrázkové značení jako v Příkladě 2.11 a navíc pro každý vrchol zakreslíme jeho okamžitou dočasnou vzdálenost vzdal [x]. (Tj. zpracované vrcholy budeme značit kroužkem a hrany plnou čarou.) Jednotlivé kroky následují: 34 Z průběhu algoritmu vidíme, že již ve třetím kroku jsme určili dočasnou vzdálenost z U do v na 7, ale to nebyla ta nejkratší. Nakonec po proběhnutí všech kroků algoritmu vzdálenost u,v poklesla až na optimálních 5. Nejkratší cesta je naznačená tlustými čarami. Pamatujte proto, že Dijkstruv algoritmus musíte provádět vždy tak dlouho, dokud se konečně nezpracuje cílový vrchol. □ 35 A nyní se v procvičení vrátíme (již naposled) ke starým známým příkladům o isomorfismu grafů, neboť teprve opakováni je matka moudrosti. Příklad 3.13. Dány jsou následující čtyři jednoduché grafy na 12 vrcholech každý. Vašim úkolem je mezi nimi najít všechny isomorfní dvojice a zdůvodnit svou odpověď. Zadané grafy si opět (po pár pokusech) pěkně názorně překreslíme, například takto (procvičte si sami vyznačení isomorfismu mezi obrázky nahoře a dole): Nyní je jasné, že B ~ D. Zároveň jsou naše nové obrázky natolik „průzračné", že v nich snadno můžeme spočítat počty kružnic délek 4: A, B i D jich obsahují 6, kdežto C je obsahuje jen 4 (vidíte proč?). Proto C není s žádným dalším isomorfní. Navíc A obsahuje vrchol incidental' se třema kružnicema délky 4 (vyznačený v obrázku vlevo), kdežto žádný takový vrchol v B ani D zřejmě neexistuje. Tudíž A^BaC^Ba stejně s D. Tím jsme hotovi, existuje právě jedna isomorfní dvojice B ~ D. □ Příklad 3.14. Vašim úkolem je zjistit, kolik vzájemně neisomorfních grafů může vzniknout z následujícího grafu vlevo přidáním jednoho nového vrcholu x a (jediné) hrany z x do některého původního vrcholu. Svou odpověď aspoň stručně zdůvodněte. 36 G F G F AB BA Nejprve si uvědomíme, že operace přidání nového vrcholu x má vlastně jen jediný účinek v našem příkladě - „označí" sousední vrchol toho x. Po překladu tedy je úkolem nalézt, kolik vzájemně nesymetrických vrcholů náš graf má. V mírně překresleném obrázku téhož grafu vpravo vidíme automorfismus, tj. isomorfismus grafu sama na sebe, „středovou symetrií". Z toho plynou symetrie mezi vrcholy A ~ G, B ~ F, C ~ J, D~I,E~H. Nyní je třeba zdůvodnit, proč další dvojice symetrických vrcholů nejsou, neboli proč například neexistuje automorfismus našeho grafu mapující A na B. To plyne třeba z faktu, že A sousedí s jedním trojúhelníkem grafu a B sousedí se dvěma. Navíc C, D, E přímo v trojíhelníku jsou, takže s A, B nemohou být symetrické. C není symetrické s D, neboť C leží ve 4-cyklu a D ne. Nakonec E není symetrické s C ani D, protože E je sousedem A, kdežto C, D jsou sousedé B ~ F, mezi kterými jsme již rozlišili. Takže odpověď je 5 vzájemně neisomorfních grafů. □ Úlohy k řešení (3.5.1) Jaká je největší vzdálenost mezi dvěma vrcholy v každém z následujících dvou grafů? Vyznačte tyto dva nejvzdálenější vrcholy. (3.5.2) Jaká je největší vzdálenost mezi dvěma vrcholy v každém z následujících dvou grafů? Vyznačte tyto dva nejvzdálenější vrcholy. (3.5.3) Kolik (neuspořádaných) dvojic vrcholů v následujícím grafu má vzdálenost právě 3 ? 37 (3.5.4) Kolik nejméně hran musíme přidat do následujícího grafu, aby největší vzdálenost mezi dvěma vrcholy byla 2? Zdůvodněte. (3.5.5) Jaká je největší vzdálenost mezi dvojicí vrcholů v tomto váženém grafu? 2 2 1 4 rl-----ÍT3 (3.5.6) Kolik nejvíce vrcholů může mít graf, který má všechny vrcholy stupně 3 a největší vzdálenost mezi dvěma vrcholy je 2 ? * (3.5.7) Jaká největší vzdálenost může být mezi dvěma vrcholy kružnice délky 9, jejíž hrany jsou ohodnoceny vzdálenostmi 1,2, ...,8,9 v nějakém (libovolném) pořadí? A jakou největší vzdálenost můžeme garantovat pro libovolné pořadí ohodnocení na kružnici? (3.5.8) Představme si graf, jehož vrcholy jsou všechna přirozená čísla od 2 do 15 a hrany spojují právě ty dvojice vrcholů, které jsou soudělné jako čísla. Přitom délka hrany je vždy rovna největšímu společném děliteli. (Například 4, 5 nejsou spojené a 8,12 jsou spojené hranou délky 4.) Pomineme-li izolované vrcholy 11 a 13, jaká je největší vzdálenost mezi zbylými vrcholy tohoto grafu ? * (3.5.9) Proč každý ^-regulární graf s 24 vrcholy obsahuje dvojici vrcholů ve vzdálenosti 4? (3.5.10) Nakreslete libovolný ^-regulární graf na 12 vrcholech se dvěma ve vzdálenosti 6. *(3.5.11) Pokud ^-regulární graf na 12 vrcholech obsahuje dva ve vzdálenosti 5, musí potom obsahovat i trojúhelník? Dokažte svou odpověď. (3.5.12) Lze přidat dvě hrany ke kružnici délky 10 tak, aby výsledný graf měl maximální vzdálenost 3 ? * (3.5.13) Kolika neisomorfními způsoby lze přidat dvě hrany ke kružnici délky 12 tak, aby výsledný graf měl maximální vzdálenost 4 ? 38 Cast II Další Užitečné Oblasti a Problémy 4 Stromy a les Úvod Jedním ze základních, a patrně nejjednodušším, typem grafů jsou takzvané stromy. Jedná se o souvislé grafy bez kružnic. Přes svou (zdánlivou) jednoduchost mají stromy bohatou strukturu a především množství vlastních aplikací. Patrně nejstarší motivací pojmu stromu jsou rodokmeny, jejichž původ sahá daleko před vznik teorie grafů. Proto také mnoho pojmů týkajících se stromů je motivováno rodokmeny. Co vidíme na následujících dvou obrázcích? O důležitosti souvislosti grafu jsme pojednali dříve. Se stromy jako se souvislými (pod)grafy bez kružnic se pak setkáváme nejvíce v situacích, kde absence kružnic vyplývá z podstaty věci, nebo kde jsou kružnice zcela nežádoucí. To jsou různá schémata, datové struktury či již zmíněné rodokmeny. Stromy například přirozeně popisují různé hierarchické struktury. Mimo popisy struktur je ještě jedna důležitá oblast aplikací stromů, týkající se tzv. koster a problému hledání minimální kostry v grafu. Cíle Úkolem této lekce je hlavně deßnovat pojem stromu a ukázat základní vlastnosti stromů včetně jejich zdůvodnění. Podrobněji jsou probrány kořenové a uspořádané stromy a práce s nimi. Dále je zaveden pojem koster grafu a jejich zajímavé vlastnosti. 4.1 Základní vlastnosti stromů Začneme definicemi lesa a stromů. Jelikož i smyčky a násobné hrany v multigrafech jsou považovány za kružnice délek 1 a 2, v lesech a stromech se nenacházejí. Bavíme se zde tudíž pouze o jednoduchých grafech. Definice: Les je jednoduchý graf bez kružnic. Definice 4.1. Strom je jednoduchý souvislý graf T bez kružnic. Fakt. Komponenty souvislosti lesa jsou stromy. Jeden vrchol (bez hran) je také strom. Dále si ukážeme přehled základních vlastností stromů, včetně jejich zdůvodnění, která jsou poměrně jednoduchá. Následující vlastnosti dokonce plně popisují stromy a mohou tudíž být použity místo uvedené Definice 4.1. Jedná se sice o dosti formální teoretický oddíl, ale alespoň zběžné porozumění uvedeným vlastnostem je potřebné pro další práci se stromy a s jinými strukturami založenými na stromech. Lenia 4.2. Strom s více než jedním vrcholem obsahuje vrchol stupně 1. 39 Důkaz: Souvislý graf s více než jedním vrcholem nemůže mít vrchol stupně 0. Proto vezmeme strom Tav něm libovolný vrchol v. Sestrojíme nyní co nejdelší sled S v T začínající ve v: S začne libovolnou hranou vycházející z v. Y každém dalším vrchole u, do kterého se dostaneme a má stupeň větší než 1, lze pak pokračovat sled S další novou hranou. Uvědomme si, že pokud by se ve sledu S poprvé zopakoval některý vrchol, získali bychom kružnici, což ve stromě nelze. Proto sled S musí jednou skončit v nějakém vrcholu stupně 1 v T. □ Komentář: Zamyslete se, proč v každém stromě s více než jedním vrcholem jsou alespoň dva vrcholy stupně 1 (odpověď je skrytá už v předchozím důkaze). Zároveň si odpovězte, jestli lze tvrdit, že každý strom s více než jedním vrcholem obsahuje tři vrcholy stupně 1. Věta 4.3. Strom na n vrcholech má přesně n — \ hran pro n > 1. Důkaz: Toto tvrzení dokážeme indukcí podle n. Strom s jedním vrcholem má n—1 = 0 hran. Nechť T je strom na n > 1 vrcholech. Podle Lematu 4.2 má T vrchol v stupně 1. Označme T' = T — v graf vzniklý z T odebráním vrcholu v. Pak T" je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T' má n — 1 — 1 hran, a proto T má n — 1 — 1 + 1 = n — 1 hran. □ Věta 4.4. Mezi každými dvěma vrcholy stromu vede právě jediná cesta. Důkaz: Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u, v vede nějaká cesta. Pokud by existovaly dvě různé cesty Pi,P2 mezi u,v, tak bychom vzali jejich symetrický rozdíl, podgraf H = P1AP2 s neprázdnou množinou hran, kde H zřejmě má všechny stupně sudé. Na druhou stranu se však podgraf stromu musí opět skládat z komponent stromů, a tudíž obsahovat vrchol stupně 1 podle Lematu 4.2, spor. Proto cesta mezi u a v existuje jen jedna. □ Důsledek 4.5. Přidáním jedné nové hrany do stromu vznikne právě jedna kružnice. Důkaz: Nechť mezi vrcholy u, v ve stromu T není hrana. Přidáním hrany e = uv vznikne právě jedna kružnice z e a jediné cesty mezi u,v v T podle Věty 4.4. □ Věta 4.6. Strom je minimální souvislý graf (na daných vrcholech). Důkaz: Strom je souvislý podle definice. Pokud by ale vypuštěním hrany e = uv ze stromu T vznikl opět souvislý graf, pak by mezi u, v v T existovaly dvě cesty (dohromady kružnice) - hrana e a jiná cesta v T — e. To je ve sporu s Větou 4.4. Naopak, pokud by souvislý graf měl kružnici, zůstal by souvislý i po vypuštění některé hrany té kružnice. Proto každý minimální souvislý graf (na daných vrcholech) je stromem. Tudíž strom je právě minimálním souvislým grafem na daných vrcholech. □ Závěrem si pro správné pochopení základních vlastností stromů vyřešíme následující (ne zcela jednoduchý) příklad. Příklad 4.7. Kolik nejvýše kružnic vznikne v grafu, který vytvoříme ze stromu přidáním dvou hran? Přidáním jedné hrany do stromu T vznikne jedna kružnice dle Důsledku 4.5. Druhá hrana vytvoří nejméně ještě jednu kružnici ze stejných důvodů, ale může vytvořit i dvě další kružnice, jako třeba v následujícím grafu, kde strom T je vyznačen plnými čarami a dvě přidané hrany čárkovaně. 40 Každá z přidaných dvou hran vytvoří vlastní trojúhelník a navíc ještě vznikne kružnice délky 4 procházející oběma z přidaných hran. Na druhou stranu chceme ukázat, že více než 3 kružnice vzniknout nemohou po přidání dvou hran e, / do stromu T: Podle Důsledku 4.5 vznikne jen jedna kružnice procházející hranou e a neobsahující /, stejně tak jedna kružnice procházející / a neobsahující e. Nakonec stačí nahlédnout, že je nejvýše jedna možná kružnice procházející oběma hranami e, /: Pokud by takové byly dvě různé C\, G 0. Pokud jejich kódy vyjdou shodné, jsou isomorfní. Naopak pro isomorfní T',r a U',s existuje bijekce mezi vzájemně isomorfními podstromy jejich kořenů, tudíž podle indukčního předpokladu kódy těchto podstromů jsou po dvojicích shodné. Jelikož se v obou případech setřídí kódy podstromů stejně, vyjde minimalni_kod(T', r) = minimalni_kod(U/, s). □ Úlohy k řešení (4.3.1) Odvoďte správný závorkový kód pro tento pěstovaný strom: (4.3.2) Nakreslete pěstovaný strom odpovídající závorkovému kódu (((()())())((())(())))• 46 4.4 Kostry grafů Kromě stromů samotných se zabýváme i stromy, které jsou obsaženy jako podgrafy ve větších grafech. Definice 4.14. Kostrou souvislého grafu G je podgraf v G, který je sám stromem a obsahuje všechny vrcholy grafu G. Komentář: Kostrou stromu je strom sám. Na druhou stranu kostrou kružnice Cn je každá z n cest vzniklých z Cn vypuštěním jedné hrany. Složitější grafy mají pak ještě více možných koster. Poznámka: Pojem kostry lze definovat i pro nesouvislé grafy, pak se kostrou myslí les, jehož stromy jsou kostrami jednotlivých komponent. Příklad 4.15. Kolik různých koster má tento graf? n r\ Podívejme se na kostru grafu takto - jaké hrany z grafu vymažeme, aby zbyl strom? Zajisté musíme vymazat některou hranu z první kružnice (5 možností) a některou hranu z druhé kružnice (6 možností). Na druhou stranu to v tomto jednoduchém příkladě už stačí, vždy pak zbude strom. Výběr vymazané hrany z první kružnice je nezávislý na druhé kružnici (jsou disjunktní), a proto dle principu nezávislých výběrů máme 5 • 6 = 30 možností vybrat dvě hrany k vymazání. Celkem tedy vyjde 30 koster. D Následující výsledek patří ke „krásným drahokamům" teorie grafů. Věta 4.16. (Cayley) Úplný graf Kn pro n > 0 má přesně nn~2 koster. Komentář: Pro tento výsledek existuje několik různých velmi pěkných důkazů, které si zájemci mohou najít v literatuře [5]. My si dále uvedeme ještě jeden zcela obecný (a z pohledu výpočetní složitosti docela překvapivý) výsledek. Definice. Laplaceova matice Q = ( '0' a '((())()())'• P° seřazení a spojení nám celkový minimální kód levého stromu vyjde '(((()())())((())()())())'• Obdobně budeme postupovat při rekurzivním určování minimálního kódu pravého stromu. Zde nám podkódy jednotlivých tří podstromů kořene x vyjdou '()', '((())())' a '((()())()())'• P° seřazení a spojení nám celkový minimální kód pravého stromu vyjde '(((()())()()) ((())()) 0 )'• Napíšeme si tedy získané dva kódy pod sebe a uvidíme, kde se liší sí (((()())()) ((())()())()) (((()())()())((())())()) . Dané dva stromy tudíž nejsou isomorfní. D 48 Příklad 4.19. Kolik různých koster má tento graf? Jak vidíme, opět musíme vymazat dvě hrany z grafu, aby zbyla kostra. Nelze však vypouštět jednu hranu z levé kružnice a jednu z pravé, neboť by výběry nebyly nezávislé - hrana x je oběma sdílená. Podíváme se tedy na řešení jako na součet disjunktních možností; počtu koster obsahujících x a počtu koster bez hrany x. Pokud hranu x vymažeme, zbude kružnice délky 11 a ta má 11 koster. Pokud naopak hranu x zachováme, musíme z "levého oblouku" kružnice od x vymazat jednu ze 6 hran a z "pravého oblouku" jednu z 5 hran. Tyto výběry již jsou nezávislé a počet možností je 6 • 5 = 30. Celkem má náš graf 11 + 30 = 41 koster. □ Úlohy k řešení (4.5.1) Kolik hran je třeba vypustit z následujícího grafu na 9 vrcholech, aby zbyla jeho kostra? (4.5.2) Kolik vrcholů má strom s 2004 hranami? Je to jednoznačné? (4.5.3) Les má 2009 vrcholů a celkem 4 souvislé komponenty. Kolik má hran? (4.5.4) Kolik komponent souvislosti má les s 2004 vrcholy a 1993 hranami? (4.5.5) Mějme čísla {10,11,13,14,15,21} a spojme dvojice z nich hranami, pokud jsou soudělná. Je výsledný graf stromem? A aspoň lesem? (4.5.6) Které z následujících výrazů jsou správnými závorkovými kódy pro nakreslené uspořádané kořenové stromy? A: (((()()())())((())())) B: (((()()()())())(()())) C: (((()()())())(()(()))) (4.5.7) Kolik koster může mít graf, který vznikne ze stromu na 8 vrcholech přidáním libovolné nové hrany (mezi dvěma nespojenými vrcholy)? Uvědomte si, že pro různé stromy a hrany mohou vyjít různé výsledky, a vašim úkolem je najít všechny možné počty, včetně příslušných obrázků. "(4.5.8) Kolik různých koster mají grafy na následujícím obrázku? 49 (4.5.9) Kolik hran je třeba vypustit z úplného grafu na n vrcholech, aby vznikla jeho kostra? * (4.5.10) Kolik nejméně vrcholů musí mít graf (bez násobných hran), ve kterém lze nalézt dvě kostry nesdílející žádnou hranu? Zdůvodněte. * (4.5.11) Dokážete nalézt souvislý graf s přesně 2003 kostrami bez kružnice C2003 jako pod- grafem? Abyste si ušetřili čas, 2003 je prvočíslo. (4.5.12) Ověřte řešení Příkladu 4.19 podle Věty 4.17. 50 5 Minimální kostry, Hladový algoritmus Úvod Kromě teoretických "hrátek" mají kostry grafů (Oddíl 4.4) následující důležité praktické použití: Dříve jsme uvažovali spojení v grafech cestami jdoucími z jednoho místa do druhého, ale nyní se podíváme na jiný způsob "propojování" všech vrcholů grafu najednou. Vezměme si třeba požadavky propojení domů elektrickým rozvodem, propojení škol internetem, atd. Zde nás ani tak nezajímají délky jednotlivých cest mezi propojenými body, ale hlavně celková délka či cena vedení/spojení, které musíme postavit. Našim cílem je tedy najít minimální souvislý podgraf daného grafu, tedy minimální způsob propojení (v daných podmínkách), ve kterém existují cesty mezi každou dvojicí vrcholů. Podle Věty 4.6 je tímto minimálním propojením strom - kostra našeho grafu. Vstupní graf nám přitom udává všechny možné realizovatelné propojky s jejich cenami. Jak uvidíme, úloha se dá velmi dobře řešit tím asi nejjednodušším způsobem, tzv. hladovým postupem -bereme vždy to nejlepší, co se zrovna nabízí... Cíle V lekci probereme významný problém minimální kostry grafu, včetně jednoduchého "hladového" algoritmu pro jeho řešení. Obecně je postup tzv. hladové optimalizace demonstrován na řešení několika jiných kombinatorických problémů, a v jeho souvislosti je také zmíněn pojem matroidu. 5.1 Hledání minimální kostry Problém 5.1. Problém minimální kostry (MST) Je dán (souvislý) vážený grafG,w s nezáporným ohodnocením hran w. Otázkou je najít kostru T v G, která má nejmenší možné celkové ohodnocení. Formálně MST = mm kostra TcG \e€E(T) 10(e) Komentář: Kostra daného grafu je minimální podgraf, který zachovává souvislost každé komponenty původního grafu. Proto nám vlastně ukazuje "minimální propojení" daných vrcholů, ve kterém ještě existují cesty mezi všemi dvojicemi, které byly propojeny i původně. Praktickou formulací problému je třeba propojení domů elektrickým rozvodem, škol internetem, atd. Jedná se tady o zadání, ve kterých nás zajímá především celková délka či cena propojení, které je třeba vytvořit. Příklad je uveden na následujícím obrázku i s vyznačenou minimální kostrou vpravo. 3 4 3 \ 3 . 2 l/ 1 1 l\ 1----------------------^ Á Algoritmus 5.2. „Hladový" pro minimální kostru. Je dán souvislý vážený grafG,w s nezáporným ohodnocením hran w. - Seřadíme hrany grafu G vzestupně podle jejich ohodnocení, tj. w(ei) < w(e2) < ■■ < w(em). - Začneme s prázdnou množinou hran T = 0 pro kostru. 51 - Pro i = 1,2,..., m vezmeme hranu e» a pokud T U {e»} nevytváří kružnici, přidáme e» do T. Jinak e» "zahodíme". - Na konci množina T obsahuje hrany minimálni kostry váženého grafu G,w. Komentář: Podrobnou ukázku průběhu hladového algoritmu čtenář najde v Příkladě 5.15. Důkaz správnosti Algoritmu 5.2: Nechť T je množina hran získaná v Algoritmu 5.2 a nechť hrany jsou již seřazené w(e\) < w(e2) < ••• < w(em). Vezměme množinu hran To té minimálni kostry (může jich být více se stejnou hodnotou), která se s T shoduje na co nejvíce prvních hranách. Pokud To = T, algoritmus pracoval správně. Předpokládejme tedy, že To / T, a ukážeme spor, tj. že toto nemůže ve skutečnosti nastat. Označme j > 0 takový index, že se množiny To a T shodují na prvních j — 1 hranách ei,..., e.,_i, ale neshodují se na e,-. To znamená, že e,- € T, ale e,- ^ To. (Jistě nemůže nastat e,- ^ T, ale e,- € To.) Podle Důsledku 4.5 obsahuje graf na hranách To U {ej} právě jednu kružnici C. Kružnice C však nemůže být obsažena v nalezené kostře T, a proto existuje hrana e^ v C, která e^ ^ T a zároveň A; > j. Potom však je w(ek) > w(ej) podle našeho seřazení hran, a tudíž kostra na hranách (To \ {e^}) U {ej} (vzniklá nahrazením hrany e^ hranou e,-) není horší než To a měli jsme ji v naší úvaze zvolit místo To. To je hledaný spor. □ Komentář: Správný pohled na předchozí důkaz by měl být následovný: Předpokládali jsme, že nalezená kostra T se s některou optimální kostrou shoduje aspoň na prvních j — 1 hranách. Poté jsme ukázali, že některou další hranu e^ v (předpokládané) optimální kostře lze zaměnit hranou ej, a tudíž dosáhnout shodu aspoň na prvních j hranách. Dalšími iteracemi záměn ukážeme úplnou shodu naší nalezené kostry T s některou optimální kostrou. V našem důkaze jsme se vlastně zaměřili na fakt, že ta poslední iterace záměn nemůže selhat. Nakreslete si tento důkaz obrázkem! Základní hladový algoritmus pro hledání minimální kostry grafu byl poprvé explicitně popsán Kruskalem, ale už dříve byly objeveny jeho podobné varianty, které zde jen stručně zmíníme. Algoritmus 5.3. Jarníkův pro minimální kostru. Hrany na začátku neseřazujeme, ale začneme kostru vytvářet z jednoho vrcholu a v každém kroku přidáme nejmenší z hran, které vedou z již vytvořeného podstromu do zbytku grafu. Poznámka: Tento algoritmus je velmi vhodný pro praktické výpočty a je dodnes široce používaný. Málokdo ve světě však ví, že pochází od Vojtěcha Jarníka, známého českého matematika — ve světové literatuře se obvykle připisuje Američanu Primovi, který jej objevil až skoro 30 let po J arnikoví. Avšak historicky vůbec první algoritmus pro problém minimální kostry (z roku f 928) byl nalezen jiným českým (brněnským) matematikem: Algoritmus 5.4. Borůvkův pro minimálni kostru (náznak). Toto je poněkud složitější algoritmus, chová se jako Jarníkův algoritmus spuštěný zároveň ze všech vrcholů grafu najednou. Detaily lze nalézt v literatuře [5, Oddíl 5.4]. Doplňkové otázky (5.1.1) Co se stane, pokud v Algoritmu 5.2 seřadíme hrany naopak, tedy sestupně? (5.1.2) Čím je Jarníkův algoritmus pro MST výhodnější než základní hladový postup? (5.1.3) Promyslete si Jarníkův algoritmus, jaké datové struktury potřebujete pro jeho co nejrychlejší implementaci? 52 5.2 Hladový algoritmus v obecnosti Asi nejprimitivnějším možným přístupem při řešení diskrétních optimalizačních úloh je postupovat stylem beru vždy to nejlepší, co se zrovna nabízí... Tento postup obecně v češtině nazýváme hladovým algoritmem, i když lepší by bylo použít správnější překlad anglického "greedy", tedy nenasystný algoritmus. A ještě hezčí české spojení by bylo "algoritmus hamouna". Jednoduše bychom jej nastínili takto: • Postupně v krocích vyber vždy to nejlepší, co se dá (nabízí). • To vyžaduje zvolit uspořádání na objektech, ze kterých vybíráme. • Průběh a úspěch algoritmu silně závisí na tomto zvoleném uspořádání (které již dále neměníme). Komentář: Jak asi každý ví, nenasystnost či hamounství nebývá v životě tím nejlepším postupem, ale kupodivu tento princip perfektně funguje v mnoha kombinatorických úlohách! Jedním známým příkladem je výše uvedené hledání minimální kostry. Jiným příkladem je třeba jednoduchý problém přidělování (uniformních) pracovních úkolů, na němž si obecné schéma hladového algoritmu ilustrujeme. Problém 5.5. Přidělení pracovních úkolů Uvažujeme zadané pracovní úkoly, které mají přesně určený čas začátku i délku trvání. (Jednotlivé úkoly jsou tedy reprezentovány uzavřenými intervaly na časové ose.) Cílem je takové přidělení úkolů pracovníkům, aby jich celkově bylo potřeba co nejméně. Všichni pracovníci jsou si navzájem rovnocenní - uniformní, tj. každý zvládne všechno. Komentář: Pro příklad zadání takové problému si vezměme následující intervaly úkolů: 4 .--------------. 1 •---------• 3 •------------------------------• 2 •------------------------• •-------------------• 2 1 .------------------------------. Kolik jek jejich splnění potřeba nejméně pracovníků? Asi sami snadno zjistíte, že 4 pracovníci stačí, viz zobrazené očíslování. Ale proč jich nemůže být méně? Poznámka: Uvedené zadání může být kombinatoricky popsáno také jako problém optimálního obarvení daného intervalového grafu (vrcholy jsou intervaly úkolů a hrany znázorňují překrývání intervalů). Algoritmus 5.6. Hladový algoritmus rozdělení pracovních úkolů. Problém 5.5 je vyřešen následující aplikací hladového postupu: 1. Úkoly nejprve seřadíme podle časů začátků. 2. Každému úkolu v pořadí přidělíme volného pracovníka s nejnižším číslem. Důkaz: Nechť náš algoritmus použije celkem k pracovníků. Dokážeme jednoduchou úvahou, že tento počet je optimální - nejlepší možný. V okamžiku, kdy začal pracovat pracovník číslo k, všichni 1, 2,... , k — 1 také pracovali (jinak bychom vzali některého z nich). V tom okamžiku tedy máme k překrývajících se úkolů a každý z nich vyžaduje vlastního pracovníka. □ 53 Komentář: Příklad neoptimálního přidělení pracovních úkolů dostaneme například tak, že na začátku úkoly seřadíme podle jejich časové délky. (Pj. čím delší úkol, tím dříve mu hladově přiřadíme pracovníka.) 5 •---------• •------------------------• 3 2 •---------• 2 •------------------------------• 3 •-------------------------• •-------------------• 4 1 .----------------------------------------. Pákový postup by se také mohl zdát rozumný, vždyť se v praxi často rozdělují nejprve ty velké úkoly a pak průběžně ty menší. Vidíme však na obrázku, že nalezené řešení není optimální - vyžaduje 5 místo 4 pracovníků. Je tedy velmi důležité, podle jakého prinicipu seřadíme objekty (úkoly) na vstupu. Doplňkové otázky (5.2.1) Proč tedy nestačí méně než 4 pracovníci pro splnění pracovních úkolů v zadání za Problémem 5.5? (5.2.2) Co kdybychom v hladovém řešení Problému 5.5 seřadili úkoly podle časů jejich ukončení? 5.3 Pojem matroidu Pojem matroidu se často vyskytuje ve spojení s diskrétní optimalizací, viz třeba mnohé práce Edmondse. Jedná se o pojem velice "obtížný k uchopení", a proto si o něm zde uvedeme jen několik základních poznatků v souvislosti s hladovým algoritmem (Věta 5.12). Definice 5.7. Matroid na množině X, značený M = (X,M), je takový systém J\í podmnožin nosné množiny X, ve kterém platí následující: 1. 0€JV 2. AeMaBcA => B e M 3. A, B GM a \A\ < \B\ => 3y g B \ A : A U {y} g N Množinám ze systému M říkáme nezávislé množiny. Těm ostatním pak říkáme závislé. Nezávislým množinám, do kterých již nelze přidat žádný prvek tak, že zůstanou nezávislé, říkáme báze matroiáu. Komentář: Nejdůležitější částí definice matroidu je zvýrazněný třetí bod. Přímo ukázkový příklad matroidu nám dává lineární algebra - všechny lineárně nezávislé podmnožiny vektorů tvoří matroid. Odtud také pocházejí pojmy nezávislosti a báze matroidu, které přímo odpovídají příslušným pojmům vektorového prostoru. Lema 5.8. Všechny báze matroiáu obsahuji stejně mnoho prvků. Důkaz: Toto přímo vyplývá z třetí vlastnosti definice matroidu: Pokud nezávislá množina A má méně prvků než báze B, tak do A lze vždy přidat další prvek x tak, že zůstane A U {x} nezávislá. □ Nyní uvedeme několik poznatků o stromech, které jsou relevantní pro zavedení "grafových" matroidu. 54 Lema 5.9. Les na n vrcholech s c komponentami souvislosti má přesně n — c hran. Důkaz: Každý vrchol lesa L náleží právě jedné komponentě souvislosti z definice. Jak známo, každý strom, tj. komponenta lesa L, má o jednu hranu méně než vrcholů. Ve sjednocení c komponent tak bude právě o c méně hran než vrcholů. □ Definice: Řekneme, že podmnožina hran F C E (G) je acyklická, pokud podgraf s vrcholy V(G) a hranami z F nemá kružnici. Lema 5.10. Nechť Fi,F2 jsou acyklické podmnožiny hran grafu G a \Fi\ < \F2\. Pak existuje hrana f € F2 \ F\ taková, že F\ U {/} je také acyklická podmnožina. Důkaz: Jelikož |Fi| < |i<2| a platí Lema 5.9, má podgraf G\ tvořený hranami z F\ více komponent než podgraf G2 tvořený hranami z F2. Potom však některá hrana / € F2 musí spojovat dvě různé komponenty podgrafu G\, a tudíž přidáním / do F\ nevznikne kružnice. □ Definice: Podle Lematu 5.10 tvoří systém všech acyklických podmnožin hran v (libovolném) grafu G matroid. Tento matroid nazýváme matroidem kružnic grafu G. V analogií s grafy dále používáme název kružnice pro minimální závislé množiny matroid u. Komentář: Dva příklady matroidu jsou hezky ilustrovány v následujícím obrázku, který ukazuje, jak hrany grafu K4 vlevo odpovídají vektorům v matroidu kružnic vpravo. Cáry (zvané "přímky") v pravém schématu vyznačují lineární závislosti mezi vektory; tj. nezávislé jsou ty trojice bodů, které neleží na žádné společné "přímce". KA Abstraktní hladový algoritmus V praxi se matroid obvykle nezadává výčtem všech nezávislých množin, protože těch je příliš mnoho (až 2n pro n-prvkovou množinu X). Místo toho bývá dána externí funkce pro testování nezávislosti dané podmnožiny. Algoritmus 5.11. Nalezení minim, báze matroidu - hladový algoritmus. vstup: množina X s váhovou funkcíw : X —> R, matroid na X určený externí funkcí nezávisia (Y); setřídit X=(x[l] ,x[2] , . . . ,x[n]) tak, aby w[x[l]]<=. . .<=w[x[n]] ; B = 0; for (i=l; i<=n; i++) if (nezavisla(BU{x[i]})) B = BU{x[i]}; výstup: báze B daného matroidu s minimálním součtem ohodnocení vzhledem k w. 55 Poznámka: Pokud X v tomto algoritmu je množina hran grafu, w váhová funkce na hranách a nezávislost znamená acyklické podmnožiny hran (matroid kružnic grafu), pak Algoritmus 5.2 je přesně instancí Algoritmu 5.11. Věta 5.12. Algoritmus 5.11 (hladový algoritmus) pro danou nosnou množinu X s váhovou funkcí w : X —>■ IR a pro daný matroid M na X správně najde bázi v N s nejmenším součtem vah. Důkaz: Z definice matroidu je jasné, že k výsledné množině B již nelze přidat další prvek, aby zůstala nezávislá, proto je B báze. Seřaďme si prvky X podle vah jako v algoritmu w(a;[l]) < ••• < w(x[n}). Nechť indexy ii,Í2,---,ik určují vybranou k-prvkovou bázi B v algoritmu a nechť indexy ji,J2, ■ ■ ■ ,jk vyznačují (třeba jinou?) bázi {a;[ji],..., a;[jfc]} s nejmenším možným součtem vah. Vezměme nejmenší r > 1 takové, že w(x[ir}) / w(x[jr]). Potom nutně w(x[ir}) < w(x[jr}), protože náš algoritmus je "hladový" a bral by menší w(x[jr]) již dříve. Na druhou stranu, pokud by druhá báze {«[ji],...,#[jfc]} dávala menší součet vah, muselo by existovat jiné s > 1 takové, že w(x[is}) > w(x[js}). Nyní vezměme nezávislé podmnožiny A\ = {x[ii\,... ,x[is-i\} a A2 = {x[j\],... ,x[js}}, kde A2 má o jeden prvek více než A\ a všechny prvky A2 mají dle předpokladu menší váhu než w(x[is}). Podle definice matroidu existuje y€Í2\^i takové, že A\ U {y} je nezávislá. Přitom samozřejmě y = x[£] pro nějaké £. Ale to není možné, protože, jak je výše napsáno, w(y) < w(x[is]), takže by náš hladový algoritmus musel y = x[£], l < is vzít dříve do vytvářené báze B než vzal x[is]. Proto jiná báze s menším součtem vah než nalezená B neexistuje. □ Tím jsme zároveň podali i jiný důkaz správnosti Algoritmu 5.2, který je jen specifickou instancí Algoritmu 5.11. Poznámka: Požadavek, že hladový Algoritmus 5.11 hledá bázi s minimálním součtem vah je v zásadě jen naší konvencí. Je jasné, že obrácením znamének u hodnot w se z minimalizace stává maximalizace a naopak. Na druhou stranu je obecně podstatný požadavek, že výsledná množina má být bází, ne jen nezávislou množinou, neboť při kladných hodnotách w by minimální nezávislou množinou byla vždy 0. (Naopak při maximalizaci s kladnými hodnotami w vychází automaticky báze jako ta nezávislá množina s maximálním ohodnocením.) 5.4 Kdy hladový algoritmus (ne)pracuje správně Čtenáře asi napadne, že hladový algoritmus nemůže fungovat vždy optimálně. My jsme dokonce schopni popsat všechny struktury, na kterých hladový postup funguje univerzálně - jsou to právě matroidy. Věta 5.13. Nechť X je nosná množina se systémem "nezávislých" podmnožin N splňující podmínky (1,2) Definice 5.7. Pokud pro jakoukoliv váhovou funkci w : X —>■ R najde Algoritmus 5.11 optimální nezávislou množinu zN, tak N splňuje také podmínku (3), a tudíž tvoří matroid na X. Důkaz: Tvrzení dokazujeme sporem. Předpokládejme, že vlastnost (3) neplatí pro dvojici nezávislých množin A,B, tj. že \A\ < \B\, ale pro žádný prvek y € B \ A není Au{y} nezávislá. Nechť \A\ = a, \B\ = b, kde 26 > 2a+l. Zvolíme následující ohodnocení • w(x) = —26 pro x G A, • w(x) = —2a — 1 pro x € B \ A, • w(x) = 0 jinak. 56 Hladový algoritmus přirozeně najde bázi B\ obsahující A a disjunktní s B \ A podle našeho předpokladu. Její ohodnocení je w(B\) = —lab. Avšak optimální bází je v tomto případě jiná £>2 obsahující celé B a mající ohodnocení nejvýše io(£>2) < (—2a — 1)6 = —lab — b < w{B\). To je ve sporu s dalším předpokladem, že i při námi zvoleném ohodnocení w nalezne hladový algoritmus optimální bázi. Proto je sporný náš předpoklad o množinách A, B a podmínka (3) je splněna. □ Příklad 5.14. Nakonec uvádíme dvě ukázky dobře známých kombinatorických úloh, ve kterých hladový algoritmus výrazně selže: Obarvení grafu. Problém obarvení grafu žádá přiřazení co nejméně barev vrcholům tak, aby sousední dvojice dostaly různé barvy. Jak jsem již poznamenali, v Problému 5.5 bylo přidělování úkolů pracovníkům vlastně barvením grafu. Obecně hladově barvíme graf tak, že ve zvoleném pořadí vrcholů každému následujícímu přidělíme první volnou barvu. ®------------•-------------•------------® 12 3 1 Třeba v nakreslené cestě délky 3 můžeme barvit hladově v pořadí od vyznačených krajních vrcholů, a pak musíme použít 3 barvy místo optimálních dvou (viz Lekce 7). Vrcholové pokrytí. Problém vrcholového pokrytí se ptá na co nejmenší podmnožinu C vrcholů daného grafu takovou, že každá hrana má alespoň jeden konec v C. Přirozeným hladovým postupem by bylo vybírat od vrcholů nejvyšších stupňů ty, které sousedí s doposud nepokrytými hranami. Bohužel tento postup také obecně nefunguje. Viz. Příklad 5.18. D Poznámka: Zmíněná selhání hladového algoritmu se obecně vážou k nevhodně zvolenému pořadí kroků. Nemysleme si však, že by se tato selhání dala nějak snadno napravit volbou jiného pořadí - platí, že nalezení optimálního pořadí kroků pro použití hladového algoritmu může být (a bývá) stejně obtížné jako vyřešení úlohy samotné. Doplňkové otázky (5.4.1) Jak špatně může dopadnout hladové barvení bipartitního grafu? (Bipartitní grafy jsou ty, které lze optimálně obarvit 2 barvami.) Přesně se otázkou myslí, kolik barev se hladově použije pro nejhorší bipartitní graf při nejhorším uspořádání jeho vrcholů, když se v každém kroku pro nový vrchol vybírá první volná barva. (5.4.2) V jakém (jednoduše spočitatelném) pořadí barvit vrcholy bipartitního grafu, aby stačily 2 barvy? (5.4.3) Jak lze (dobře) využít hladový algoritmus pro obarvení grafu se všemi vrcholy stupně k pomocí k + 1 barev? Rozšiřující studium Problém minimální kostry a jeho historie jsou výborně shrnuty v [5, Oddíly 4.3,4.5]. Dosti obsáhlý rozbor algoritmů používaných na problém minimální kostry je v [4, Kapitoly 5,6]. Hladový postup je běžně zmiňován a používán v knihách zabývajících se algoritmy a optimalizací. Pro konkrétní algoritmické implementace odkazujeme i na [3]. V oblasti teorie matroidů je jen poskrovnu českých textů, ale obsáhlou a základní anglickou monografií je [8]. Krátký čtivý úvod do matroidů je volně dostupný na J. Oxley, What is a Matroid?, http://www.math.lsu.edu/~preprint/2002/jgo2002e.pdf. 57 5.5 Cvičení: Příklady o stromech, kostrách a hladovém postupu Příklad 5.15. Najděme hladovým algoritmem minimální kostru v tomto váženém grafu (váhy hran jsou zapsány čísly v obrázku). 3 4 3 3 \2 1/ l\ i----------------------------- A 1 Hrany si nejprve seřadíme podle jejich vah 1,1,1,1,2,2,2,2,3,3,3,4,4. (na pořadí mezi hranami stejné váhy nezáleží, proto jej zvolíme libovolně). Začneme s prázdnou množinou hran (budoucí) kostry. Pak hladovým postupem přidáme první dvě hrany váhy 1 vlevo dole, které nevytvoří kružnici. Třetí hrana váhy 1 vlevo s nimi už tvoří trojúhelník, a proto ji přidat nelze, je zahozena. Při znázornění průběhu používáme tlusté čáry pro vybrané hrany kostry a tečkované čáry pro zahozené hrany: 3 4 3 1 1 3 1 ''■.. i-------------------------------------< / 2 1 / 3 4 3 1 > ^ 4 Poté přejdeme na hrany s vahou 2, z nichž lze tři postupně přidat bez vytvoření kružnice a čtvrtá (úplně vpravo) již kružnici vytvoří a je proto zahozena. Viz. obrázek vpravo. Nakonec ještě přidáme hranu nejmenší vyšší váhy 3 vlevo nahoře a zbylé hrany již zahodíme, protože všechny tvoří kružnice. 3 4 3 3 \< A / 1 1 1 '■ i------------------------- —Jí / \ <4 Získáme tak minimální kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, která je v tomto případě (náhodou) cestou, na posledním obrázku vpravo. Poznamenáváme, že při jiném seřazení hran stejné váhy by kostra mohla vyjít jinak, ale vždy bude mít stejnou minimální velikost 12. (Například místo levé svislé hrany může obsahovat přilehlou úhlopříčku stejné váhy 1.) □ Příklad 5.16. Najděme minimální kostru grafu z Příkladu 5.15 Jarníkovým algoritmem. Kostru začneme budovat v levém dolním vrcholu. (Tj. naše částečná kostra zatím dosáhla jen na levý dolní vrchol.) Vidíme, že obě hrany z něj vycházející mají váhu 1, proto je obě do kostry přidáme. Takto naše budovaná kostra již dosáhla na tři vrcholy 58 grafu, které si v následujícím obrázku vlevo vyznačíme. (Zbylé hrany mezi dosaženými vrcholy jsou již k ničemu, proto je zahodíme.) 2 i V dalším kroku ze všech tří dosažených vrcholů vybíráme nejmenší hranu vedoucí mimo ně. Jak hned vidíme, nejmenší taková hrana má váhu 2, takže ji k naší kostře přidáme a dosáhneme čtvrtý vrchol grafu. Poté opět vybíráme nejmenší hranu z dosažených vrcholů ven, ale ty mají nyní váhu nejméně 3 (zvolíme tu nahoře vlevo). Také ji přidáme do kostry a dostaneme se do situace vyznačené na horním obrázku vpravo. Nyní již je dosažených vrcholů 5 a nejmenší z hran vedoucích z dosažených ven má váhu 2. (Všimněte si dobře tohoto rozdílu od základního hladového postupu - v tomto algoritmu se nemusí hrany probírat globálně monotónně podle svých vah!) Takto dosáhneme i pravého dolního vrcholu, na následujícím obrázku vlevo. 3 4 3 2 1 > ^ 4 Nakonec ještě dosáhneme zbylé dva vrcholy hranami po řadě vah 2 a 1. Získáme tak stejnou minimální kostru jako v Příkladě 5.15. Opět je však možnost nalézt jinou z minimálních koster stejné velikosti, pokud mezi hranami stejné váhy vedoucími ven v každém kroku vybíráme jinak. □ V dalších dvou příkladech si ukážeme použití hladového postupu na řešení jiných problémů než minimální kostry. Obě aplikace postupu jsou podobné a poměrně přirozené, přesto jen první z nich je matematicky korektní - dává vždy optimální výsledek, kdežto druhá ne. Příklad 5.17. Podívejme se na tento přirozený problém z univerzitního prostředí: Kroužky studentů mají během dne pevně naplánované časy cvičení. Našim úkolem je rozmístit cvičení do co nejméně učeben, aby se samozřejmě v jedné učebně cvičení nepřekrývala. K vyřešení použijeme hladový postup: - Nejdříve začínající cvičení umístíme do učebny č. 1. - Vybereme nejdříve začínající neumístěné cvičení (libovolné, pokud jich více začíná ve stejnou dobu) a umístíme jej do první volné učebny nejmenšího čísla. - Opakujeme předchozí bod, dokud nejsou všechna cvičení rozmístěna. Jak dobrý výsledek (tj. maximální počet potřebných učeben) nám tento postup dá? Je to možná s podivem, ale tento primitivní postup nám dá zcela optimální řešení úlohy, jak si nyní stručně zdůvodníme: Předpokládejme, že učebny jsou číslovány 1,2,3,.... Pokud uvedený hladový postup potřebuje celkem k učeben, znamená to, že v některém svém kroku již měl učebny 1,2,..., k — 1 obsazené probíhajícími cvičeními a pro další cvičení musel použít učebnu 59 číslo k. (Jinak by použil učebnu menšího čísla.) To však znamená, že v onom okamžiku se najednou koná k různých cvičení, a proto použití nejméně k učeben je nutné. Vidíte přímou souvislost s Problémem 5.5? □ Příklad 5.18. Vrcholovým pokrytím v grafu G nazveme množinu vrcholů X C V (G) takovou, že každá hrana grafu G má aspoň jeden konec v X. Zadaným úkolem je nalézt v grafu vrcholové pokrytí nejmenší možné velikosti. Použijeme hladový postup (kdy se snažíme každým krokem pokrýt co nejvíce ze zbylých hran v grafu): - Začneme s prázdnou X = 0. - Vybereme vrchol v největšího stupně v G a přidáme jej do X. - Vrchol v odebereme z grafu G (i s jeho hranami) a jdeme zpět na předchozí bod, dokud nezbude graf G prázdný. Proč je toto řešení obecně nekorektní? Popsaný hladový postup v některých případech nenalezne nejmenší možnou množinu vrcholového pokrytí. Podívejme se na tento graf: Hladový postup nejprve vybere prostřední vrchol, ale pak ještě musí v dalších čtyřech krocích vybrat 4 vrcholy, tedy celkem vyjde množina X velikosti 5: Snadno však zjistíme, že optimální vrcholové pokrytí má velikost jen 4 a je vyznačené na obrázku vpravo. □ 60 6 Toky v sítích Úvod Nyní se podíváme ještě na jednu oblast úloh, kde našla teorie grafů (konkrétně orientované grafy) bohaté uplatnění v praxi. Jde o oblast tzv. „síťových" úloh: Pojem stí používáme jako souhrnné pojmenování pro matematické modely situací, ve kterých přepravujeme nějakou substanci (hmotnou či nehmotnou) po předem daných přepravních cestách, které navíc mají omezenou kapacitu. Jedná se třeba o potrubní sítě přepravující vodu nebo plyn, o dopravní stí silnic s přepravou zboží, nebo třeba o internet přenášející data. Obvykle nás zajímá problém přenést z daného „zdroje" do daného cíle čili „stoku" co nejvíce této substance, za omezujících podmínek kapacit jednotlivých přepravních cest (případně i jejich uzlů). Obrázkem můžeme vyjádřit stí s danými kapacitami přepravy jako: Problém maximálního toku v síti je snadno algoritmicky řešitelný, jak si také popíšeme. Jeho řešení má (kupodivu) i mnoho teoretických důsledků, třeba pro souvislost či párování v grafech. Cíle Úkolem této lekce je teoreticky popsat problém toku v síti a vysvětlit základní algoritmus nenasycených cest pro jeho řešení. Dále jsou uvedeny některé důsledky vysvětlené látky (pro rozšířené sítě, pro bipartitní párování a výběr reprezentantů množin, pro vyšší souvislost grafů - Mengerovu větu). 6.1 Definice sítě Základní strukturou pro reprezentaci sítí je orientovaný graf. Vrcholy grafu modelují jednotlivé uzly sítě a hrany jejich spojnice. Vzpomeňme si (strana 7), že v orientovaných grafech je každá hrana tvořena uspořádanou dvojicí (u, v) vrcholů grafu, a tudíž taková hrana má směr z vrcholu u do v. Definice 6.1. Síť je čtveřice S = (G,z,s,w), kde - G je orientovaný graf, - vrcholy z € V(G), s € V (G) jsou zdroj a stok, - w : E(G) —>■ R+ je kladné ohodnocení hran, zvané kapacita hran. Komentář: Na obrázku je zakreslena síť s vyznačeným zdrojem z a stokem s, jejíž kapacity hran jsou zapsány čísly u hran. Šipky udávají směr hran, tedy směr proudění uvažované substance po spojnicích. (Pokud směr proudění není důležitý, vedeme mezi vrcholy dvojici opačně orientovaných hran se stejnou kapacitou.) Kapacity hran pak omezují maximální množství přenášené substance. 61 Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a stok, z něhož / do nějž vedou hrany do ostatních zdrojů / stoků. (Dokonce pak různé zdroje a stoky mohou mít své kapacity.) Obvykle nás na síti nejvíce zajímá, jak mnoho substance můžeme (různými cestami) přenést ze zdroje do stoku. Pro to musíme definovat pojem toku, což je formální popis okamžitého stavu přenášení v síti. Značení: Pro jednoduchost píšeme ve výrazech znak e —> v pro hranu e přicházející do vrcholu v a e <— v pro hranu e vycházející z v. Definice 6.2. Tok v síti S = (G,z,s,w) je funkce / : E{G) —>■ Rj splňující - VeeE(G) : 0 < /(e) -u / v=z,s \e<—v e—>-u / (Sčítance uprostřed předchozího vztahu nabývají nulové hodnoty pro všechny vrcholy v kromě z & s dle definice toku.) Proto velikost toku počítaná u zdroje je rovna opačné velikosti toku počítaného u stoku ÍE/(e)-E/(e)) = ÍE/(e)-E \e<—z e—>z / \e—>s e<—s /(e) 62 6.2 Hledání maximálního toku Naším úkolem je najít co největší tok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy. Problém 6.3. Maximálního toku v síti Je dána síť S = (G, z, s, w) a našim úkolem je pro ni najit co největší tok ze zdroje z do stoku s vzhledem k ohodnocení w. Formálně hledáme max||/|| dle Definice 6.2. Komentář: Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v této síti najdeme i tok velikosti 6: Jak však poznáme, že větší tok již v dané síti neexistuje? V této konkrétní ukázce to není obtížné, vidíme totiž, že obě dvě hrany přicházející do stoku mají součet kapacit 2 + 4 + 6, takže více než 6 do stoku ani přitéct nemůže. V obecnosti lze použít obdobnou úvahu, kdy najdeme podmnožinu hran, které nelze tokem „obejít" a které v součtu kapacit dají velikost našeho toku. Existuje však taková množina hran vždy? Odpověď nám dá následující definice a věta. Definice 6.4. Řez v síti S = (G,z,s,w) je podmnožina hran C C E (G) taková, že v podgrafu G — C (tj. po odebrání hran C z G) nezbude žádná orientovaná cesta ze z do s. Velikostí rezu C rozumíme součet kapacit hran z C, tj. ||C|| = J2eecw(e)- Věta 6.5. Maximální velikost toku v síti je rovna minimální velikosti řezu. Komentář: Na následujícím obrázku vidíme trochu jinou síť s ukázkou netriviálního minimálního řezu velikosti 5, naznačeného svislou čárkovanou čarou. Všimněte si dobře, že definice řezu mluví o přerušení všech orientovaných cest ze z do s, takže do řezu stačí započítat hrany jdoucí přes svislou čáru od z do s, ale ne hranu jdoucí zpět. Proto je velikost vyznačeného řezu 1 + 4 = 5. Poznámka: Tato věta poskytuje tzv. dohrou charakterizací problému maximálního toku: Když už nalezneme maximální tok, tak je pro nás vždy snadné dokázat, že lepší tok není, nalezením příslušného řezu o stejné velikosti. Přitom toto zdůvodnění řezem můžeme směle ukázat i někomu, kdo se moc nevyzná v matematice. Důkaz Věty 6.5 bude proveden následujícím algoritmem. 63 Nenasycené cesty v síti Definice: Mějme síť S a v ní tok /. Nenasycená cesta (v S vzhledem k /) je neorientovaná cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících hran ei, e2,..., em, kde /(e») < w(ei) pro e» ve směru z u do v a /(e») > 0 pro e» v opačném směru. Hodnotě w(ei) — /(e») pro hrany e» ve směru z u do v a hodnotě /(e») pro hrany ei v opačném směru říkáme rezerva kapacity hran e». Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran. Komentář: Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou kapacity +1. © rezerva kapacity: +1 3/4 1/2 1/1 2/3 2/4 0 + 1 +1 +2 +2 Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech. Algoritmus 6.6. Ford-Fulkersonův pro tok v síti. vstup síí S = (G,z,s,w); tok / = 0; repeat { Prohledáváním grafu najdeme množinu U vrcholů G, do kterých se dostaneme ze z po nenasycených cestách; if ( s € U ) { P = (výše nalezená) nenasycená cesta v S ze z do s; Zvětšíme tok f o minimálni rezervu kapacity hran v P; } until ( s g U ); výstup vypíšeme maximálni tok f; výstup vypíšeme min. řez jako množinu hran vedoucích z U do V (G) — U. Důkaz správnosti Algoritmu 6.6: Pro každý tok / a každý řez C v síti S platí ||/|| < ||C||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti ||C|| = ||/||, je jasné, že jsme našli maximálni možný tok v síti S. (Pozor, zastavení algoritmu jsme zatím nezdůvodnili, to není tak jednoduché.) Takže dokažme, že po zastavení algoritmu nastane rovnost ||/|| = ||C||, kde C je vypsaný řez mezi U a zbytkem grafu G. Vezměme tok f v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s. Schematicky vypadá situace takto: /(e) = 0 Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e <— U (odcházející z U) plný tok /(e) = 10(e) a každá hrana e —> U (přicházející do U) tok /(e) = 0, takže ei-U e->U ei-U e€C e = 64 Na druhou stranu, když v sumě uvažujeme všechny hrany grafu indukované na naší množině U, tj. e € E \ U, analogicky dostaneme požadované o = E (/(e) - /(e)) = E f E /(e) - E /(e)) - f E /(e) - E /(e) e€E\U v&J \e<-v e-^v J \e^U e^U = (E/(e) - E/(e)) - [E /(e) - E /(e)) = ii/ii - n • \e<-.z e^z J \ei-U e->U J D Z důkazu Algoritmu 6.6 odvodíme několik zajímavých faktů: Fakt: Pokud zajistíme, že Algoritmus 6.6 vždy skončí, zároveň tím dokážeme i platnost Věty 6.5. (Takže se teď podívejte na Algoritmus 6.8.) Fakt: Pro celočíselné kapacity hran sítě S Algoritmus 6.6 vždy skončí. Pro další využití v teorii grafů je asi nejdůležitější tento poznatek: Důsledek 6.7. Pokud jsou kapacity hran sítě S celočíselné, optimální tok také vyjde celočíselně. Vylepšení algoritmu nenasycených cest Bohužel pro reálná čísla kapacit hran není skončení Algoritmu 6.6 vůbec zaručeno, dokonce se dají najít extrémní případy, které nepovedou k řešení ani v limitě. Proto je potřebné základní algoritmus (i pro potřeby teorie) poněkud vylepšit. Algoritmus 6.8. Edmonds-Karpův pro tok v síti V Algoritmu 6.6 vždy sytíme nejkratší nenasycenou cestu, neboli prohledáváme naši stí do šířky (viz množina U). Tato implementace zaručeně skončí po 0{\V{G)\ ■ \E(G)\) iteracích cyklu, celkem tedy v čase 0{\V{G)\ ■ \E{G)\2). Ještě lepších výsledků dosahují následující "chytré" algoritmy. Algoritmus 6.9. Dinicův pro tok v síti (náznak) V intencích Algoritmu 6.6 provádíme následující iterace: • Prohledáváním sítě do šířky nalezneme všechny nenasycené cesty nejkratší délky souběžně, které nám vytvoří "vrstvenou síť" (vrstvy odpovídají nenasycené vzdálenosti vrcholů od zdroje). • Nalezené nenasycené cesty pak nasytíme novým prohledáním vrstvené sítě. Tato implementace zaručeně skončí už po 0(\V(G)\) iteracích cyklu, ale jednotlivé iterace jsou poněkud náročnější - 0(|F(G)| • \E(G)\). Algoritmus 6.10. MPM („Tří Indů") pro tok v síti (náznak) Postupuje se stejně jako v Algoritmu 6.9, jen nesyceniv druhém bodě proběhne rychlejším algoritmem v čase 0{\V{G)\2) v každé iteraci, celkem tedy v 0(\V(G)\3). 65 Úlohy k řešení (6.2.1) Jaký je maximální tok touto sítí ze z do s? 3 (6.2.2) Co obsahuje výsledná množina U Algoritmu 6.6 v předchozím příkladě? (6.2.3) Kde je minimální řez v této síti mezi zas? (6.2.4) Proč Algoritmus 6.6 vždy skončí pro celočíselné kapacity hran? * (6.2.5) Dokažte časový odhad Algoritmu 6.8. (6.2.6) Nalezněte příklad sítě s reálnými kapacitami, na které Algoritmus 6.6 neskončí. 6.3 Zobecnění definice sítí Pojmy sítě a toků v ní lze zobecnit v několika směrech. My si zde stručně uvedeme tři možnosti. Sítě s kapacitami vrcholů U sítě můžeme zadat i kapacity vrcholů, neboli kapacitní váhová funkce je dána jako w : E{G) U V (G) —>■ R+. Význam pro přípustné toky v takové síti je, že žádným vrcholem nemůže celkem „protéct" více než povolené množství substance. Fakt. Takovou síť „zdvojením" vrcholů snadno převedeme na běžnou síť, ve které kapacity původních vrcholů budou uvedeny u nových hran spojujících zdvojené vrcholy. Viz neformální schéma: Sítě s dolními kapacitami Pro hrany sítě lze zadat také jejich minimální kapacity, tedy dolní meze přípustného, toku. Například u potrubní sítě mohou minimální vyžadované průtoky vody garantovat, že nedojde k zanesení potrubí, atd. To je modelováno druhou (vedle /) váhovou funkcí l : E(G) —>■ Rq\ Přípustný tok pak musí splňovat 1(e) < /(e) < 10(e) pro všechny hrany e. V této modifikaci úlohy již přípustný tok nemusí vůbec existovat. Algoritmus 6.11. Tok v síti s dolními kapacitami I tuto úlohu lze řešit dosud uvedenými nástroji, pokud postupujeme ve dvou fázích: 66 • Nejprve nalezneme přípustnou cirkulaci v síti vzniklé přidáním „zpětné" hrany sz. Toho lze dosáhnout hledáním toku ve speciální síti vyjadřující „přebytky" (či nedostatky) dolních mezí toku v jednotlivých vrcholech. — Z dané sítě S = (G,z,s,w) utvoříme novou síť So = (Go,zo,so,wq), kde Go vznikne přidáním hrany sz a nových vrcholů zq, So s hranami do a z V(G) podle níže uvedeného pravidla. Pro e € E (G) je wo(e) = w(e) — 1(e). Pro x € V(G) a „přebytek" p = J2f^x^(f) ~ Y^f<-X^(f) > 0 Je zavedena hrana zqx s kapacitou w(zqx) = p, naopak pro p < 0 je zavedena hrana xsq s kapacitou w(xso) = —p. — Pro S*o je nalezen maximální tok, který musí nasytit všechny hrany vycházející z so- Pokud takový neexistuje, neexistuje ani přípustné řešení původní úlohy. V opačné případě je tento tok na hranách G navýšen o příslušné dolní kapacity. • Poté z přípustné cirkulace jako výchozího stavu už získáme maximální tok kterýmkoliv algoritmem pro toky. Tzv. vícekomoditní toky V síti lze najednou přepravovat více typů substancí. To vede na problém tzv. vícekomoditních toků v síti. Tento problém je složitější, už není v obecnosti snadno řešitelný a přesahuje rámec našeho textu, takže se jím nebudeme zabývat. Kromě uvedených (a podobných) zobecnění toků v sítích jsou velmi zajímavé i některé speciální formulace problému toků, které se vyskytují v možná i nečekaných oblastech. Více o tom napíšeme v další části této lekce. Úlohy k řešení (6.3.1) Nakreslete si sami příklad sítě s dolními kapacitami bez přípustného toku. *(6.3.2) Dokažte si, že Algoritmus 6.11 funguje správně. 6.4 Speciální aplikace sítí Bipartitní párování Biparitní grafy jsou grafy, jejichž vrcholy lze rozdělit do dvou množin tak, že všechny hrany vedou jen mezi těmito množinami. Definice: Párování y (biparitním) grafu G je podmnožina hran M C E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol. Komentář: Pojem (bipartitního) párování má přirozenou motivaci v mezilidských vztazích. Pokud neuvažujeme bigamii ani jisté menšiny, můžeme si partnerské vztahy představit jako párování v bipartitním grafu. Jednu stranu grafu tvoří muži a druhou ženy. Hrana mezi mužem a ženou znamená vzájemné sympatie (přitom jedinec může mít vzájemné sympatie s několika jinými opačného pohlaví). Pak skutečné, tradiční partnerské vztahy by měly představovat párování v popsaném grafu. Úlohu nalézt v daném bipartitním grafu co největší párování lze poměrně snadno vyřešit pomocí toků ve vhodně definované síti. Uvedená metoda použití toků v síti na řešení problému párování přitom hezky ilustruje obecný přístup, jakým toky v sítích pomohou řešit i úlohy, které na první pohled se sítěmi nemají nic společného. 67 Algoritmus 6.12. Nalezení bipartitního párování Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme síť S následovně: A B Všechny hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. Nyní najdeme (celočíselný) maximální tok v S Algoritmem 6.6. Do párování vložíme ty hrany grafu G, které mají nenulový tok. Důkaz správnosti Algoritmu 6.12: Podle Důsledku 6.7 bude maximální tok celočíselný, a proto každou hranou poteče buď 0 nebo 1. Jelikož však do každého vrcholu v A může ze zdroje přitéct jen tok 1, bude z každého vrcholu A vybrána do párování nejvýše jedna hrana. Stejně tak odvodíme, že z každého vrcholu B bude vybrána nejvýše jedna hrana, a proto vybraná množina skutečně bude párováním. Zároveň to bude největší možné párování, protože z každého párování lze naopak vytvořit tok příslušné velikosti a větší než nalezený tok v S neexistuje. □ Poznámka: Popsaná metoda je základem tzv. Maďarského algoritmu pro párování v bipartitních grafech. Úlohu nalezení maximálního párování lze definovat i pro obecné grafy a také ji efektivně algoritmicky vyřešit, ale příslušný algoritmus [Edmonds] není jednoduchý. Vyšší grafová souvislost Představme si, že na libovolném grafu G definujeme zobecněnou síť tak, že kapacity všech hran a všech vrcholů položíme rovny 1 v obou směrech. Pak celočíselný tok (viz Důsledek 6.7) velikosti k mezi dvěma vrcholy u, v se skládá ze soustavy k disjunktních cest (mimo společné koncové vrcholy u,v). Naopak řez odděluje u a v do různých souvislých komponent zbylého grafu. Aplikace Věty 6.5 na tuto situaci přímo poskytne následující tvrzení. Důsledek 6.13. Nechť u, v jsou dva vrcholy grafu G ak > 0 je přirozené číslo. Pak mezi vrcholy u a v existuje v G aspoň k disjunktních cest, právě když po odebrání libovolných k — l vrcholů různých odu,v z G zůstanou u a v ve stejné komponentě souvislosti zbylého grafu. Použitím tohoto tvrzení pro všechny dvojice vrcholů grafu snadno dokážeme dříve uvedenou důležitou Větu 2.6 (Mengerovu). Ještě jiné použití si ukážeme na problému výběru reprezentantů množin. Výběr různých reprezentantů Definice: Nechť Mi, M2,..., M& jsou neprázdné množiny. Systémem různých reprezentantů množin Mi,M2,... ,Mfc nazýváme takovou posloupnost různých prvků {x\,X2, ■ ■ ■ ,Xk), že Xi € Mi pro i = 1, 2,... , k. Důležitým a dobře známým výsledkem v této oblasti je Hallova věta plně popisující, kdy lze systém různých reprezentantů daných množin nalézt. 68 Věta 6.14. Necht Mi, M2,..., Mj, jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí VJC{1,2,...,A:}:|U j&J Mi > \J\ neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno. Důkaz: Označme X\, X2, ■ ■ ■, xm po řadě všechny prvky ve sjednocení Mi U M2 U • • • U Mfc. Definujeme si bipartitní graf G na množině vrcholů {1, 2,... , k} U {x\, X2, ■ ■ ■, xm} U {u, v}, ve kterém jsou hrany {u, i} pro i = 1, 2,..., k, hrany {v, Xj} pro j = 1, 2,..., m a hrany {i, x j} pro všechny dvojice i, j, pro které x j € M». Komentář: Konstrukce našeho grafu G je obdobná konstrukci sítě v Algoritmu 6.12: Vrcholy u a v odpovídají zdroji a stoku, ostatní hrany přicházející do vrcholu Xj znázorňují všechny z daných množin, které obsahují prvek Xj. Cesta mezi u a v má tvar u,i,Xj,v, a tudíž ukazuje na reprezentanta x j € Mj. Systém různých reprezentantů tak odpovídá k disjunktním cestám mezi u a v. Nechť X je nyní libovolná minimální množina vrcholů v G, neobsahující samotné u a v, po jejímž odebrání z grafu nezbude žádná cesta mezi u a v. Podle Důsledku 6.13 a této úvahy mají naše množiny systém různých reprezentantů, právě když každá taková oddělující množina X má aspoň k prvků. Položme J = {1,2,... ,k} \ X. Pak každá hrana z J (mimo u) vede do vrcholů z X n {x\,..., xm} (aby nevznikla cesta mezi u,v), a proto IU j&J Mi = \xn{xi,...,xm}\ = \x\ -\xn{i,...,k}\ = \x\ -k + \J\. (První rovnost vyplývá z minimality množiny X!) Vidíme tedy, že \X\ > k pro všechny (minimální) volby oddělující X, právě když |J je dokazovaná podmínka naší věty. KjMj > \J\ pro všechny volby J, což D Poznámka: Předchozí důkaz nám také dává návod, jak systém různých reprezentantů pro dané množiny nalézt - stačí použít Algoritmus 6.6 na vhodně odvozenou síť. Úlohy k řešení (6.4.1) Najděte největší párování v tomto bipartitním grafu: (6.4.2) Najděte největší párování v tomto bipartitním grafu: (6.4.3) Mají všechny tříprvkové podmnožiny množiny {1, 2, 3, 4} systém různých reprezentantů ? 69 (6.4.4) Majívšechny tříprvkovépodmnožiny množiny {1, 2, 3,4, 5} systém různých reprezentantů ? Rozšiřující studium Problematika toků v sítích je běžnou součástí teorie grafů (i když není pokryta v [5]) a je možno najít její popis třeba v [3], případně na volně dostupných webových zdrojích jako http://en.wikipedia.org/wiki/Flow_network, http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm, nebo http://mathworld.wolfram.com/NetworkFlow.html. Jiný podrobný popis variant algoritmů pro toky v sítích se nachází v prvních dvou kapitolách [4]. Jedná se také o klasické téma kombinatorické optimalizace. Z dalších internetových zdrojů je možno zmínit třeba implementace na http://www.es.sunysb.edu/~algorith/files/network-flow.shtml. Teorie párování tvoří samostatnou rozvinutou oblast grafů, mající zajímavé aplikace v jiných oborech jako statistické fyzice. Zájemce o obecnou teorii odkazujeme třeba na [1, Chapter 2] nebo internetově na http://en.wikipedia.org/wiki/Matching. 6.5 Cvičení: Příklady toků v sítích Příklad 6.15. Jaký je maximální tok znázorněnou sítí ze z do s? Na tomto příkladě si ukážeme průběh Algoritmu 6.6. Začneme s nulovým tokem a najdeme nejkratší z nenasycených cest mezi zas (vedoucí spodem grafu a vyznačenou na prvním obrázku). Minimální rezerva kapacity na této cestě je 2, takže tok nasytíme o 2 podél této cesty (viz obrázek vpravo). V dalším kroku najdeme nenasycenou cestu délky 3 vedoucí vrchem grafu. Její minimální rezerva kapacity je opět 2, takže ji o tolik nasytíme (viz další obrázek vlevo). Nyní již nenasycená cesta délky 3 neexistuje, takže najdeme nenasycenou cestu délky 4 s rezervou kapacity 1, kterou hned nasytíme (viz obrázek vpravo). 70 Obdobně ještě najdeme nenasycenou cestu délky 5, kterou také nasytíme o 1. Závěrečný obrázek nám ukazuje všechny nenasycené hrany, mezi kterými již nevede žádná nenasycená cesta ze z do s, takže máme maximální tok velikosti 6 v naší síti. 3/3 4/4 */* 4/4 Zároveň je na posledním obrázku vyznačen i příslušný minimální řez velikosti 6. □ Úlohy k řešení (6.5.1) Najděte maximální tok v této síti. (Kapacity hran jsou vyznačeny u svých šipek.) Tok do obrázku zapište, vyznačte hrany příslušného minimálního řezu a napište velikost toku. (6.5.2) Obdobně najděte maximální toky v následujících sítích. 71 (6.5.3) Má tento seznam množin systém různých reprezentantů? Pokud ano, vyznačte je v množinách, jinak správně zdůvodněte, proč systém různých reprezentantů nemají. {1,2,3,4}, {6,7,8,9}, {3,5,7}, {3,4,5,6}, {1,2,8,9}, {3,6,7}, {4,5,6,7}, {4,5,6}, {4,6,7}. (6.5.4) Má tento seznam množin systém různých reprezentantů? Pokud ano, vyznačte je v množinách, jinak správně zdůvodněte, proč systém různých reprezentantů nemají. {1,2,3,4}, {6,7,8,9}, {1,3,9}, {3,4,5,6}, {1,2,3,9}, {2,4,9}, {4,5,6,7}, {2,3,4}, {3,4,9}. 72 7 Barevnost a další těžké problémy Úvod Pro motivaci této lekce se podíváme hlouběji do historie počátků grafů v matematice. Již dříve jsme si připomínali jeden z historických kamenů teorie grafů - slavný problém sedmi mostů v Královci (dnešním Kaliningrads). Další neméně slavný problém pochází z poloviny 19. století a je obvykle zvaný problémem čtyř barev. Na rozdíl od sedmi mostů, problém čtyř barev zůstal nevyřešený po více než 100 let! A právě marné snahy o jeho vyřešení se zapříčinily o rozvoj mnoha oblastí teorie grafů a celé kombinatoriky. Problém čtyř barev byl původně formulován pro politické mapy států: Výrobci map chtěli státy barevně odlišit, aby každé dva sousední měli různé barvy. Přitom chtěli mapy tisknout co nejlevněji, tedy s nejmenším možným počtem barev. Není problém nakreslit čtyři státy tak, že každý s každým sousedí, a proto 4 barvy jsou někdy potřebné. Praxe brzy ukázala, že 4 barvy vždy stačí, ale matematici si dlouho lámali hlavy s tím, jak to přesně dokázat, jedná se totiž o nebývalé obtížný problém... Takto se zde (a dále v Oddíle 8.4) přirozeně dostáváme k široce studované problematice barvení grafů. Někteří matematici však kladou prapočátky teorie grafů daleko před Eulerovými sedmi mosty či problémem čtyř barev, až ke středověké otázce, zda lze šachovým koněm obejít celou šachovnici bez opakování. Tato otázka nakonec vede k dalšímu zajímavému a obtížnému problému tzv. Hamiltonovské kružnice v grafu, nazvané podle tvůrce příslušného hlavolamu z 19. století. I na tento specihcký problém a jeho obtížnost se blíže podíváme. A také na několik jiných typických představitelů „ obtížných" grafových problémů. Cíle Prvním cílem této lekce je deßnovat barevnost grafů a naučit se s ní pracovat. Druhým cílem je ukázat několik dalších „obtížných" problémů dehnovaných přirozeně na grafech a přivést je do kontextu teorie výpočetní složitosti a NT'-úplnosti. Studující bez zájmu o informatické aspekty mohou látku týkající se složitosti jednoduše přeskočit. 7.1 Barevnost grafu Nejprve si uveďme pojem barevnosti - představme si, že hrany grafu nám říkají, že jejich koncové vrcholy musí být barevně odlišené (třeba proto, že reprezentují sousední státy, nebo proto, že jinak jsou si příliš podobné a je třeba je jinak rozlišit, atd).Samozřejmě bychom mohli každému vrcholu grafu dát jinou barvu, ale k čemu by pak takový problém byl? My bychom chtěli použít barev celkem co nejméně. Definice: Obarvením grafu G pomocí k barev myslíme libovolné zobrazení c:V(G)^{l,2,...,k} takové, že každé dva vrcholy spojené hranou dostanou různé barvy, tj. c{u) / c{v) pro všechny {u, v} € E(G). Definice 7.1. Barevnost grafu G je nejmenší přirozené číslo x(G) pro které existuje obarvení grafu G pomocí x(G) barev. Čísla 1,2,..., k z předchozí definice tak nazýváme barvami vrcholů (je to pohodlnější, než popisovat barvy běžnými jmény jako bílá, červená, atd). Poznámka: Uvědomme si, že barevnost lze definovat pouze pro graf bez smyček, protože oba konce smyčky mají vždy stejnou barvu a nic s tím nenaděláme. 73 Příklad 7.2. Určete barevnost grafu Na první pohled je vidět, že potřebujeme aspoň 3 barvy, neboť graf má trojici navzájem spojených vrcholů (trojúhelník). Na druhý pohled pak zjistíme, že levý a pravý vrchol spojené hranou nejsou, a proto jim lze přiřadit stejnou barvu (a další dvě barvy vrchnímu a spodnímu vrcholu). Proto má graf barevnost 3. D V obecnosti lze o barevnosti grafů říci následující. Lema 7.3. Nechť G je jednoduchý graf (bez smyček) na n vrcholech. Pak x(G) < n a rovnost nastává právě když G ~ Kn je úplný graf. Důkaz: Stačí každý vrchol obarvit jinou barvou a máme skutečné obarvení n barvami dle definice. Navíc pokud některá dvojice u, v vrcholů není spojená hranou, můžeme volit lepší obarvení c(u) = c(v) = 1 a zbylé vrcholy různými barvami 2, 3,..., n — 1, tj. pak X{G) 1 Pokud bychom tak získali třeba dva vrcholy spojené hranou / v sudé vzdálenosti od v, získáme uzavřený sled S liché délky přes f a v. Stejně tak pro dva vrcholy v liché vzdálenosti. Ponecháme-li ze sledu S ty hrany, které se opakují lichý počet krát, dostaneme Eulerovský podgraf T lichého počtu hran. Jak již víme (Oddíl 4.1), T pak obsahuje kružnici a tudíž jej lze induktivně sestrojit jako hranově-disjunktní sjednocení kružnic. Avšak sjednocení kružnic sudé délky nevytvoří T liché velikosti, spor. Proto naše obarvení za daných předpokladů nemůže dát stejnou barvu sousedním vrcholům, a tudíž dvě barvy stačí. □ Poněkud nepříjemnou skutečností je, že o barvení a určování barevnosti grafů nemůžeme v obecnosti přesně říci o mnoho více, než jsme uvedli výše. Jedná se o problém algoritmicky ještě obtížnější než byl problém isomorfismu a nepředpokládá se, že by se barevnost grafu dala algoritmicky určit jinak, než hrubou silou probráním (téměř) všech možných obarvení. Hladové obarvování Přes všechnu svou obtížnost, za vhodných okolností má problém barvení grafů docela jednoduché přibližné hladové řešení (viz Oddíl 5.2). Definice: Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupně nejvýše k. Komentář: Příkladem ^-degenerovaného grafu je každý graf stupně nejvýše k, ale na druhou stranu fc-degenerované grafy mohou mít vysoké stupně. (Nestačí však mít jen nízký nejmenší stupeň!) Věta 7.6. Každý k-degenerovaný graf lze správně hladově obarvit k + 1 barvami. Důkaz: Jelikož graf G je fc-degenerovaný, vybereme libovolný jeho vrchol V\ stupně nejvýše k a rekurzivní aplikací tohoto postupu obarvíme podgraf G — v\, který je podle definice také fc-degenerovaný. Nakonec si všimneme, že < k sousedé vrcholu v\ dostanou nejvýše k různých barev, takže V\ dobarvíme zbylou barvou. □ Důležité aplikace této věty uvidíme v příští lekci, avšak jedno zajímavé zesílení {Brooksovu větu) si uvedeme nyní: Věta 7.7. Nechť G je souvislý jednoduchý graf maximálního stupně k > 2. Pak x(G) < k až na případy, kdy G je úplný graf nebo lichá kružnice. 75 Důkaz (náznak): Pro k = 2 plyne tvrzení z Věty 7.5. Nechť tedy k > 3. V jednom směru je jasné, že x{Kk+i) = k + 1. Naopak tedy předpokládejme, že G není úplný graf. Zároveň se omezme jen na případ, že G má všechny stupně rovné k, neboť jinak lze aplikovat postup z Věty 7.6. • Prvním krokem nahlédneme, že pak G obsahuje dva nespojené vrcholy u, v se společným sousedem w. Pokud ale je graf G — {u,v} nesouvislý, pak graf příslušně rozdělíme a indukcí po částech obarvíme. • Přidejme tedy předpoklad, že G — {u, v} je souvislý. Druhým krokem nahlédneme, že graf H vzniklý z G — w ztotožněním u s v do jednoho vrcholu je (k — l)-degenerovaný. • Tudíž graf H hladově obarvíme k barvami podle Věty 7.6. Po opětovném „rozpojení" vrcholů u, v získáme obarvení G — w k barvami takové, že u, v mají stejnou barvu. Nyní w má v sousedství nejvýše k — 1 barev a G celý obarvíme. Grafy vysoké barevnosti Ke správnému pochopení barevnosti grafu je nezbytné se zamyslet, které grafy mají vysokou barevnost. Jedná se například o grafy obsahující velké kliky (úplné podgrafy). Je to však vše? Není! Lze nalézt grafy s libovolně vysokou barevností neobsahující ani trojúhelníky. Tvrzení 7.8. (Mycielski) Graf získaný z grafu G následující konstrukcí (viz obrázek) má barevnost x(G) + 1 a neobsahuje trojúhelníky, pokud je neobsahuje ani G. Nejobecněji lze říci následující překvapivé tvrzení: Věta 7.9. (Erdös) Pro každá c, r > 0 existuje graf s barevností alespoň c a neobsahující kružnice kratší než r. Důkaz (náznak): Třebaže k tomuto tvrzení dnes existují konstruktivní důkazy, stále nejkratším a z jistého pohledu nejsilnějším důkazem je původní pravděpodobnostní (nekonstruktivní) argument Erdöse: • Ve vhodném pravděpodobnostním modelu sestrojíme náhodný graf H. • Spočítáme, že s velkou pravděpodobností H nemá velké nezávislé množiny. • Spočítáme, že střední hodnota počtu krátkých kružnic v H je velmi nízká. • Proto existuje volba H, ve kterém je málo krátkých kružnic a malá hodnota nezávislosti. Tudíž z tohoto H lze odstraněním několika vrcholů všechny krátké kružnice zrušit a díky malé nezávislosti zůstane jeho barevnost vysoká. 76 D Úlohy k řešení (7.1.1) Kolika nejméně barvami korektně obarvíte graf pravidelného osmistěnu? A (7.1.2) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. (7.1.3) Jaká je barevnost stromu? (7.1.4) Představme si, že nějaký (velký) graf má všechny vrcholy stupně nejvýše 101. Kolika barvami takový graf jistě obarvíme? (7.1.5) Kolik nejméně barev vždy stačí na korektní obarvení grafu vzniklého z kružnice délky 2006 přidáním jedné nové hrany? A co přidáním dvou nových hran? Dokažte. (7.1.6) Necht dva (pod)grafy G a H sdílejí trojúhelník. Dokažte, že pokud jsou G i H 4-obarvitelné, tak i jejich sjednocení G U H je 4-obarvitelné. *(7.1.7) Dokažte podrobně první krok důkazu Věty 7.7, když je graf G — {u,v} nesouvislý. *(7.1.8) Dokažte podrobně druhý krok důkazu Věty 7.7, proč je graf H (k —\)-degener ováný. (7.1.9) Dokažte si Tvrzení 7.8. 7.2 Variace na barevnost a jiné Definice 7.10. Hranová barevnost grafu G. Hledáme obarvení ce{E(G)) —>■ {1,2,... ,k} takové, že žádné dvě hrany se společným vrcholem nedostanou stejnou barvu. Nejmenší možný počet barev k, pro které hranové obarvení existuje, se nazývá hranová barevnost Xe{G) grafu. Na rozdíl od běžné barevnosti umíme hranovou barevnost docela ostře aproximovat. Věta 7.11. (Vizing) Pro každý jednoduchý graf platí A(G) < Xe(G) < A(G) + 1. Komentář: Platí, že většina grafů splňuje A(G) = Xe(G). Umíte jednoduše sestrojit (a dokázat) příklady pro druhý případ? Problém přesného určení hranové barevnosti grafu však stále zůstává algoritmicky velmi obtížný a také úzce souvisí s problémem čtyř barev. Definice 7.12. Výběrová barevnost grafu G. Je dán graf G spolu s přiřazenými „seznamy barev" L : V (G) —> (^) (fc-prvkové podmnožiny). Nyní hledáme obarvení cch{V{G)) —>■ N takové, že žádné dva sousední vrcholy nedostanou stejnou barvu a navíc cch(v) € L (v) pro každý vrchol v. Nejmenší možná délka k seznamů barev, pro kterou výběrové obarvení vždy existuje (tj. pro každou možnou takovou volbu seznamů), se nazývá výběrová barevnost ch{G) grafu. 77 Výběrová barevnost může (kupodivu!) být libovolně „vzdálena" běžné barevnosti. Tvrzení 7.13. Pro každé k nalezneme bipartitní graf s výběrovou barevností větší než k. Fakt: Hranová výběrová barevnost úplných bipartitních grafů úzce souvisí se známým problémem latinských obdélníků. Hamiltonovské grafy Definice: Kružnice C obsažená v grafu G se nazývá Hamiltonovska, pokud C prochází všemi vrcholy G. Obdobně mluvíme o Hamiltonovské cestě P v G, pokud cesta P C G prochází všemi vrcholy G. Graf G je Hamiltonovský, pokud obsahuje Hamiltonovskou kružnici. Možná to zní překvapivě, ale i problém Hamiltonovské kružnice úzce souvisel s řešením problému čtyř barev. To je však mimo rámec našeho textu. Věta 7.14. (Dirac) Každý graf na n > 3 vrcholech s minimálním stupněm > n/2 je Hamiltonovský. Důkaz (náznak): Nechť P je nejdelší cesta v grafu G s vrcholy po řadě Uq, U\,..., Uk-Podle její maximality leží každý soused uq i Uk na P. Pak existuje 0 < i < k takové, že uoiii+i € E(G) a zároveň UkUi € E{G). Pak uqUí+\ PukUi P tvoří kružnici v G a snadno plyne, že se jedná o Hamiltonovskou kružnici. □ Úlohy k řešení (7.2.1) Jaká je hranová barevnost liché kružnice a proč? * (7.2.2) Jaká je hranová barevnost úplných grafů Kn v závislosti nan? Dokažte. (7.2.3) Dokažte, že graf K6 s jednou hranou podrozdělenou novým vrcholem má hranovou barevnost 6. (7.2.4) Lze znění Věty 7.6 beze změny aplikovat na výběrovou barevnost? (7.2.5) Určete výběrovou barevnost grafu ÍÍ2,4- * (7.2.6) Dokažte Tvrzení 7.13. (7.2.7) Nalezněte ^-regulární jednoduchý souvislý graf bez Hamiltonovské kružnice. 7.3 A/^P-úplnost grafových problémů Zatím prakticky všechny grafové problémy probírané v minulých lekcích (s drobnou výjimkou isomorfismu) byly řešitelné rozumně rychlými algoritmy. V této lekci se situace radikálně obrací... Studující ve stručnosti odkazujeme na formální definici WP-úplnosti z oblasti algoritmické složitosti. Komentář: Definice složitostní třídy J\ÍV se týká výhradně rozhodovacích problémů (s „ANO/NE" odpovědí). Dá se neformálně říci, že problém patří do třídy J\ÍV, pokud jeho odpověď ANO lze prokázat (ve smyslu „uhodnout a ověřit") výpočtem, který běží v polynomiálním čase. TVP-úplné problémy jsou zhruba řečeno ty, které ve třídě J\ÍV mají nejvyšší obtížnost řešení. Od jednoho TVP-úplného problému A se dostaneme k jinému B tzv. polynomiálním převodem: Ukážeme, jak bychom ze známého postupu řešení B efektivně nalezli řešení (libovolné instance) A. Nyní si ukážeme vhodnými převody, že oněch „nejobtížnějších" (MV-úplných) problémů je v teorii grafů mnoho, bohužel by se dalo říci většina. To ostatně ukazuje, 78 proč jsme zatím v praxi tak málo úspěšní při počítačovém řešení mnohých praktických problémů - přesné a efektivní řešení WP-úplných úloh se totiž všeobecně považuje za nemožné. Problém 7.15. 3-SAT (splnitelnost logických formulí ve spec. verzi) Následující problém je MV-úplný: Vstup: Logická formule $ v konjunktivním normálním tvaru taková, že každá klauzule obsahuje nejvýše 3 literály. Výstup: Existuje logické ohodnocení proměnných tak, aby výsledná hodnota $ byla 1 (pravda)? Pomocí tohoto základního a pro převody velmi vhodného MV-úplného problému snadno ukážeme A/T'-úplnost mnoha běžných grafových problémů. Problém 7.16. 3-COL (3-obarvení grafu) Následující problém je NV-úplný: Vstup: Graf G. Výstup: Lze vrcholy G korektně obarvit 3 barvami? Důkaz (náznak): Ukážeme si polynomiální převod z problému 3-SAT. Sestrojíme graf G pro danou formuli $. Základem grafu je trojúhelník, jehož vrcholy označíme X,T,F (přitom barvy přiřazené vrcholům T, F budou reprezentovat logické hodnoty). Každé proměnné Xi ve $ přiřadíme dvojici vrcholů spojených s X. Každé klauzuli ve $ přiřadíme podgraf na 6 vrcholech (z nichž tři jsou spojené s T), jako na obrázku. Nakonec volné „půlhrany" z obrázku pospojujeme dle toho, jaké literály vystupují v klauzulích. {x\ V -iXí V ...) Například první pulhrana naznačené klauzule na obrázku je napojena na pulhranu značenou x\ vlevo, druhá pulhrana na pulhranu značenou -*Xi vlevo, atd. Pokud v klauzuli chybí třetí literal, je jeho pulhrana napojena přímo na F vpravo. Pak G má 3-obarvení právě když je $ splnitelná, jak si lze ověřit na obrázku. Tím jsme sestrojili polynomiální převod formule $ z problému 3-SAT na graf G v problému 3-obarvení. WP-úplnost nyní vyplývá z 7.15. □ Kromě barevnosti grafu je MV-úplných mnoho problémů ptajících se na výběry vrcholů v grafu s jistými vlastnostmi. Problém 7.17. IS (nezávislá množina) Následující problém je NV -úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít nezávislou podmnožinu velikosti (aspoň) kl 79 Důkaz: Ukážeme polynomiální převod z problému 3-COL. Nechť H je graf na n vrcholech, který je za úkol obarvit třemi barvami. Položíme k = n a graf G sestrojíme ze tří disjunktních kopií grafu H tak, že vždy tři kopie každého jednoho vrcholu v € V(H) spojíme hranami do trojúhelníku Tv v G. \ Pokud c : V (H) —> {1,2,3} je obarvení H třemi barvami, v grafu G lze vybrat k = n nezávislých vrcholů tak, že pro každý v € V(H) vezmeme c(v)-tou kopii vrcholu v v grafu G. (Nakreslete si v obrázku!) Naopak pokud / je nezávislá množina v grafu G o velikosti k = n, pak z každého trojúhelníku Tv, v € V(H) náleží do / právě jeden vrchol. Podle toho již určíme jednu ze tří barev pro vrchol v v H. □ Problém 7.18. VC (vrcholové pokrytí) Následující problém je NV-úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít vrcholové pokrytí, tj. množinu C C V (G) takovou, že každá hrana G má alespoň jeden konec v C, o velikosti nejvýše kl Důkaz: Problém vrcholového pokrytí jasně patří do MV a jeho úplnost je dokázána polynomiálním převodem z Příkladu 7.26. □ Problém 7.19. DOM (dominující množina) Následující problém je NV -úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít dominující množinu, tj. množinu D C V (G) takovou, že každá vrchol G má některého souseda v D, o velikosti nejvýše kl Důkaz (náznak): Problém dominující množiny jasně patří do MV a jeho úplnost je dokázána polynomiálním převodem z Příkladu 7.27. □ Další předvedené problému se týkají procházení grafem (pokud možno) bez opakování vrcholů. Problém 7.20. HC (Hamiltonovský cyklus) Následující problém je NV-úplný: Vstup: Orientovaný graf G. Výstup: Lze v G najít orientovanou kružnici (cyklus) procházející všemi vrcholy? Tento převod pro jeho technickou obtížnost vynecháváme.. Problém 7.21. HK (Hamiltonovská kružnice) Následující problém je NV-úplný: Vstup: Graf G. 80 Výstup: Lze v G najít kružnici procházející všemi vrcholy? Důkaz: Použijeme snadný převod z předchozího problému HC. Každý vrchol v orientovaného grafu H nahradíme třemi vrcholy tvořícími cestu Pv délky 2 v grafu G. Orientované hrany grafu H přicházející do v pak přivedeme do prvního vrcholu cesty Pv, hrany odcházející z v naopak vedeme z posledního vrcholu cesty Pv. □ Problém 7.22. TSP (problém obchodního cestujícího) Následující problém je NV-úplný: Vstup: Souvislý graf G s nezáporným ohodnocením hran (délkou) a číslo r. Výstup: Lze v G najít uzavřený sled procházející všemi vrcholy a mající součet délek hran (včetně opakovaných) nejvýše roven r? Důkaz: Použijeme snadný převod z předchozího problému HK. Každou hranu ohodnotíme délkou 1 a položíme r = n, kde n je počet vrcholů našeho grafu. Pak uzavřený sled délky n se nesmí opakovat v žádném vrcholu ani hraně, aby prošel všemi vrcholy, a proto musí být kružnicí. □ Úlohy k řešení (7.3.1) Rozhodněte, které z následujících problémů patří do třídy V všech polynomiálně řešitelných problémů. (Předpokládejte při tom J\ÍV ^ V'.) A: Problém rozhodnout, zda daný graf obsahuje nezávislou množinu (tj. podmnožinu vrcholů nespojených hranami) velikosti 7. B: Problém rozhodnout, zda daný graf obsahuje nezávislou množinu (tj. podmnožinu vrcholů nespojených hranami) velikosti nejméně 2005. C: Problém rozhodnout, zda daný graf má barevnost nejméně tři. D: Problém rozhodnout, zda daný graf má barevnost nejvýše tři. E: Problém rozhodnout, zda daný graf má barevnost přesně tři. F: Problém rozhodnout, zda daný graf má barevnost přesně dva. (7.3.2) Patří do třídy MV problém zjistit, zda graf G obsahuje dvě Hamiltonovské kružnice, které nesdílí žádnou hranu? (7.3.3) Patří do třídy MV problém zjistit, jaká je barevnost grafu? * (7.3.4) Je známo, že do třídy MV patří problém k-obarvení (zda graf lze obarvit korektně k barvami, tj. zda barevnost je < k) pro všechna k. Patří ale do třídy MV problém zjistit, zda graf G má barevnost právě k ? Pro která k ? * (7.3.5) Rozhodněte, které z následujících problémů patří do třídy MV. (Předpokládejte při tom, že negace MV -úplných problémů už nepatří do třídy MV.) A: Problém rozhodnout, zda daný graf má barevnost nejvýše čtyři. B: Problém rozhodnout, zda daný graf má barevnost přesně čtyři. C: Problém rozhodnout, zda daný graf má barevnost nejméně čtyři. D: Problém rozhodnout, zda daný graf obsahuje nejméně tři Hamiltonovské kružnice. E: Problém rozhodnout, zda daný graf obsahuje přesně tři Hamiltonovské kružnice. (7.3.6) Zdůvodněte, proč je následující problém ("orientovaná dominující množina") MV-úplný: Vstupem je orientovaný graf G a přirozené číslo k. Lze v grafu G najít podmnožinu D C V (G) s nejvýše k vrcholy takovou, že každý vrchol w grafu G náleží do D nebo do w vede orientovaná hrana (šipka) z některého vrcholu v D? 81 Návod: Použijte třeba polynomiální převod z problému vrcholového pokrytí. (7.3.7) Ukažte, že také následující problém tzv. "kubické kostry" je J\ÍV-úplný: Vstupem je jednoduchý souvislý neorientovaný graf G. Otázkou je, zde lze v grafu G najít takovou kostru, jejíž všechny vrcholy jsou stupně nejvýše 3 ? (Stupně se samozřejmě myslí v té kostře, ne v G.) Jedná se vlastně o obdobu Hamiltonovské cesty, která je kostrou, jejíž všechny vrcholy jsou stupně nejvýše 2. Návod: Použijte třeba převod z problému Hamiltonovské cesty. * (7.3.8) Ukažte, proč je následující problém MV -úplný: Vstupem je jednoduchý neorientovaný graf G. Ptáme se, zda lze v grafu G najít uzavřený tah procházející všemi vrcholy takový, že nejvýše jednou projdeme znovu jediným vrcholem, kterým jsme již prošli dříve? Pro osvětlení - u Hamiltonovské kružnice jde o uzavřený tah, který žádný vrchol nezopakuje, kdežto v našem případě je dovoleno tahem zopakovat nejvýše jednou jeden vrchol. Návod: Použijte třeba převod z problému Hamiltonovské kružnice. 7.4 Příběh problému vrcholového pokrytí Komentář: Bylo nebylo, jednou se dva slovutní informatici (při surfovaní na moři?) začali zabývat otázkou, proč dva tak „podobné" problémy jako vrcholové pokrytí a dominující množina mají (přestože oba TVP-úplné) tak rozdílné algoritmické chování... Ale dost pohádek, více konkrétních informací čtenář najde v [R. Downey and M. Fellows, Parameterized complexity, Springer f 999]. Mimo jiné se dozví, že tato zdánlivě okrajová otázka dala vzniknout zcela novému pohledu na výpočetní složitost problémů, který jde „jaksi mimo" klasickou polynomiální hierarchii a umožňuje docela rozumně řešit i některé problémy, které jsou jinak TVP-těžké. Takže v čem spočívá zásadní rozdíl v našich znalostech o řešení problémů dominující množiny a vrcholového pokrytí? • Pokud se v analýze zaměříme na hodnotu parametru k vstupu, tak dominující množinu velikosti k stejně nedokážeme nalézt rychleji než probráním prakticky všech fc-tic vrcholů grafu G. To je i pro malé fixní hodnoty k, třeba k = f 0,20 v praxi neproveditelné. • Avšak vrcholové pokrytí velikosti k dokážeme nalézt jednoduchým algoritmem v čase 0(2k ■ n), což pro malé fixní hodnoty k dává skvěle použitelný lineární algoritmus! Algoritmus 7.23. k-VC (vrcholové pokrytí) Pro fixní k vyřešíme následující problém. Vstup: Graf G. Výstup: Lze v G najít vrcholové pokrytí o velikosti nejvýše kl Pro inicializaci položíme C = 0 a F = E(G). • Pokud F = 0, vracíme C jako vrcholové pokrytí. Jinak pokud \C\ >k, vracíme odpověď NE. • Vybereme libovolnou hranu f = uv € F a pro oba její konce x = u, v uděláme: - C' = Cu{x} a F' vytvoříme z F odebráním všech hran vycházejících z vrcholu x v G. - Rekurzivně zavoláme tento algoritmus pro G, C1 a F1. 82 Kolik tento algoritmus provede rekurzivních volání celkem? Každý průchod generuje dvě další volání, ale jen do fixní hloubky k, takže ve výsledku bude čas výpočtu jen 0{2k-n). Poznámka: Dnes je již známo, že faktor 2k lze promyšlenějším přístupem „vylepšit" na mnohem menší základ mocniny. (2006: 1.2738fc) Rozšiřující studium Problematika rovinného kreslení grafů a jejich barvení je úvodně pokryta v [5, Kapitola 6]. Další informace lze nalézt na web, třeba http: //en. wikipedia. org/wiki/Graph_coloring, a jako "rozcestník" pro další studium problematiky barvení grafů dobře poslouží monograße Jensena a Tofta na stránce http://www. imada. sdu.dk/Research/Graphcol/. Více o NT'-úplnosti vybraných grafových problémů je uvedeno ještě v následujícím apendixu. Pro případné hlubší studium složitosti a NT'-úplnosti grafových problémů odkazujeme na české [3], mnohé anglické monograße teoretické informatiky nebo na další in-ternetové zdroje jako http://en.wikipedia.org/wiki/NP-complete. Co se týče specißcky parametrizované složitosti (lehce uvedené v Oddíle 7.4), lze mimo uvedenou již klasickou monograßi [Downey and Fellows, Parameterized complexity, Springer 1999] odkázat na volně dostupnou práci R. Niedermeiera "Invitation to Fixed-Parameter Algorithms" na http://www-fs.informatik.uni-tuebingen.de/~niedermr/publications/habil.ps.gz. 7.5 Cvičení: Příklady o barevnosti grafů Příklad 7.24. Určete a zdůvodněte barevnost tohoto grafu: # Vidíme, že obvodová kružnice tohoto grafu má délku 5, což je liché číslo, a proto je potřeba na její korektní obarvení použít aspoň tři barvy 1,2,3. Pak je ale středový vrchol spojený s každou z těchto barev 1,2,3, tudíž pro něj potřebujeme čtvrtou barvu 4. 'ú: To znamená, že daný graf má barevnost 4. □ Příklad 7.25. Kolik nejméně hran musíte vypustit z úplného grafu na 7 vrcholech, aby se výsledný graf dal korektně obarvit dvěma barvama? Musíme vypustit všechny hrany mezi vrcholy, kterým chceme dát stejnou barvu, aby výsledné obarvení bylo korektní. Jelikož všechny vrcholy úplného grafu jsou si ekvivalentní, stačí se rozhodnout, kolik z nich dostane barvu 1 a kolik barvu 2. Jak snadno zjistíme, optimální je barvy rozdělit napůl, tj. 3 a 4 v tomto případě. Je tedy potřeba vypustit nejméně (g) + (2) = 3 + 6 = 9 hran. 83 D Úlohy k řešení (7.5.1) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. (7.5.2) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. (7.5.3) Obarvěte následující graf na 8 vrcholech třemi barvami 1,2,3 tak, aby se barva 3 použila co nejvíce krát. (7.5.4) Obarvěte následující graf na 9 vrcholech třemi barvami 1,2,3 tak, aby se barva 3 použila co nejméně krát. (7.5.5) Jaká může být barevnost grafu, který vznikne z úplného grafu na 15 vrcholech vypuštěním tří hran? (Je to jednoznačné?) * (7.5.6) Dokažte, že na obarvení grafu vzniklého z libovolného stromu přidáním dvou libovolných nových hran vždy stačí 3 barvy. 7.6 Apendix: Další J\ÍV-úp\né grafové problémy V tomto (nepovinném) dodatku si jednak probereme další příklady polynomiálních převodů mezi některými základními grafovými problémy. Za druhé si ukážeme, jak u různých problémů poznat, zda náleží do třídy NV nebo ne a zda případně jsou MV-úplné. Jelikož se jedná o látku značně vzdálenou klasické teorii grafů, čtenáři bez zájmu o informatické aplikace ji mohou klidně přeskočit. Polynomiální převody grafových problémů Komentář: Neformálně řečeno, polynomiálním převodem problému P\ na problém P2 nazveme postup, který v polynomiálním čase ze známého způsobu řešení problému P2 „získá" řešení pro problém P\. Příklad 7.26. Problém nezávislé množiny se ptá, zda v grafu existuje podmnožina k vrcholů nespojených žádnými hranami. Problém vrcholového pokrytí se ptá, zda v 84 grafu existuje podmnožina m vrcholů dotýkajících se všech hran. (Vrchol se dotýká hrany, pokud je jejím koncem.) Ukažme si podrobně, jak se problém nezávislé množiny polynomiálně převede na problém vrcholového pokrytí. Nejprve si ujasněme, co je vstupem a výstupem kterého problému. Pro nezávislou množinu je vstupem dvojice G, k, kde G je graf a k přirozené číslo. Pro vrcholové pokrytí je obdobně vstupem dvojice G, m. (V případě nezávislé množiny se přirozeně snažíme dostat co největší vyhovující k, kdežto u vrcholového pokrytí co nejmenší m.) V obou případech se jedná o rozhodovací problémy, takže odpovědí je ANO/NE. Všimněme si následujícího jednoduchého faktu: Pokud / C V (G) je nezávislá množina v grafu G, pak žádná hrana G nemá oba konce v I. To ale znamená, že doplněk množiny J = V (G) \I se dotýká všech hran grafu G, a tudíž J je vrcholovým pokrytím. Pokud \I\ = k, pak \J\ = \V(G)\ — k = m. Naopak doplňkem vrcholového pokrytí J je ze stejného důvodu nezávislá množina / = V(G) \ J. Příklad je na následujícím obrázku. (Zakreslete si to také do některého vlastního grafu.) nezávislá množina vrcholové pokrytí Takže stačí vstup G, k problému nezávislé množiny převést na vstup G,m, m = \V(G)\ — k problému vrcholového pokrytí, ze kterého už získáme správnou odpověď i na původní problém. Tento převod dokonce spočítáme v konstantním čase, jen provedeme jedno odečtení. (Všimněme si ještě jedné zajímavosti - při našem převodu se vůbec nezměnil graf G, jen číslo k na m, ale to je pouze specifickou vlastností tohoto jednoduchého převodu. Ve složitějších případech však dochází ke změně celého vstupu, včetně grafu.) □ Příklad 7.27. Problém dominující množiny se ptá, zda v grafu existuje podmnožina m vrcholů taková, že každý jiný vrchol je s některým z nich spojený hranou. Ukažme si podrobně, jak se problém vrcholového pokrytí polynomiálně převede na problém dominující množiny na souvislých grafech. Definice dominující množiny je velmi podobná vrcholovému pokrytí, že? Vlastně by mělo stačit jaksi ke každé hraně daného grafu G (ve kterém hledáme vrcholové pokrytí) přiřadit nějaký nový vrchol, který bude třeba po převodu dominovat. Abychom se vyhnuli patologickým případům, předpokládáme souvislé grafy s více než jedním vrcholem. Začneme jednoduchou ukázkou, jak třeba dominující množina může vypadat. (Dokážete odpovědět, proč graf z obrázku nemá dominující množinu velikosti 2?) Nyní přejdeme k popisu naznačeného převodu ze vstupu G, m problému vrcholového pokrytí na vstup H, m' problému dominující množiny. 85 ®--------------------® (sr-----------------------• Graf H vytvoříme z grafu G přidáním, pro každou hranu e € E (G), nového vrcholu ve spojeného hranami do obou koncových vrcholů hrany e. (Tak se vlastně z každé hrany stane trojúhelník s třetím novým vrcholem, viz naznačený obrázek.) Číselný parametr m' = m zůstane tentokrát nezměněn. Abychom zdůvodnili, že se skutečně jedná o převod problémů, musíme dokázat implikace v obou směrech: Ze vrcholové pokrytí C C V (G) je zároveň dominující množinou v novém grafu H a že dominující množina D C V (H) vytváří i stejně velké vrcholové pokrytí v původním grafu G. První část je snadná, podle definice vrcholového pokrytí každá hrana e grafu G má některý konec u v množině C, takže jak druhý konec hrany e, tak i nově přidaný vrchol ve v grafu H jsou dominovány z vrcholu u € C. Navíc z předpokladu souvislosti G plyne, že žádné další izolované vrcholy v H nejsou, takže C je zároveň dominující množinou v H. Naopak vezměme dominující množinu D C V (H) v novém grafu H. (Pozor, nelze hned říci, že by D byla vrcholovým pokrytím v G, neboť D může obsahovat přidané vrcholy, které v G nebyly.) Definujeme novou množinu D' C V (G) takto: Pokud w € D n V (G), pak w € D'. Jinak pro w € D, kde w = ve byl přidán pro hranu e € E (G), dáme do D' libovolný z konců hrany e. Potom \D'\ < \D\ a D' je vrcholovým pokrytím v původním grafu G, neboť pro každou hrany e € E (G) je přidaný vrchol ve € V (H) dominován v grafu H množinou D, a tudíž hrana e bude mít některý konec v D'. Dokázali jsme tedy, že se jedná o převod problému, a zbývá zdůvodnit, že tento převod je spočítán v polynomiálním čase. Pokud G má n vrcholů, má nejvýše 0{n2) hran, a proto nový graf H má velikost 0{n2) a v takovém čase jsme snadno schopni jej sestrojit. Je to polynom v n. □ Problémy ve třídě J\fP Nyní se budeme věnovat otázkám, proč některé grafové problémy náleží či nenáleží do třídy NV. Komentář: Definice třídy AÍVse týká výhradně rozhodovacích problémů (s „ANO/NE" odpovědí). Dá se neformálně říci, že problém patří do třídy J\ÍV, pokud jeho odpověď ANO lze prokázat (ve smyslu "uhodnout a ověřit") výpočtem, který běží v polynomiálním čase. Příklad 7.28. Hamiltonovska kružnice v grafu G je takový podgraf, který je isomorfní kružnici a přitom obsahuje všechny vrcholy G. (Jinak řečeno, kružnice procházející každým vrcholem jednou.) Proč patří do třídy MV problém poznat, zda daný graf G obsahuje Hamiltonovskou kružnici? Jak již bylo řečeno výše u definice, třída NV je vlastně třídou těch problémů, kde odpověď ANO lze ověřit efektivně s vhodnou nápovědou. Jestliže se ptáme na existenci Hamiltonovska kružnice v grafu G, přirozeně se jako nápověda nabízí právě ona kružnice. Pro ilustraci ukazujeme příklady dvou grafů, kde v prvním je Hamiltonovska kružnice 86 vyznačena tlustě, kdežto ve druhém neexistuje. # Jak ale Hamiltonovskou kružnici popíšeme a jak ověříme, že se skutečně jedná o Hamiltonovskou kružnici? Obojí musíme zvládnout v polynomiálním čase! Jako popis Hamiltonovske kružnice se přirozeně nabízí zadat tu permutaci vrcholů grafu G, v jejímž pořadí dotyčná kružnice vrcholy prochází. (Tím neříkáme, že by nebyly jiné způsoby popisu, jen že tento se nám hodí.) Takže nápovědu zadáme jednoduše polem k[] délky n, kde n je počet vrcholů G. Pro ověření, že se jedná o Hamiltonovskou kružnici, stačí zkontrolovat, že k[i] / k[j] pro různá i, j a že vždy {k[i\, k[i + í\} je hranou v grafu G pro i = 1,2,...,n — 1 a také {k[í\, k[n]} je hranou. Při vhodné implementaci maticí sousednosti grafu G to zvládneme vše zkontrolovat v lineárním čase, ale i při jiných implementacích nám stačí čas n ■ 0(n) = 0(n2), což je skutečně polynomiální. Proto problém existence Hamiltonovske kružnice patří do třídy MV. □ Příklad 7.29. Patří do třídy NV problém poznat, zda daný graf G obsahuje nejvýše čtyři Hamiltonovske kružnice? Čtenář opět může navrhnout, že vhodnou nápovědou pro příslušnost do třídy NV jsou ony čtyři Hamiltonovske kružnice v grafu. To lze přece snadno ověřit stejně jako v předchozím příkladě. Skutečně tomu tak je? Není]!! My sice dokážeme ověřit, že napověděné čtyři kružnice v grafu jsou Hamiltonovske, ale nijak tím neprokážeme, že více Hamiltonovských kružnic v grafu není. Takové ověření by nakonec bylo stejně obtížné, jako nalezení Hamiltonovske kružnice samotné. Proto na základě současných znalostí teoretické informatiky nelze tvrdit, že by popsaný problém náležel do třídy NV. Avšak pokud bychom otázku negovali, tj. ptali se, zda graf G obsahuje více než čtyři Hamiltonovske kružnice, tak by už problém do třídy MV náležel. (Napověděli bychom některých pět Hamiltonovských kružnic.) Proto vidíte, jak je důležité správně se v zadání problému ptát. □ A/^P-úplnost a její důkazy Dále si zopakujme stručný neformální návod, jak by vlastně běžný polynomiální převod pro zdůvodnění WP-úplnosti problému měl vypadat... Komentář: Dle definice je TVP-úplný problém takový, že jeho efektivní vyřešení v polynomiálním čase by poskytlo podobná řešení i pro všechny ostatní problémy ve třídě MV. Předpokládejme, že o problému P již víme, že je TVP-úplný, a o problému Q to chceme dokázat. Neboli chceme ukázat, že každý vstup problému P bychom uměli rozřešit převodem na případ problému Q, a tudíž i problém Q musí být tak těžký jako P. Takže v jednoduchých případech stačí vzít obecný (libovolný) vstup V známého těžkého problému P a "přeložit" jej na vstup Li pro problém Q tak, že Q odpoví ANO na nový vstup Li právě tehdy, když P odpověděl ANO na V. (Všimněte si dobře, že musíte dokázat logickou ekvivalenci, tedy že z odpovědi ANO v Q vyplývá ANO v P i naopak!) Příklad 7.30. Problém k-obarvení grafu se ptá, zda daný graf lze obarvit k barvami tak, aby žádná hrana nespojovala dva vrcholy stejné barvy. (Skutečná barevnost 87 našeho grafu může být i menší než k, o to v problému nejde.) Dokažme, že problém k-obarvení je NV-úplný pro každé (i fíxní) k > 3. Nejprve musíme zdůvodnit, že problém patří do třídy NV. To je snadné, neboť nápovědou nám je ono obarvení grafu G pomocí k barev. Napověděné obarvení snadno zkontrolujeme v počtu kroků úměrném počtu hran grafu G, tedy polynomiálně v počtu vrcholů bez ohledu na hodnotu k. Na druhou stranu už víme z Problému 7.16, že 3-obarvení grafu je MV-úplné. Stačí nám tedy nalézt polynomiální převod z problému 3-obarvení na problém fc-obarvení grafu. Předpokládejme tedy, že k > 3 a že je dán graf G, o kterém se ptáme, zda jej lze obarvit 3 barvami. My sestrojíme graf G' přidáním k — 3 nových vrcholů ke grafu G spojených každý se všemi ostatními vrcholy. Proč to děláme? To je zřejmé, v grafu G' všechny nově přidané vrcholy musí mít různých barvu od všech ostatních, takže pokud původní graf G šel obarvit 3 barvami, půjde tak i graf G' obarvit k barvami. Naopak pokud G' je obarven k barvami, všechny barvy nových k — 3 vrcholů jsou jiné a různé od barev všech původních vrcholů, takže na původní vrcholy G nám zbudou jen k — (k — 3) =3 různé barvy, což je přesně problém 3-obarvení na G. (Neboli 3-obarvení G jednoznačně odpovídají fc-obarvením G1.) Schematickým obrázkem: 1,2,3 Vidíme tedy, že jsme našli polynomiální převod ze 3-obarvení grafu G na fc-obarvení grafu G', a proto je problém fc-obarvení NV-iěžký. Celkem dostáváme, že fc-obarvení je WP-úplné. □ Příklad 7.31. Hamiltonovska cesta v grafu je takový podgraf, který je isomorfní cestě a prochází všemi vrcholy grafu. (Obdoba Hamiltonovské kružnice.) Dokažme, že problém zjištění existence Hamiltonovské cesty v daném grafu G je NV-úplný. Již víme z Problému 7.21, zjištění existence Hamiltonovské kružnice je AAP-ůplné. Problém Hamiltonovské cesty taktéž náleží do AÍV, snadnou nápovědou existence je ukázat onu Hamiltonovskou cestu. Pro důkaz WP-ůplnosti využijeme polynomiální převod Hamiltonovské kružnice na Hamiltonovskou cestu. Názorně řečeno, potřebujeme převést daný graf G na jiný graf H tak, že Hamiltonovska kružnice v G se stane Hamiltonovskou cestou v H a naopak. Na první pohled by se toto zdálo jako snadný cíl - přece z každé Hamiltonovské kružnice uděláme cestu odebráním hrany či vrcholu. Velký problém je však v onom slůvku "naopak", my také musíme zajistit, že každá Hamiltonovska cesta v H vytvoří Hamiltonovskou kružnici v G! Proto nějakým způsobem musíme fixovat počátek a konec Hamiltonovské cesty v H tak, aby se daly spojit do kružnice v G. Jednou z možností je vybrat jakýkoliv vrchol v v G, "zdvojit" jej (tj. přidat další vrchol se stejnými sousedy jako v) a navíc ke každé v% ze zdvojených kopií v přidat novou hranu vedoucí do nového vrcholu w% stupně 1. Tyto přidané vrcholy to1,«;2 pak nutně musí být konci Hamiltonovské cesty, pokud ona existuje (jinak se do vrcholů stupně 1 přece dostat nedá). 88 Schematickým obrázkem: D Příklad 7.32. Pro jaké k je NV-úplný problém zjistit, zda v daném grafu existuje nezávislá množina velikosti k? (Nezávislá množina je taková podmnožina vrcholů grafu, z níž žádné dva její vrcholy nejsou spojené hranou.) Je tento problém MV-úplný pro fíxník nebo pro proměnné hodnoty k? Tento příklad uvádíme proto, aby si čtenář dobře uvědomil roli parametrů problému, které jsou fixní, a těch, které jsou proměnlivé, neboli dané na vstupu. Problém existence nezávislé množiny velikosti k totiž snadno rozřešíme v čase 0{nk+l) - prostě projdeme hrubou silou všechny fc-tice vrcholů grafu a pokaždé se podíváme, zda náhodou netvoří nezávislou množinu. Čas 0(nk+1) je pochopitelně polynomiální pro každé fixní k, takže pak tento problém těžko může být MV-úphiý. Naopak pro k na vstupu problému se jedná o WP-ůplný problém podle našeho Tvrzení 7.17. □ Úlohy k řešení (7.6.1) Analogicky k Příkladu 7.26 ukažte převod problému vrcholového pokrytí na nezávislou množinu. (Tj. opačný směr.) (7.6.2) Párováním v grafu rozumíme podmnožinu hran, které nesdílejí žádný svůj koncový vrchol. Jak byste polynomiálně převedli problém nalezení párování velikosti p v grafu G na problém nezávislé množiny? * (7.6.3) Dokážete najít převod problému dominující množiny na vrcholové pokrytí? (Tj. opačný směr k Příkladu 7.27.) * (7.6.4) Patří do třídy MV problém zjistit, zda graf G obsahuje právě jedinou Hamiltonovskou kružnici? A co třeba negace tohoto problému? (7.6.5) Sice už víme, že jak Hamiltonovská kružnice, tak i Hamiltonovská cesta jsou J\fV-úplné, ale zkuste cvičně najít polynomiální převod Hamiltonovské cesty na Hamiltonovskou kružnici (naopak než v Příkladě 7.31). 89 8 Rovinnost a kreslení grafů Úvod V přímé návaznosti na předchozí Lekci 7 se zaměříme na druhý důležitý aspekt slavného problému čtyř barev; na otázku kreslení grafů do roviny bez křížení. Jak tedy taková obarvovaná politická mapa souvisí s kreslením grafů ? Jednoduše - souvislé státy můžeme reprezentovat jako vrcholy grafu a hranami pak zaznamenat „soused-nost" mezi státy. Důležité je, že takto vzniklý graf můžeme zřejmě zakreslit v rovině bez křížení hran a nazýváme jej proto rovinným grafem. V našem výkladu si uvedeme (a zčásti odvodíme) základní vlastnosti rovinných grafů a sdělíme něco málo o kreslení grafů obecněji. Cíle Prvním cílem je deßnovat rovinné grafy a přehledově ukázat jejich vlastnosti, především ve vztahu k jejich barevnosti a ke geometrii. Mimo jiné se naučíme rovinné grafy rozpoznávat podle Kuratowského věty. Za druhé si řekneme o obarvování rovinných grafů a v závěru uvedeme poznatky o kreslení nerovinných grafů do roviny s co nejmenším počtem křížení (tzv. průsečíkové číslo). 8.1 Rovinné kreslení grafu Dalším důležitým grafovým pojmem úzce svázaným s problémem čtyř barev je rovinné nakreslení, tj. nakreslení bez překřížených hran. Komentář: Jen málokteré grafy rovinné nakreslení mají, ale důležitost grafů s rovinným nakreslením je motivována jak esteticky (nakreslení bez křížení hran vypadají hezky a jsou snadno čitelná), tak jejich teoretickým významem i praktickými aplikacemi (představme si jednostranný plošný spoj jako graf obvodu - hrany při jeho realizaci fyzicky nemůžeme křížit bez drátových propojek). Definice 8.1. Rovinným nakresleni grafu G myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body v rovině a hrany jako oblouky (čili jednoduché křivky) spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. Graf je rovinný pokud má rovinné nakreslení. Komentář: Důležitým příkladem rovinných grafů jsou grafy (třírozměrných Euklidovských) mnohostěnů, třeba graf čtyřstěnu, krychle, osmistěnu, dvanáctistěnu, atd. A Platí, že grafy mnohostěnů jsou vždy rovinné a 3-souvislé. Naopak každý rovinný 3-souvislý jednoduchý graf je grafem nějakého mnohostěnu. (Důkaz tohoto tvrzení je obtížný.) Geometrický příklad grafů mnohostěnů také přináší část terminologie rovinných kreslení a hlavně motivuje důležitý a slavný Eulerův vztah (Věta 8.2). 90 Definice: Stěnami rovinného nakreslení grafu nazýváme (topologicky) souvislé oblasti roviny ohraničené tímto nakreslením grafu. Komentář: Rovinný graf může mít více podstatně různých nakreslení, jak vidíme na uvedeném ilustračním obrázku, ale platí, že 3-souvislý rovinný graf má ve všech svých rovinných nakresleních „stejné stěny" (Důsledek 8.11). To intuitivně znamená, že ze znalosti grafu mnohostěnu můžeme odvodit přibližný tvar původního tělesa. Podívejte se zpět na konstrukci použitou v Příkladě 7.4 - oblasti, neboli stěny, mapy jsme nahrazovali vrcholy nového grafu a spojovali jsme hranami sousedící dvojice oblastí. Tuto konstrukci lze formálně zobecnit na stěny nakreslení libovolného rovinného grafu: Definice. Duální (multi)graf rovinného nakreslení grafu G získáme tak, že stěny nahradíme vrcholy duálu a hranami spojíme sousedící dvojice stěn. Komentář: Duální multigraf k rovinnému grafu je vždy rovinný, což je relativně snadné dokázat topologicky. Na druhou stranu však často bude obsahovat násobné hrany a dokonce i smyčky. Uvědomte si dobře, že počet hran duálního grafu je stejný jako u primárního grafu. Pro příklad odvození duálního grafu se podívejme na obrázek: Úlohy k řešení (8.1.1) Nakreslete rovinně tento graf: tŤh (8.1.2) Co je duálním grafem k rovinnému nakreslení grafu krychle? (8.1.3) Dokažte, že graf každého 3D konvexního mnohostěnu je rovinný. "(8.1.4) Dokažte, že graf každého 3D konvexního mnohostěnu je 3-souvislý. 8.2 Eulerův vztah o počtu stěn Nyní si uvedeme zajímavý a vlastně „jediný rozumný kvantitativní" vztah o rovinných nakresleních grafů. Jedná se o slavný Eulerův vztah, který říká: Věta 8.2. Nechť rovinné nakreslení neprázdného souvislého grafu G má f stěn. Pak \V{G)\+f-\E{G)\=2. Důkaz: Nechť počet vrcholů v G je v a hran h. Důkaz této důležité věty pouze naznačíme, detaily lze najít v literatuře. 91 • Pokud je G strom, tj. nemá kružnice, má ve svém nakreslení jedinou stěnu a dle Věty 4.3 má přesně h = v — 1 hran. Potom platí v + f — h = v + 1 — (v — 1) = 2. • Pokud G obsahuje kružnici C, pak vypustíme jednu její hranu e. Tím se počet hran sníží o 1, ale zároveň se sníží o 1 počet stěn, protože kružnice C původně oddělovala (viz Jordánova věta o kružnici) dvě stěny přilehlé k hraně e od sebe, ale nyní tyto dvě stěny „splynou" v jednu. Počet vrcholů se nezmění. Proto se nezmění hodnota v + / - h = v + (/ - 1) - {h - 1) = 2. Tvrzení tak plyne z principu matematické indukce. □ Poznámka: Všimněte si dobře, že Eulerův vztah vůbec nezávisí na tom, jak je graf G nakreslený, je to vlastnost grafu jako takového. Tento jednoduše vypadající vztah má mnoho aplikací a důsledků, z nichž část si uvedeme i dokážeme. Důsledek 8.3. Jednoduchý rovinný graf na v > 3 vrcholech má nejvýše 3v — 6 hran. Jednoduchý rovinný graf na v > 3 vrcholech a bez trojúhelníků má nejvýše 2v — 4 hran. Důkaz: Můžeme předpokládat, že graf je souvislý, jinak bychom přidali další hrany. Nechť počet vrcholů v G je v, stěn je / a hran h. Jelikož nemáme smyčky ani násobné hrany, má každá stěna v nakreslení grafu na obvodu aspoň 3 hrany, přitom každou hranu započítáme ve dvou přilehlých stěnách. Pak tedy platí h> \ -3/, neboli \h> f. Dosazením do vztahu Věty 8.2 získáme 2 1 2 = v + f — h < v + -h — h = v — -h h<3(v-2) =Sv-6. Druhá část se dokazuje obdobně, ale nyní víme, že graf nemá ani trojúhelníky, a tudíž má každá stěna v nakreslení grafu na obvodu aspoň 4 hrany. Pak tedy platí h > \ ■ 4/, neboli jh > f. Dosazením do vztahu Věty 8.2 získáme 2 1 2 = v + f — h < v + -h — h = v-----h h<2(v-2) =2v-4. Tím jsme hotovi. □ Důsledek 8.4. Každý jednoduchý rovinný graf obsahuje vrchol stupně nejvýše 5. Každý jednoduchý rovinný graf bez trojúhelníků obsahuje vrchol stupně nejvýše 3. Důkaz: Pokud by všechny vrcholy měly stupně alespoň 6, celý graf by měl aspoň \ ■ 6v = 3v hran, což je ve sporu s Důsledkem 8.3. Některý vrchol musí tudíž mít menší stupeň než 6. Obdobně postupujeme u druhého tvrzení. □ Úlohy k řešení (8.2.1) Graf pravidelného dvacetistěnu má 12 vrcholů a 20 stěn. Kolik má hran? (8.2.2) K rovinnému nakreslení stromu přidáme dvě nekřížící se hrany. Kolik bude mít výsledný graf stěn ? * (8.2.3) Jak bude znít Eulerův vztah pro nesouvislý rovinný graf s k komponentami? 92 8.3 Rozpoznání rovinných grafů Při praktickém využití rovinných grafů je potřeba umět abstraktně zadaný graf rovinně nakreslit bez křížení hran. Na rozdíl od problému určení barevnosti grafu se naštěstí jedná o efektivně algoritmicky řešitelný problém. První algoritmus běžící v lineárním čase byl podán Hopcroftem a Tarjanem 1974 a od té doby se objevilo několik jednodušších algoritmů, ale stále nejsou dostatečně přístupné, abychom je mohli ukázat v omezeném čase na přednášce. Věta 8.5. Rozhodnout rovinnost a nalézt příslušné nakresleni daného grafu lze v lineárním čase (vůči počtu vrcholů). Místo obecných algoritmů pro rovinné kreslení grafů se zde podíváme na otázku, jak odůvodnit nerovinnost (malého) grafu. Příklad 8.6. Ukažme, že následující dva grafy, Ks a K33 nejsou rovinné. Při zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf Ks má 5 vrcholů a 10 > 3 • 5 — 6 hran. Podobně graf ÍÍ33 má 6 vrcholů a 9 > 2 • 6 — 4 hran, přitom neobsahuje žádné trojúhelníky. Proto podle Důsledku 8.3 žádný z nich není rovinný. (Pokud by byl rovinný, počet jeho hran by musel být menší, než skutečně je.) D Důsledek 8.7. Grafy K$ a Ksts nejsou rovinné. Význam grafů K$ a Ks^ uvedených v předchozím důsledku spočívá v tom, že jsou to „nejmenší" nerovinné grafy ve velmi silném významu slova nejmenší - každý další nerovinný graf jeden z nich „obsahuje". Pro uvedení takového popisu rovinných grafů ještě potřebujeme jednu definici. Definice: Podrozdělením grafu G rozumíme graf, který vznikne z G nahrazením některých hran novými cestami libovolné (kladné) délky. Důležitý abstraktní popis všech rovinných grafů nalezl K.Kuratowski: Věta 8.8. Graf G je rovinný právě když neobsahuje podrozdělení grafů K$ nebo Ksts jako podgrafy. Poznámka o rozpoznání nerovinnosti grafu: Pokud chceme ukázat, že daný graf je rovinný, prostě jej nakreslíme v rovině bez křížení hran. Předchozí věta nám naopak dává spolehlivý způsob, jak ukázat, že daný graf není rovinný - prostě v něm najdeme podrozdělení grafů Ks nebo Ä3,3- (Ve skutečnosti tuto obtížnou větu ani nepotřebujeme ke zdůvodnění nerovinnosti, stačí nám Důsledek 8.7. Věta 8.8 nám jen říká, že příslušná podrozdělení vždy v nerovinných grafech najdeme.) Pro praktické použití věty dodáme, že až na vzácné výjimky se lépe v nerovinných grafech najde podrozdělení grafu ÍÍ33 než grafu Ks- 93 Příklad 8.9. Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholu), nebo zdůvodněte nerovinnost grafu. Po chvíli zkoumání určitě přijdeme na to, že graf A se dá nakreslit rovinně takto: ' W. .A. Graf B na druhou stranu rovinný není podle Věty 8.8, protože je v něm obsaženo podrozdělení grafu K33,, které je ukázáno na tomto obrázku: D Jednoznačnost rovinného nakreslení Již jsme neformálně zmiňovali, že rovinná nakreslení téhož grafu mohou být podstatně různá, ale pro 3-souvislé grafy je tomu jinak. Nyní si tento poznatek zpřesníme. Fakt: V 2-souvislém rovinném grafu je každá stěna ohraničená kružnicí. Díky tomuto faktu lze snadno nadefinovat, že dvě rovinná nakreslení 2-souvislého grafu jsou ekvivalentní, pokud jejich stěny tvoří stejné soubory kružnic. Klíčovým výsledkem nyní je: Lenia 8.10. Kružnice C v 3-souvislém rovinném grafu G je stěnou jeho nakresleni, právě když podgraf G — V (C) je souvislý graf. Důkaz: V jednom směru, pokud G' = G — V (C) je souvislý, pak podle Jordánovy věty o kružnici leží celý G' uvnitř jedné oblasti C, tudíž druhá oblast C je stěnou v každém nakreslení G. Naopak pokud C ohraničuje stěnu v některém rovinném nakreslení grafu G, dokážeme, že každé dva vrcholy mimo C lze spojit cestou disjunktní s C. Nechť tedy x,y G V (G) \ V(C) a označme X (či Y) množinu těch vrcholů C dosažitelných z x (z y) po cestách neprocházejících přes C. Jelikož x,y náleží stejné stěně kružnice C, množiny X,Y se na C „nepřekrývají", přesněji je lze od sebe oddělit odebráním některých dvou vrcholů c, d € V {C). Pak však {c, d} je řezem v grafu G oddělujícím a; od y a to odporuje předpokladu 3-souvislosti, spor. □ Důsledek 8.11. Každá dvě rovinná nakreslení 3-souvislého grafu jsou ekvivalentní. 94 Zajímavou aplikací Důsledku 8.11 je algoritmus pro rozpoznávání isomorfizmu rovinných grafů, který mimo porovnávání rovinných nakreslení 3-souvislých komponent používá metody rozkladu grafu na "více-souvislé" komponenty a testování isomorfizmu stromů: Věta 8.12. Problém isomorfizmu rovinných grafů je řešitelný v lineárním čase. Závěrem si ještě bez důkazu uvedeme, že rovinné grafy vždy mají pěkné nakreslení v rovině. Věta 8.13. Každý jednoduchý rovinný graf lze nakreslit v rovině (bez kříženi hran) tak, že hrany jsou úsečky. Úlohy k řešení (8.3.1) Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholu), nebo zdůvodněte nerovinnost grafu. M, (8.3.2) Pro která n je úplný graf Kn rovinný? (8.3.3) Kdy je úplný bipartitní graf Kmn rovinný? (8.3.4) Kolik hran stačí přidat ke kružnici, aby vznikl nerovinný graf? 8.4 Barvení map a rovinných grafů Komentář: Vzpomeňme si na již zmiňovaný převod mapy na graf - jedná se vlastně o vytvoření duálního grafu k této mapě (strana 91). Aby v duálním grafu k mapě nevznikly smyčky, v mapě nesmí žádný stát sousedit sám se sebou, což je přirozený požadavek. V roce 1976 Appel a Haken, a pak znovu v roce 1993 Robertson, Seymour, Sanders a Thomas, dokázali tuto větu, která rozřešila problém čtyř barev a která je jedním z nejslavnějších výsledků diskrétní matematiky vůbec: Věta 8.14. Každý rovinný graf bez smyček lze obarvit 4 barvami. Důkaz této věty je nesmírně složitý (však byl také hledán po více než 100 let a k jeho úplnému provedení je stále třeba počítač), a proto si uvedeme slabší a mnohem jednodušší tvrzení: Tvrzení 8.15. Každý rovinný graf bez smyček lze obarvit 6 barvami. Každý rovinný graf bez smyček a bez trojúhelníků lze obarvit 4 barvami. Důkaz: Podle Důsledku 8.4 najdeme v každém podgrafu G vrchol v stupně nejvýše 5, a tudíž je G 5-degenerovaný a obarvíme jej podle Věty 7.6. Druhou část dokážeme obdobně, když nalezneme vrchol stupně < 3. □ Už dávno je přitom známo, že staré neúspěšné pokusy o důkaz problému čtyř barev ukazují alespoň, že barevnost rovinných grafů je nejvýše 5. Asi nejhezčí důkaz tohoto faktu [Thomassen] dokazuje indukcí mnohem více (a je v tom ohledu optimální): Věta 8.16. Každý rovinný graf bez smyček má výběrovou barevnost nejvýše 5. 95 Důkaz (náznak): Poměrně přímočarou indukcí lze dokázat následující zesílené tvrzení: Nechť rovinný graf G s vnější stěnou ohraničenou kružnicí C má všechny ostatní stěny trojúhelníky. Nechť každý vrchol mimo C má přiřazen seznam 5 barev, vrcholy C mají seznamy 3 barev a jisté dva sousední vrcholy x,y na C mají přímo předepsané (různé) barvy. Pak G lze výběrově obarvit. • Nechť z 7^ y je druhý soused x na C. Pokud některá hrana f ze z nenáležející C má druhý konec také na C, pak podél / „rozdělíme" G na podgraf G\ obsahující x,y & podgraf G2 sdílející hranu / s G\. Indukcí nejprve obarvíme G\, pak G2 taktéž splní indukční předpoklad a i jej dobarvíme. • Jinak budeme indukcí barvit podgraf G3 = G — z; přičemž všem sousedům z uvnitř G odebereme ze seznamu (jejich pěti) barev dvě z barev seznamu u vrcholu z různé od barvy x. Následně dobarvíme vrchol z, pro nějž máme tři možnosti a jen jeho dva sousedé na C s ním mohou být v konfliktu. D Úlohy k řešení (8.4.1) Jaká je barevnost grafu pravidelného dvacetistěnu? *(8.4.2) Nechí rovinný graf má každou stěnu délky 4. Jaká je jeho barevnost? Dokažte. (8.4.3) Předpokládejme, že každý vrchol rovinného grafu leží na vnější stěně. Dokažte, že pak je jeho barevnost nejvýše 3. * (8.4.4) Dokážete najít rovinný graf, jehož výběrová barevnost je 5? (8.4.5) Proč každý rovinný graf na f 3 vrcholech musí obsahovat nezávislou množinu velikosti 4? 8.5 Praktické „pružinové" kreslení grafů Závěrem se podívejme na trochu jinou problematiku - jak prakticky nakreslit daný (nerovinný) graf, aby vše „vypadalo hezky". Jeden ze základních heuristických přístupů ke kreslení grafů se dá shrnout následovně: Metoda 8.17. Pružinové kreslení grafu • Vytvoříme „fyzikální" model grafu, kde vrcholy budou kuličkami, které se vzájemně odpuzují, a hrany budou pružinami, které své koncové vrcholy vzájemně přitahují. • Náš model budeme iterovat jako dynamický systém, až do konvergence pozic vrcholů. Zde je potřebné modelovat i „tlumení" pohybů vrcholů, aby nedošlo k rozkmitání systému. • I když kreslíme graf do roviny, je užitečné začít modelovat systém s dimenzí navíc (aby měly vrcholy „více místa k pohybu") a teprve v průběhu času dodatečnou silou přidanou dimenzi „eliminovat", neboli zkonvergovat pozice vrcholů do zvolené roviny. Rozšiřující studium Problematika rovinného kreslení grafů a jejich barvení je úvodně pokryta v [5, Kapitola 6]. Zájemce o přístupný český popis (poněkud pomalejšího, kvadratického) algoritmu na rovinné kreslení odkazujeme na [3]. Jeden z existujících lineárích algoritmů na rovinné kreslení je vysvětlen třeba na http: //www. math. gatech. edu/~thomas/planarity. ps. Zábavné hraní si s rovinností grafů je pak k dispozici na http: //www. planarity. net/. 96 Zájemci o podrobný popis historie i náznaku řešení problému čtyř barev si mohou přečíst přímo http://www.math.gatech.edu/~thomas/FC/fourcolor.html. K pružinovému modelu kreslení grafů ("spring layout") existuje na webu mnoho popisů i dostupných implementací, i když ne vždy kvalitních, dokonce i mezi demonstračními aplety Javy na http://Java.sun.com/applets/jdk/1.4/. 8.6 Cvičení: Příklady na rovinnost grafů Příklad 8.18. Kolik nejméně hran je třeba vypustit z následujícího 8-vrcholového grafu, aby vznikl rovinný graf? Zdůvodněte. Nejprve se podíváme, zda náš graf náhodou není rovinný. To ale není, protože zde vidíme v něm obsažené podrozdělení 1^3,3: Tento obrázek zároveň ukazuje ještě jednu zajímavost - náš graf nebude rovinný, ani když vypustíme libovolnou z "tětiv" obvodové kružnice. Na druhou stranu není těžké objevit, že stačí vypustit třeba pravou svislou hranu a získáme rovinné nakreslení: Stačí tedy vypustit jednu hranu a získáme rovinný graf. □ Úlohy k řešení (8.6.1) Je tento graf rovinný? (8.6.2) Je tento graf rovinný? 97 (8.6.3) Kolik nejvýše hran lze přidat do následujícího grafu na 8 vrcholech, aby ještě zůstal rovinný a jednoduchý? (8.6.4) Kolik nejvýše hran lze přidat do následujícího grafu na 9 vrcholech, aby ještě zůstal rovinný a jednoduchý? (8.6.5) Vezměme libovolný rovinný graf s 18 hranami a 10 stěnami. Kolik má takový graf vrcholů ? (8.6.6) Kolik nejméně hran je nutno odebrat z úplného grafu Kj, aby se stal rovinným? "(8.6.7) Dokažte, že rovinný graf, jehož každá stěna je trojúhelník, musí být 3-souvisIý. (8.6.8) Je možné, aby rovinný 2-souvislý graf na 1000 vrcholech měl více než 1000 neekvivalentních nakreslení (s jinými soubory stěnových kružnic)? 98 Část III Vybrané Pokročilé Partie Na tomto místě začíná poslední část našeho studijního textu, která se od dosavadních poněkud liší. Zatímco předchozí lekce pokrývaly základní otázky teorie grafů, které by měly být v každém obecném kurzu vysvětleny, nyní se lehce a tak trochu i neformálně zaměříme na několik vybraných partií pokročilé teorie grafů, které přesahují běžnou náplň základních kurzů, ale které jsou „ blízké autorovu srdci". Tato část nejspíše bude v permanentním vývoji a výběr látky z nik výuce bude na aktuálním rozhodnutí učitele. .. Pojmy a poznatky z následujících lekcí také nebudou explicitně vyžadovány u zkoušky MA010 Teorie Grafů na FI MU, avšak pokročilé myšlenky a důkazové techniky zde prezentované mohou zvídavým studentům pomoci jak při skládání zkoušky, tak i v budoucích aplikacích grafů v informatice. 9 Krátké povídání o průnikových grafech Úvod V nadcházejících lekcích se zaměříme na několik vybraných partií Teorie grafů blízkých autorovu srdci. Naším prvním výběrem tématu jsou průnikové grafy, což jsou grafy, jejichž vrcholy jsou jisté množiny a hrany spojují pronikající se dvojice. Pochopitelně, hlavní motivací studia těchto grafů je jejich geometrická názornost a aplikovatelnost v reálných situacích. Jedná se však také o oblast zajímavou z pohledu historie a vývoje teorie grafů. Cíle Účelem této lekce je ukázat čtenáři pěkný svět tzv. průnikových grafů. Ty jsou definovány průniky jistých, povětšinou geometrických množin. Postupujeme od klasických intervalových a chordálních grafů, přes krátký neformální přehled jiných dobře známých tříd až po speciální křivkové a úsečkové reprezentace. 9.1 Průnikové a intervalové grafy Začneme základní všeobecnou definicí této oblasti. Definice 9.1. Průnikovým grafem množinového systému A4 nazveme graf Im na vrcholech V = A4 s množinou hran E = { {A, B} C A4 : Ap\B / 0}. Oblast průnikových grafů je obsáhle studovaná a má mnoho zajímavých zákoutí a pěkných výsledků, jak v oblasti teorie, tak i po algoritmické stránce. My si několik takových v této lekci ukážeme. Nejprve základní fakta o průnikových reprezentacích grafů. Fakt: Průnikové grafy (určitého typu) jsou vždy uzavřené na indukované podgrafy. Fakt: Každý jednoduchý graf je isomorfní průnikovému grafu nějakého systému množin. Stačí zvolit soubor hran incidentních s vrcholem x za množinu Mx reprezentující x. 99 Intervalové grafy Pro začátek se podívejme na průnikové grafy intervalů na přímce - intervalové grafy (zkratka INT). Komentář: Jedná se o skutečně historický příklad průnikových grafů, přitom intervalové grafy jsou intenzivně studovány dodnes a mají zajímavé aplikace, třeba v DNA sekvencování. Zde je jednoduchý příklad intervalového grafu: 6 Vzpomeňte si, že s intervalovými grafy jsme se vlastně setkali už v Problému 5.5. Lema 9.2. Každá kružnice délky větší než tři v intervalovém grafu má chordu. Věta 9.3. Třídu všech intervalových grafů lze charakterizovat pomocí jednoho z následujících, tvrzení. • Graf je intervalový právě když neobsahuje žádný z následujících zakázaných indukovaných podgrafů: \_y v^^ 1 2 3 ■■■ n K „;íi>2 C„;n>4 1 2 Á -^ L „;n>l Graf je intervalový, právě když neobsahuje indukovanou kružnici C4 a jeho doplněk má tranzitivní orientaci. Úlohy k řešení (9.1.1) Dokažte si sami, že kružnice délky větší než 3 není intervalovým grafem. *(9.1.2) Dokažte si sami, že další zakázané grafy z Věty 9.3 nejsou intervalové *(9.1.3) Jak byste charakterizovali grafy, které jsou průnikovými grafy intervalů stejné délky? (9.1.4) Jak byste jednoduše nahlédli, že doplněk intervalového grafu má tranzitivní orientaci? 100 9.2 Chordální grafy Chordální grafy představují velmi užitečné zobecnění intervalových grafů. Podívejte se potom na ně také z jiného pohledu Lekce 10. Definice: Graf G je chordální pokud neobsahuje žádnou indukovanou kružnici delší než tři. Například: Úplně základním poznatkem o chordálních grafech je následující stará věta, poprvé dokázaná už v jednom z prvních článků o intervalových grafech. Dnes existují i krátké důkazy a my si zde uvedeme jeden alternativní a striktně elementární důkaz. Věta 9.4. Každý chordální graf G obsahuje simpliciální vrchol, tj. vrchol s takový, že všichni sousedé s tvoří kliku v G. Důkaz: Dokazujeme posloupnost tří snadných tvrzení o chordálním grafu G. Řekneme, že graf H je bisimpliciální, pokud H je úplný nebo H obsahuje dva nespojené simpliciální vrcholy. 1. Pro každou kružnici C a hranu e y G existuje hrana / taková, že C \ {e} U {/} obsahuje trojúhelník. 2. Nechť uv je hranou G a sousedé v tvoří (indukují) bisimpliciální podgraf. Pokud v je simpliciální mezi sousedy u, ale ne v celém G, pak existuje vrchol w spojený s v a nespojený s u takový, že w je simpliciální mezi sousedy v. 3. Pokud G není bisimpliciální, ale sousedé každého jeho vrcholu indukují bisimpliciální podgraf, pak G obsahuje kružnici C odporující bodu 1. 4. Tudíž G je bisimpliciální. Xq = u Přímým důsledkem Věty 9.4 je existence simpliciální dekompozice libovolného chordálního grafu; jedná se o seřazení jeho vrcholů do posloupnosti v\,V2, ■ ■ ■ ,vn tak, že každé Ví, i = 2,..., n, je simpliciální v podgrafu indukovaném na v\,..., Ví-\. Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. 101 Věta 9.5. Graf G je chordální právě když G je průnikovým grafem podstromů ve vhodném stromě. Důkaz (náznak ve směru doprava): Povedeme indukcí podle počtu vrcholů G. Báze pro jeden vrchol je zřejmá. Navíc zřejmě každý průnikový graf podstromů v nějakém stromě musí být chordální. Jinak nechť v je simpliciální vrchol chordálního grafu G. Indukcí sestrojíme průnikovou reprezentaci také chordálního grafu G — v. Pak sousedé v tvoří kliku, tudíž v průnikové reprezentaci grafu G — v se v některém uzlu stromu všichni překrývají. Na tomto místě přidáme nový list stromu, který bude reprezentovat v a bude překryt reprezentanty sousedů v. □ Úlohy k řešení (9.2.1) Proč každý intervalový graf obsahuje aspoň dva simpliciální vrcholy? (9.2.2) Jak byste snadno zdůvodnili, že daný graf je chordální? Přes definici to přímo nejde, nebot byste museli zkontrolovat až exponenciálně mnoho kružnic. 9.3 Třídy průnikových grafů Zde si uvedeme jen stručný neformální přehled některých typů průnikových grafů, které jsou běžně studovány. • Hranový graf je průnikovým grafem hran v běžném grafu. • Kruhově-intervalové grafy (CA) jsou průnikovými grafy intervalů na kružnici. • Kružnicové grafy (CIR) jsou průnikovými grafy tětiv v kružnici. p* c5 p4 ***£ • Diskové grafy (DISC) jsou průnikovými grafy kruhů v rovině. Lze uvažovat také jen jednotkové kruhy (unit-DISC). 102 • Kvádrové grafy (BOX) jsou průnikovými grafy kvádrů ve dvou, třech či více dimenzích, se stěnami rovnoběžnými se souřadnicemi. • Dotykové ... grafy jsou variantou průnikových grafů geometrických objektů, ve které se požaduje, aby vnitřky objektů byly po dvou disjunktní. Moc hezkým výsledkem v oblasti dotykových grafů je následující, který už mnoho let starý a několikrát byl nezávisle znovu objevován. Věta 9.6. (Koebe) Graf je rovinný právě když je dotykovým grafem kruhů v rovině. Grafy definované viditelností Jiné, tzv. viditelnostní grafy nejsou definovány průniky objektů, ale jejich vzájemnou viditelností v geometrickém světě. Použití nacházejí například při plánování cesty autonomního robota. Úlohy k řešení (9.3.1) Najděte nějaký graf, který není CA. (9.3.2) Najděte nějaký graf, který není CIR. (9.3.3) Najděte nějaký graf, který není DISC. * (9.3.4) Najděte nějaký graf, který není průnikovým grafem koulí v 3D. * (9.3.5) Dokažte formálně, že dotykové grafy kruhů v rovině jsou vždy rovinné. 9.4 Průnikové grafy křivek a úseček Více se podíváme na následující typy průnikových grafů. (Jejich výběr není reprezentativní, ani nemá nějaký hlubší význam, jen že jsou zajímavé a blízko autorovu dřívějšímu výzkumu v oblasti průnikových grafů.) Definice: Niťovými grafy nazveme průnikové grafy (obyčejných) křivek v rovině. 103 Tvrzení 9.7. Každý rovinný graf je niťový. Následující tvrzení je poněkud překvapivé a samo o sobě naznačuje, že studium niťových grafů nebude lehké. Tvrzení 9.8. Existují grafy, které jsou niťové, ale každá jejich taková reprezentace obsahuje dvojici křivek majících exponenciálně mnoho (k počtu vrcholů) vzájemných průsečíků. Co se týče algoritmické složitosti, je poznání niťových grafů velmi algoritmicky náročné. Vhledem k Tvrzení 9.8 je mnohem obtížnější dokázat příslušnost problému do třídy MV, než jeho těžkost (to je poměrně neobvyklý fenomén v teorii složitosti), [Kratochvíl / Pelsmajer, Schaeffer, Stefankovič]. Věta 9.9. Problém rozpoznat, zda daný graf je niťový, je NV-úplný. Velmi podobně je definována třída úsečkových grafů, což jsou průnikové grafy úseček v rovině. Opět je dokázáno, že jejich rozpoznávání je J\ÍV-těžké [Kratochvíl], ale příslušnost problému do třídy NV zůstává otevřená kvůli následujícímu. Tvrzení 9.10. Existují grafy, které jsou úsečkové, ale každá jejich taková reprezentace obsahuje úsečku, k zápisu jejíž souřadnic je třeba exponenciálně mnoho (k počtu vrcholů) bitů. Ve srovnání s jednoduchým Tvrzením 9.7 vynikne tento docela dlouho otevřený problém: Hypotéza 9.11. Je každý rovinný graf úsečkovým grafem? „Zápalkové" grafy Výše jsem zmínili obecný pojem geometrických dotykových grafů, nyní se z tohoto úhlu pohledu podíváme na dotykové grafy úseček v rovině: Tímto pojmem nazýváme ty průnikové grafy úseček v rovině, u nichž je dodatečnou podmínkou, že žádné dvě úsečky se neprotínají ve svých vnitřních bodech. (Jakoby „zápalkové" reprezentace v rovině.) 33 Věta 9.12. Graf je dotykovým grafem disjunktních horizontálních a disjunktních vertikálních úseček, právě když se jedná o rovinný bipartitní graf. Opět se jedná o výpočetně obtížnou třídu grafů, neboť již: Věta 9.13. Problém rozpoznat dotykový graf úseček je NV-úplný. Úlohy k řešení (9.4.1) Dokažte si sami Tvrzení 9.7. (9.4.2) Najděte jakýkoliv rovinný graf, který není dotykovým grafem úseček. 104 Rozšiřující studium Jelikož jsou průnikové a chordální grafy obsáhle studovány, množství další informací lze snadno nalézt na Internetu pod heslem "intersection graphs". Specificky je třídám průnikových grafů věnována třeba monografie [McKee, McMorris, Topics in Intersection Graph Theory, SIAM monographs on discrete mathematics and applications, 1999]. Mnohé výsledky a reference specificky se vztahující k dotykovým grafům se nacházejí také v autorově dizertační práci (MFF UK, 2000) na webu http://www.fi.muni.cz/~hlineny/Research/papers/kamthesis.pdf. 105 10 Dekompozice grafů, algoritmy a minory Úvod Další autorův výběr tématu nás zavede ke strukturální teorii grafů - k různým jejich dekompozicím, grafovým minorům a navazujícím efektivním algoritmům pro jinak těžké problémy. Obecnou inspirací nám je známý fakt, že většinu jinak těžkých problémů lze řešit snadno a efektivně na stromech. Podobná situace nastává třeba u intervalových grafů nebo obecně u chordálních grafů. Proto se podíváme na grafy, které jsou svým způsobem „ stromům blízké", ve smyslu existence jejich vhodné dekompozice. Stromová dekompozice přitom má definičně blízko i ke dříve zmiňovaným chordálním grafům. Vrcholem této lekce je formulace hlavního výsledku takzvané „ Graph Minors Theory" od Robertsona a Seymoura, který lze bez nadsázky prohlásit za asi největší výsledek, kterého dosud teorie grafů dosáhla (i v porovnání s Větou o čtyřech barvách). Cíle Cílem této lekce je uvést čtenáře do problematiky „šířkových" parametrů a dekompozic grafů a jejich aplikace na design efektivních algoritmů pro jinak velmi těžko řešitelné problémy. Důraz bude kladen především na stromovou šířku a její návaznost na dříve definované pojmy jako třeba chordální grafy. Závěrem je dehnován pojem minoru a formulována Robertson-Seymourova věta o dobrém kvaziuspořádání konečných grafů vzhledem k minorům. 10.1 Obtížné problémy na speciálních grafech V Lekci 7 jsme uvedli některé „neřešitelně obtížné", přesněji MV-těžké grafové problémy, například 3-obarvení grafu (Problém 7.16) nebo nezávislá množina vrcholů (Problém 7.17). Přesto i takto obtížné problémy dokážeme řešit efektivně na některých specifických třídách grafů - a to nejen na stromech. Stačí si vzpomenout na Problém 5.5 o přidělování pracovních úkolů, neboli o barevnosti intervalových grafů v terminologii Lekce 9, který jsme řešili rychlým hladovým algoritmem. Obdobně vyřešíme i nezávislou množinu na intervalových grafech: Algoritmus 10.1. Nalezení nezávislé množiny v intervalovém grafu Předpokládejme, že graf G je daný svou intervalovou reprezentací (v případě potřeby je možno tuto reprezentaci efektivně sestrojit). Maximální nezávislou množinu nalezneme následovně. • Uspořádáme intervaly reprezentující G podle jejich pravých konců. • Do nezávislé množiny hladově (v tomto uspořádání) vložíme vždy první interval ne-protínající se s předchozími vybranými. Také na obecnějších chordálních grafech můžeme navrhovat rychlé a povětšinou i snadné algoritmy. Algoritmus 10.2. Určení barevnosti chordálního grafu • Snadno zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.4). • Graf G je fc-degenerovaný, kde k = oj {G) — 1 je největší stupeň simpliciálního vrcholu v některém kroku simpliciální dekompozice G. Hladově tudíž můžeme G obarvit k + 1 barvami a to je optimální (neboť máme v G kliku velikosti k + 1). Algoritmus 10.3. Nalezení nezávislé množiny chordálního grafu • Opět zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.4). • V pořadí této dekompozice hladově přidáváme vrcholy do nezávislé množiny. (Tento postup je přímým zobecněním Algoritmu 10.1, viz také Věta 9.5.) 106 Možná zobecnění? Zajímavou a užitečnou otázkou teď je, jak takové postupy zobecnit na širší třídy grafů, které mají nějakou specifickou omezující (ale ne příliš) vlastnost - „parametr". Úlohy k řešení *(10.1.1) Jak byste efektivně nalezli nejmenší dominující množinu na intervalovém grafu? (10.1.2) Jak byste efektivně nalezli nejmenší vrcholové pokrytí v chrodálním grafu? *(10.1.3) Dokažte správnost Algoritmu 10.3. 10.2 Tree-width — čtyři definice Výlet za strukturálními parametry grafů začneme pojmem, který už lze dnes prohlásit za klasický. Název „tree-width" byl zaveden Robersonem a Seymourem počátkem 80-tých let, ale pak se ukázalo, že ekvivalentní definice již uvažovali matematici léta před nimi, například v souvislosti s takzvanými „fc-trees" nebo se simpliciálními dekompozicemi. (Důsledkem tohoto vývoje je také bohatost různých definic stejného pojmu...) Připomeňme, že velikost největší kliky v grafu G se označuje uj(G). Definice: Stromovou šířkou (tree-width) grafu G nazveme nejmenší přirozené k takové, že existuje chordální graf H s oj {H) = k + 1 obsahující G jako podgraf (H ^ G). Komentář: Například každý podgraf následujícího chrodálního grafu má tree-width < 2: Kde je však v této dennici nějaký „strom"? Je, ale skrytý- podívejte se na Větu 9.5 popisující chordální grafy jako průnikové grafy podstromů ve stromě. Jinou možnost popisu ukazuje: Definice: Vrcholy V(G) grafu G uspořádáme do posloupnosti (permutace) (v\,V2, ■ ■ ■ ,vn). Pro i = 1,2,...,n definujme 1(ví) jako počet všech indexů j € {1,... ,i — 1} takových, že vrcholy Ví a Vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj,Ví,Ví+\, ... ,vn}. Druhou stromovou šířkou grafu G nazveme nejmenší hodnotu výrazu maxc £(ti) přes všechny permutace vrcholů V(G). Komentář: Všimněte si, že uspořádání vrcholů z této definice je vlastně zpětnou simpliciální dekompozicí chordálního grafu H D G z předchozí definice (viz také Věta 9.4). V nakresleném příkladě grafu C5 vidíme uspořádání vrcholů se šířkou 2. (Tečkované hrany ukazují tzv. chordální doplnění grafu, relevantní k první definici tree-width.) Ještě další, značně odlišný, přístup má tato definice: 107 Definice: Pro libovolný strom T uvažujeme (libovolné) zobrazení r : E (G) —> V (T). Pro vrchol t € V (T) označíme Ti,..., Tj jednotlivé komponenty lesa T—t a Fi = r-1 (V(Ti)). Označme d £T(t) = \V(G)\ + (d - 1) • c(G) - Y, í=l kde c(H) značí počet souvislých komponent grafu H. t:E Třetí stromovou šířkou grafu G pak definujeme jako nejmenší možnou, přes všechny dvojice T, t, hodnotu výrazu maxíey(T) £T(ť). Nakonec si uvedeme ještě původní definici Robertsona a Seymoura, která se většinou uvádí jako ta první a hlavní (a na ostatní možné definice málokdy přijde řeč). Definice 10.4. Stromová dekompozice grafu G. Stromovou dekompozicí grafu G nazveme strom T spolu se systémem množin Xt (zvaných „balíky") pro t € V (T), kde • XtGV(G)a\JteV(T)Xt = V(G), • pro každou hranu e = uv € E(G) je u, v € Xt pro nějaké t € V (T), • (interpolační vlastnost) pro každý vrchol v € V(G) tvoří podmnožina všech t € F (T) svě^í podstrom v T. Šířkou dekompozice T, X rozumíme největší hodnotu \Xt\ — 1 pro t € V (T) a čtvrtou stromovou šířkou grafu G nazveme nejmenší možnou šířku stromové dekompozice G. {1,5,6,8} {1,2,3,6} 1 2 >v l \ ( f A i K #1,3,6,8} {1,3," 4, 8} {3,6,7,8} Přes veškerou zdánlivou odlišnost uvedených definic platí následovné. Věta 10.5. Všechny čtyři výše uvedené definice stromové šířky definují přesně tutéž hodnotu, pokud graf G má neprázdnou množinu hran. Důkaz plného znění této věty je však nad rámec našeho textu. Komentář: Parametr stromové šířky omezuje pouze „globální" strukturu grafu, grafy omezené tree-width mohou sice lokálně vypadat téměř jakkoliv, ale z celkového (globálního) pohledu musí dodržovat jistá velice striktní omezení. Neformálně lze říci, že když se na velký graf omezené tree-width podíváme z velké dálky (kdy už se jednotlivé vrcholy budou slévat), obrázek nám bude připomínat velký strom. 108 O četnících a zloději Na závěr si představme hru na četníky a zloděje s těmito pravidly: Zloděj se bleskovou rychlostí pohybuje po hranách grafu přes vrcholy neobsazené četníky (jeho pohyb vždy skončí ve vrcholu, ne „uprostřed" hrany). Naopak četníci se grafem vůbec nepohybují, jen přilétají do a odlétají z vrcholů helikoptérou. Zloděj je chycen ve svém vrcholu z přiletivším četníkem, pokud jsou i všichni sousedé z zrovna obsazeni četníky. Věta 10.6. Nejmenší počet četníků potřebných k zaručenému chyceni zloděje v grafu G je roven stromové šířce G plus 1. Úlohy k řešení (10.2.1) Dokažte si sami ekvivalenci prvních dvou deßnic tree-width. Vyjděte přitom z existence simpliciální dekompozice chordálního grafu (Věta 9.4). (10.2.2) Dokažte, že pro každou stromovou dekompozici grafu G platí, že každá klika v G se nachází celá v jednom některém balíku. (10.2.3) Které grafy mají vysokou tree-width? *(10.2.4) Dokážete nalézt rovinný graf s vysokou tree-width? (10.2.5) Jak mohou 3 četníci chytit zloděje na kružnici? A proč 2 nestačí? 10.3 Některé další parametry Pro ukázku si uvedeme jiné dva šířkové parametry, které místo „stromového tvaru" strukturu grafu „linearizují". Definice: Cestní dekompozici a šířku (path-width) grafu G definujeme stejně jako v Definici 10.4, jen požadujeme navíc, aby T byla cesta. Definice: Vrcholy V(G) grafu G uspořádáme do posloupnosti (permutace) (v\,V2, ■ ■ ■ ,vn). Bandwidth grafu G definujeme jako nejmenší hodnotu výrazu maxc.^.gB(G) \i — j\ přes všechny permutace vrcholů V(G). Větvené dekompozice Další definice se váží k zásadně jinému, a přesto v konečném důsledku ekvivalentnímu pohledu na stromovou šířku. Graf je kubický, pokud má všechny vrcholy stupně 3. Strom je podkubický, pokud má všechny vrcholy stupně < 3. Definice: Pro libovolný graf G a podmnožinu X C E (G) definujeme funkci souvislosti Xg(X) jako počet vrcholů G, které jsou konci některých hran z X i hran z E(G) \ X {separace množiny X). Definice 10.7. Větvená dekompozice grafu G Nechť T je podkubický strom a r : E (G) —>■ L (T) je bijekce hran grafu G do listů L (T) stromu T. Pro každou hranu x stromu T definujeme šířku x jako \q(X), kde X = r-1 (V(T{)) pro jednu z komponent Ti, T2 lesa T — x. 109 x E\X šírka(aľ) := AG(X) = XG(E\X) Pak šířkou dekompozice T, r je maximální šířka ze všech hran T a větvenou šířkou grafu G je nejmenší možná šířka větvené dekompozice G. Komentář: Pro ilustraci si ukážeme větvenou dekompozici šířky 4 pro úplný graf Kq. (Například stromová šířka Kq je rovna 5.) de aj ef cd \, df bf cf be ac ad >— ab 3/ bd \ bc ce Věta 10.8. Pokud graf G má stromovou šířku t a větvenou šířku b > 1, tak bv = 1 pro u £ X & v eV \X, právě když uv je hranou v G. Definice 10.9. Ranková dekompozice grafu G Nechť T je podkubický strom a r : V (G) —>■ L (T) je bijekce vrcholů grafu G do listů L(T) stromu T. Pro každou hranu x stromu T definujeme šířku x jako 7g(X), kde X = r-1 (V(Ti)) pro jednu z komponent Ti, T2 lesa T — x. Pak šířkou dekompozice T, r je maximální šířka ze všech hran T a rankovou šířkou grafu G je nejmenší možná šířka rankové dekompozice G. Komentář: Následuje ukázka rankové dekompozice šířky 2 pro kružnici C5. d d (00 1 l)N Fakt: Rankovou šířku grafu lze omezit funkcí jeho větvené šířky, ale naopak toto neplatí - třeba úplné grafy mají rankovou šířku 1, kdežto jejich větvená i stromová šířka roste nade všechny meze. 110 Úlohy k řešení (10.3.1) Může graf omezené path-width mít vrcholy velkého stupně? * (10.3.2) Jak může souviset path-width grafu s hrou na četníky a zloděje? (10.3.3) Jaká je bandwidth kružnice? Dokažte. (10.3.4) Dokažte, že graf omezené bandwidth má omezený maximální stupeň. Jaký je přesný vztah max. stupně k bandwidth? (10.3.5) Dokažte, že větvená šířka grafu K4 je právě 3. (10.3.6) Podobně dokažte, že větvená šířka grafu Kq je právě 4. * (10.3.7) Dokažte Větu 10.8. (10.3.8) Nalezněte příklady grafů, které dokazují těsnost obou nerovností ve Větě 10.8. (10.3.9) Jaká je ranková šířka úplných bipartitních grafů? (10.3.10) Najděte nějaký dosti velký graf, který není úplný ani úplný bipartitní, a přesto má rankovou šířku 1. (10.3.11) Jaká je ranková šířka kružnic? * (10.3.12) Umíte najít nějaký graf velké rankové šířky? 10.4 Efektivní algoritmy na dekompozicích V této části si uvedeme pár ukázek jednoduchých algoritmů běžících „dynamicky" na vhodné dekompozici grafu. Samotné řešené problémy jsou sice nedůležité, ale účelem je ukázat principy návrhu takových efektivních algoritmů. Již víme z 7.17, že určení velikosti největší nezávislé množiny v grafu je MV-úplný problém. Stromová dekompozice fixní šířky však tento problém umožňuje řešit velice snadno. Algoritmus 10.10. Nezávislá množina na stromové dekompozici Danou stromovou dekompozici vstupního grafu si libovolně „zakořeníme". • V každém listě dekompozice vyřešíme problém hrubou silou v konstantním čase. • Ve směru od listů ke kořeni sbíráme následující informaci: V každém balíku B dekompozice, pro každou X C B, velikost největší nezávislé množiny / v grafu indukovaném na podstromu pod B takové, že I P\ B = X. • Vzhledem k interpolační vlastnosti naší dekompozice lze výše popsanou informaci v každém balíku dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace ze všech jeho potomků v dekompozici. Výsledný algoritmus pracuje v čase úměrném počtu uzlů dekompozice, tedy v lineárním čase! Další problém hledání (maximálního) párování v grafu sice je polynomiálně řešitelný, ale zjišťování počtu všech párování už je #V-úplné, neboli stejně těžké (jinými slovy beznadějné) jako výpočet permanentu matice nebo spočítání všech řešení SAT problému. Algoritmus 10.11. Počet párování na větvené dekompozici Opět si větvenou dekompozici vstupního grafu libovolně „zakořeníme". • V každém listě dekompozice je řešení triviální. • Ve směru od listů ke kořeni sbíráme následující informaci: V každé hraně dekompozice, pro každou podmnožinu X C S vrcholů separace S indukované touto hranou v dekompozici, počet všech párování, která ze separace S „obsazují" právě vrcholy X. 111 • Opět lze výše popsanou informaci na každé hraně dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace z obou jejich podstromů v dekompozici (vzájemným vynásobením a sečtením počtů). Výsledný algoritmus pracuje v čase úměrném počtu hran dekompozice, tedy opět v lineárním čase. Jeden všeobecný výsledek Nápadná vzájemná podobnost předchozích algoritmů určitě není náhodná, chtěli jsme jimi ilustrovat jeden důležitý obecný princip, který objevili postupně [Courcelle / Arn-borg, Lagergren, Seese / Borie, Parker, Tovey]. Věta 10.12. Každá vlastnost grafů, která je vyjádřitelná v tzv. (E) MS O jazyce, se dá vypočítat v lineárním čase pro všechny grafy omezené stromové šířky. Pro zjednodušení nebudeme přesně definovat, co (E)MSO jazyk znamená, ale zhruba jde o jazyk, který má dovoleno kvantifikovat přes podmnožiny vrcholů a hran grafu a enu-merovat počty prvků množin. Většina grafových vlastností, které jsme zatím probírali, spadá do této kategorie. Úlohy k řešení * (10.4.1) Dokázali byste efektivně nalézt Hamiltonovskou kružnici v grafu na jeho větvené dekompozici fixní šířky? 10.5 Minory v grafech Závěrem nahlédneme do (nedozírných?) hlubin strkturální teorie grafů. Klíčem k ní je pojem minoru, který zobecňuje běžné podgrafy, Definice: Říkáme, že graf G je minorem grafu H, pokud lze G získat z H kontrakcemi hran a vypouštěním vrcholů a hran. Komentář: Význam vypouštění vrcholů či hran je zřejmý. Pro pochopení operace kontrakce hrany („stažení do jednoho vrcholu") je nejlepší se inspirovat následujícím obrázkem. Robertson—Seymourova věta Věta 10.13. Mějme libovolnou grafovou vlastnost 2 crosscapů a h uší, tak E je homeomorfní ploše vzniklé ze sféry přidáním k — 2 crosscapů a h + 1 uší. 11.2 Kreslení grafů na plochy Přirozeným zobecnění rovinných nakreslení grafu z Definice 8.1 je následující definice. Definice 11.3. Nakreslení grafu G na plochu E myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body na E a hrany jako oblouky (čili jednoduché křivky) spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. Na vyšší plochy přenášíme i další pojmy rovinného kreslení, jako pojem stěny. Čtenář by si však měl uvědomit, že na vyšších plochách nemusí stěny být „jen placaté", a proto pro zajištění jisté konzistence s rovinným případem je třeba následujícího pojmu. Definice: Nakreslení grafu G na plochu E je buňkové, pokud je každá stěna (bez své hranice!) homeomorfní otevřenému disku. Fakt: Buňkové nakreslení grafu G je jednoznačně určeno svými stěnovými kružnicemi a jako takové definuje i plochu E až na homeomorfismus. (Neboli plochu E lze „slepit" z jednotlivých disků stěn podél společných hran u stěnových kružnic.) Tvrzení 11.4. Buňkové nakreslení grafu G na orientovatelnou plochu E je jednoznačně určeno rotačním schématem vycházejících hran u svých vrcholů. (V případě neoriento-vatelných ploch je třeba ještě přidat jistá „znaménka".) Rotační schéma u každého vrcholu v nakreslení určuje cyklické pořadí hran (v globálně zvolené orientaci) vycházejících z tohoto vrcholu v našem nakreslení. Kreslení na určenou plochu První otázkou o kreslení grafů na plochy je, zda dokážeme takto nakreslit i jiné než rovinné grafy. Například úplný graf K§ nelze nakreslit do roviny. Tvrzení 11.5. Do projektivní roviny lze bez křížení hran nakreslit úplný graf Kq, na torus i K'j, kdežto na Kleinovu láhev také jen Kq. 115 Také mnohé jiné poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Z těch jednoduchých je nejdůležitější Eulerův vztah (Věta 8.2). Věta 11.6. Nechť buňkové nakreslení neprázdného souvislého grafu G na ploše E má f stěn. Pak \V(G)\+f-\E(G)\=x&), kde x(E) (kulérová charakteristika plochy) je 2 — 2h pro E = S h a 2 — k pro E = A/V Obdobně rovinnému případu, z Eulerova vztahu vyplývají důležitá omezení na maximální počet hran jednoduchých grafů nakreslitelných na určené plochy. Například jednoduchý n-vrcholový graf nakreslený na toru nebo Kleinově láhvi nemůže mít více než 3n hran. 11.3 Překážky kreslení na plochy Podle Věty 8.5 lze rovinnost zadaného grafu poměrně rychle algoritmicky rozhodnout i najít nakreslení. I tento silný výsledek má stejně silné zobecnění na vyšší plochy, ale už bohužel není vhodný pro praktické implementace. Věta 11.7. (Mohar) Pro každou pevnou plochu E existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na E, nebo určí minimální překážku nakreslitelnosti na E. Poznámka: Za poznamenání stojí, že obecnější problém určit nejjednodušší plochu, na kterou lze daný graf nakreslit, je už J\fV-téžký. Z jiné strany lze zobecňovat Kuratowského větu na vyšší plochy. Třebaže je známo, že takové zobecnění s konečným počtem překážek je platné pro každou plochu, konkrétní seznam zakázaných minorů či podrozdělení známe pouze u jediné vyšší plochy. Věta 11.8. (Archdeacon) Graf G je nakreslitelný do projektivní roviny, právě když neobsahuje žádný minor isomorfní některému z následujících 35 grafů. Význam grafů na plochách Komentář: Původní motivace výzkumu kreslení grafů na plochy je přirozená - byla to především snaha o řešení problému čtyř barev. Nyní však již máme Větu o čtyřech barvách, takže co dále motivuje výzkum kreslení grafů na vyšší plochy, mimo „pěkných obrázků"? 116 S grafy nakreslenými na vyšších plochách se setkáme ve dvou základních teoretických oblastech: • Algebraické - studium pravidelných „map" na plochách. • Strukturální grafové - celá Robertson-Seymourova teorie grafových minorů, třebaže na první pohled s kreslením grafů nemá nic společného, stojí na grafech nakreslených na plochách. Abychom poslední překvapivé tvrzení blíže vysvětlili, uvedeme si stručně asi nejdůležitější mezivýsledek Robertson-Seymourovy teorie. (Všimněte si, že minor grafu je vždy nakreslitelny na stejnou plochu jako původní graf, třeba ne buňkově.) Věta 11.9. Mějme nerovinný graf H. Pak každý graf G, který neobsahuje minor isomorfní H, má stromovou dekompozici (Definice 10.4) takovou, jejíž každý balík indukuje podgraf, který je až na omezeně mnoho „lokálních výjimek" nakreslitelny na nějakou plochu X takovou, že H na X nakreslit nelze. Úlohy k řešení (11.3.1) Najděte nakreslení grafu ÍÍ44 na torus. (Vezměte si k tomu nějaký fyzický model toru, třeba posilovači kolečko.) *(11.3.2) Dokažte, že graf K r nelze nakreslit bez křížení na Kleinovu láhev. (11.3.3) Určuje nám Eulerova charakteristika (Věta 11.6) jednoznačně plochu, na kterou je graf nakreslený? Kdy? (11.3.4) Lze nějaký graf nakresit buňkově na různé plochy? (11.3.5) Proč tento graf PVV^i nelze nakreslit do projektivní roviny? (11.3.6) Proč graf K35 nelze nakreslit do projektivní roviny? * (11.3.7) Uměli byste o dalších, složitějších, grafech z Věty 11.8 dokázat, že nejsou projektivní? IIA O průsečíkovém čísle grafů Třebaže již dobře víme (a umíme algoritmicky rozpoznat), které grafy jsou rovinné, praxe požaduje „hezká nakreslení v rovině" i pro nerovinné grafy. Jak tedy na hezká kreslení nerovinných grafů do roviny? Přirozené je asi požadovat, aby křížení hran - když už musí být - bylo co nejméně. Definice (rozšíření Definice 8.1): Nakreslením grafu G do roviny rozumíme zobrazení, ve kterém jsou vrcholům G přiřazeny různé body roviny a hranám jednoduché křivky spojující koncové vrcholy. Přitom je požadováno, aby se žádné tři hrany neprotínaly v jednom bodě (jiném než koncový vrchol), aby žádná hrana neprocházela jiným vrcholem a aby se každá protínající dvojice hran skutečně „křížila" (tj. ne jednostranný dotyk). Příklad 11.10. Podívejme se na následující tři (korektní) nakreslení do roviny. Jsou všechna „optimální", tj. je počet jejich křížení nejmenší možný? 117 Snadno vidíme, že první graf lze nakreslit i bez křížení a druhý graf jen s jedním křížením. Naopak třetí graf už s méně kříženími nakreslit nelze. Uměli byste toto dokázat? D Definice 11.11. Průsečíkové číslo grafu G v rovině je definováno jako nejmenší možný počet křížení dvojic hran přes všechna korektní nakreslení G do roviny. Značíme cr(G). Komentář: Původ problému průsečíkového čísla spadá do doby druhé světové války, kdy P. Turán byl na nucených pracech v cihelně. Jejich úkolem bylo tlačit vozíky s cihlami po kolejnicích a na každé křižovatce s tím měli velké problémy. Proto Turán přemýšlel, jak navrhnout kolejiště lépe, aby minimalizoval počet křížení kolejnic. V dnešní době je problém průsečíkového čísla velmi důležitý v praktických oblastech VLSI designu [Leighton] a „lidsky čitelné" vizualizace grafů v různých schématech. Příklad 11.12. Určeme průsečíková čísla následujících dvou grafů: # Asi snadno každý nalezne nakreslení prvního grafu (Petersenův) s pouze dvěma kříženími hran. Jak však dokázat, že jej nelze nakreslit s jedním křížením? Všimněme si, že každá jeho hrana je „ekvivalentní" s každou jinou. To znamená, že by ostraněním jedné zvolené hrany z Petersenova grafu mělo vytvořit rovinný graf, ale to není pravda. Druhý graf Kq lze nakreslit s 3 kříženími - začněme s kružnicí délky 5 a posledním vrcholem spojeným uvnitř. Zbylých 5 hran pak už dokážeme dokreslit s vytvořením tří křížení. Zkuste si to! Proč není možných méně křížení? Předpokládejme, že dvě křížení hran postačují, pak bychom vypuštěním dvou dotčených hran získali rovinný graf. Ten by však měl 6 vrcholů a 13 > 3 • 6 — 6 hran, spor. D Fakt: Přesné obecné hodnoty průsečíkových čísel nejsou známy ani pro úplné či úplné bipartitní grafy. Věta 11.13. Problém určit, zda průsečíkové číslo cr{G) < k pro G a k na vstupu je NV-úplný. Toto platí dokonce i když G je kubický 3-souvislý graf. Zamyslete se sami, proč by problém průsečíkového čísla měl vůbec náležet do třídy J\ÍV, není to tak zřejmé... Komentář: V praxi se ukazuje, že určení průsečíkového čísla je přímo zoufale těžký problém, ještě mnohem beznadějnější než třeba barevnost. Snad jediným existujícím „pozitivním" (i když zcela nepraktickým) algoritmickým výsledkem je následující výsledek Groheho a poté K awarabayashi-Reeda: Věta 11.14. Pro fixní k lze otestovat, zda cr{G) < k, v lineárním čase vzhledem k počtu vrcholů grafu (závislost na parametru k je však doslova „brutální"). Aby nebylo všem špatným zprávám konec, v roce 2010 Cabello a Mohar dokázali následující velmi překvapivý výsledek. Věta 11.15. Je-li dán rovinný graf G a dvojice jeho nespojených vrcholů u,v, tak problém určit, zda průsečíkové číslo cr{G + uv) < k pro k na vstupu je NV-úplný. 118 11.5 O problému rovinného pokrytí Na závěr si jako kuriozitu uvedeme zajímavý, třebaže okrajový, problém známý od 80-tých let pod názvem Negamiho hypotéza planárních pokrytí'nebo Negamiho 12 oo hypotéza. Avšak k velmi podobné otázce nezávisle ve stejné době dospěl i Fellows. Problém je hezký především svou „chytlavostí" a jednoduchostí zadání. Definice: Říkáme, že graf H pokrývá graf G, pokud existuje surjektivní zobrazení r : V (H) —>■ V (G) takové, že sousedé každého vrcholu v grafu H jsou bijektivně zobrazeny na sousedy vrcholu r (v) grafu G. r(u3) H G Negamiho hypotéza rovinných pokrytí Hypotéza 11.16. Souvislý graf G má pokrytí (nějakým) konečným rovinným grafem, právě když G samotný je nakreslitelný do projektivní roviny. Komentář: Zde je příklad dvojitého pokrytí grafu Ks rovinným grafem o 10 vrcholech. Pokrytí je získáno z projektivního nakreslení Ks a zobrazení t vrcholů z definice pokrytí je naznačeno pojmenováním "centrálních" vrcholů. t{vi) = t(w2) = v H v2 Vl G = Ks Fakt: Je-li G nakreslitelný do projektivní roviny, pak univerzální pokrytí projektivní roviny sférou okamžitě dá nakreslení dvojitého rovinného pokrytí grafu G. Lema 11.17. K důkazu Hypotézy 11.16 stačí ověřit, že žádný z 32 souvislých zakázaných minorů z Věty 11.8 nemá konečné rovinné pokrytí. Kupodivu pro většinu z oněch 32 grafů to lze dokázat velmi snadno. Další výsledky, na kterých se podíleli Archdeacon, Fellows, Negami, Thomas a autor, vedly k dále uvedeným poznatkům, které jsou doposud tím nejsilnějším, co o řešení Negamiho hypotézy víme. Věta 11.18. Pokud graf ^1,2,2,2 nemá konečné rovinné pokrytí, tak je Hypotéza 11.16 pravdivá. Věta 11.19. Existuje jen 16 následujících konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.16 mohla být nepravdivá. 119 O rovinných emulátorech Mírnou modifikací konceptu planárního pokrytí představuje tato definice, podaná Fel-lowsem nezávisle na Negamim. Definice: Říkáme, že graf H je emulátorem grafu G, pokud existuje surjektivní zobrazení r : V (H) —>■ V (G) takové, že sousedé každého vrcholu v grafu H jsou surjektivně zobrazeny na sousedy vrcholu t (v) grafu G. Komentář: Na rozdíl od rovinných pokrytí mohou mít emulátory poměrně bohatší strukturu, přesněji řečeno sousedé mohou být "duplikovaní", viz tento příklad emulátoru trojúhelníka: C2 b2 H G Jelikož je na první pohled z definice "jasné", že duplikace sousedů nemůže být přínosná pro existenci planárních emulátorů (ve srovnání s pokrytími), již Fellows vyslovil domněnku, že souvislý graf má konečné rovinné pokrytí právě tehdy, když má konečný rovinný emulátor. Přesto se na závěr roku 2008 objevilo skutečné překvapení: Věta 11.20. (Rieck a Yamashita) Existuje graf, který není projektivní a nemá konečné rovinné pokrytí a přesto má konečný rovinný emulátor. Jiné příklady grafů z Věty 11.20 byly následně objeveny Chimanim a autorem a jeden z nich (až překvapivě jednoduchý a malý) ukazuje náznakem tento obrázek: 1 3 2 Problematika, které grafy mají konečné rovinné emulátory, je stále široce otevřená. Úlohy k řešení (11.5.1) Dokažte si sami Lema 11.17. (11.5.2) Proč tento graf J^V V^l nemá konečné rovinné pokrytí? "(11.5.3) Dokažte, že graf K35 nemá konečné rovinné pokrytí. 120 * (11.5.4) Řešte předchozí dvě otázky pro emulátory místo pokrytí. Rozšiřující studium Při popisu kreslení grafů na plochy vycházíme z výborné monograße Mohara a Thomassena [7]. Na této monografii také zakládáme pokročilý výběrový předmět MA051 na FI MU, který zájemcům o grafy vřele doporučujeme. V této krátké lekci však problematiku velmi zjednodušujeme z důvodu nedostatku místa, takže pro zájemce může být přínosné si přečíst, jak kreslení grafů na plochy hluboce souvisí s fundamentálními problémy klasické topologie v Thomassenově skvělém podání. Co se týče Negamiho hypotézy a planárních pokrytí, obsáhlý ucelený popis lze nalézt v autorově dizertační práci (Georgia Tech, 1999) http://www.fi.muni.cz/~hlineny/Research/papers/gtthesis.pdf a doplnit nejnovější informace lze ze shrnujícího článku (2009) http://www.fi.muni.cz/~hlineny/Research/papers/plcover20-gc.pdf. K průsečíkovému číslu grafů (není nám o něm známa žádná tištěná monograße) lze nalézt množství doplňujících informací na Internetu, jako třeba http://en.wikipedia.org/wiki/Crossing_number. 121 Cast IV Klíč k řešení úloh 1.1.1) Kružnice délky 5. 1.1.2) Pro n = 1 a 2, cesty délky 0 a 1. 1.1.3) Pro n = 3, trojúhelník. 1.1.4) Pro m = n = 2, délky čtyři. 1.1.5) Pro m = 1 nebo n = 1 a druhé libovolné. 1.1.6) 9 1.1.7) Oba stejně 36 hran. 1.2.1) 34 1.2.2) Ano: 1.2.3) Ano, kružnice délky 6 a dvě kružnice délky 3 vedle sebe. 1.2.4) Po odebrání případného izolovaného vrcholu zbývá n vrcholů, ze kterých každý má stupeň mezi 1 a n — 1, takže některé musí mít stejné stupně. 1.3.1) Ano, ale musí mít délku aspoň o 2 kratší než délka kružnice. Vidíte proč? 1.3.2) 3, více nelze, neboť na obvodě kružnice by se musely ob-jeden střídat. 1.3.3) 3 1.3.4) 7 1.3.5)* 5, dokážete ji vůbec najít? 1.3.6) Ano, například |/ \ ^ I Tento graí obsahuje 4 trojúhelníky, kdežto původní graí jen 3. Mohli jste však sestrojit úplně jiný graí... 1.3.7)* a) Jeden, jen kružnice délky 5. b) Dva, kružnice délky 6 a dva trojúhelníky, c) Čtyři... 1.4.1) Je mnoho možností, třeba tato: Rozložte hrany Kr do tří kružnic Cr, každou zorientujte jedním směrem. Jedna z těch tří kružnic prochází vrcholy po řadě, druhá ob dva, třetí ob tři vrcholy. 1.4.2) Protože každá šipka jednou vychází a jednou přichází, takže výchozích musí být celkem stejně jako příchozích. 1.6.1) Ano. 1.6.2) Ne. 1.6.3) Pro x = 7, 9,11. 1.6.4) Dva. 1.6.5) A: 23, B: 20, C: 22. 1.6.6) Snadno, začněte mapováním mezi jedinečnými vrcholy stupně 4. 1.6.7) Isom. z pravého do levého grafu: spodní dva nahoru vpravo, pravé dva dolů vpravo, atd. 1.6.8) Začněte mapování od jedinečného (izolovaného) trojúhelníku v grafech. 1.6.9) B c; C, A c; D, u neisomorfních dvojic vždy jedna obsahuje kružnice délky 5 a druhá ne. 1.6.10) A ano, ÍÍ33 a graf trojbokého hranolu. B ne, protože dva vrcholy stupně 3 musí být spojené s ostatníma a tím již získáme celý graf jednoznačně. C ne, neboť lze vrchol stupně 2 zanedbat a zbytek musí být K4. 1.6.11) Nejdelší C$ v obou, nejdelší indukovaná C@ v A & jen C5 v B. 1.6.12)* 20, po vynechání jednoho vrcholu jsou vždy dvě možnosti na vyplnění zbytku kružnicí. 1.6.13)* (4 ) • 3, neboť (4 ) způsoby vybereme čtveřici vrcholů pro ten podgraf a každé 4 vrcholy lze třemi způsoby propojit do kružnice. (1.6.14)* Je jich 10, 6 z nich vznikne různým přidáváním vrcholů stupně 2 na hrany úplného 122 grafu K4 a 4 další jsou jiné. 1.6.15) ... 1.6.16) Vlevo 4, vpravo 3. 1.6.17) Vlevo 3, vpravo 3. 1.6.18) A ~ B ~ D, ale C má kružnici délky 4. 1.6.19)* 11 2.1.1) B 2.1.2) 4 2.3.1) Vrcholově n-souvislý. 2.3.2) Najdeme 3 disjunktní cesty mezi x,y. Proto musíme vypustit 3 vrcholy. 2.3.3) Prostě začněte z C5. 2.3.4) 1 do kružnice. 2.3.5) (V) 2.3.6)* Třeba podle přidávání uší - poslední přidaná cesta v konstrukci našeho grafu G má délku 1, neboli je naší hranou e. Proč? 2.4.1) Ne, má čtyři vrcholy lichého stupně. 2.4.2) Tři, dvě by teoreticky stačily na změnu všech stupňů na sudé, ale v tomto grafu jen dvě hrany prostě přidat nejdou. 2.5.1) 5, samé trojúhelníky. 2.5.2) 6, samé úplné grafy K5. 2.5.3) Souvislý s 15 hranami (ke každému vrcholu 3 sousedé). 2.5.4) 18, stupně > 3, třeba jako šestiboký hranol. 2.5.5) a) 28: Kg + K^ Ku b) 9: K3 + K3 + K3 + Kx 2.5.6) Jen v A: graf Ä2,3 a graf C5 s jednou diagonálou; C: cesta délky 4 a trojúhelník s hranou vedie. Pro B uvažte doplněk toho grafu - má stupně 2,1,1,1,1, což dá jednoznačný graf. 2.5.7) Jen B: úplný K4 s hranou vedle a dále K4 s "rozpojenou" hranou. Pro A jde sestrojit jen kružnice C5, protože na nesouvislý nemá dost hran. 2.5.8)* A~C~D 2.5.9)* 5 2.5.10)* Některý vrchol má stupeň aspoň 3, jinak vezmeme doplněk. Pak ti tři sousedi jsou nezávislí... 2.5.11) Třeba úplný bipartitní K34. 2.5.12) Ano, ale jen otevřeným. 2.5.13) Není to strom, proto obsahuje kružnici. 2.5.14)* Pomůže vám nakreslení uzavřeným tahem... 2.5.15) Jde o Eulerovský tah, který musí být uzavřený, neboť všechny stupně jsou sudé 6 (plus 2 za smyčku). 3.1.1) 1, ale jen 0 pro graf na jednom vrcholu. 3.1.2) 2 3.1.3) 5 3.1.4) 7 3.1.5) n — 1 - tj. počet hran kostry. 3.1.6) 3, najdete příslušnou dvojici vrcholů? 3.1.7) Poloměr 2, centrum obsahuje právě 3 vrcholy (najdete je?). 3.1.8) Třeba: 3.1.9)* rad(G) < diam(G) < 2 • rad(G), rovnost v prvním pro Kn, v druhém pro cestu. 123 X (3.2.1) Vyjde /O 1 2 1\ 2 (3.2.2) (3.3.1) (3.3.2) 1 \í 2 1 0/ Není, hodnoty s jedním indexem t se přece v iteraci t nezmění nikdy. 5 Jsou to vrcholy ve zbylých dvou cípech hvězdy, do každého dalšího vrcholu je z nich vzdálenost nejvýše 4. Lépe to nejde. (3.3.3) Určitě bychom měli zakázat bezprostřední opakování hran. V případě existence záporných cyklů bychom se museli omezit jen na prosté cesty. (3.4.1) Krok výběru dalšího vrcholu ke zpracování- i když bereme nejbližší nezpracovaný vrchol, z jiného, vzdálenějšího, vrcholu se lze později přes hranu záporné délky dostat do vybraného vrcholu "kratší" cestou. (3.4.2) Bohužel nebude, důvod je stejný jako v předchozí otázce. Je nutno použít jiné algoritmy. (3.4.3) w(xy) +Pv(y)>\\x,y\\+ Pv(y) > Pv(x) (3.4.4) Pak (za samozřejmého předpokladu pv(v) = 0) nutně bude upravená délka některé hrany na optimální cestě zídoo záporná. Neboli býti dolním odhadem je nutná podmínka pro přípustný potenciál, bohužel ale obecně nedostačující. (3.5.1) Vlevo 3 a vpravo 2. (3.5.2) Vlevo 3 a vpravo 5. (3.5.3) 3. Ten prostřední vrchol má vzdálenost < 2 do každého dalšího. Zbytek grafu je grafem krychle, kde největší vzdálenost 3 mají protilehlé dvojice vrcholů (ve smyslu geometrické krychle). Z těchto 4 dvojic má kratší spojení přes prostřední vrchol, takže zbývají 3 dvojice. (3.5.4) 2 - jedná se o graf krychle, tak přidáme dvě úhlopříčky na jednu stěnu-čtverec. Pak budou vzdálenosti < 2. Naopak jedna hrana nestačí, protože po přidání libovolné hrany e stále najdeme dva protilehlé vrcholy krychle, které hraně e nepatří, a tyto dva vrcholy zůstanou ve vzdálenosti 3. (3.5.5) 2 + 3 + 2 = 7 (3.5.6) 10. Vezmeme jeden vrchol v, ten má 3 sousedy a každý ze sousedů v má 2 další sousedy mimo v. To je dohromady 10 vrcholů a více jich už nemůže být, protože vzdálenosti jsou < 2 od v. Nakreslete si takový graf! (3.5.7)* 22, což je |_45/2_|, ohodnocení hran v pořadí 1, 2, 3, 4, 5, 7, 6, 8, 9. Garantovat vždy můžeme existenci dvojice ve vzdálenosti ???. (3.5.8) Vzdálenost 14 mezi 7 a 5. (3.5.9)* Spočítejte si, kolik vrcholů může být do vzdálenosti 3... (3.5.10) (3.5.11)* Ano, musí. (3.5.12) Ano. (3.5.13)* Osmi. (4.1.1) Jsou to cesty Pn a úplné bipartitní grafy K\^n. (4.1.2) Lze, ale jenom o kružnici. Úplné grafy K\ a K2 totiž stromy jsou. (4.1.3) 3, jeden bez hran, jeden s jednou hranou a poslední strom s dvěma hranami. (4.1.4) 2, cesta P3 a hvězda K\ß. (4.1.5)* Nenajdete, to by bylo v rozporu s Důsledkem 4.5. (4.1.6)* Jen 4 (odtrhejte 8 vrcholů stupně 1, co zbude?). 11 9 ^ 15 (4.2.1) 124 (4.2.2) Centra jsou vyznačená: (4.2.3) Pokud centrum vyjde jeden vrchol, odebereme celkem 32 listů - za každou hranu jeden. Jinak odebereme jen 31 listů a jedna hrana zbude jako centrum. (4.3.1) ((()(()()()))((()())(()))) 4.4.1) 1, bez hran. 4.4.2) 2004 4.4.3)* Procvičení symbolických úprav matic... 4.4.4) Je celkem 5!/2 = 60 koster, co jsou cestou P4, dále jen 5 koster, co jsou hvězdou K\^ a nakonec 5 • 4 • 3 = 60 koster, které mají vrchol stupně 3. 4.4.5)* mn-lnm-x 4.4.6) Třeba kružnice Cg a C223 sdílející jeden vrchol. 4.5.1) 3 4.5.2) Ano, 2005 vrcholů podle Věty 4.3. 4.5.3) 2009 - 1 - 1 - 1 - 1 = 2005 4.5.4) 11, počítejte hrany v každé komponentě - stromu. 4.5.5) Graf není souvislý, 13 není spojeno s ničím. Není ani lesem, neboť 10,14,21,15 tvoří kružnici. 4.5.6) Vlevo B, vpravo A. 4.5.7) 3 až 8 koster. Nejméně koster, 3, vznikne pokud nová hrana vytvoří trojúhelník. Nejvíce, 8, pokud strom byl cestou délky 7 a nová hrana ji uzavře do kružnice délky 8. 4.5.8)* Levý graf 14. Pravý 56: Obvodová kružnice má 8 koster, dalších 3-5 = 15 koster obsahuje vrchní příčku a 15 spodní příčku, nakonec 3 • 3 • 2 = 18 koster obsahuje obě příčky. 4.5.9) (™) -n + í 4.5.10)* 4. Pro 3 vrcholy by každá kostra musela mít 2 hrany, ale 2 + 2 = 4 hrany mezi třemi vrcholy nelze mít. Na druhou stranu úplný graf K4 má takové dvě kostry. 4.5.11)* Třeba kružnice C503 s tětivou tvořící kružnici délky 4. 4.5.12) Platí. 5.1.1) Nalezneme kostru s největším celkovým ohodnocením. 5.1.2) Není potřeba na začátku všechny (mnoho) hrany seřadit, seřazují se jen některé hrany potřebné v průběhu algoritmu. 5.1.3) Hlavně nějaký rychlý typ haldy pro ukládání seznamu hran vycházejících ze současné komponenty ven a vybírání nejmenší z nich. 5.2.1) V jistém časovém okamžiku vidíme, že se zpracovávají 4 úkoly najednou, a proto méně než 4 pracovníci nestačí. 5.2.2) Také to bude fungovat, dokažte si sami. 5.4.1) Jakkoliv špatně, pro každý zvolený počet barev se dá nalézt špatný příklad, zkuste si to... 5.4.2) V pořadí jakéhokoliv souvislého prohledávání našeho grafu. 5.4.3) Jednoduše, prostě hladový algoritmus spustíme a on nikdy nepoužije barvu vyšší než k + 1, neboť každý vrchol má jen k (možná) obarvených sousedů. 125 (6.2.1) Tok 5. (6.2.2) Jen zdroj z. (6.2.3) Rez velikosti 4 oddělující dva vrcholy vpravo nahoře. (6.2.4) Protože rezervy kapacit jsou celočíselné, neboli aspoň +1 v každé iteraci, takže v konečném počtu kroků se dostaneme k maximálnímu toku. (6.2.5)* Myšlenka: Pokud se jednou nasycená hrana vrátí mezi nenasycené, bude to určitě na delší nenasycené cestě. (6.2.6) Viz http://en.wikipedia.Org/wiki/Ford-Fulkerson_algorithm#Non-terminating_example (6.3.1) Snadné... (6.3.2)* Klíčové je dokázat, že získaný tok v první fázi po navýšení vytváří cirkulaci na původním grafu G (součty ve všech vrcholech 0). (6.4.1) Velikost i 5: i /, X /• ti 4: i /:. i /. (6.4.2) Velikosti (6.4.3) Ano, reprezentanti jsou zapsaní první: (1,2,3), (2,1,4), (3,1,4), (4,2,3). (6.4.4) Ne, všech podmnožin je (3) = 10, ale prvků k reprezentaci jen 5. (6.5.1) 12 (6.5.2) 13, 11 a 9, po řadě. (6.5.3) Nemá - 6 z množin má sjednocení {3,4,5,6,7}, kde se najde jen 5 různých prvků pro reprezentanty. (6.5.4) Nemá - 6 z množin má sjednocení {1,2,3,4,9}, kde se najde jen 5 různých prvků pro reprezentanty. (7.1.1) 3 (7.1.2) Méně než 4 barvy nestačí, protože najdeme úplný podgraf na 4 vrcholech. Obarvení 4 barvami je snadné. (7.1.3) 0 pro prázdný, 1 pokud má jeden vrchol a jinak 2 podle Věty 7.5 - stromy totiž nemají žádné kružnice. (7.1.4) 102 barvami, postup je následovný: Odebereme jeden vrchol v, zbytek grafu rekurzivně obarvíme 102 barvami a v nejhorším případě dostanou sousedé vrcholu v 101 různých barev. Proto i v můžeme korektně dobarvit. (7.1.5) 3 oboje. (7.1.6) Na sdíleném trojúhelníku má každý z G, H tři různé barvy. Tudíž barvy H permutujeme tak (nezávisle na G), aby byly shodné s barvami G na tomto trojúhelníku. (7.1.7)* Jestliže jsou Vi, V2 vrcholové komponenty G— {u, v} a u, v dohromady mají více sousedů ve Ví, obarvíme nejprve podgraf indukovaný na V\ U {u, v}. Pokud u, v získají stejnou barvu, obarvíme indukčně podgraf indukovaný na V2 U {u, v} se ztotožněnými vrcholy u,v, jinak tento podgraf s hranou uv navíc. Nakonec obě obarvení ztotožníme vhodnou permutací barev. (7.1.8)* Nechť F je podgraf H. Jelikož je nyní G — {u, v} souvislý, v grafu H U {w} vede cesta z w do nejbližšího vrcholu t podgrafu F mimo u = v, takže t má v F stupeň menší než k. (7.1.9) Představte si w obarvené barvou 1, která pak nemůže být v žádném ze sousedů. Dále dokážeme, pro každé i, že vrchol ví můžeme nakonec obarvit (či přebarvit) stejně, jako vrchol tudíž dostáváme spor s barevností původního grafu. (7.2.1) 3, stejně jako u vrcholové barevnosti. (7.2.2)* n — 1 pro sudá nan pro lichá mimo 1. (7.2.3) Pokud by stačilo 5 barev, jedna barva by se musela vyskytnout \E(G)\/5 = 16/5 tj. aspoň 4-krát, což na 7 vrcholech nelze. (7.2.4) Ano, včetně důkazu. (7.2.5) 3, neboť pro seznamy 12 a 34 na jedné straně a 13,14, 23, 24 na druhé straně není obarvení. 126 (7.2.6)* Podobně předchozí úloze... (7.2.7) Stačí vzít nějaký s vrcholem, jehož vypuštění poruší souvislost. (7.3.1) A,B,C,F (7.3.2) Ano, patří, tyto kružnice napovíme a snadno ověříme. (7.3.3) Ani nemůže patřit, neboť se nejedná o rozhodovací problém! (7.3.4)* Pro k = 0,1, 2 lze barevnost efektivně určit, takže tam otázka patří přímo do třídy V. Také pro k = 3 patří problém barevnosti k do J\ÍV, neboť napovězené obarvení 3 barvami jsme schopni snadno ověřit, a zároveň dokážeme určit, že barevnost není 2 (kružnice liché délky). Ale pro k > 3 již problém (dle současných znalostí teoretické informatiky) do třídy J\ÍV nepatří, protože neumíme nijak efektivně prokázat, že graf G nelze obarvit méně než k barvami. (7.3.5)* A,D (7.3.6) Je to kupodivu ještě jednodušší než v Tvrzení 7.19. Prostě v převodu z vrcholového pokrytí na grafu G vytvoříme orientovaný graf, jehož vrcholy jsou vrcholy G a také středy hran G. Šipky vedou vždy od vrcholů do středů přilehlých hran. (7.3.7) V převodu připojte ke každému vrcholu nový vrchol stupně 1. (7.3.8)* Stačí G vytvořit tak, že k danému grafu připojíme jedním vrcholem w jeden nový trojúhelník. Právě vrchol w se pak v tahu bude muset zopakovat. (7.5.1) 3 (7.5.2) 4, všimněte si, že graf obsahuje K4. (7.5.3) 3 (7.5.4) 1 (7.5.5) 14, pokud vypustíme tři hrany z jednoho vrcholu, nebo 13, pokud vypustíme tři hrany jednoho trojúhelníku, nebo 12, pokud vypustíme tři disjunktní hrany. (7.5.6)* Dokážeme, že takto vzniklý graf je 2-degenerovaný, neboť každý graf stupně nejméně 3 musí ke stromu přidat aspoň 3 hrany. (7.6.1) Je to stejný převod, neboť to funguje v obou směrech. (7.6.2) Definujeme pro graf G nový graf H, jehož vrcholy budou odpovídat hranám grafu G, a hranami H budou spojeny dvojice hran z G sdílející vrchol. Potom prostě stačí v grafu H hledat nezávislou množinu velikosti p, což dá párování v G. (7.6.3)* Toto je fakt obtížné... (7.6.4)* Nepatří, neboť nijak polynomiálně neověříme, že graf G neobsahuje více než jednu Hamiltonovskou kružnici. Ani v případě negace problému nejsme schopni ověřit případ, kdy G neobsahuje žádnou Hamiltonovskou kružnici. (7.6.5) Přidejte do grafu nový vrchol x spojený se vším - pak H. kružnice v novém musí procházet x a po odebrání x z ní zbude H. cesta. (8.1.1) Je to graf krychle. (8.1.2) Graf pravidelného osmistěnu. (8.1.3) Užijte projekci z bodu velmi blízkého zvolené stěně. (8.1.4)* Obtížné... (8.2.1) v = 12, f = 20, v + f - h = 2, tedy h = 12 + 20 - 2 = 30. (8.2.2) 3 (8.2.3)* Jako v — h + f = 1 + k. Všimněte si, že za každou novou komponentu sice na pravé straně vztahu "přibude" 2, ale jedna vnější stěna se sdílí dohromady mezi všechny komponenty, a proto skutečně se pravá strana s každou komponentou zvýší o +1. (8.3.1) Rovinný jen B. (8.3.2) Pron= 1,2,3,4. (8.3.3) Jen pokud m < 2 nebo n < 2, jinak v sobě obsahuje K33,. (8.3.4) 3 - takto z kružnice délky 6 vytvoříme graf ^3,3, nakreslete si to. (8.4.1) 4 (8.4.2)* <2 127 8.4.3) Stačí dokázat, že takový graí je 2-degenerovaný. 8.4.4)* Viz článek DOI: 10.1016/0012-365X(95)00216-J, M. Voigt. 8.4.5) Protože každý rovinný graí lze obarvit 4 barvami a mezi 13 vrcholy čtyř barev je jedna barva aspoň na 4 vrcholech, mezi kterými pak nemohou být hrany. 8.6.1) Ano, stačí dolní levé dva vrcholy překreslit nahoru. 8.6.2) Ne, obsahuje podrozdělení Ksts, najdete jej? 8.6.3) 8 8.6.4) 11 8.6.5) Má vždy 10 vrcholů podle Eulerova vztahu. 8.6.6) Q - (3-7-6) = 6 8.6.7)* Sporem, co bude se stěnou přilehlou ke dvojici vrcholů tvořících řez? 8.6.8) Ano, stačí 2-řez, který jej rozdělí na mnoho komponent a každou z nich lze nezávisle zrcadlově převracet. 9.1.1) Podívejte se, sporem, na interval nejvíce vlevo -jeho dva sousedé na kružnici se pak musí překrývat... 9.1.2)* Opět si pomožte úvahami o položení a nuceném překrývání intervalů v reprezentaci... 9.1.3)* Intervalové plus neobsahují indukované K\ß. 9.1.4) Neprotínající-se intervaly uspořádáme podle jejich polohy na ose (zleva doprava). 9.2.1) Podívejte se na interval, který má první pravý konec zleva - všichni jeho sousedé se překrývají. Totéž zprava. 9.2.2) Podáte jeho simpliciální dekompozici. 9.3.1) Například velká kružnice s "ocáskem" délky 2. 9.3.2) Například kružnice délky 5 s dalším vrcholem spojeným všude. 9.3.3) Například K>j^. Umíte toto krátce zdůvodnit? 9.3.4)* Například ^13,13, souvisí s problémem zvaným "kissing number"... 9.3.5)* Spojte úsečkama středy kruhů a dokažte, že se takové hrany neprotínají. 9.4.1) Vezměte rovinné nakrelsení a kolem každého jeho vrcholu "obejděte půlhrany" z něj vycházející jeho křivkou. 9.4.2) Třeba do každé trojúhelníkové stěny K4 přidejte nový vrchol spojený do vrcholů toho trojúhelníka. 10.1.1)* Uspořádáme intervaly podle jejich konců a vždy do dominující množiny vložíme poslední interval protínající se s prvním dosud nepokrytým. 10.1.2) Jako doplněk nezávislé množiny, kterou umíme. 10.1.3)* Myšlenka je následovná: Je-li x simpliciální vrchol, tak ze sousedů x může být v nezávislé množině jen jeden (tvoří kliku), takže si neuškodíme, pokud dáme do nezávislé množiny přímo x. 10.2.1) Docela přímočaré - uspořádání v druhé definici je přesně postup odtrhávání simpliciální ch vrcholů od konce... 10.2.2) Jinak by se porušila interpolační vlastnost; každá dvojice kliky má hranu a ta musí být ve společném balíku. 10.2.3) Třeba úplné podle předchozí otázky... 10.2.4)* Třeba velká "mříž". Podle hry na četníky a zloděje je třeba více četníku než je počet řádků / sloupců mříže. Proč? 10.2.5) Jeden četník se postaví napevno a další dva vzájemným přeskakováním projdou zbytek kružnice. Pokud jsou jen dva četníci, v některém okamžiku se jeden z nich musí zvednou v helikoptéře a tehdy zloděj uteče kamkoliv jinam - hra je zas na začátku a nikam nevede. 10.3.1) Ano. 10.3.2)* Je potřeba přesně path-width plus 1 četníků k chycení zloděje, kterého četníci nevidí dokud ho nedopadnou. 10.3.3) 2, menši byt nemůže a uspořádaní na 2 si najdete sami... 10.3.4) A < 2 • bandwidth 128 (10.3.5) Horní odhad snadný, pro dolní je třeba nahlédnout, že každý podkubický strom s 6 listy má hranu oddělující aspoň dva listy na každé straně. (10.3.6) Využijte, že každý podkubický strom s 15 listy má hranu oddělující na každé straně aspoň 5 listů. (10.3.7)* Převádějte dekompozice jednu na druhou... (10.3.8) Zprava třeba úplné grafy, zleva úplné bipartitní s odebraným párováním. (10.3.9) 1 (10.3.10) Třeba cesty. (10.3.11) 1 pro C3, C4, jinak 2. (10.3.12)* Třeba velká mříž, podobně jako s tree-width. (10.4.1)* Ano, ale není to lehké... Je třeba ukládat všechny možnosti spárování hraničních vrcholů (pro separace v dekompozici) pomocí systému cest pokrývajících všechny vrcholu v tomto podstromu dekompozice. To je vzhledem k fixní šířce dekompozice konstantně velká informace. (10.5.1) Jsou to lesy, acyklické grafy. (10.5.2) Jsou to tzv. sériově-paralelní grafy. (10.5.3)* Jsou to grafy, které lze nakreslit do roviny tak, aby všechny vrcholy ležely na vnější stěně. (10.5.4)* No, měli bychom důkaz P = NP, ale žádný použitelný algoritmus k tomu. Zajímavá situace... (11.3.1) IV^IWI (11.3.2)* "Rozviňte" si pro spor takové nakreslení do roviny, dostanete podle Eulerova vztahu triangulaci (nekonečnou) roviny, a odvoďte následně fakt, že směr rotace hran kolem vrcholů se v této triangulaci musí zachovávat. To je spor s neorientovatelností Kleinovy láhve. (Těžké k přečtení, že? Ale krátké.) (11.3.3) Jenoznačně pro hodnoty 2 a všechny liché, pro ostatní sudé 0, —2, —4,... nerozlíši mezi příslušnou orientovatelnou a neorientovatelnou plochou. (11.3.4) Samozřejmě, nakrelete si třeba K4 i na torus. Vždy však lze definovat nejmenší a největší takovou plochu pro daný graf. (11.3.5) Obsahuje dvě hranově disjunktní kopie Ks, jen jedna z nich může ke svému nakreslení "využít" crosscap, ta druhá by byla rovinná, spor. (11.3.6) Z Eulerova vztahu pro projektivní rovinu získáme odhad počtu hran h < 2v — 2 pro grafy bez trojúhelníků, ale 15 > 16 — 2, spor. (11.3.7)* ... (11.5.1) Není-li graf projektivní, obsahuje jeden ze zakázaných minorů (32 souvislých), přitom vlastnost míti rovinné pokrytí se jednoduše dědí na minory. (11.5.2) Obdobná úvaha jako v 11.3.5. (11.5.3)* Opět se počítá vhodně počet hran proti Eulerovu vztahu... (11.5.4)* První je v podstatě stejná, ale řešení pro ÍÍ35 vyžaduje pomocné tvrzení, že vrcholy emulátoru zobrazované na vrcholy stupně 3 mohou být také upraveny na stupně 3. 129 Reference [1] R. Diestel, Graph Theory (third edition), Springer, 2005. Online http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ [2] J.L. Gross, J. Yellen, eds. Handbook of Graph Theory, CRC Press, 2004. [3] L. Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983. [4] M. Mareš, Krajinou grafových algoritmů, ITI MFF UK, 2007. http://iti.mff.cuni.cz/series/files/iti330.pdf. [5] J. Matoušek a J. Nešetřil, Kapitoly z Diskrétní Matematiky, Karolinum, UK Praha, 2007. [6] J. Matoušek and J. Nešetřil, Invitation to Discrete Mathematics, second edition. Oxford University Press, 2008. [7] B. Mohär, C. Thomassen, Graphs on Surfaces, Johns Hopkins, 2001. [8] J. Oxley, Matroid Theory, Oxford University Press, 1992. 130