Teorie Grafů (FI: MA010) Doc. RNDr. Petr Hliněný, Ph.D. hlineny@fi.muni.cz 14. srpna 2008 Verze 1.00. c 2005­2008 Petr Hliněný. Obsah I Základy 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 26 3.1 Vzdálenost v grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Výpočet metriky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Vážená (ohodnocená) vzdálenost . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 Hledání nejkratší cesty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.5 Cvičení: Příklady o grafových vzdálenostech . . . . . . . . . . . . . . . . . 32 II Další Užitečné Oblasti a Problémy 37 4 Stromy a les 37 4.1 Základní vlastnosti stromů . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Kořenové stromy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.3 Isomorfismus stromů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.4 Kostry grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.5 Cvičení: Příklady o stromech a kostrách . . . . . . . . . . . . . . . . . . . 46 5 Minimální kostry, Hladový algoritmus 48 5.1 Hledání minimální kostry . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2 Hladový algoritmus v obecnosti . . . . . . . . . . . . . . . . . . . . . . . . 50 5.3 Pojem matroidu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.4 Kdy hladový algoritmus (ne)pracuje správně . . . . . . . . . . . . . . . . . 53 5.5 Cvičení: Příklady o stromech, kostrách a hladovém postupu . . . . . . . . 55 6 Toky v sítích 58 6.1 Definice sítě . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.2 Hledání maximálního toku . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.3 Zobecnění sítí a další aplikace . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.4 Cvičení: Příklady toků v sítích . . . . . . . . . . . . . . . . . . . . . . . . 66 ii 7 Barevnost a další těžké problémy 69 7.1 Barevnost grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2 Variace na barevnost a jiné . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.3 NP-úplnost grafových problémů . . . . . . . . . . . . . . . . . . . . . . . 74 7.4 Příběh problému vrcholového pokrytí . . . . . . . . . . . . . . . . . . . . . 78 7.5 Cvičení: Příklady o barevnosti grafů . . . . . . . . . . . . . . . . . . . . . 79 7.6 Apendix: Další NP-úplné grafové problémy . . . . . . . . . . . . . . . . . 80 8 Rovinnost a kreslení grafů 86 8.1 Rovinné kreslení grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.2 Rozpoznání rovinných grafů . . . . . . . . . . . . . . . . . . . . . . . . . . 89 8.3 Barvení map a rovinných grafů . . . . . . . . . . . . . . . . . . . . . . . . 91 8.4 O průsečíkovém čísle grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8.5 Cvičení: Příklady na rovinnost grafů . . . . . . . . . . . . . . . . . . . . . 94 III Vybrané Pokročilé Partie 96 9 Krátce o průnikových grafech 96 9.1 Intervalové a chordální grafy . . . . . . . . . . . . . . . . . . . . . . . . . 96 9.2 Třídy průnikových grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.3 Průnikové grafy křivek a úseček . . . . . . . . . . . . . . . . . . . . . . . . 99 10 Dekompozice grafů, minory a algoritmy 101 10.1 Tree-width ­ čtyři definice . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 10.2 Některé další parametry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 10.3 Efektivní algoritmy na dekompozicích . . . . . . . . . . . . . . . . . . . . 104 10.4 Minory v grafech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 11 Více o kreslení grafů 107 11.1 Kreslení grafů na plochy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 11.2 O problému rovinného pokrytí . . . . . . . . . . . . . . . . . . . . . . . . 109 11.3 Praktické ,,pružinové kreslení grafů . . . . . . . . . . . . . . . . . . . . . 110 IV 112 Klíč k řešení úloh 112 Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 iii 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 chuť do studia. Části věnované algoritmickým aplikacím navíc předpokládají jistou znalost a zběhlost v programování. Svým rozsahem látka odpovídá jednomu semestru běžné výuky včetně cvičení. Tento výukový text vychází ve svých základech z vynikající moderní učebnice [6] Kapitoly z Diskrétní Matematiky 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 [7]. 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šeho textu. Přednesený 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. Náš je text 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. Přejeme vám mnoho úspěchů při studiu 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 iv Pár slov o vzniku Původní učební text diskrétní matematiky 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 VŠB ­ TUO. Tento text byl pak autorem upraven a druhotně (především v teoretické oblasti) rozšířen podle potřeb výuky magisterského předmětu MA010 Teorie grafů na FI MU Brno od roku 2006. Je třeba podotknout, že nová třetí část textu je stále ve vývoji a očekáváme její další doplnění a rozšíření volitelných témat podle potřeb budoucí výuky. Za přípravu některých příkladů a zvláště za kontrolu celého textu patří dík také cvičícím ­ z FEI VŠB ­ TUO Martinu Kotovi, Ondřeji Kohutovi, Michalu Kolovratovi a Pavlu Moravcovi a z FI MU Brno Janu Boudovi, Janu Obdržálkovi a Pavlíně Vařekové. v Část I Základy 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ě definovat, 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ů a 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: V = {1, 2, 3, 4}, E = {1, 2}, {1, 3}, {1, 4}, {3, 4} 1 2 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: Cn 6 5 2 1 7 . . . 4 n 3 Cesta délky n má n + 1 vrcholů spojených za sebou n hranami: Pn 1 2 3 4 . . . n n + 1 Úplný graf na n 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem n 2 hran): Kn 1 2 3 4 n. . . Úplný bipartitní graf na m 1 a n 1 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: Km,n m n 2 Úlohy k řešení (1.1.1) Zapíšeme graf výčtem vrcholů {a, b, 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 Km,n 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 K9 nebo úplný bipartitní graf K6,6? 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 dG(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 tento zakreslený graf má stupně vrcholů 1, 2, 3, 4, 4, 4, 6. Definice: Graf je d-regulární, pokud všechny jeho vrcholy mají stejný stupeň d. Značení: Nejvyšší stupeň v grafu G značíme (G) a nejnižší (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ý. 2 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ť d1 d2 . . . dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupňů d1, d2, . . . , dn právě tehdy, když existuje graf s n - 1 vrcholy stupňů d1, d2, . . . , dn-dn-1, dn-dn - 1, . . . , dn-2 - 1, dn-1 - 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: s s s s s s s s s s s s s s s (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. 2 Ú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, 3? 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: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů V (H) V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V (H). Píšeme H G, tj. stejně jako množinová inkluze (ale význam je trochu jiný). Komentář: Na následujícím obrázku vidíme, co je (vlevo) a co není (vpravo) podgraf. (Zvýrazněny jsou vybrané podmnožiny vrcholů a hran.) Definice: Indukovaným podgrafem je podgraf H G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V (H). 4 ,,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í f : 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(u), 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). Komentář: 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 1 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 f isomorfismem, musí zobrazovat na sebe vrcholy stejných stupňů, tj. dG(v) = dH (f(v)). Naopak to však nestačí! Příklad 1.7. Jsou následující dva grafy isomorfní? s s s s s s s s s s s s 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 nerozliš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 1, se zobrazí na nejlevější vrchol 1 v druhém grafu (taky stupně tři). vrchol označený 1 se zobrazí na 1 . 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 1 se zobrazí na analogické sousedy 2 , 6 vrcholu 1 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: 5 s s s s s s 1 4 2 3 6 5 s s s s s s 1' 2' 3' 4' 5' 6' 2 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ů. 2 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 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 G, který je isomorfní nějaké cestě, říkáme cesta v G. * Podgrafu H 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ý pograf, který je maximální vzhledem k inkluzi.) * Podmnožině vrcholů X 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 G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G. Komentář: s s s s s s 1 4 2 3 6 5 s s s s s s 1 4 2 3 6 5 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á 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. 6 Příklad 1.9. Jsou následující dva grafy isomorfní? s s s s s s s s s s s s 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í. 2 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. s s s s s s s s (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 V × 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, ), kde V E = a : E V 2 V (V × V ) je incidenční zobrazení hran. Komentář: Značení V 2 v definici reprezentuje neorientované hrany, V neorientované smyčky a V × V orientované hrany a smyčky. 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 K7 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]=1 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]-1] udávají seznam sousedů vrcholu i. Poznámka: Dávejte si pozor na symetrii hran v implementaci! To znamená, že pokud uložíte hranu g[i][j]=1, tak musíte zároveň uložit i hranu g[j][i]=1, 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.. . 8 Rozšiřující studium Rozsáhlý matematický úvod do teorie grafů je zahrnut v [6, Kapitola 3] 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_(data_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[5]. 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í isomorfismu grafů a dalších podobných grafových počítačových úloh, nejlépe je se podívat na http://cs.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: s s s s s s s s s s s s 2 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ť ). 9 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. A s s s s ss s s s s B s s s s ss s s s s C s s s ssss s s s Postupujme systematicky: Všechny tři grafy mají po 10 vrcholech a všechny vrcholy stupňů 3. Takto jsme je tedy nijak nerozliš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 s s s s ss s s s s C s s s ssss s s s a odpovídající bijekce je na pohled zřejmá. (Doplňte si ji společným očíslováním vrcholů obou grafů.) 2 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. s s s ssss s s s 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, 10 nejdelší při troše snahy najdeme indukovanou kružnici délky 7, jako třeba na následujícím obrázku: s s s ssss s s s s s sss s s 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á. 2 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. s s ss s s s s Použijeme-li k zápisu disjunktního sjednocení grafů symbol +, můžeme všechny možnosti systematicky vypsat: P1 +C3 +C3, P1 +C6, P2 +C5, P3 +C4, P4 +C3, P7. Existuje tedy právě 6 požadovaných grafů. 2 Ú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 B: 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 (1.6.6) Najděte a vyznačte isomorfismus mezi následujícími dvěma grafy na 7 vrcholech. s s s s s s s s s s s s s s 11 (1.6.7) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: s s s s s s s s s s s s s s s s (1.6.8) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: s s s s s s s s s s s s s s s s (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 s s ss s s ss B s s ss s s ss C s s s s ss s s D s s s s ss s s 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ňů A: 3,3,3,3,3,3, 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 C9? s s s s s s s s s s (1.6.13) Kolik podgrafů úplného grafu K10 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. 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. s s s s s s s s s s s s s s s s s 12 (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ěď. A s s s s ss s s s s B s s s s ss s s s s C s s s s ss s s s s D s s s s ss s s s s (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íť, 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 v0, e1, v1, e2, v2, . . . , en, vn , ve které vždy hrana ei má koncové vrcholy vi-1, vi. 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. 2 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 = v0, e1, v1, . . . , en, vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu w0 = u, který už bude cestou: ­ Předpokládejme, že nový sled W už má počátek w0, e1, w1, . . . , wi (na začátku i = 0, tj. jen w0 bez hran), kde wi = vj pro některé j {0, 1, . . . , n}. ­ Najdeme největší index k j takový, že vk = vj = wi, a sled W pokračujeme krokem . . . , wi = vj = vk, ek+1, wi+1 = vk+1, . . .. ­ Zbývá dokázat, že nový vrchol wi+1 = vk+1 se ve sledu W neopakuje. Pokud by tomu ale tak bylo wl = wi+1, l i, pak bychom na vrchol wi+1 ,,přeskočili už dříve z vrcholu wl, spor. ­ Nakonec skončíme, když wi = v. 2 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 v G. 2 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: s s s s ss s s s s s s Vidíte obě dvě komponenty? Úlohy k řešení (2.1.1) Který z těchto dvou grafů je souvislý? A s s s s s s s s B s s s s s s s s 15 (2.1.2) Kolik komponent souvislosti má tento graf? s s s s ss s s s 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ých komponent grafu Algoritmus projde a zpracuje každou hranu a vrchol grafu G. Průchod se děje po jednotlivých komponentách, po projití jedné komponenty se přejde na případnou další. 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í; uschovna U = {libovolný vrchol v0 grafu G}; stav(v0) = nalezený; // zpracování vybrané komponenty G while (U je neprázdná) { vybrat v U; U = U \ {v}; ZPRACUJ(v); for (e hrany vycházející z v) { if (stav(e)==iniciační) ZPRACUJ(e); 16 w = druhý vrchol e = vw; if (stav(w)==iniciační) { stav(w) = nalezený; U = U {w}; } stav(e) = zpracovaná; } stav(v) = zpracovaný; // případný přechod na další komponentu G if (U je prázdná && G má další komponenty) U = {lib. vrchol v1 další komponenty G}; } Příklady aplikací schématu Algoritmu 2.4 jsou uvedeny dále například v Důsledku 3.4 a v Algoritmu 3.11. 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 v0. (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 - 1)-souvislý. Pokud mluvíme jen o k-souvislém grafu, máme (obvykle) na mysli vrcholově k-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 - 1 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ů). s s s s s s s ss s s 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?) 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. 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.) s s s s ss s s s s s s ss s s s s ss s s s ss s 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 x 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. 2 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 18 grafu můžeme vést až 4 disjunktní cesty. U druhého grafu třeba mezi levým a pravým koncem 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, f E(G). Sestrojíme graf G podrozdělením obou hran e, f 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í e i f. 2 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 U1, U2 V (G), |U1| = |U2| = k v G existuje k zcela disjunktních cest z vrcholů U1 do vrcholů U2. Úlohy k řešení (2.3.1) Jaký stupeň souvislosti má úplný bipartitní graf Kn,n? (2.3.2) Kolik nejméně vrcholů musíte vypustit z nakresleného grafu, aby v něm nezbyla žádná cesta mezi vrcholy x a y? Zdůvodněte. s s s s ss s s x y (2.3.3) Sestrojte graf K5 ,,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 si sami toto tvrzení: Každý 2-souvislý graf G na alespoň čtyřech vrcholech, který má všechny stupně větší než 2, obsahuje hranu e takovou, že G - e je 2-souvislý. 2.4 Jedním tahem: Eulerovské grafy Asi 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 o kreslení grafů jedním tahem tak zařazujeme na závěr především z historických důvodů. 19 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. 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 G nakreslená jedním uzavřeným tahem TC. ­ Vzhledem k souvislosti grafu G každá komponenta 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. 2 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. 2 Úlohy k řešení (2.4.1) Lze tento graf nakreslit jedním otevřeným tahem? s s s s ss s (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í [6, Oddíly 3.2,8] a Eulerovským grafům [6, Oddíl 3.7]. Algoritmy pro procházení grafu jsou podrobně popsány (včetně netriviálních aplikací) v [3] a demonstrovány i v [4]. Za zmínku stojí i [5, Kapitola 3]. Pro hlubší teoretické poznatky a aplikace vyšší souvislosti grafů odkazujeme čtenáře na [1, Chapter 3]. 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. 20 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. s s s s ss s s s s a b c d ef g h i j V této ukázce budeme obrázky znázorňovat stavy Algoritmu 2.4 v jednotlivých krocích takto: Neprohledané 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. s s s s ss s s s s a b c d ef g h i j f s s s s ss s s s s a b c d ef g h i j f f s s s s ss s s s s a b c d ef g h i j f f f s s s s ss s s s s a b c d ef g h i j f f f f s s s s ss s s s s a b c d ef g h i j f f f f f s s s s ss s s s s a b c d ef g h i j f f f f ff s s s s ss s s s s a b c d ef g h i j f f f f ff f s s s s ss s s s s a b c d ef g h i j f f f f ff f f s s s s ss s s s s a b c d ef g h i j f f f f ff f f ff Tímto zpracování zadaného grafu skončilo. Mimo jiné jsme zjistili, že graf má jedinou komponentu souvislosti. 2 21 Příklad 2.12. Ukázka průchodu následujícím grafem do šířky z vrcholu a. s s s s ss s s s s a b c d ef g h i j V této ukázce budeme obrázky znázorňovat stavy Algoritmu 2.4 stejně jako v předchozím příkladě. s s s s ss s s s s a b c d ef g h i j f s s s s ss s s s s a b c d ef g h i j f f s s s s ss s s s s a b c d ef g h i j f f f s s s s ss s s s s a b c d ef g h i j f f f f s s s s ss s s s s a b c d ef g h i j f f f f f s s s s ss s s s s a b c d ef g h i j f f f f f f s s s s ss s s s s a b c d ef g h i j f f f f f ff s s s s ss s s s s a b c d ef g h i j f f f f f ff f s s s s ss s s s s a b c d ef g h i j f f f f f ff f ff Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu příkladu? 2 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 odpovídající prázdné množině je spojený se všemi sedmi ostatními vrcholy, takže graf je souvislý. Nakreslete si jej! 22 Každý vrchol i-prvkové podmnožiny je pak spojený s 23-i disjunktními podmnožinami doplňku. Celkem tedy máme součtem všech stupňů 1 2(7 + 3 22 + 3 21 + 20) = 13 hran. 2 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. 2 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. Příklad 2.15. Dány jsou následující čtyři jednoduché grafy na 12 vrcholech každý. A : s s s s ss s s s s ss B : s s s s ss s s s s ss C : s s s s ss s s s s ss D : s s s s ss s s s s ss 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: A : s s ss s s ss s s s s B : s s ss s s s sss s s C : s s ss s s s sss s s D : s s ss s s s sss s s 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. 23 (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 C. Dále zdůvodníme v obrázku, že B D obsahují celkem jen 4 kružnice délky 4, a tudíž A B a C B a stejně s D. Tím jsme hotovi, existuje právě jedna isomorfní dvojice B D. 2 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? s s s s ss s s s s s s s s ss s s s s 1 2 3 4 5 67 8 9 10 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ť G3 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í G3. (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. 2 Ú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) Kolik existuje neisomorfních grafů s 9 vrcholy, všemi stupně 2? Nakreslete je všechny a nezapomeňte na ty nesouvislé. (2.5.4) 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.5) Kolik nejméně hran musí mít graf na 12 vrcholech, aby stupeň jeho souvislosti byl 3? (2.5.6) 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. 24 (2.5.7) Existují dva neisomorfní jednoduché grafy se stejnou posloupností stupňů A: 2,2,2,3,3, B: 2,3,3,3,3, 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.8) Existují dva neisomorfní jednoduché grafy se stejnou posloupností stupňů A: 2,2,2,2,2, B: 1,1,3,3,3,3 ? (2.5.9) Kolik existuje neisomorfních jednoduchých grafů na 6 vrcholech s posloupností stupňů 1, 1, 2, 2, 2, 2 ? Všechny tyto grafy nakreslete a zdůvodněte i, proč jich není více. (2.5.10) Najděte mezi následujícími grafy všechny isomorfní dvojice a zdůvodněte svou odpověď. A s s s s ss s s s s ss B s s s s ss s s s s ss C s s s s ss s s s s ss D s s s s ss s s s s ss (2.5.11) Kolik navzájem neisomorfních jednoduchých grafů lze získat z grafu B v úloze 2.5.10 přidáním jedné hrany? (2.5.12) 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.13) 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-souvislý a přitom neobsahuje Hamiltonovskou kružnici. (2.5.14) Lze tento graf nakreslit jedním tahem? A uzavřeným? (Uprostřed není vrchol, jen se tam kříží hrany.) s s s s ss s s s s (2.5.15) Dokažte, že každý 3-regulární graf obsahuje 2-regulární podgraf. (2.5.16) Dokažte, že každý 4-regulární graf se dá rozložit na dva 2-regulární grafy. 25 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. a b c d x 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 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. V obecném případě však při určování vzdálenosti bereme do úvahy délky jednotlivých hran podél cesty (tyto délky musí být nezáporné!). Jako hlavní náplň lekce si uvedeme známý Dijkstrův algoritmus pro určování nejkratší cesty v grafu. (Tento algoritmus je, mimo jiné aplikace, také základem programů vyhledávajících vlaková/autobusová spojení.) Většina tvrzení a algoritmy obsažené v této přednášce je 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 definovat vzdálenost v grafech a její základní vlastnosti. Dalším úkolem je ukázat a správně pochopit Dijkstrův algoritmus pro hledání nejkratší cesty 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 v0, e1, v1, e2, v2, . . . , en, vn, ve které hrana ei má koncové vrcholy vi-1, vi. Definice 3.1. Vzdálenost dG(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 dG(u, v) = . 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ě dG(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í. Poznámka: V neorientovaném grafu je vzdálenost symetrická dG(u, v) = dG(v, u). Lema 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: u, v, w V (G) : dG(u, v) + dG(v, w) dG(u, w) . Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky dG(u, v) mezi u, v lze navázat sled délky dG(v, w) mezi v, w, čímž vznikne sled délky dG(u, v) + dG(v, w) mezi u, w. Skutečná vzdálenost mezi u, w pak už může být jen menší. 2 26 Zjištění vzdálenosti Věta 3.3. Nechť u, v, w jsou vrcholy souvislého grafu G takové, že dG(u, v) < dG(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 dG(u, v): Pro dG(u, v) = 0, tj. u = v je tvrzení jasné ­ vrchol u jako počátek prohledávání byl nalezen první. Proto nechť dG(u, v) = d > 0 a označme v souseda vrcholu v bližšího k u, tedy dG(u, v) = d - 1. Stejně tak značme w souseda vrcholu w bližšího k u, tedy dG(u, w) > dG(u, v). Potom byl vrchol v 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ž w, a tudíž sousedé v (mezi nima v) budou při prohledávání nalezeni dříve než sousedé w. 2 Důsledek 3.4. Základní algoritmus procházení grafu do šířky lze použít pro výpočet vzdálenosti z vrcholu u: Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého jsme jej nalezli. Komentář: My si ale dále ukážeme obecnější Dijkstrův algoritmus, který 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) = maxxV (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 V (G) takových, jejichž excentricita je rovna rad(G). ­ Steinerova vzdálenost mezi vrcholy libovolné podmnožiny W 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. Jedna zajímavost Pro zajímavost (a zvídavé studenty) si uveďme následující vlastnost grafů. Definice: Graf je vzdálenostně dědičný (distance-hereditary), pokud vzdálenost každé dvojice jeho vrcholů u, v je stejná ve všech indukovaných souvislých podgrafech obsahujících u, v. Fakt. Grafy bez kružnic jsou vzdálenostně dědičné. Fakt. Následující konstrukce vytváří vzdálenostně dědičné grafy: ­ Začněme z jediného vrcholu. 27 ­ Mějme dva grafy G1, G2 získané touto konstrukcí (rekurzivně). Vytvoříme jejich disjunktní sjednocení G1 ˙ G2. ­ Mějme dva grafy G1, G2 získané touto konstrukcí (rekurzivně). Vytvoříme jejich disjunktní sjednocení G1 ˙ G2 a přidáme všechny hrany mezi V (G1) a V (G2). (Najděte vzdálenostně dědičný graf, který nelze takto sestrojit. . . ) Věta 3.5. Graf G je vzdálenostně dědičný právě když každá kružnice délky alespoň 5 má v G dvě ,,zkřížené tětivy. Zkuste se zamyslet nad možným důkazem této věty. . . Úlohy k řešení (3.1.1) Jaká je největší vzdálenost dvou vrcholů v úplném grafu? (3.1.2) Jaká je největší vzdálenost dvou vrcholů v úplném bipartitním grafu K33,44? (3.1.3) Jaká je největší vzdálenost dvou vrcholů v kružnici C11? (3.1.4) Jaká je největší vzdálenost mezi dvěma vrcholy v následujícím grafu? s s s s ss s s s (3.1.5) Umíte nalézt graf na 8 vrcholech se všemi stupni 3 a průměrem 2? (3.1.6) 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 vzdálenosti z jednoho vrcholu do druhého, uvedeme si ještě ,,globální pohled na soubor všech vzdáleností v grafu, tedy na tzv. metriku grafu. Zajímavostí tohoto pohledu je především to, že výpočet celé metriky najednou má velice jednoduchý algoritmus, který není příliš známý a přitom je dobře použitelný i v jiných oblastech. (Jak třeba později uvidíte v teorii automatů.) 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.6. Iterativní 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 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 t 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!) 28 Poznámka: V praktické implementaci pro symbol 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í.) Algoritmus 3.7. Výpočet metriky grafu Tento algoritmus, pro graf s N vrcholy daný maticí sousednosti G, vypočte celou jeho metriku d. vstup: matice sousednosti G[][] grafu na N vrcholech, kde G[i,j]=1 pro hranu mezi i, j a G[i,j]=0 jinak; for (i=0; i 0 pro všechny hrany e. Definice: Mějme (kladně) vážený graf G, w. Délkou váženého sledu S = v0, e1, v1,e2, v2, . . . , en, vn v G myslíme součet dw G(S) = w(e1) + w(e2) + . . . + w(en) . Váženou vzdáleností v G, w mezi dvěma vrcholy u, v pak myslíme dw G(u, v) = min{dw G(S) : S je sled s konci u, v} . Lema 3.10. 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í graf vlevo. (Čísla u hran udávají jejich váhy, hrany bez čísel mají váhu 1.) Vážená vzdálenost mezi vrcholy a, c je 3, mezi b, c také 3. Jaká je vzdálenost mezi vrcholy a, b? Ne, není to 6, ale najdeme kratší cestu délky 5. 29 a 3 3 b c 4 x y 3 3 3 -4 V druhém příkladě vpravo je uvedena i hrana se zápornou vahou -4. Nejkratší cesta mezi vrcholy x, y tak má délku -2, ale pokud vezmeme sled, který hranu váhy -4 vícekrát zopakuje, dostaneme se na libovolně nízkou zápornou délku. To je samozřejmě nesmyslné, a proto se takovému problému radši vyhýbáme zákazem záporných vah hran. Ú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.4 Hledání nejkratší cesty Pro nalezení nejkratší (vážené) cesty mezi dvěma vrcholy kladně váženého grafu se používá známý tzv. Dijkstrův algoritmus. Poznámka: Dijkstrův algoritmus je sice 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ů. Zrovna tento algoritmus se například používá při vyhledávání vlakových či autobusových spojení. Pravděpodobně se i vy někdy dostanete do situace, kdy budete nejkratší cestu hledat, proto si tento algoritmus zapamatujte. Dijkstrův 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.11. Dijkstrův 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ů. vstup: graf na N vrcholech daný seznamem sousedů sous[][] a del[][], kde sous[i][0],...,sous[i][st[i]-1] jsou sousedé vrcholu i stupně st[i] a hrana z i do sous[i][k] má délku del[i][k]>0; vstup: u,v, kde hledáme cestu z u do v; 30 // 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 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. 2 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 P1, P2 mezi u, v, tak bychom vzali jejich symetrický rozdíl, podgraf H = P1P2 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. 2 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. 2 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. 2 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ší 38 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ě. s s s s 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, f do stromu T : Podle Důsledku 4.5 vznikne jen jedna kružnice procházející hranou e a neobsahující f, stejně tak jedna kružnice procházející f a neobsahující e. Nakonec stačí nahlédnout, že je nejvýše jedna možná kružnice procházející oběma hranami e, f: Pokud by takové byly dvě různé C1, C2, podívali bychom se na jejich symetrický rozdíl, podgraf H = C1C2, který má všechny stupně sudé, neprázdnou množinu hran a je navíc pografem stromu T . Takže stejně jako ve Větě 4.4 dostáváme spor s faktem, že podgrafy stromů s hranami musí obsahovat vrchol stupně 1. 2 Úlohy k řešení (4.1.1) Které ze základních typů grafů z Oddílu 1.1 jsou stromy? (A nezapomněli jste na jeden podtyp?) (4.1.2) Lze o některém ze základních typů grafů z Oddílu 1.1 říci, že to určitě nebude strom? (4.1.3) Kolik je neisomorfních lesů na třech vrcholech? Nakreslete si je. (4.1.4) Kolik je neisomorfních stromů na čtyřech vrcholech? Nakreslete si je. (4.1.5) Najdete graf s dvěma kružnicema, z něhož lze odebráním jedné hrany vytvořit strom? Zdůvodněte a případně nakreslete. (4.1.6) Určete, kolik neisomorfních stromů se všemi vrcholy stupňů 1 nebo 3 existuje na 14 vrcholech? 4.2 Kořenové stromy Při mnoha aplikacích stromových struktur se ke stromu jako grafu samotnému ještě váží dodatečné informace, jako třeba vyznačený jeden vrchol, tzv. kořen stromu, ze kterého celý strom ,,vyrůstá . Typickým příkladem jsou různé (acyklické) datové struktury, ve kterých je vyznačený vrchol ­ kořen, referován jako ,,začátek uložených dat. Jinak třeba evoluční stromy druhů v biologii mají za kořen jejich společného (dávného) předchůdce. Kořenové stromy mají také tradiční motivaci v rodokmenech a z toho vychází jejich běžná terminologie. Definice 4.8. Kořenovým stromem je strom T spolu s vyznačeným kořenem r V (T), zkráceně zapsaný dvojicí T, r. Komentář: Příklad kořenového stromu je na následujícím obrázku: s ss s s s s s ss s s r f Zajímavostí je, že v informatice stromy většinou rostou od kořene směrem dolů. (Však také nejsme v biologii. . . ) 39 Definice: Mějme kořenový strom T, r a v něm vrchol v. Označme u souseda v na cestě směrem ke kořeni r. Pak je u nazýván rodičem v a v je nazýván potomkem u. Komentář: Kořen nemá žádného rodiče. V přirozeně přeneseném významu se u kořenových stromů používají pojmy prarodič, předchůdce, následovník, sourozenci, atd. Zběžná ilustrace použití těchto pojmů je na následujícím schématu stromu. s ss s s s s s ss s spotomci rodič "prarodič" kořenf Často se také setkáte v kořenových stromech s označováním ,,otec­syn místo rodič­potomek. My jsme takové označení nepoužili proto, že by (hlavně v zemích na západ od nás) mohlo být považováno za sexistické. Definice: Vrchol stupně 1 v libovolném stromu nazýváme listem. Komentář: Pozor, i kořen stromu může být listem, pokud má stupeň 1, ale obvykle se to tak neříká. List kořenového stromu, který není kořenem, nemá potomky. Občas se můžeme dostat do situace, kdy k danému stromu potřebujeme zvolit kořen, aby jeho volba byla jednoznačná, tj. aby bylo zaručeno, že pro dva isomorfní stromy nezávisle zvolíme tentýž kořen. K tomu nám dopomůže následující názorná definice centra. Definice: Centrem stromu T rozumíme buď vrchol nebo hranu nalezenou v T následujícím postupem: ­ Pokud má strom T jeden vrchol, je to jeho centrum. Pokud má strom T dva vrcholy, je jeho centrem hrana spojující tyto dva vrcholy. ­ Jinak vytvoříme menší strom T T vypuštěním všech listů T najednou. Je zřejmé, že T je neprázdný, a vracíme se na předchozí bod. Získané (rekurzivně) centrum T je zároveň centrem T. Příklad 4.9. Ilustrací definice centra jsou následující dva postupy nalezení centra (zleva doprava): s s s s s s s s ss s s s s s s s s s s sf s ss s s s s ss s s ss s s s f f V prvním stromě získáme kořen jako jediný vrchol po třech rekurzivních krocích odebrání listů. V druhém stromě je kořenem hrana, kterou získáme po dvou rekurzivních krocích. 2 40 Fakt. Pokud chceme danému (abstraktnímu) stromu přiřadit jednoznačně kořen, je nejlepší jej přiřadit centru stromu. Speciálně, pokud je centrem hrana, bude kořenem nový vrchol ,,rozdělující tuto hranu na dvě. Viz předchozí příklad: s ss s s s s ss s f s ss s f s s sf Další dodatečnou informací často vázanou ke kořenovým stromům je nějaké uspořádání potomků každého vrcholu, jako třeba seřazení potomků v rodokmenech podle jejich data narození. To formalizujeme následující definicí. Definice: Kořenový strom T, r je uspořádaný, pokud je pro každý jeho vrchol jednoznačně dáno pořadí jeho potomků (zleva doprava). Uspořádaný kořenový strom se také nazývá pěstovaný strom. Komentář: Uspořádaný kořenový strom si jinak také můžeme představit jako strom s vyznačeným kořenem a pevně zvoleným nakreslením v rovině bez křížení hran. Nakreslení hran potomků vzhledem k hraně rodiče pak udává (ve zvolené orientaci) pořadí potomků. Tento pohled vede k názvu pěstovaný strom. Uspořádání potomků vrcholu ve stromu je přirozeně požadováno v mnoha praktických situacích. Například ve stromových datových strukturách jsou často potomci explicitně seřazeni podle daného klíče, jako třeba ve vyhledávacích binárních stromech. I v případech, kdy uspořádání potomků ve stromě není dáno, je možné jej jednoznačně definovat, jak uvidíme v následující části. Úlohy k řešení (4.2.1) Binární vyhledávací strom je uspořádaný kořenový strom, který se pro daná data obvykle tvoří následovně: První prvek dat se uloží do kořene. Každý další příchozí prvek, pokud má menší klíč než kořen, uloží se rekurzivně do levého podstromu, pokud větší, tak do pravého podstromu. Vytvořte binární vyhledávací strom pro danou posloupnost dat s klíči 11, 15, 9, 5, 13, 10, 20, 21, 1, 6 . (4.2.2) Určete centra následujících dvou stromů: s s s s s s s s ss s s s s s s s s s s s s s s s s s s s ss s s s s s s s s s s s (4.2.3) Mějme libovolný strom s 33 vrcholy. Kolik jeho listů postupně odebereme, než určíme centrum? (Je to jednoznačné?) 41 4.3 Isomorfismus stromů Jelikož stromy jsou speciálním případem grafů, je isomorfismus stromů totéž co isomorfismus grafů obecně. Avšak na rozdíl od grafů, kdy je určení isomorfismu algoritmicky (nakonec i ručně) těžký problém, pro isomorfismus stromů existuje efektivní postup, který si ukážeme. Nejprve si uvedeme restriktivnější (tj. vyžadující více shody) verze definice isomorfismu pro kořenové a uspořádané stromy. Definice: (Dva stromy jsou isomorfní pokud jsou isomorfní jako grafy.) Dva kořenové stromy T, r a T, r jsou isomorfní pokud existuje isomorfismus mezi stromy T a T, který kořen r zobrazuje na kořen r. Komentář: Například následující dva (isomorfní) stromy nejsou isomorfní coby kořenové stromy. s ss s s s s s ss s r f s s s s s s s s ss s r f Definice: Dva uspořádané kořenové (pěstované) stromy jsou isomorfní pokud je mezi nimi isomorfismus kořenových stromů, který navíc zachovává pořadí potomků všech vrcholů. Komentář: Například následující dva (isomorfní) kořenové stromy nejsou isomorfní coby uspořádané kořenové stromy, neboť pořadí potomků levého syna kořene se liší. s ss s s s s s ss s r f s ss ss s s s ss s r f Kódování uspořádaných kořenových stromů Uspořádanému kořenovému stromu lze snadným postupem přiřadit řetězec vnořených závorek, který jej plně popisuje. (Možná jste se již s touto jednoduchou korespondencí závorek a kořenových stromů setkali, třeba při sémantické analýze matematických vý- razů.) Definice: s ss s s s s ss s s () () () () () () ( ()()() ) ( (()()()) () ) (()) ( () (()) ) ( ((()()())()) (()(())) ) Kód uspořádaného kořenového stromu se spočítá rekurzivně z kódů všech podstromů kořene, seřazených v daném pořadí a uzavřených do páru závorek. 42 Poznámka: Místo znaků `(' a `)' lze použít i jiné symboly, třeba `0' a `1'. Klíčovým a snadno zdůvodnitelným faktem o kódech pěstovaných stromů je toto tvrzení: Lema 4.10. Dva uspořádané kořenové (pěstované) stromy jsou isomorfní právě když jejich kódy získané podle předchozího popisu jsou shodné řetězce. Fakt. Je-li dán kód s uspořádaného kořenového stromu, příslušný strom nakreslíme následujícím postupem: ­ Při přečtení znaku `(' na začátku spustíme pero na papír, do kořene. ­ Při každém dalším přečtení znaku `(' nakreslíme hranu do následujícího potomka současného vrcholu. ­ Při každém přečtení znaku `)' se perem vrátíme do rodiče současného vrcholu, případně zvedneme pero, pokud už jsme v kořeni. Příklad 4.11. Nakreslete jako pěstovaný strom ten odpovídající závorkovému kódu ( (()(()()()())) (()()) ) . s ss ss s s s ss s f 2 Při určování isomorfismu obecných stromů použijeme Lema 4.10 pro jejich jednoznačnou reprezentaci uspořádanými kořenovými stromy, ve které kořen volíme v centru a potomky seřadíme podle jejich kódů vzestupně lexikograficky (tj. abecedně). Jinak se dá také říci, že kód přiřazený stromu T je lexikograficky nejmenší ze všech kódů uspořádaných stromů vzniklých z T s kořenem v jeho centru. Takový kód je zřejmě určující vlastností stromu T jako takového, a proto správnost následujícího algoritmu můžeme snadno nahlédnout. Algoritmus 4.12. Určení isomorfismu dvou stromů. Pro dané dva obecné stromy T a U implementujeme algoritmus zjišťující isomorfismus T ? U následovně v symbolickém zápise: Vstup < stromy T a U; for (X=T,U) { // určení center daných stromů pro kořeny x = centrum(X); if (x je jeden vrchol ) r = x; else nový r, nahraď hranu x=uv hranami ru, rv; k[X] = minimalni kod(X,r); } if (k[T]==k[U] jako řetězce) printf("Jsou isomorfní."); else printf("Nejsou isomorfní."); exit; Funkce minimalni kod(strom X, vrchol r) { 43 if (X má jeden vrchol) return "()"; Y[1...d] = {souvislé komponenty X-r, tj. podstromy kořene r}; s[1...d] = kořeny podstromů Y[] v odpovídajícím pořadí; for (i=1,...,d) k[i] = minimalni kod(Y[i],s[i]); sort lexikograficky (abecedně) podle klíče k[1]<=k[2]<=...<=k[d]; return "("+k[1]+...+k[d]+")"; } Pro zdůvodnění správnosti Algoritmu 4.12 je klíčové následující tvrzení. Věta 4.13. Mějme dva stromy T, U a nechť T, r a U, s jsou po řadě jejich kořenové stromy získané v první části Algoritmu 4.12 (kde r, s jsou centra T, U). Pak platí: a) T a U jsou isomorfní, právě když T, r je isomorfní U, s. b) T, r je isomorfní U, s, právě když minimalni kod(T, r) = minimalni kod(U, s). Důkaz(náznak): Tvrzení (a) ihned plyne z jednoznačnosti definice centra stromu. Za druhé (b) dokazujeme indukcí podle hloubky našich kořenových stromů T, r a U, s. (Zřejmě pokud mají různé hloubky, isomorfní nejsou.) Dva kořenové stromy hloubky 0 jsou vždy isomorfní a mají shodný kód ,,() . Dále vezmeme T, r a U, s hloubky > 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). 2 Úlohy k řešení (4.3.1) Odvoďte správný závorkový kód pro tento pěstovaný strom: s ss ss s ss s s s s s f (4.3.2) Nakreslete pěstovaný strom odpovídající závorkovému kódu ( ((()())()) ((())(())) ) . 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. 44 Příklad 4.15. Kolik různých koster má tento graf? s s s s s s s ssss 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. 2 Následující výsledek patří ke ,,krásným drahokamům teorie grafů. Věta 4.16. Ú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. 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 = (qij)n i,j=1 grafu G o n vrcholech je definována: ­ qii = dG(i) (stupeň vrcholu), ­ qij = 0 pro vrcholy i = j nespojené hranou, ­ qij = -1 pro vrcholy i = j spojené hranou. Věta 4.17. Nechť Q je Laplaceova matice grafu G a matice Q vznikne vyškrtnutím jejího prvního řádku a sloupce. Pak počet koster grafu G je roven determinantu |Q |. Komentář: Důkaz této překvapivé věty je mimo dosah naši přednášky (využívá silné nástroje lineární algebry). Uvědomte si, proč samotná matice Q je singulární (determinantu 0) neboť součet prvků v každém řádku je 0. Je také možno vyškrtávat jiné řádky a sloupce, ale může se tím změnit znaménko determinantu. Úlohy k řešení (4.4.1) Kolik koster má graf K1? (4.4.2) Kolik koster má kružnice délky 2004? (4.4.3) Ověřte předchozí výsledek podle Věty 4.17. (4.4.4) Zkuste sami vlastním počítáním odvodit, že počet koster úplného grafu K5 je 125 = 53 . Návod: Zkuste něco chytřejšího, než kreslení všech koster. Co třeba se podívat na jednotlivé typy koster? (4.4.5) Odvoďte pomocí Věty 4.17, kolik koster má úplný bipartitní graf Km,n. (4.4.6) Dokážete nalézt souvislý graf s přesně 2007 kostrami bez kružnice C2007 jako pod- grafem? Rozšiřující studium Stromům, jejich isomorfismu a kódování se věnují [6, Oddíly 4.1,2]. Zájemci o hlubší studium počítání koster v grafech a příslušné důkazy si mohou přečíst (poměrně obtížnou) [6, Kapitolu 7]. 45 4.5 Cvičení: Příklady o stromech a kostrách Příklad 4.18. Zjistěte, zda následující dva stromy jsou isomorfní. s s s s s s s s s s s s ss ss s s s s ss s s Nejprve si ověříme, že stromy mají stejný počet vrcholů (hran je pak také stejně). K daným dvěma stromům najdeme jejich centra a překreslíme si je jako kořenové stromy s kořeny v centrech. s s s s s s s s s s s s fa b s s ss s s s s ss s s fx Nyní přejdeme k určení minimálního závorkového kódu pro levý strom (Algoritmus 4.12): Například při rekurzivním volání ve vrcholu b určíme kódy jeho podstromů jako '()' a '(()())'. Jelikož levou závorku považujeme za slovníkově menší, tyto dva podkódy seřadíme a spojíme takto '( (()()) () )'. Obdobně postupujeme dále. . . Nakonec v kořeni a získáme rekurzivními voláními kódy jeho tří podstromů '( (()()) () )', '()' a '( (()) ()() )'. Po 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 '((()())()())'. Po seřazení a spojení nám celkový minimální kód pravého stromu vyjde '( ((()())()()) ((())()) () )'. Napíšeme si tedy získané dva kódy pod sebe a uvidíme, kde se liší ( ((()())()) ((())()()) () ) ( ((()())()()) ((())()) () ) . Dané dva stromy tudíž nejsou isomorfní. 2 Příklad 4.19. Kolik různých koster má tento graf? s s s s s s s ssss x 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. 2 46 Ú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? s s s s s s s s s (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: (((()()())())(()(()))) s ss s s s s ss s s s ss s s s s ss s s (4.5.7) Kolik různých koster má tento graf? s s s s s s s s (4.5.8) 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.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) Kolik koster má graf na následujícím obrázku? s s s s ss s s (4.5.12) Dokážete nalézt souvislý graf s přesně 2003 kostrami bez kružnice C2003 jako podgrafem? Abyste si ušetřili čas, 2003 je prvočíslo. (4.5.13) Ověřte řešení Příkladu 4.19 podle Věty 4.17. 47 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ý graf G, 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 = min kostra TG eE(T) w(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. s s s s s s s s 1 4 2 343 12 1 2 1 3 2 s s s s s s s s 1 4 2 343 12 1 2 1 3 2 Algoritmus 5.2. ,,Hladový pro minimální kostru. Je dán souvislý vážený graf G, w s nezáporným ohodnocením hran w. ­ Seřadíme hrany grafu G vzestupně podle jejich ohodnocení, tj. w(e1) w(e2) . . . w(em). 48 ­ Začneme s prázdnou množinou hran T = pro kostru. ­ Pro i = 1, 2, . . . , m vezmeme hranu ei a pokud T {ei} nevytváří kružnici, přidáme ei do T. Jinak ei "zahodíme". ­ Na konci množina T obsahuje hrany minimální 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(e1) w(e2) . . . w(em). Vezměme množinu hran T0 té minimální 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 T0 = T, algoritmus pracoval správně. Předpokládejme tedy, že T0 = T, a ukážeme spor, tj. že toto nemůže ve skutečnosti nastat. Označme j > 0 takový index, že se množiny T0 a T shodují na prvních j - 1 hranách e1, . . . , ej-1, ale neshodují se na ej. To znamená, že ej T, ale ej T0. (Jistě nemůže nastat ej T, ale ej T0.) Podle Důsledku 4.5 obsahuje graf na hranách T0 {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 ek v C, která ek T a zároveň k > j. Potom však je w(ek) w(ej) podle našeho seřazení hran, a tudíž kostra na hranách (T0 \ {ek}) {ej} (vzniklá nahrazením hrany ek hranou ej) není horší než T0 a měli jsme ji v naší úvaze zvolit místo T0. To je hledaný spor. 2 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 ek 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 Jarníkovi. Avšak historicky vůbec první algoritmus pro problém minimální kostry (z roku 1928) byl nalezen jiným českým (brněnským) matematikem: Algoritmus 5.4. Borůvkův pro minimální 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 [6, Oddíl 4.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? 49 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ů: s s s s s s s s s s s s 1 2 1 3 4 2 Kolik je k 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. 2 50 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. (Tj. čím delší úkol, tím dříve mu hladově přiřadíme pracovníka.) s s s s s s s s s s s s s s 2 3 1 2 5 4 3 Takový 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, N), je takový systém N podmnožin nosné množiny X, ve kterém platí následující: 1. N 2. A N a B A B N 3. A, B N a |A| < |B| y B \ A : A {y} N Množinám ze systému N ří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 matroidu. 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 matroidu obsahují 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 {x} nezávislá. 2 Nyní uvedeme několik poznatků o stromech, které jsou relevantní pro zavedení "grafových" matroidů. Lema 5.9. Les na n vrcholech s c komponentami souvislosti má přesně n - c hran. 51 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ů. 2 Definice: Řekneme, že podmnožina hran F E(G) je acyklická, pokud podgraf s vrcholy V (G) a hranami z F nemá kružnici. Lema 5.10. Nechť F1, F2 jsou acyklické podmnožiny hran grafu G a |F1| < |F2|. Pak existuje hrana f F2 \ F1 taková, že F1 {f} je také acyklická podmnožina. Důkaz: Jelikož |F1| < |F2| a platí Lema 5.9, má podgraf G1 tvořený hranami z F1 více komponent než podgraf G2 tvořený hranami z F2. Potom však některá hrana f F2 musí spojovat dvě různé komponenty podgrafu G1, a tudíž přidáním f do F1 nevznikne kružnice. 2 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 mat- roidu. 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. Čá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". K4 a b c d ef a bc d e f 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 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 , matroid na X určený externí funkcí nezavisla(Y); setřídit X=(x[1],x[2],...,x[n]) tak, aby w[x[1]]<=...<=w[x[n]]; B = ; for (i=1; i<=n; i++) if (nezavisla(B{x[i]})) B = B {x[i]}; výstup: báze B daného matroidu s minimálním součtem ohodnocení vzhledem k w. 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. 52 Věta 5.12. Algoritmus 5.11 (hladový algoritmus) pro danou nosnou množinu X s váhovou funkcí w : X a pro daný matroid N 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(x[1]) . . . w(x[n]). Nechť indexy i1, i2, . . . , ik určují vybranou kprvkovou bázi B v algoritmu a nechť indexy j1, j2, . . . , jk vyznačují (třeba jinou?) bázi {x[j1], . . . , x[jk]} 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 {x[j1], . . . , x[jk]} 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 A1 = {x[i1], . . . , x[is-1]} a A2 = {x[j1], . . . , x[js]}, kde A2 má o jeden prvek více než A1 a všechny prvky A2 mají dle předpokladu menší váhu než w(x[is]). Podle definice matroidu existuje y A2 \A1 takové, že A1 {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[], < 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. 2 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 . (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 najde Algoritmus 5.11 optimální nezávislou množinu z N, 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í A{y} nezávislá. Nechť |A| = a, |B| = b, kde 2b > 2a+1. Zvolíme následující ohodnocení * w(x) = -2b pro x A, * w(x) = -2a - 1 pro x B \ A, * w(x) = 0 jinak. Hladový algoritmus přirozeně najde bázi B1 obsahující A a disjunktní s B \ A podle našeho předpokladu. Její ohodnocení je w(B1) = -2ab. Avšak optimální bází je v tomto případě jiná B2 obsahující celé B a mající ohodnocení nejvýše w(B2) (-2a - 1)b = 53 -2ab - b < w(B1). 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. 2 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. s s s sf f 1 2 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. 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. 2 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 [6, Oddíly 4.3,4.5]. Dosti obsáhlý rozbor algoritmů používaných na problém minimální kostry je v [5, 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 asi nejlepší anglickou monografií je [9]. Krátký čtivý úvod do matroidů je volně dostupný na [10]. 54 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). s s s s s s s s 1 4 2 343 12 1 2 1 3 2 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: s s s s s s s s 1 4 2 343 12 1 2 1 3 2 s s s s s s s s 1 4 2 343 12 1 2 1 3 2 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. s s s s s s s s 1 4 2 343 12 1 2 1 3 2 s s s s s s s s 1 4 2 343 12 1 2 1 3 2 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.) 2 Příklad 5.16. Najděme minimální kostru grafu z Příkladu 5.15 Jarníkovým algo- ritmem. 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 55 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.) s s s s s s s s f f f 1 4 2 343 12 1 2 1 3 2 s s s s s s s s f f f ff 1 4 2 343 12 1 2 1 3 2 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. s s s s s s s s f f f ff f 1 4 2 343 12 1 2 1 3 2 s s s s s s s s 1 4 2 343 12 1 2 1 3 2 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. 2 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 56 čí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? 2 Příklad 5.18. Vrcholovým pokrytím v grafu G nazveme množinu vrcholů X 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 = . ­ 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: s s s s s s s s s 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: s s s s s s s s sf f f ff s s s s s s s s s f f ff Snadno však zjistíme, že optimální vrcholové pokrytí má velikost jen 4 a je vyznačené na obrázku vpravo. 2 57 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 síť 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í síť 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 síť s danými kapacitami přepravy jako: 2 z 5 1 3 4 5 2 1 s 4 2 3 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) + je kladné ohodnocení hran, zvané kapacita hran. Komentář: 2 z 5 1 3 4 5 2 1 s 4 2 3 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 58 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. 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 f : E(G) + 0 splňující ­ e E(G) : 0 f(e) w(e), ­ v V (G), v = z, s : ev f(e) = ev f(e). Velikost toku f je dána výrazem f = ez f(e) - ez f(e). Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu F/C, kde F je hodnota toku na hraně a C je její kapacita. Komentář: Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno (ve směru této hrany, proto hrany musí být orientované). Tok je pochopitelně nezáporný a dosahuje nejvýše dané kapacity hrany. z 0/1 2/5 0/2 0/1 s 3/4 2/22/4 3/3 0/2 3/5 0/3 Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5. Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť 0 = e (f(e) - f(e)) = v ev f(e) v ev f(e) = v=z,s ev f(e) - ev f(e) . (Dvojité sumy uprostřed předchozího vztahu nabývají stejných hodnot pro všechny vrcholy kromě z a s dle definice toku.) Proto velikost toku počítaná u zdroje je rovna opačné velikosti toku počítaného u stoku ez f(e) - ez f(e) = - es f(e) - es f(e) . 59 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 najít co největší tok ze zdroje z do stoku s vzhledem k ohodnocení w. Formálně hledáme max f 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: z 0/1 2/5 0/2 0/1 s 4/4 2/23/4 3/3 0/2 4/5 1/3 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 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í řezu C rozumíme součet kapacit hran z C, tj. C = eC w(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. z s 3 4 1 1 4 1 2 4 1 Poznámka: Tato věta poskytuje tzv. dobrou charakterizaci 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 vůbec nevyzná v matematice. Důkaz Věty 6.5 bude proveden následujícím algoritmem. 60 Definice: Mějme síť S a v ní tok f. Nenasycená cesta (v S vzhledem k f) je neorientovaná cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících hran e1, e2, . . . , em, kde f(ei) < w(ei) pro ei ve směru z u do v a f(ei) > 0 pro ei v opačném směru. Hodnotě w(ei) - f(ei) pro hrany ei ve směru z u do v a hodnotě f(ei) pro hrany ei v opačném směru říkáme rezerva kapacity hran ei. 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. sz 3/4 1/2 1/1 2/3 2/4 +1 +1 +2 +2+1rezerva kapacity: 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 f 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ální rezervu kapacity hran v P; } until ( s U ); výstup vypíšeme maximální 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 f a každý řez C v síti S platí f C . Jestliže po zastavení algoritmu s tokem f nalezneme v síti S řez o stejné velikosti C = f , je jasné, že jsme našli maximální 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 f = 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: z s f(e) = 0 f(e) = w(e) U Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e U (odcházející z U) plný tok f(e) = w(e) a každá hrana e U (přicházející do U) tok f(e) = 0, takže eU f(e) - eU f(e) = eU f(e) = eC w(e) = C . To je přesně, co jsme chtěli dokázat o výsledném toku. Zbývá ,,selským rozumem nahlédnout, že eU f(e) - eU f(e) = f , a důkaz je hotov. 2 Z důkazu Algoritmu 6.6 odvodíme několik zajímavých faktů: 61 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ě. 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 síť do šířky. Tato implementace zaručeně skončí po O(|V (G)| |E(G)|) iteracích cyklu. Algoritmus 6.9. ,,Tří Indů 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. * Nalezené nenasycené cesty pak souběžně nasytíme ,,dynamickým algoritmem. Tato implementace zaručeně skončí už po O(|V (G)|) iteracích cyklu, ale jednotlivé iterace jsou poněkud náročnější. Úlohy k řešení (6.2.1) Jaký je maximální tok touto sítí ze z do s? z s 3 2 3 3 3 1 3 2 1 (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 z a s? z s 3 2 1 2 4 1 3 2 1 (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čí. 62 6.3 Zobecnění sítí a další aplikace Pojmy sítě a toků v ní lze zobecnit v několika směrech. My si zde stručně uvedeme tři možnosti: 1. U sítě můžeme zadat i kapacity vrcholů. To znamená, že žádným vrcholem nemůže celkem protéct více než povolené množství substance. 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 z 3 4 5 42 5 3 z s3 3 5 4 2 4 2. Pro hrany sítě lze zadat také minimální kapacity, tedy dolní meze toku. (Například u potrubní sítě mohou minimální vyžadované průtoky vody garantovat, že nedojde k zanesení potrubí.) V této modifikaci úlohy již přípustný tok nemusí vůbec existovat. Takto zobecněná úloha je také snadno řešitelná, ale my se jí nebudeme dále zabývat. 3. V síti lze najednou přepravovat více 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 také 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ších částech tohoto oddílu. 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í v (biparitním) grafu G je podmnožina hran M 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. 63 Algoritmus 6.10. 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ásle- dovně: s s s s s s s s s s A B z s 1 1 1 1 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.10: 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. 2 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.11. Nechť u, v jsou dva vrcholy grafu G a k > 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-1 vrcholů různých od u, 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. Různí reprezentanti Definice: Nechť M1, M2, . . . , Mk jsou neprázdné množiny. Systémem různých reprezentantů množin M1, M2, . . . , Mk nazýváme takovou posloupnost různých prvků (x1, 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. 64 Věta 6.12. Nechť M1, M2, . . . , Mk jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí J {1, 2, . . . , k} : jJ Mj |J| , neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno. Důkaz: Označme x1, x2, . . . , xm po řadě všechny prvky ve sjednocení M1 M2 . . . Mk. Definujeme si bipartitní graf G na množině vrcholů {1, 2, . . . , k}{x1, x2, . . . , xm} {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, xj} pro všechny dvojice i, j, pro které xj Mi. Komentář: Konstrukce našeho grafu G je obdobná konstrukci sítě v Algoritmu 6.10: 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 xj Mi. 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 Lematu 6.11 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 {x1, . . . , xm} (aby nevznikla cesta mezi u, v), a proto jJ Mj = |X {x1, . . . , xm}| = |X| - |X {1, . . . , 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ž jJ Mj |J| pro všechny volby J, což je dokazovaná podmínka naší věty. 2 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.3.1) Najděte největší párování v tomto bipartitním grafu: s s s s s s s sssss (6.3.2) Najděte největší párování v tomto bipartitním grafu: s s s s s s s sssss (6.3.3) Mají všechny tříprvkové podmnožiny množiny {1, 2, 3, 4} systém různých reprezen- tantů? 65 (6.3.4) Mají všechny tříprvkové podmnožiny množiny {1, 2, 3, 4, 5} systém různých repre- zentantů? Rozšiřující studium Problematika toků v sítích je běžnou součástí teorie grafů (i když není pokryta v [6]) a je možno najít její obsáhlejší popis třeba v [3], včetně demonstrace v [4]. Jiný podrobný popis variant algoritmů pro toky v sítích se nachází v prvních dvou kapitolách [5]. Z dalších internetových zdrojů je možno zmínit třeba http://en.wikipedia.org/wiki/Net_flow nebo http://mathworld.wolfram.com/NetworkFlow.html a implementace na http://www.cs.sunysb.edu/~algorith/files/network-flow.shtml. Navíc se toky v sítích objevují jako klasické téma kombinatorické optimalizace. 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.4 Cvičení: Příklady toků v sítích Příklad 6.13. Jaký je maximální tok touto sítí ze z do s? z s 2 5 3 3 4 1 2 6 1 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 z a s (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). z s 0/2 0/5 0/3 0/3 0/4 1 0/2 0/6 0/1 z s 2/2 0/5 0/3 0/3 2/4 1 0/2 2/6 0/1 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). z s 2/2 2/5 2/3 0/3 2/4 1 2/2 2/6 0/1 z s 2/2 3/5 2/3 0/3 3/4 1 2/2 3/6 1/1 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. 66 z s 2/2 4/5 3/3 1/3 4/4 1 2/2 4/6 1/1 z s 2/2 4/5 3/3 1/3 4/4 1 2/2 4/6 1/1 Zároveň je na posledním obrázku vyznačen i příslušný minimální řez velikosti 6. 2 Úlohy k řešení (6.4.1) Najděte maximální tok v následující 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. s s s s s s s s s s 6 5 3 2 3 1 2 5 4 3 3 2 4 41 1 2 5 z s (6.4.2) Najděte maximální tok v následující síti. s s s s s s s s s s 3 6 5 2 3 1 2 5 4 3 3 2 4 4 1 1 3 5 z s (6.4.3) Najděte maximální tok v následující síti. s s s s s s s s s s 6 5 3 2 3 1 2 1 4 3 3 2 4 41 1 1 5 z s 67 (6.4.4) Najděte maximální tok v následující síti. s s s s s s s s s s 1 6 5 2 3 1 2 2 4 3 3 2 3 4 1 1 4 6 z s (6.4.5) 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.4.6) 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}. 68 7 Barevnost a další těžké problémy Úvod 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 Kaliningradě). 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, proč tomu tak je. . . Takto se zde (a dále v Oddíle 8.3) 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 specifický problém a jeho obtížnost se blíže podíváme. Cíle Prvním cílem této lekce je definovat 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ů definovaných přirozeně na grafech a přivést je do kontextu teorie výpočetní složitosti a NP-úplnosti. Studující bez zájmu o informatické aspekty mohou látku týkající se složitosti klidně 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 rozlíš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) {1, 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 (G) pro které existuje obarvení grafu G pomocí (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. Příklad 7.2. Určete barevnost grafu s s s s . 69 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. 2 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 (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 (G) < n. 2 Příklad 7.4. Vraťme se k příkladu ,,barvení mapy z úvodu lekce a ukažme si, jak mapy souvisejí s grafy a jejich barevností. Označme si státy na následující mapě písmeny a, b, . . . , h. 1 1 2 3 4 2 3 1 a b c d e f g h s s s s s s s s a b c d e f g h Jednotlivé oblasti na mapě (předpokládáme, že každý stát má souvislé území, tj. státy = oblasti) prohlásíme za vrcholy našeho grafu a sousední dvojice států spojíme hranami. Nezapomeňme přitom, že ,,sousední znamená sdílení celého úseku hranice, ne jen jednoho rohu. Výsledkem bude graf nakreslený vpravo. Podíváme-li se nyní zpátky na definici barevnosti grafu, vidíme, že se jedná přesně o ten samý problém jako u barvení původní mapy. Při troše snahy také najdeme lepší obarvení uvedené mapy využívající pouhých tří barev: 2 1 2 3 1 2 3 1 s s s s s s s s 2 1 2 3 1 2 3 1 2 Podívejme se, které grafy mají nízkou barevnost. Je jasné, že jedna barva stačí, jen pokud graf nemá hrany. Grafy obarvitelné dvěma barvami už tvoří zajímavější třídu a jsou obvykle nazývané jedním slovem bipartitní. Poměrně jednoduchý popis bipartitních grafů je uvedený v následujícím tvrzení. Věta 7.5. Neprázdný graf G má barevnost 1 právě když nemá žádné hrany. G má barevnost 2 právě když nemá žádnou kružnici liché délky jako podgraf. Důkaz: Pokud graf nemá hrany, můžeme všechny vrcholy obarvit stejnou barvou 1. Naopak pokud mají všechny vrcholy stejnou barvu, nemůže graf mít žádnou hranu. Druhá část: Na jednu stranu, lichou kružnici nelze obarvit dvěma barvami, viz obrázek. Na druhou stranu si představme, že zvolíme libovolný vrchol v grafu G s barvou 1 70 a ostatní vrcholy obarvíme takto: Vrcholy, jejichž vzdálenost od v je lichá, obarvíme 2. Vrcholy, jejichž vzdálenost od v je sudá, obarvíme 1. Stačí nyní dokázat, že jsme získali korektní obarvení. s s s s s 1 2 1 2 ?? s s s s s s s v 2 1 1 2 1 2 1 Pokud bychom tak získali třeba dva vrcholy spojené hranou f 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. Vezmeme-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čí. 2 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 k-degenerovaného grafu je každý graf stupně nejvýše k, ale na druhou stranu k-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 k-degenerovaný, vybereme libovolný jeho vrchol v1 stupně nejvýše k a rekurzivní aplikací tohoto postupu obarvíme podgraf G - v1, který je podle definice také k-degenerovaný. Nakonec si všimneme, že k sousedé vrcholu v1 dostanou nejvýše k různých barev, takže v1 dobarvíme zbylou barvou. 2 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 (G) k až na případy, kdy G je úplný graf nebo lichá kružnice. 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 (Kk+1) = 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. 71 ˇ 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-1)-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. 2 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 (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˝os) 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˝ose: * 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á. 2 Úlohy k řešení (7.1.1) Kolika nejméně barvami korektně obarvíte graf pravidelného osmistěnu? s s s s s s 72 (7.1.2) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. s s s s s s s s (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) Nechť 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 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-1)-degenerovaný. (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 e(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í (G) e(G) (G) + 1. Komentář: Platí, že většina grafů splňuje (G) = e(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) k (k-prvkové podmnožiny). Nyní hledáme obarvení cch(V (G)) 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. 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ů. 73 Hamiltonovské grafy Definice: Kružnice C obsažená v grafu G se nazývá Hamiltonovská, pokud C prochází všemi vrcholy G. Obdobně mluvíme o Hamiltonovské cestě P v G, pokud cesta P 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ě u0, u1, . . . , uk. Podle její maximality leží každý soused u0 i uk na P. Pak existuje 0 < i < k takové, že u0ui+1 E(G) a zároveň ukui E(G). Pak u0ui+1 P ukui P tvoří kružnici v G a snadno plyne, že se jedná o Hamiltonovskou kružnici. 2 Ú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 na n? 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 K2,4. (7.2.6) Dokažte Tvrzení 7.13. (7.2.7) Nalezněte 3-regulární jednoduchý graf bez Hamiltonovské kružnice. 7.3 N 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 NP-úplnosti z oblasti algoritmické složitosti. Komentář: Definice složitostní třídy NP 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 NP, pokud jeho odpověď ANO lze prokázat (ve smyslu ,,uhodnout a ověřit ) výpočtem, který běží v polynomiálním čase. NP-úplné problémy jsou zhruba řečeno ty, které ve třídě NP mají nejvyšší obtížnost řešení. Od jednoho NP-ú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 (NP-úplných) problémů je v teorii grafů mnoho, bohužel by se dalo říci většina. To ostatně ukazuje, 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í NP-ú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 NP-úplný: 74 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 NP-úplného problému snadno ukážeme NP-úplnost mnoha běžných grafových problémů. Problém 7.16. 3-COL (3-obarvení grafu) Následující problém je NP-ú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. s s s X F T s s s s x1 x1 ... xi xi s s s ... ss s (x1 xi . . .) Například první půlhrana naznačené klauzule na obrázku je napojena na půlhranu značenou x1 vlevo, druhá půlhrana na půlhranu značenou xi vlevo, atd. Pokud v klauzuli chybí třetí literál, je jeho půlhrana 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í. NP-úplnost nyní vyplývá z 7.15. 2 Kromě barevnosti grafu je NP-ú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 NP-úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít nezávislou podmnožinu velikosti (aspoň) k? 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) 75 spojíme hranami do trojúhelníku Tv v G. s s s s s H v s s s s s s s s s s s s s s s G Tv 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 I 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 I právě jeden vrchol. Podle toho již určíme jednu ze tří barev pro vrchol v v H. 2 Problém 7.18. VC (vrcholové pokrytí) Následující problém je NP-úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít vrcholové pokrytí, tj. množinu C V (G) takovou, že každá hrana G má alespoň jeden konec v C, o velikosti nejvýše k? Důkaz: Problém vrcholového pokrytí jasně patří do NP a jeho úplnost je dokázána polynomiálním převodem z Příkladu 7.26. 2 Problém 7.19. DOM (dominující množina) Následující problém je NP-úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít dominující množinu, tj. množinu D V (G) takovou, že každá vrchol G má některého souseda v D, o velikosti nejvýše k? Důkaz (náznak): Problém dominující množiny jasně patří do NP a jeho úplnost je dokázána polynomiálním převodem z Příkladu 7.27. 2 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 NP-ú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 NP-úplný: Vstup: Graf G. Výstup: Lze v G najít kružnici procházející všemi vrcholy? 76 Důkaz: sv s s s Pv 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. 2 Problém 7.22. TSP (problém obchodního cestujícího) Následující problém je NP-ú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í. 2 Úlohy k řešení (7.3.1) Rozhodněte, které z následujících problémů patří do třídy P všech polynomiálně řešitelných problémů. (Předpokládejte při tom NP = P.) 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 NP problém zjistit, zda graf G obsahuje dvě Hamiltonovské kružnice, které nesdílí žádnou hranu? (7.3.3) Patří do třídy NP problém zjistit, jaká je barevnost grafu? (7.3.4) Je známo, že do třídy NP 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 NP 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 NP. (Předpokládejte při tom, že negace NP-úplných problémů už nepatří do třídy NP.) 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") NPúplný: Vstupem je orientovaný graf G a přirozené číslo k. Lze v grafu G najít podmnožinu D 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? Návod: Použijte třeba polynomiální převod z problému vrcholového pokrytí. 77 (7.3.7) Ukažte, že také následující problém tzv. "kubické kostry" je NP-ú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 NP-ú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 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 surfování 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 NP-úplné) tak rozdílné algoritmické chování.. . Ale dost pohádek, více konkrétních informací čtenář najde v [R. Downey, M. Fellows, Parametrized complexity, Springer 1999]. 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 NP-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 k-tic vrcholů grafu G. To je i pro malé fixní hodnoty k, třeba k = 10, 20 v praxi neprove- ditelné. * Avšak vrcholové pokrytí velikosti k dokážeme nalézt jednoduchým algoritmem v čase O(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 k? Pro inicializaci položíme C = a F = E(G). * Pokud F = , 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 = C{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, C a F. 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 O(2k n). 78 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.2738k ) Rozšiřující studium Problematika rovinného kreslení grafů a jejich barvení je úvodně pokryta v [6, Kapitola 5]. 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ží monografie Jensena a Tofta na stránce http://www.imada.sdu.dk/Research/Graphcol/. Více o NP-ú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 NP-úplnosti grafových problémů odkazujeme na české [3] nebo na další internetové zdroje jako http://en.wikipedia.org/wiki/NP-complete. Co se týče specificky parametrizované složitosti (lehce uvedené v Oddíle 7.4), lze mimo uvedenou monografii [Downey, Fellows] (která je snad již vyprodaná) 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: s s s s s s 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. s s s s s s 1 2 3 1 2 4 To znamená, že daný graf má barevnost 4. 2 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ě 3 2 + 4 2 = 3 + 6 = 9 hran. s ss s s s s 1 2 2 79 Ú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. s s s s s s s s (7.5.2) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. s s s s s s s s (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. s s s s s s s s (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. s s s s s s s s s (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ší N P-úplné 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 NP nebo ne a zda případně jsou NPú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 P1 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 P1. 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 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í. 80 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 I 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 I = V (G) \ J. Příklad je na následujícím obrázku. (Zakreslete si to také do některého vlastního grafu.) s s ss s s ss f f f s s ss s s ss f f f f f 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.) 2 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. s s ss s s ss f f f (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. 81 s s ss s f ff s s ss s s s s s s s f ff 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: Že vrcholové pokrytí C V (G) je zároveň dominující množinou v novém grafu H a že dominující množina D 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 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 V (G) takto: Pokud w D 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 O(n2) hran, a proto nový graf H má velikost O(n2) a v takovém čase jsme snadno schopni jej sestrojit. Je to polynom v n. 2 Problémy ve třídě N P Nyní se budeme věnovat otázkám, proč některé grafové problémy náleží či nenáleží do třídy NP. Komentář: Definice třídy NPse 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 NP, 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. Hamiltonovská 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 NP problém poznat, zda daný graf G obsahuje Hamiltonovskou kružnici? Jak již bylo řečeno výše u definice, třída NP 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 Hamiltonovské 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 Hamiltonovská kružnice 82 vyznačena tlustě, kdežto ve druhém neexistuje. s s s s ss s s s s s s s s s s s s s s 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 Hamiltonovské 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+1]} je hranou v grafu G pro i = 1, 2, . . . , n - 1 a také {k[1], 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 O(n) = O(n2), což je skutečně polynomiální. Proto problém existence Hamiltonovské kružnice patří do třídy NP. 2 Příklad 7.29. Patří do třídy NP problém poznat, zda daný graf G obsahuje nejvýše čtyři Hamiltonovské kružnice? Čtenář opět může navrhnout, že vhodnou nápovědou pro příslušnost do třídy NP jsou ony čtyři Hamiltonovské 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 Hamiltonovské, 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í Hamiltonovské 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 NP. Avšak pokud bychom otázku negovali, tj. ptali se, zda graf G obsahuje více než čtyři Hamiltonovské kružnice, tak by už problém do třídy NP 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. 2 N 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í NP-úplnosti problému měl vypadat. . . Komentář: Dle definice je NP-ú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ě NP. Předpokládejme, že o problému P již víme, že je NP-ú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 U pro problém Q tak, že Q odpoví ANO na nový vstup U 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 83 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 NP-úplný pro každé (i fixní) k 3. Nejprve musíme zdůvodnit, že problém patří do třídy NP. 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 NP-úplné. Stačí nám tedy nalézt polynomiální převod z problému 3-obarvení na problém k-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í k-obarvením G.) Schematickým obrázkem: s s s s 1,2,3 G s s s 4 5 k ... G Vidíme tedy, že jsme našli polynomiální převod ze 3-obarvení grafu G na k-obarvení grafu G, a proto je problém k-obarvení NP-těžký. Celkem dostáváme, že k-obarvení je NP-úplné. 2 Příklad 7.31. Hamiltonovská 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 NP-úplný. Již víme z Problému 7.21, zjištění existence Hamiltonovské kružnice je NP-úplné. Problém Hamiltonovské cesty taktéž náleží do NP, snadnou nápovědou existence je ukázat onu Hamiltonovskou cestu. Pro důkaz NP-ú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 Hamiltonovská 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á Hamiltonovská 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é vi ze zdvojených kopií v přidat novou hranu vedoucí do nového vrcholu wi stupně 1. Tyto přidané vrcholy w1, w2 pak nutně musí být konci Hamiltonovské cesty, pokud ona existuje (jinak se do vrcholů stupně 1 přece dostat nedá). 84 Schematickým obrázkem: s s s sv G s s s s s H s sw1 w2 v1 v2 2 Příklad 7.32. Pro jaké k je NP-ú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 NPúplný pro fixní 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 O(nk+1) ­ prostě projdeme hrubou silou všechny k-tice vrcholů grafu a pokaždé se podíváme, zda náhodou netvoří nezávislou množinu. Čas O(nk+1) je pochopitelně polynomiální pro každé fixní k, takže pak tento problém těžko může být NP-úplný. Naopak pro k na vstupu problému se jedná o NP-úplný problém podle našeho Tvrzení 7.17. 2 Ú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 NP 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 NPúplné, ale zkuste cvičně najít polynomiální převod Hamiltonovské cesty na Hamiltonovskou kružnici (naopak než v Příkladě 7.31). 85 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í. 1 1 2 3 4 2 3 1 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 ,,sousednost 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 definovat 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 nakreslení 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. s s ss s s ss s s s s s s 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). 86 Definice: Stěnami rovinného nakreslení grafu nazýváme (topologicky) souvislé oblasti roviny ohraničené tímto nakreslením grafu. Komentář: s s s s s s s s s s s s 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 snadné dokázat. 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: s s s s s s s s 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. * 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 Jordanova 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 + f - h = v + (f - 1) - (h - 1) = 2. Tvrzení tak plyne z principu matematické indukce. 2 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. 87 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 f 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 1 2 3f, neboli 2 3 h f. Dosazením do vztahu Věty 8.2 získáme 2 = v + f - h v + 2 3 h - h = v - 1 3 h h 3(v - 2) = 3v - 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 1 2 4f, neboli 2 4h f. Dosazením do vztahu Věty 8.2 získáme 2 = v + f - h v + 2 4 h - h = v - 1 2 h h 2(v - 2) = 2v - 4 . Tím jsme hotovi. 2 Důsledek 8.4. Každý rovinný graf obsahuje vrchol stupně nejvýše 5. Každý 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ň 1 2 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í. 2 Úlohy k řešení (8.1.1) Nakreslete rovinně tento graf: s s ss ss s s (8.1.2) Graf pravidelného dvacetistěnu má 12 vrcholů a 20 stěn. Kolik má hran? (8.1.3) Co je duálním grafem k rovinnému nakreslení grafu krychle? (8.1.4) K rovinnému nakreslení stromu přidáme dvě nekřížící se hrany. Kolik bude mít výsledný graf stěn? (8.1.5) Jak bude znít Eulerův vztah pro nesouvislý rovinný graf s k komponentami? (8.1.6) Dokažte, že graf každého 3D konvexního mnohostěnu je rovinný. (8.1.7) Dokažte, že graf každého 3D konvexního mnohostěnu je 3-souvislý. 88 8.2 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é nakreslení 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, K5 a K3,3 nejsou rovinné. K5 s s s s s K3,3 s s s s s s Při zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf K5 má 5 vrcholů a 10 > 3 5 -6 hran. Podobně graf K3,3 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.) 2 Důsledek 8.7. Grafy K5 a K3,3 nejsou rovinné. Význam grafů K5 a K3,3 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é délky. s s s s s s s s s s s s s s s s s 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ů K5 nebo K3,3 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ů K5 nebo K3,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 K3,3 než grafu K5. 89 Příklad 8.9. Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholů), nebo zdůvodněte nerovinnost grafu. A s s ss s s B s s ss s s s Po chvíli zkoumání určitě přijdeme na to, že graf A se dá nakreslit rovinně takto: s s ss s s a b cd x y s s s s s s a b c d x y Graf B na druhou stranu rovinný není podle Věty 8.8, protože je v něm obsaženo podrozdělení grafu K3,3, které je ukázáno na tomto obrázku: s ss s s s 2 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: Lema 8.10. Kružnice C v 3-souvislém rovinném grafu G je stěnou jeho nakreslení, 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 Jordanovy 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 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 x od y a to odporuje předpokladu 3-souvislosti, spor. 2 Důsledek 8.11. Každá dvě rovinná nakreslení 3-souvislého grafu jsou ekvivalentní. Závěrem si ještě bez důkazu uvedeme, že rovinné grafy vždy mají pěkné nakreslení v rovině. 90 Věta 8.12. Každý jednoduchý rovinný graf lze nakreslit v rovině (bez křížení hran) tak, že hrany jsou úsečky. Úlohy k řešení (8.2.1) Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholů), nebo zdůvodněte nerovinnost grafu. A s s ss s s s B s s ss s s s (8.2.2) Pro která n je úplný graf Kn rovinný? (8.2.3) Kdy je úplný bipartitní graf Km,n rovinný? (8.2.4) Kolik hran stačí přidat ke kružnici, aby vznikl nerovinný graf? 8.3 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 87). 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.13. 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.14. 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. 2 Už dávno je 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 [Thomassen] tohoto faktu dokazuje indukcí mnohem více (a je optimální): Věta 8.15. Každý rovinný graf bez smyček má výběrovou barevnost nejvýše 5. 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 = 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 f ,,rozdělíme G na podgraf G1 obsahující x, y a podgraf G2 sdílející hranu f s G1. Indukcí nejprve obarvíme G1, pak G2 taktéž splní indukční předpoklad a i jej dobarvíme. 91 ˇ 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. 2 Úlohy k řešení (8.3.1) Jaká je barevnost grafu pravidelného dvacetistěnu? (8.3.2) Nechť rovinný graf má každou stěnu délky 4. Jaká je jeho barevnost? Dokažte. (8.3.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.3.4) Dokážete najít rovinný graf, jehož výběrová barevnost je 5? (8.3.5) Proč každý rovinný graf na 13 vrcholech musí obsahovat nezávislou množinu velikosti 4? 8.4 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í i nerovinných grafů do roviny. 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 8.16. 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ý? s s ss s s ss s s s s s s s s s s 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? 2 Definice 8.17. 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. 92 Příklad 8.18. Určeme průsečíková čísla následujících dvou grafů: s s s s s s s s s s s s s s s s 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 K6 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. 2 Fakt: Přesné obecné hodnoty průsečíkových čísel nejsou známy ani pro úplné či úplné bipartitní grafy. Věta 8.19. Problém určit, zda průsečíkové číslo cr(G) k pro G a k na vstupu je NP-ú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 NP, 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: Věta 8.20. Pro fixní k lze otestovat, zda cr(G) k, v polynomiálním kvadratickém čase vzhledem k počtu vrcholů grafu. (2006: Dnes je známo i vylepšení v lineárním čase.) Poznámka: Dodnes zatím nevíme, jak v polynomiálním čase přesně určit průsečíkové číslo grafu, který vznikne z rovinného grafu přidáním jedné hrany! (Umíme jen aproximovat s faktorem daným největším stupněm grafu.) Rozšiřující studium Problematika rovinného kreslení grafů a jejich barvení je úvodně pokryta v [6, Kapitola 5]. 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á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 průsečíkovému číslu grafů (není nám o něm známa žádná tištěná monografie) je také množství informací na internetu, jako třeba http://en.wikipedia.org/wiki/Crossing_number. 93 8.5 Cvičení: Příklady na rovinnost grafů Příklad 8.21. Kolik nejméně hran je třeba vypustit z následujícího 8-vrcholového grafu, aby vznikl rovinný graf? Zdůvodněte. s s ss ss s s 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í K3,3: s ss s s s 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í: s s ss ss s s s s ss s s ss Stačí tedy vypustit jednu hranu a získáme rovinný graf. 2 Úlohy k řešení (8.5.1) Je tento graf rovinný? s s s s s s s s (8.5.2) Je tento graf rovinný? s s s s s s s s (8.5.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ý? s s s s s s s s 94 (8.5.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ý? s s s s s s s s s (8.5.5) Vezměme libovolný rovinný graf s 18 hranami a 10 stěnami. Kolik má takový graf vrcholů? (8.5.6) Kolik nejméně hran je nutno odebrat z úplného grafu K7, aby se stal rovinným? (8.5.7) Jaké je průsečíkové číslo grafu K4,4? (8.5.8) Dokážete nalézt graf takový, že jeho průsečíkové číslo je 3, ale po vypuštění libovolné jeho hrany klesne průsečíkové číslo na 1? 95 Čá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 zaměříme lehce a tak trochu i neformálně na několik vybraných partií pokročilé teorie grafů, které jsou ,,blízké autorovu srdci . Tato část nejspíše bude v permanentním vývoji a výběr látky z ní k 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átce 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 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. 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 tříd až po křivkové a úsečkové reprezentace. 9.1 Intervalové a chordální grafy Definice 9.1. Průnikovým grafem množinového systému M nazveme graf IM na vrcholech V = M s množinou hran E = {A, B M : A B = }. 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 nyní ukážeme. Intervalové grafy Podívejme se na průnikové grafy intervalů na přímce ­ intervalové grafy (zkratka INT). Komentář: Zde je jednoduchý příklad intervalového grafu: s ss s s ss s s ss s 1 2 3 4 5 6 ss s s s s 1 2 3 4 5 6 96 Fakt: Každá kružnice délky větší než tři v intervalovém grafu má chordu. * Intervalové grafy lze hezky popsat následujícícmi zakázanými indukovanými podgrafy: * Graf je intervalový, právě když neobsahuje indukovanou C4 a jeho doplněk má tranzitivní orientaci. * Jednotkové intervalové grafy jsou ty mající intervalovou reprezentaci se všemi intervaly délky 1. Jsou to právě ty intervalové grafy bez indukovaného K1,3. Chordální grafy Tyto grafy představují velmi užitečné zobecnění intervalových grafů. Podívejte se 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. Ú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.2. 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 v G existuje hrana f taková, že C \ {e} {f} 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í. 97 x0 = u NG(x0) x1 = v x2 = w NG(x1) x3 x-1 x-2 NG(x-1) x-3 2 Přímým důsledkem Věty 9.2 je existence simpliciální dekompozice libovolného chordálního grafu; jedná se o seřazení jeho vrcholů do posloupnosti v1, v2, . . . , vn tak, že každé vi, i = 2, . . . , n, je simpliciální v podgrafu indukovaném na v1, . . . , vi-1. Fakt: Simpliciální dekompozici lze využít k efektivnímu rozpoznávání intervalových i chordálních grafů. Věta 9.3. Graf G je chordální právě když G je průnikovým grafem podstromů ve vhodném stromě. Důkaz (náznak): 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. 2 Ú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) Proč každý intervalový graf obsahuje aspoň dva simpliciální vrcholy? (9.1.3) Dokažte si sami, že další zakázané grafy z předchozí strany nejsou intervalové (9.1.4) Jak byste snadno zdůvodnili, že daný graf je chordální? Přes definici to přímo nejde, neboť byste museli zkontrolovat až exponenciálně mnoho kružnic. 9.2 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. * Diskové grafy (DISC) jsou průnikovými grafy kruhů v rovině. Lze uvažovat také jen jednotkové kruhy (unit-DISC). * 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. 98 ˇ Dotykové . . . grafy jsou variantou průnikových grafů geometrických objektů, ve které se požaduje, aby vnitřky objektů byly po dvou disjunktní. Věta 9.4. Graf je rovinný právě když je dotykovým grafem kruhů v rovině. * Jiné, tzv. viditelnostní grafy nejsou definovány průniky objektů, ale jejich vzájemnou viditelností v geometrickém světě. Úlohy k řešení (9.2.1) Najděte nějaký graf, který není CA. (9.2.2) Najděte nějaký graf, který není CIR. (9.2.3) Najděte nějaký graf, který není DISC. (9.2.4) Najděte nějaký graf, který není průnikovým grafem koulí v 3D. 9.3 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ě. Tvrzení 9.5. 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.6. 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.6 je mnohem obtížnější dokázat příslušnost problému do třídy NP, než jeho těžkost(to je poměrně neobvyklý fenomén v teorii složitosti), [Kratochvíl / Pelsmajer, Schaeffer, Štefankovič]. Věta 9.7. Problém rozpoznat, zda daný graf je niťový, je NP-ú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 NP-těžké [Kratochvíl], ale příslušnost problému do třídy NP zůstává otevřená kvůli následujícímu. Tvrzení 9.8. 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.5 vynikne tento docela dlouho otevřený pro- blém: Hypotéza 9.9. Je každý rovinný graf úsečkovým grafem? 99 ,,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ě.) Věta 9.10. 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ů [PH]. Věta 9.11. Problém rozpoznat dotykový graf úseček je NP-úplný. U ,,zápalkových grafů je možno dále zkoumat několik dodatečných omezení. ­ Povolíme ,,oboustranné dotyky úseček, nebo jen jednostranné? ­ Kolika úsečkám dovolíme dotyk v jednom bodě? k-dotykové grafy ­ Co když zobecníme úsečky na obyčejné křivky v rovině? Dá se ukázat, že třídy dotykových grafů popsané předchozími body jsou různé a obtížnost jejich rozpoznání zůstává, až na triviální případy. . . Úlohy k řešení (9.3.1) Dokažte si sami Tvrzení 9.5. (9.3.2) Prozkoumejte podněty za Větou 9.11, jaké zajímavé podtřídy zápalkových grafů získáte? 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. 100 10 Dekompozice grafů, minory a algoritmy Úvod Další autorův výběr tématu nás zavede blíže 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 poměrně zřejmý fakt, že většinu jinak těžkých problémů lze řešit snadno a efektivně na stromech. Proto se podíváme na grafy, které jsou svým způsobem ,,stromům blízké , ve smyslu existence jejich vhodné dekompozice. 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ále je definován pojem minoru a formulována Robertsona­Seymourova věta o dobrém kvaziuspořádání konečných grafů vzhledem k minorům. 10.1 Tree-width ­ čtyři definice Naši látku začneme s pojmem, který už dnes lze prohlásit za klasický. Název ,,treewidth 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 ,,k-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 (G). Definice: Stromovou šířkou (tree-width) grafu G nazveme nejmenší přirozené k takové, že exituje chordální graf H s (H) = k + 1 obsahující G jako podgraf (H G). Jinou možnost popisu ukazuje: Definice: Vrcholy V (G) grafu G uspořádáme do posloupnosti (permutace) (v1, v2, . . . , vn). Pro i = 1, 2, . . . , n definujme (vi) jako počet všech indexů j {1, . . . , i- 1} takových, že vrcholy vi a vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj, vi, vi+1, . . . , vn}. Druhou stromovou šířkou grafu G nazveme nejmenší hodnotu výrazu maxv (v) přes všechny permutace vrcholů V (G). Ještě další, značně odlišný, přístup má tato definice: Definice: Pro libovolný strom T uvažujeme (libovolné) zobrazení : E(G) V (T). Pro vrchol t V (T) označíme T1, . . . , Td jednotlivé komponenty lesa T -t a Fi = -1(V (Ti)). Označme (t) = |V (G)| + (d - 1) c(G) - d i=1 c(G - Fi), kde c(H) značí počet souvislých komponent grafu H. T1 T2 T3 x : E FxF1 F2 F3 101 Třetí stromovou šířkou grafu G pak definujeme jako nejmenší možnou, přes všechny dvojice T, , hodnotu výrazu max tV (T) (t). Nakonec si uvedeme ještě 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.1. Stromová dekompozice grafu G. Stromovou dekompozicí grafu G nazveme strom T spolu se systémem množin X t (zvaných balíky) pro t V (T), kde * Xt V (G) a tV (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 V (T) s v Xt 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. Věta 10.2. Všechny čtyři výše uvedené definice stromové šířky definují přesně tutéž hodnotu, pokud graf G má neprázdnou množinu hran. 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. Úlohy k řešení (10.1.1) Dokažte si sami ekvivalenci prvních dvou definic tree-width. Vyjděte přitom z existence simpliciální dekompozice chordálního grafu (Věta 9.2). (10.1.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.1.3) Které grafy mají vysokou tree-width? (10.1.4) Dokážete nalézt rovinný graf s vysokou tree-width? 10.2 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.1, jen požadujeme navíc, aby T byla cesta. Definice: Vrcholy V (G) grafu G uspořádáme do posloupnosti (permutace) (v1, v2, . . . , vn). Bandwidth grafu G definujeme jako nejmenší hodnotu výrazu maxvivj E(G) |i - j| přes všechny permutace vrcholů V (G). 102 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 F E(G) definujeme funkci souvislosti G(F) jako počet vrcholů G, které jsou konci některých hran z F i hran z E(G) \ F (separace množiny F). F E \ F Definice 10.3. Větvená dekompozice grafu G Nechť T je podkubický strom a : 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 G(X), kde X = -1(V (T1)) pro jednu z komponent T1, T2 lesa T - x. x T X E \ X šířka(x) := G(X) = G(E \ X) Pak šířkou dekompozice T, 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 K6. (Například stromová šířka K6 je rovna 5.) s s s s s s a b c d e f s s s s s ab bc bdac ad ss s s ef ae af be bf s s s scd de df ce cf Věta 10.4. (Robertson and Seymour) Pokud graf G má stromovou šířku t a větvenou šířku b > 1, tak b t + 1 3 2 b . Jiný přístup Nechť G je graf a X V (G). Jako funkci hodnosti řezu G(F) na množině F označíme hodnost X × (V \ X)-matice A = (ai,j) nad binárním tělesem GF(2), kde au,v = 1 pro u X a v V \ X, právě když uv je hranou v G. 103 Definice 10.5. Ranková dekompozice grafu G Nechť T je podkubický strom a : 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 G(X), kde X = -1(V (T1)) pro jednu z komponent T1, T2 lesa T - x. Pak šířkou dekompozice T, je maximální šířka ze všech hran T a rankovou šířkou grafu G je nejmenší možná šířka rankové dekompozice G. 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. Úlohy k řešení (10.2.1) Může graf omezené path-width mít vrcholy velkého stupně? (10.2.2) Jaká je bandwidth kružnice? Dokažte. (10.2.3) Dokažte, že graf omezené bandwidth má omezený maximální stupeň. Jaký je přesný vztah max. stupně k bandwidth? (10.2.4) Dokažte, že větvená šířka grafu K4 je právě 3. (10.2.5) Podobně dokažte, že větvená šířka grafu K6 je právě 4. (10.2.6) Dokažte Větu 10.4. (10.2.7) Nalezněte příklady grafů, které dokazují těsnost obou nerovností ve Větě 10.4. (10.2.8) Jaká je ranková šířka úplných bipartitních grafů? (10.2.9) Najděte nějaký dosti velký graf, který není úplný ani úplný bipartitní, a přesto má rankovou šířku 1. (10.2.10) Jaká je ranková šířka kružnic? (10.2.11) Umíte najít nějaký graf velké rankové šířky? 10.3 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ů. Jak jistě víte, určení velikosti největší nezávislé množiny v grafu je NP-úplný problém. Stromová dekompozice fixní šířky však tento problém umožňuje řešit velice snadno. Algoritmus 10.6. 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 B, velikost největší nezávislé množiny I v grafu indukovaném na podstromu pod B takové, že I 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! 104 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 #P-ú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.7. 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 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. * 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 / Arnborg, Lagergren, Seese / Borie, Parker, Tovey]. Věta 10.8. Každá vlastnost grafů, která je vyjádřitelná v tzv. (E)MSO 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 enumerovat 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.3.1) Dokázali byste efektivně nalézt Hamiltonovskou kružnici v grafu na jeho větvené dekompozici fixní šířky? 10.4 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. s s ss s s s ss s s s ss s s s ss s s ss s s s s ss s ss s s s ss s 105 Robertson­Seymourova věta Věta 10.9. Mějme libovolnou grafovou vlastnost , která je uzavřená na minory (tj. pokud G má , pak každý minor G má také ). Pak existuje konečně mnoho grafů F1, . . . , F (zakázané minory) takových, že G má právě když G neobsahuje minor isomorfní žádnému z F1, . . . , F. Mimo jiné lze tudíž vlastnost rozhodnout v čase O(n3) pro každý n-vrcholový graf G. Poznámka: Tato věta je zcela nekonstruktivní, neboli nepodává žádný návod, jak zmíněný algoritmus sestrojit! Úlohy k řešení (10.4.1) Jak vypadají grafy, ve kterých zakážeme coby minor graf K3? (10.4.2) Jak vypadají grafy, ve kterých zakážeme coby minor graf K4? (10.4.3) Jak vypadají grafy, ve kterých zakážeme coby minory grafy K4 a K2,3? (10.4.4) Jak vypadají grafy, ve kterých zakážeme coby minor graf K3,3? (10.4.5) A teď malý námět k zamyšlení pro zvídavé: Dovedete si představit, co by znamenalo, pokud by se podařilo třeba dokázat NP-úplnost nějakého problému uzavřeného na minory? Rozšiřující studium Odkazovaná učebnice [1] je nejen kvalitním úvodem do teorie grafů obecně, ale zároveň poskytuje i poměrně hluboký přehled strukturální teorie a minorů. Šířkové parametry grafů se významně využívají také v teorii parametrizované složitosti algoritmů. Na FI se můžete o strukturální teorii grafů mnohem více dozvědět v navazujícím výběrovém předmětu MA052. Další zmínku o zajímavých souvislostech grafových minorů naleznete také v Lekci 11. 106 11 Více o kreslení grafů Úvod Tato lekce se soustřeďuje na následující otázku: Jak vhodně nakreslíme nerovinný graf? Této otázce jsme se již implicitně věnovali u průsečíkového čísla grafu a nyní si ukážeme dva různé pohledy. Buď budeme grafy kreslit stále bez křížení, ale na tzv. ,,vyšší plochy jako torus nebo projektivní rovina. (Co nám toto přinese nového?) Nebo zůstaneme v rovině, ale povolíme křížení hran a budeme hledat nějaká ,,esteticky pěkná nakreslení. (To už se jedná o vyloženě aplikovaný počítačový problém. . . ) Cíle Prvním cílem této lekce je definovat nakreslení grafu na vyšších plochách (kdy si stručně uvedeme i klasifikaci ploch). Druhou oblastí této lekce je vysvětlení praktického heuristického postupu na ,,estetické kreslení libovolných grafů v rovině. 11.1 Kreslení grafů na plochy Mimo tradičního kreslení grafů ,,na papír , tj. do roviny, si lze představit kreslení grafů na složitější povrchy (plochy), třeba na povrch duše pneumatiky. Co nám takovéto rozšířené kreslení grafů přinese nového? Nejprve si stručně uvedeme důležitý výsledek klasické topologie ­ klasifikaci ploch. Věta 11.1. Každá plocha (tj. kompaktní 2-manifold) je homeomorfní jedné z ­ S sféře. ­ Sh sféře s h přidanýma ,,ušima (handle). ­ Nk sféře s k přidanými ,,křížícími místy (crosscap). Definice: Crosscap na ploše je kružnice, jejíž protilehlé dvojice bodů jsou ztotožněny (vnitřek kruhu přitom ploše už nepatří). Poznámka: Plocha S1 je známý torus, neboli povrch duše kola. Plocha N1 je projektivní rovina a vypuštěním kruhu z N1 vzniká známý Möbiův proužek. Plocha N 2 je tzv. Kleinova láhev. Plochy S a Sh jsou orientovatelné, kdežto Nk jsou neorientovatelné. Lema 11.2. Máme-li plochu vzniklou ze sféry přidáním k > 2 crosscapů a h uší, tak je homeomorfní ploše vzniklé ze sféry přidáním k - 2 crosscapů a h + 1 uší. Definice 11.3. Nakreslení grafu G na plochu myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body na 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. Definice: Nakreslení grafu G na plochu 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 až na homeomorfismus. (Neboli plochu lze ,,slepit z jednotlivých disků stěn podél společných hran stěnových kružnic.) Tvrzení 11.4. Buňkové nakreslení grafu G na orientovatelnou plochu je jednoznačně určeno rotačním schématem vycházejících hran u svých vrcholů. (V případě neorientovatelných ploch je třeba ještě přidat jistá ,,znaménka .) 107 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 K5 nelze nakreslit do roviny. Tvrzení 11.5. Do projektivní roviny lze bez křížení hran nakreslit úplný graf K6, na torus i K7, kdežto na Kleinovu láhev také jen K6. Mnohé poznatky o kreslitelnosti grafů lze zobecnit z rovinných na vyšší plochy. Věta 11.6. Nechť buňkové nakreslení neprázdného souvislého grafu G na ploše má f stěn. Pak |V (G)| + f - |E(G)| = () , kde () (Eulerova charakteristika plochy) je 2 - 2h pro = Sh a 2 - k pro = Nk. Věta 11.7. (Mohar) Pro každou pevnou plochu existuje algoritmus, který v lineárním čase pro daný graf buď nalezne jeho nakreslení na , nebo určí minimální překážku nakreslitelnosti na . Za poznamenání stojí, že obecnější problém určit nejjednodušší plochu, na kterou lze daný graf nakreslit, je už NP-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í máme pouze u jediné vyšší plochy. Věta 11.8. (Archdeacon) Graf G je nakreslitelný do projektivní roviny právě když neobsahuje žádný z následujících 35 grafů isomorfní svému minoru. 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ů ? 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. 108 ˇ 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 nakreslitelný 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.1) takovou, jejíž každý balík indukuje podgraf, který je až na omezeně mnoho ,,lokálních výjimek nakreslitelný na nějakou plochu takovou, že H na nakreslit nelze. Úlohy k řešení (11.1.1) Najděte nakreslení grafu K7 na torus. (Vemte si k tomu nějaký fyzický torus, třeba posilovací kolečko.) (11.1.2) Dokažte, že graf K7 nelze nakreslit bez křížení na Kleinovu láhev. (11.1.3) Určuje nám Eulerova charakteristika (Věta 11.6) jednoznačně plochu, na kterou je graf nakreslený? Kdy? (11.1.4) Lze nějaký graf nakresit buňkově na různé plochy? (11.1.5) Proč tento graf nelze nakreslit do projektivní roviny? (11.1.6) Proč graf K3,5 nelze nakreslit do projektivní roviny? (11.1.7) Uměli byste o dalších, složitějších, grafech z Věty 11.8 dokázat, že nejsou projek- tivní? 11.2 O problému rovinného pokrytí Následující zajímavý partikulární problém je hezký především svou ,,chytlavostí a jednoduchostí zadání. Je znám pod názvem Negamiho hypotéza planárních pokrytí nebo Negamiho 12 hypotéza. Avšak k ekvivalentnímu problému nezávisle ve stejné době dospěl i Fellows. Definice: Říkáme, že graf H pokrývá graf G, pokud existuje surjektivní zobrazení : V (H) V (G) takové, že sousedé každého vrcholu v grafu H jsou bijektivně zobrazeny na sousedy vrcholu (v) grafu G. Hypotéza 11.10. 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 K5 rovinným grafem o 10 vrcholech. Pokrytí je získáno z projektivního nakreslení K5 a zobrazení vrcholů z definice pokrytí je naznačeno čísly u vrcholů. 1 2 3 4 5 1 2 3 4 51 2 3 4 5 1 2 3 4 5 + 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. 109 Lema 11.11. K důkazu Hypotézy 11.10 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, navíc lze využít následovný poznatek k další výrazné redukci počtu případů: Lema 11.12. Tzv. Y -operace (nahrazení vrcholu stupně 3 trojúhelníkem na jeho sousedech) zachovává vlastnost míti konečné rovinné pokrytí. Přesto k této hypotéze stále není znám důkaz (a asi většina matematiků zabývajících se topologickou teorií grafů si s ní už zkoušela někdy lámat hlavu). Nejsilnější publikované poznatky o ní se dají shrnout následovně: Věta 11.13. (Archdeacon, Fellows, Negami, PH) Pokud graf K1,2,2,2 nemá konečné rovinné pokrytí, tak je Hypotéza 11.10 pravdivá. Věta 11.14. (Thomas, PH) Existuje jen 16 následujících konkrétních grafů (až na triviální modifikace), pro které by Hypotéza 11.10 mohla být nepravdivá. Úlohy k řešení (11.2.1) Dokažte si sami Lema 11.11. (11.2.2) Dokažte si sami Lema 11.12. (11.2.3) Proč tento graf nemá konečné rovinné pokrytí? (11.2.4) Dokažte, že graf K3,5 nemá konečné rovinné pokrytí. 11.3 Praktické ,,pružinové kreslení grafů Závěrem se podívejme na trochu jinou problematiku ­ jak prakticky nakreslit daný (nerovinný) graf, aby to ,,vypadalo hezky . Fakt: Psychologické výzkumy ukázaly, že jedním z nejvýznamnějších kvantitativních parametrů nakreslení grafu pro jeho ,,lidskou čitelnost je počet křížení hran. Tento poznatek na jednu stranu ukazuje důležitost průsečíkového čísla grafu pro jeho vizualizaci, ale na druhou stranu nás nechává v poměrně beznadějné situaci, neboť určení průsečíkového čísla se ukazuje jako prakticky nemožné. Jeden z nejstarších užitečných heuristických přístupů ke kreslení grafů se dá shrnout následovně: 110 Metoda 11.15. 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 Při popisu kreslení grafů na plochy vycházíme ze skvělé monografie [8]. Na této monografii také zakládáme pokročilý výběrový předmět MA051 na FI MU. Co se týče Negamiho hypotézy a planárních pokrytí, asi v současnosti nejobsáhlejší ucelený popis lze nalézt v autorově dizertacční práci (Georgia Tech, 1999) na webu http://www.fi.muni.cz/~hlineny/Research/papers/gtthesis.pdf. Problematika praktického kreslení grafů je velmi rozsáhlá oblast se spoustou materiálu na webu, hledejte pod klíčovými slovy "Graph drawing" a specificky "Spring embedder" pro pružinové kreslení. 111 Část 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: s s s s ss s (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 s s s s s s s s . Tento graf obsahuje 4 trojúhelníky, kdežto původní graf jen 3. Mohli jste však sestrojit úplně jiný graf... (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) ... (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... (1.6.7) Isom. z pravého do levého grafu: spodní dva nahoru vpravo, pravé dva dolů vpravo, atd. (1.6.8) ... (1.6.9) B C, A D, u neisomorfních dvojic vždy jedna obsahuje kružnice délky 5 a druhá ne. (1.6.10) A ano, K3,3 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ší C8 v obou, nejdelší indukovaná C6 v A a jen C5 v B. (1.6.12) 20 (1.6.13) 10 4 3, neboť 10 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 grafu K4 a 4 další jsou jiné. 112 (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) ... (2.3.4) 1 do kružnice. (2.3.5) n-1 2 (2.3.6) ... (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) Celkem 4. (2.5.4) Souvislý s 15 hranami (ke každému vrcholu 3 sousedé). (2.5.5) 18, stupně 3, třeba jako šestiboký hranol. (2.5.6) a) 28: K8 + K1 + K1, b) 9: K3 + K3 + K3 + K1 (2.5.7) Jen v A: graf K2,3 a graf C5 s jednou diagonálou; C: cesta délky 4 a trojúhelník s hranou vedle. Pro B uvažte doplněk toho grafu ­ má stupně 2, 1, 1, 1, 1, což dá jednoznačný graf. (2.5.8) 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.9) 3 (2.5.10) A C D (2.5.11) 5 (2.5.12) Některý vrchol má stupeň aspoň 3, jinak vezmeme doplněk. Pak ti tři sousedi jsou nezávislí... (2.5.13) Třeba úplný bipartitní K3,4. (2.5.14) Ano, ale jen otevřeným. (2.5.15) Není to strom, proto obsahuje kružnici. (2.5.16) Pomůže vám nakreslení uzavřeným tahem... (3.1.1) 1, ale jen 0 pro graf na jednom vrcholu. (3.1.2) 2 (3.1.3) 5 (3.1.4) 3, najdete příslušnou dvojici vrcholů? (3.1.5) Třeba: s s ss s s ss (3.1.6) . . . (3.2.1) Vyjde 0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0 . (3.3.1) 5 (3.3.2) 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. 113 (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 bude, důvod je stejný jako v předchozí otázce. (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. (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. (3.5.12) Ano. (3.5.13) Osmi. (4.1.1) Jsou to cesty Pn a úplné bipartitní grafy K1,n. (4.1.2) Lze, ale jenom o kružnici. Úplné grafy K1 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 K1,3. (4.1.5) Nenajdete, to by bylo v rozporu s Důsledkem 4.5. (4.1.6) Jen 3. (4.2.1) s ss s s s s s s s f 11 159 5 1310 20 21 1 6 (4.2.2) Centra jsou vyznačená: s s s s s s s s ss s s s s s s s s s s s f s s s s s s s s ss s s s s s s s s s s s f (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.3.2) s ss s s s s s s s s f (4.4.1) 1, bez hran. (4.4.2) 2004 114 (4.4.3) (4.4.4) Je celkem 5!/2 = 60 koster, co jsou cestou P4, dále jen 5 koster, co jsou hvězdou K1,4 a nakonec 5 4 3 = 60 koster, které mají vrchol stupně 3. (4.4.5) . . . (4.4.6) Třeba kružnice C9 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) 14 (4.5.8) 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.9) n 2 - n + 1 (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) 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.12) Třeba kružnice C503 s tětivou tvořící kružnici délky 4. (4.5.13) (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) ... (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ů. (6.2.1) Tok 5. (6.2.2) Jen zdroj z. (6.2.3) Řez velikosti 4 zde: z s 3 2 1 2 4 1 3 2 1 (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) ... (6.3.1) Velikosti 5: s s s s s s s sssss (6.3.2) Velikosti 4: s s s s s s s sssss (6.3.3) Ano, reprezentanti jsou zapsaní první: (1, 2, 3), (2, 1, 4), (3, 1, 4), (4, 2, 3). (6.3.4) Ne, všech podmnožin je 5 3 = 10, ale prvků k reprezentaci jen 5. 115 (6.4.1) 12 (6.4.2) 13 (6.4.3) 11 (6.4.4) 9 (6.4.5) Nemá ­ 6 z množin má sjednocení {3, 4, 5, 6, 7}, kde se najde jen 5 různých prvků pro reprezentanty. (6.4.6) 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 s s s s s s 1 2 3 1 3 2 (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 V1, V2 vrcholové komponenty G-{u, v} a u, v dohromady mají více sousedů ve V1, obarvíme nejprve podgraf indukovaný na V1 {u, v}. Pokud u, v získají stejnou barvu, obarvíme indukčně podgraf indukovaný na V2 {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 {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) (7.2.1) 3, stejně jako u vrcholové barevnosti. (7.2.2) n - 1 pro sudá n a n pro lichá mimo 1. (7.2.3) ... (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í. (7.2.6) Podobně předchozí úloze. . . (7.2.7) (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 P. Také pro k = 3 patří problém barevnosti k do NP, 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 NP 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. 116 (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) ... (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) ...? (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) v = 12, f = 20, v + f - h = 2, tedy h = 12 + 20 - 2 = 30. (8.1.3) Graf pravidelného osmistěnu. (8.1.4) 3 (8.1.5) 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.1.6) Užijte projekci z bodu velmi blízkého zvolené stěně. (8.1.7) ... (8.2.1) Rovinný jen B. (8.2.2) Pro n = 1, 2, 3, 4. (8.2.3) Jen pokud m 2 nebo n 2, jinak v sobě obsahuje K3,3. (8.2.4) 3 ­ takto z kružnice délky 6 vytvoříme graf K3,3, nakreslete si to. (8.3.1) 4 (8.3.2) 2 (8.3.3) Stačí dokázat, že takový graf je 2-degenerovaný. (8.3.4) ... (8.3.5) Protože každý rovinný graf 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.5.1) Ano, stačí dolní levé dva vrcholy překreslit nahoru. (8.5.2) Ne, obsahuje podrozdělení K3,3, najdete jej? (8.5.3) 8 (8.5.4) 11 (8.5.5) Má vždy 10 vrcholů podle Eulerova vztahu. (8.5.6) 7 2 - (3 7 - 6) = 3 (8.5.7) 4, ale spodní odhad je těžké dokázat. (8.5.8) Toroidální mříž C32C3, na 9 vrcholech. (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) Podívejte se na interval, který má první pravý konec zleva ­ všichni jeho sousedé se překrývají. Totéž zprava. (9.1.3) Opět si pomožte úvahami o položení a nuceném překrývání intervalů v reprezentaci... (9.1.4) Podáte jeho simpliciální dekompozici. 117 (9.2.1) Například velká kružnice s "ocáskem" délky 2. (9.2.2) ... (9.2.3) Například K7,7. Umíte toto krátce zdůvodnit? (9.2.4) Například K13,13, souvisí s problémem zvaným "kissing number"... (9.3.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.3.2) Viz http://www.fi.muni.cz/ hlineny/Research/papers/kamthesis.pdf. (10.1.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.1.2) ... (10.1.3) Třeba úplné podle předchozí otázky... (10.1.4) Třeba velká "mříž". (10.2.1) Ano. (10.2.2) 2, menší být nemůže a uspořádání na 2 si najdete sami... (10.2.3) 2 bandwidth (10.2.4) 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.2.5) ... (10.2.6) Převádějte dekompozice jednu na druhou... (10.2.7) Zprava třeba úplné grafy, zleva úplné bipartitní s odebraným párováním. (10.2.8) 1 (10.2.9) Třeba cesty. (10.2.10) 1 pro C3, C4, jinak 2. (10.2.11) ... (10.3.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.4.1) Jsou to lesy, acyklické grafy. (10.4.2) Jsou to tzv. sériově­paralelní grafy. (10.4.3) Jsou to grafy, které lze nakreslit do roviny tak, aby všechny vrcholy ležely na vnější stěně. (10.4.4) (10.4.5) No, měli bychom důkaz P = NP, ale žádný použitelný algoritmus k tomu. Zajímavá situace... (11.1.1) ... (11.1.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.1.3) Jenoznačně pro hodnoty 2 a všechny liché, pro ostatní sudé 0, -2, -4, .. . nerozliší mezi příslušnou orientovatelnou a neorientovatelnou plochou. (11.1.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.1.5) Obsahuje dvě hranově disjunktní kopie K5, jen jedna z nich může ke svému nakreslení "využít" crosscap, ta druhá by byla rovinná, spor. (11.1.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.1.7) ... (11.2.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. 118 (11.2.2) Stejnou operaci proveďte násobně v rovinném pokrytí. (11.2.3) Obdobná úvaha jako v 11.1.5. (11.2.4) Opět se počítá vhodně počet hran proti Eulerovu vztahu... 119 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] L. Kučera, Algovize, http://kam.mff.cuni.cz/~ludek/Algovision/Algovision.html. [5] M. Mareš, Krajinou grafových algoritmů, ITI MFF UK, 2007. http://iti.mff.cuni.cz/series/files/iti330.pdf. [6] J. Matoušek a J. Nešetřil, Kapitoly z Diskrétní Matematiky, Karolinum, UK Praha, 2000. [7] J. Matoušek and J. Nešetřil, Invitation to Discrete Mathematics, Oxford University Press, 1998. [8] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins, 2001. [9] J. Oxley, Matroid Theory, Oxford University Press, 1992. [10] J. Oxley, What is a Matroid?, http://www.math.lsu.edu/~preprint/2002/jgo2002e.pdf, LSU, USA. 120