A GRAFOVÉ ALGORITMY Slezská univerzita v Opavě • Filozoficko-přírodovědecká fakulta v Opavě • Ústav informatiky 2014 2610620627 Teorie grafů a grafové algoritmy RNDr. Luděk Cienciala Ph.D., RNDr. Lucie Ciencialová, Ph.D. Tato inovace předmětu Teorie grafů je spolufinancována Evropským sociálním fondem a Státním rozpočtem ČR, projekt číslo CZ.1.07/2.2.00/28.0014. „Interdisciplinární vzdělávání v ICT s jazykovou kompetencí". Skripta Teorie grafů slouží primárně jako vzdělávací materiál pro cílovou skupinu projektu. Recenzenti: RNDr. Šárka Vavrečková, Ph.D. ing. Richard Pcčonka Vydavatel: Ústav informatiky. Výzkumný ústav Centra excelence IT4Innovations Filozoficko-přírodovědccká fakulta v Opavě Slezská univerzita v Opavě Bezručovo náměstí 13 746 01 Opava Typesetted with WF$Í Autorská práva: © autoři, 2014 Obálka: © Lucie Ciencialová, 2014 Tisk: Z+M Partner, spol. s. r. o., Ostrava Vydáno v Opavě v srpnu 2014 ISBN: 978-80-7510-060-3 2610620527 Obsah Úvod s nádechem historie 1 1 Graf a základní pojmy 6 1.1 Graf a základní typy grafů................................. 6 1.2 Stupeň vrcholu a stupňové posloupnosti......................... 10 1.3 Podgrafy........................................... 12 1.4 Reprezentace grafů pomocí matic............................. 13 1.5 Příklady a úkoly ke kapitole................................ 15 2 Cesty, cykly a souvislost 18 2.1 Sled, tah, cesta a cyklus.................................. 18 2.2 Dosažitelnost, souvislost, vzdálenost v grafu, excentricita, průměr a poloměr ..................................... 20 3 Stromy a kostry 25 3.1 Strom............................................ 25 3.2 Kostra............................................ 30 4 Speciální grafy 33 4.1 Úplné grafy......................................... 33 4.2 Bipartitní grafy....................................... 34 5 Izomorfizmus a automorfizmus grafů 37 5.1 Izomorfizmus grafů..................................... 37 5.2 Automorfizmus grafu.................................... 41 6 Vrcholová a hranová souvislost 45 6.1 Vrcholová souvislost.................................... 45 6.2 Hranová souvislost..................................... 46 7 Párování a pokrytí grafu 50 7.1 Párování grafu....................................... 50 7.2 Párovaní a pokrytí v bipartitních grafech ........................ 52 8 Hranové a vrcholové barvení grafu 8.1 Hranové barvení grafu....... 8.2 Vrcholové barvení grafu..... 9 Planární a neplanární grafy 9.1 Planární grafy........... 9.2 Neplanární grafy......... 10 Eulerovské grafy 10.1 Úlohy typu bludiště ....... 11 Hamiltonovské grafy 12 Orientované grafy 12.1 Turnaje.............. 12.2 Sítě ................ 13 Grafové algoritmy 13.1 Nalezení minimálni kostry grafu . 13.2 Prohledávání grafu........ Literatura Uvod s nádechem historie Základním pojmem teorie grafů je pojem graf. V matematice se nejčastěji pojem graf používá v souvislosti s grafickým znázorněním funkce. Pojem graf používáme také pro vyjádření grafického znázornění dat, apod. Musíme ale hned na začátku upozornit, že daný pojem, jak ho my budeme chápat, je svou podstatou hodně vzdálen tomuto pojetí pojmu graf. Mnoho úloh z matematiky, ale i také informatiky, lze interpretovat tak, že můžeme uvažovat o množině bodů a o množině spojnic mezi některými dvojicemi bodů. Body mohou představovat města, křižovatky, osoby, uzly v obvodech atd., spojnice mohou reprezentovat cesty, spojnice mezi městy, křižovatkami, vzájemnou znalost osob, spojení uzlů v obvodech, atd. Podívejme se nejdříve trochu do historie teorie grafů. Mezi průkopníky v teorii grafů můžeme zařadit Leonharda Eulera (na obrázku 1), který v 18. století řešil problém sedmi mostů v Konigsbergu (česky Královec, dnešní Kaliningrad). Mapu města s vyznačenými mosty vidíme na obrázku 2. Městem protéká řeka Pregel. Řeka vytváří dva ostrovy, které byly spojeny s pevninou a vzájemně propojeny sedmi mosty. Úkolem bylo zjistit, zda je možné vyjít z jednoho místa, projít po každém mostě právě jednou a skončit ve výchozím bodě. V teorii grafů to koresponduje s pojmem eulerovský graf. Úloha nemá řešení, protože graf, který vyjadřuje danou situaci, nelze nakreslit jedním tahem. S Eulerovým jménem je taka spjata úloha jezdce v šachu, která v grafové intrepretaci vede k nalezení hamiltonovského cyklu v grafu. Zadání úlohy je následující. Může jezdec projít šachovnici, která má 64 polí tak, aby každým polem prošel právě jednou a posledním tahem se vrátil na výchozí pole? V grafové intrepretaci uvažujeme graf, jehož uzly jsou daná pole na šachovnici. Dva body (uzly) jsou spojeny hranou právě tehdy, když jezdec může skočit z jednoho pole na druhé. Jezdec v šachu se může pohybovat pouze do písmene L. Daný hamiltonovský cyklus existuje. 1 Obrázek 1: Leonhard Euler [0] Úvod s nádechem historie 2 Obrázek 2: Problém sednii mostů v Kónigsbergu [17] Další osobu, kterou zde můžeme zmínit, je Gustav Kirehhoff (obrázek 3), který v 19. století zkoumal elektrické sítě. V roce 1945 publikoval zákony, které platí v elektrických obvodech a slouží k výpočtu napětí a proudu v jednotlivých větvích obvodu. Dané zákony se dodnes učí ve fyzice na některých středních školách. Daná teorie našla uplatnění při studiu tzv. toků v sítích. Obrázek 3: Gustav Kirchhof [5] Obrázek 4: Johann Benedict Listing [6] V roce 1857 se anglický matematik Arthur Caylcy (obrázek 5) zabýval otázkou, kolik existuje izomerů uhlovodíku CreiÍ2n+2- Jednotlivé atomy si znázornil jako uzly v rovině a spojil čarou ty uzly, mezi nimiž je chemická vazba, což není nic jiného než grafické znázornění chemických vzorů. Johan Benedict Listing (obrázek 4) v 19. století se zabýval kreslením obrázků nejmenším počtem tahů. Sir William Hamilton (obrázek 6) v roce 1859 vymyslel hru, kterou nazval „Icosian Game'-. Jde Úvod s nádechem historie 3 Obrázek 5: Arthur Cayley [1] Obrázek 6: Wiliam Rowan Hamilton [18] v ní o hledání hamiltonovských cyklů v grafu, který odpovídá pravidelnému dvanáctistěnu. Úkolem je cestovat z vrcholu do vrcholu po hranách dvanáctistěnu za předepsaných podmínek. Hamilton rozvinul povrch dvanáctistěnu do roviny a připojil ke každému z 20 vrcholů jméno jednoho světového velkoměsta. Nabídl jednomu -výrobci hraček výrobu hlavolamu, jehož řešením je cesta kolem světa po hranách daného dvanáctistěnu, během níž se vyjde z některého města a každým z dalších měst se projde právě jednou a nakonec se vrátí do výchozího města. V grafové interpretaci odpovídá úloze graf o 20 uzlech (vrcholy dvanáctistěnu), hrany grafu představují hrany dvanáctistěnu (viz obrázek 7). Úkolem je najít cyklus procházející všemi uzly. Obrázek 7: Grafová interpretace hry „Icosian Game" V roce 1852 předložil Francis Guthrie tzv. problém čtyř barev. Položil otázku, zda je možné obarvit libovolnou mapu pomocí nejvýše čtyř barev tak, aby každé dvě sousední země (které mají společnou hranici delší než jediný bod) měly odlišnou barvu. Problém byl vyřešen až o více než sto let později, přičemž pro jeho řešení bylo zavedeno mnoho zásadních konceptů teorie grafů (rovinný graf). Od počátku existence tohoto problému se matematici snažili dokázat, že nám stačí 4 barvy. Vetu dokázali až roku 1976 američtí matematici Kenneth Appel (obrázek 8) a Wolfgang Haken tím, že pomocí počítačového programu vymodelovali 1936 možných konfigurací, dokázali, že tyto Úvod s nádechem historie 4 Obrázek 8: Kenneth Appel [10] konfigurace pokrývají všechny možnosti, a u každé z nich ukázali, že pro její obarvení stačí čtyři barvy (k tomu potřeboval počítač 1200 hodin procesorového času). Tento důkaz však velká část matematiků odmítá akceptovat, protože ho žádný matematik není schopen přímo zkontrolovat. Od té doby byl důkaz mnohokrát nezávisle zopakován a zjednodušen dalšími matematiky pomocí jiných programů, ale „hezký" důkaz tak, aby ho mohl udělat člověk, nebyl nalezen. Obrázek 9: Otakar Borůvka [15] Obrázek 10: Vojtech Jarník [14] První „grafovou" práci v české matematické literatuře publikoval v roce 1926 Otakar Borůvka (obrázek 9). Práce nazvaná „O jistém problému minimálním" se zabývala problémem nalezení minimální kostry grafu. Borůvka vytvořil první algoritmus nalezení minimální kostry. K řešení tohoto problému přivedly Borůvku praktické otázky ekonomické výstavby elektrovodních sítí. Krátce na to v roce 1930 stejný problém vyřešil zcela jiným způsobem Vojtěch Jarník (obrázek 10) v práci, která měla stejný název jako práce O. Borůvky. Tyto dvě práce ovšem zůstávají v období před druhou Úvod s nádechem historie 5 světovou válkou jedinými příspěvky české matematiky v teorii grafů. Můžeme říci, že prudký rozvoj teorie grafů nastal až ve druhé polovině 20. století. Kde nachází poznatky získané v teorii grafů uplatnění? Poznatky jsou použitelné v silničních sítích, dopravě, rozvodných sítích, ve sportu - turnaje, losování, při tvorbě rozvrhu, přidělování úkolů, v programování, v hrách apod. Intuitivně začínáme tušit, čím se v teorii grafů zaobíráme. Naše představa o grafu zatím je, že graf bude tvořen dvěrna množinami, množinou vrcholů a množinou hran. V grafické reperezentaci grafu budeme vrchol znázorňovat pomocí prázdného kolečka a hranu bude představovat křivka spojující příslušné vrcholy. V další kapitole se tedy můžeme pustit do definování základních pojmů. Většinou bude platit, že pochopit základní pojmy v teorii grafů není těžké, ale mnohem obtížnější je, jak lze poznatky používat. Kapitola Graf a základní pojmy V této kapitole uvedeme základní pojmy a definice v teorii grafu, základní typy grafů. 1.1 Graf a základní typy grafů KS" Definice 1.1 Graf G jc uspořádaná dvojice (V, E), kde V je neprázdná konečná množina vrcholů a E je konečná množina dvouprvkových podmnožin množiny V, které nazýváme hrany. _ -■---■-■- □ Pokud bychom chtěli zdůraznit, že vrcholová množina V je vrcholovou množinou grafu G, můžeme psát V(G), obdobně tak i u množiny hran E(G). Obrázek 1.1: Graf Grafy lze reprezentovat i graficky, a to tak, že vrcholy znázorňujeme kroužky a hrany znázorňujeme křivkami spojujícími dvojici vrcholů. Dané křivky nejčastěji představují úsečky nebo oblouky. Příklad grafického znázornění grafu vidíme na obrázku 1.1. V grafu představuje hrana dvojici vrcholů, přičemž v diagramu je hrana reprezentována křivkou spojující příslušné vrcholy této hrany. Proto také dané vrcholy budeme nazývat koncovými vrcholy dané hrany. O koncových 6 Kapitola 1 Graf a základní pojmy 7 vrcholech dané hrany říkáme, že jsou s danou hranou incidentnif nebo incidují s danou hranou. Ze dvou znázornění grafu volíme ten, kde jsou hrany nakresleny jako úsečky s co nejmenším počtem průsečíků. Znázornění, v němž se vyhýbáme průsečíkům hran, má uplatnění např. při navrhování tištěných spojů. Rovinným znázorněním nazveme zobrazení grafu, kde libovolné dvě křivky (odpovídající hranám grafu) mají společné nejvýše své koncové body. Zopakujeme nejdříve, co nazýváme zobrazením. Zobrazení množiny X do množiny F je pravidlo, které každému prvku x G X přiřazuje právě jeden prvek f(x) z množiny Y. Znázornění grafu můžeme definovat i formálněji, a to jako dvojici zobrazení 0 a ip. Zobrazení (j) přiřazuje vrcholům z vrcholové množiny V grafu různé body roviny a zobrazení ip přiřazuje každé hraně z hranové množiny E s koncovými vrcholy u a v křivku s krajními body 1 a h(G) označíme počet hran daného grafu, platí T,i=ideg(vi) = 2-h(G). --;-0 Důkaz: Provedeme dvěma způsoby. Nejdříve provedeme úvahu a použijeme tzv. selský rozum. Každá hrana je incidentní se dvěma vrcholy, a protože přispívá jedničkou ke stupni každého svého koncového vrcholu, přispívá do součtu stupňů všech vrcholů dvojkou. Z tohoto důvodu je tento součet roven dvojnásobku počtu hran grafu. □ Danou větu můžeme dokázat i matematickou indukcí. Matematickou indukci provedeme vzhledem k počtu vrcholů. Nejdříve ukážeme, že věta platí pro graf o jednom vrcholu a žádné hraně, tzn. pro triviální graf. n Edeg(vi) = 2h(G) i=i 0 = 0 Budeme předpokládat, že věta platí pro každý graf s nejvýše n vrcholy, kde n e N (tzv. indukční předpoklad), a budeme chtít dokázat, že daná věta platí i pro všechny grafy s n+1 vrcholy. Protože n bylo libovolné přirozené číslo, pak naše tvrzení platí pro libovolný konečný graf. Indukční předpoklad: Pro libovolný graf s n vrcholy platí Yli-i dag(vi) = 2h(G). Budeme chtít dokázat: Pro libovolný graf G' s n + 1 vrcholy platí YH=l deg(vi) = 2h(G'). Napíšeme tedy levou stranu rovnice a pomocí indukčního předpokladu a úprav budeme chtít dokázat, že i pro graf s n + 1 vrcholy dostaneme výraz 2h(Gn+i). n+l n E degGn+1 (u,;) = J2 de9Gn+i (t>i) + 2deg(ín+i {vn + 1) = í=l i=l = 2h{Gn) + 2degGn+l{vn + l) = = 2{h{Gn) + 2degGn+í{vn + \)) = = 2k(Gn+l) Tedy jsme ukázali, že daná věta platí i pro graf G' s n + l vrcholy a důkaz je hotový. □ Kapitola 1 Graf a základní pojmy 12 fy] Věta 1.2 Počet vrcholů lichého stupně v libovolném grafu je sudý. _ - 0 Důkaz: provedeme sporem. Budeme předpokládat, že počet vrcholů lichého stupně v nějakém grafu je lichý. Potom součet stupňů všech vrcholů lichého stupně v daném grafu je lichý, neboť součet lichého počtu lichých čísel je lichý. Ostatní vrcholy mohou být sudého stupně nebo stupně nula, tzn. že součet jejich stupňů je buď číslo sudé, nebo nula. Potom ale součet stupňů všech vrcholů v daném grafu je lichý, protože součet lichého čísla a sudého nebo lichého čísla a nuly je číslo liché. Dostáváme se tedy do sporu s předchozí dokázanou větou. □ Definice 1.11 Stupňovou posloupností grafu G s vrcholy t'i,i'2, • • • , i'3 nazveme posloupnost {deg(vi_),deg(v2), • • •, deg(vn)). □ 1.3 Podgrafy Definice 1.12 Podgrafcm grafu G(V,E) nazveme graf H(V',E'), pro nějž platí V C V a E' C E. _ -- □ Chccme-li zdůraznit, že nějaký podgraf H grafu G není s grafem G shodný, tedy že vznikl skutečně vynecháním některých hran nebo vrcholů, budeme říkat, že H jc vlastním podgrafem grafu G. Graf, který vznikne vynecháním vrcholu v, budeme zapisovat G — v. Z matematického hlediska bychom měli zapisovat G(V, E), kde V = V — {v}. Graf, který vznikne vynecháním hrany uv. budeme zapisovat G — uv. Z matematického hlediska bychom měli zapisovat G(V, £"), kde E' = E-{uv}. Definice 1.13 Graf G nazýváme nadgrafem nebo též supergrafem grafů H, je-li H podgrafem grafu G. _ -- □ Definice 1.14 Faktorem grafu G(V, E) nazveme podgraf F(V, E') grafu G, pro který platí V = V, tzn. F{V, E'). -■--■- □ Kapitola 1 Graf a základní pojmy 13 Faktor je podgraf, který vznikne z daného grafu G vynecháním některých hran (nebo žádných), přičemž jeho vrcholová množina je shodná s vrcholovou množinou původního grafu. Musíme si uvědomit, že graf sám je svým podgrafem. | i Definice 1.15 Indukovaný podgraf grafu G jc podgraf I(V',E'), který vznikne vynecháním některých vrcholů a všech hran incidentních s těmito vynechanými vrcholy v grafu G, avšak žádných dalších hran. Představme si graf, kde vrcholy odpovídají městům, křižovatkám a hrany cestám mezi nimi. Uvažujme na začátku, že jsme takto reprezentovali v teorii grafů celou Moravu. Pokud se omezíme pouze na křižovatky, města a silnice Severní Moravy, tak odpovídající graf je indukovaným podgrafem. Pokud si naopak řekneme, že budeme uvažovat v grafu reprezentujícím celou Moravu pouze silnice první třídy, pak daný podgraf jc faktorem. 1.4 Reprezentace grafů pomocí matic Má-li graf nepříliš velký počet vrcholů a zejména hran, je vhodné graf pro názornost reprezentovat diagramem. Ale tato reprezentace není vhodná jako vstup pro počítač. Při nevhodném nakreslení můžou být zamaskovány některé vlastnosti daného grafu. Například na obrázku 1.7 není příliš patrné, že se graf skládá ze dvou částí. Na dalším obrázku 1.8 není na první pohled vidět, že se jedná o dva různé diagramy téhož grafu. 1 3 Obrázek 1.7: Nesouvislý graf Někoho by napadlo používat pro reprezentaci grafu seznam vrcholů a seznam hran, kde by se u každé hrany uváděly koncové vrcholy. Pokud bychom takový seznam vytvořili a nebyl by nějak vhodně uspořádán, pak by se v něm špatně hledalo. Další možnost je použití seznamu vrcholů a hran, kde nejdříve uvedeme počet vrcholů a počet hran, a nakonec vypíšeme všechny hrany. Kapitola 1 Graf a základní pojmy 14 Nebo můžeme použít seznam okolí vrcholů, kde nejdříve uvedeme počet vrcholů a hran, pak vždy stupeň daného vrcholu a vrcholy, které jsou s ním sousední, a to pro každý vrchol daného grafu. Grafy můžeme reprezentovat i pomocí matic. V tomto skriptu uvedeme dvě maticové reprezentace, a to pomocí incidenční matice a pomocí matice sousednosti. Existují i další, a to např. znaménková matice, Laplaceova matice sousednosti, matice vzdáleností. fi~ Definice 1.16 Incidenční matice B(G) grafu G s n vrcholy vi, v%,... vn a m hranami ei,e2,..., em je matice typu n x m s prvky bij, i = 1,2,... n; j = 1,2,...., m; kde bij = 1, je-li vrchol ví incident ní s hranou ej. b^ = 0, jestliže Ví není incidentní s hranou ej. --'- B Vlastnosti incidenční matice: • Součet prvků i-tého řádku dává stupeň vrcholu i'i. • Součet prvků j-tého sloupce je vždy 2. • Matice je velmi řídká a rozsáhlá, zvláště u grafů s vysokým počtem hran. Příklad incidenční matice grafu je na obrázku 1.9. «1 e 2 £3 ť J e§ 66 e? fl 0 1 0 0 0 0\ u2 1 1 0 1 1 0 0 Ui 0 1 0 f) 0 1 0 U 4 0 0 1 1 0 0 1 Mg \0 0 0 0 1 1 V Obrázek 1.9: Incidenční matice grafu Kapitola 1 Graf a základní pojmy 15 I : Definice 1.17 Matice sousednosti A(G) je čtvercová matice nxn, kde n je počet vrcholů grafu G, kde je ay = 1, jsou-li vrcholy m a v j sousední, ay = 0, pokud jsou nesousední. Vlastnosti matice sousednosti: • Matice je úspornější. • Matice je symetrická. • Součet prvků i-tého řádku (i-tého sloupce) dává opět stupeň vrcholu v;. Příklad matice sousednosti grafu je na obrázku 1.10. □ Ui U-2 w3 "4 u5 71, (O 1 0 1 0\ íi2 1 0 1 1 1 «3 0 i 0 0 1 U4 1 1 0 0 1 «5 \0 1 1 1 0/ Obrázek 1.10: Matice sousednosti grafu 1.5 Příklady a úkoly ke kapitole A j Řešený příklad 1.1 Sedm přátel si před odjezdem na dovolenou slíbilo, že každý z nich pošle pohledy třem z ostatních. Může se stát, že každý z nich dostane pohledy právě jen od těch, kterým sám pohledy poslal? Nejdříve úlohu interpretujeme v teorii grafů. Každý z přátel představuje vrchol. Skutečnost, že si navzájem poslali dva přátelé pohled, budeme reprezentovat hranou. Tzn. pokud graf k dané úloze existuje, bude mít 7 vrcholů a každý vrchol bude 3. stupně. K řešení příkladu použijeme předchozí větu. Pro každý graf G s n vrcholy «1,1/2, ■ •. vn, kde n > 1 a h(G) označíme počet hran daného grafu, platí Eľ=i 1 a h(G) označíme počet hran daného grafu, platí Ym=i deg(vi) = 2h(G), Potom tedy pro součet stupňů v daném grafu platí, že je nejvýše In. Bylo však odehráno n+1 zápasů, tzn. použitím stejné věty dostáváme, že součet stupňů všech vrcholů v daném grafu je 2n + 2. Dostáváme tím spor a náš předpoklad, že každé mužstvo odehrálo nejvýše dva zápasy, je špatný. Musí existovat alespoň jeden vrchol 3. stupně, tzn. mužstvo, které odehrálo alespoň 3 zápasy. A Neřešené příklady 1. Ukažte, že není možné, aby ve skupině devíti lidí každý znal právě pět dalších z této skupiny. 2. Účastníci obchodního jednání si vzájemně vyměnili navštívenky. Dokažte, že byl celkem vyměněn sudý počet navštívenek. 3. Ukažte, že v každém grafu platí 5(G) < 2 ,W < A(G), kde v(G) označuje počet vrcholů v grafu G. 4. Ve fotbalovém turnaji hraje jedenáct mužstev. Je možné, aby v určitém čase šest mužstev z nich mělo odehrány čtyři zápasy, tři mužstva po třech zápasech a dvě mužstva jen dva zápasy? 5. Na obchodní poradu přišel Američan, Švýcar, Kanaďan, Brazilec a Francouz. Američan (A) ovládá angličtinu a španělštinu. Švýcar (Š) francouzštinu, němčinu, italštinu, Kanaďan (K) angličtinu a francouzštinu, Brazilec (B) se dohovoří španělsky a portugalsky, Francouz (F) jen svou mateřštinou. Dvojice, které se nedohovorí přímo, mají přiděleny tlumočníky t\. Í2: Č3, £4, Í5, a to t\ pro K a B, Í2 pro B a F, ts pro F a A, £4 pro A a Š, Í5 pro Š a B. Znázorněte přiřazení tlumočníků účastníkům. 6. Dokažte, že v každé skupině dvou nebo více lidí jsou vždy nejméně dva lidé, kteří mají v této skupině stejný počet známých. 7. Nechť G je fc-pravidelný graf, kde k je liché číslo. Dokažte, že počet hran grafu h(G) je násobkem k. Platí to i v případě, že k je sudé? 8. Existuje obyčejný graf o pěti vrcholech, který má jeden vrchol stupně čtyři a druhý vrchol izolovaný? Existuje obyčejný graf o pěti vrcholech, jehož každý vrchol je jiného stupně? 9. Jesliže existují v grafu G o pěti vrcholech právě dva vrcholy stejného stupně, mohou mít stupeň 0 nebo 4? Kapitola 1 Graf a základní pojmy 17 10. Kolik hran má úplný graf na n vrcholech? 11. Dokažte, že počet vrcholů pravidelného grafu lichého stupně je vždy číslo sudé. 12. Necht' G má n vrcholů a n — 1 hran. Ukažte, že G má buď vrchol stupně jedna, nebo izolovaný vrchol. 13. Dokažte, že pro každý graf G existuje graf AT takový, žc A/ je pravidelný stupně A(G) a G je indukovaný podgraf grafu Ar. 14. Dokažte matematickou indukcí vzhledem k počtu hran: Pro každý graf G s n vrcholy i'i,t'2,.. ,vn, kde n > 1 a h(G) označíme počet hran daného grafu, platí Y,deg(vi) = 2h(0). 15. Pro následující graf na obrázku 1.11 sestavte incidenční matici a matici sousednosti. Obrázek 1.11: Diagram grafu k příkladu 15 16. Zamyslete se nad definicí matice sousednosti a incidenční matice obecného grafu. 17. Čemu se rovná součet prvků řádku, resp. sloupce v incidenční matici obecného grafu? 18. Čemu se rovná součet prvků řádku, resp. sloupce v matici sousednosti obecného grafu? 19. Může mít incidenční matice jednoduchého grafu dva shodné řádky nebo sloupce? Jak je tomu u obecného grafu? Kapitola _ Cesty, cykly a souvislost 2.1 Sled, tah, cesta a cyklus V úvodu tohoto skripta jsme hovořili o možnosti reprezentace měst. křižovatek jako vrcholů a spojnic mezi městy a křižovatkami pomocí hran v grafu. Pokud ve skutečném životě budeme projížždět, procházet městy, křižovatkami z města A do města B, hovoříme o tom, že jsme zvolili cestu, respektive trasu. V této kapitole zavedeme pojmy, které se budou týkat něčeho podobného, ale tentokrát se budeme „pohybovat" grafem. Definice 2.1 Sledem bude nazývat posloupnost uq, ei, v\, e-j, ■ ■ ■, en, vn. kde n > 1 a e* je hrana s koncovými vrcholy Wf_i a kde i = 1, 2,.... n. _ —---—-;- □ Z definice vyplývá, že ve sledu se mohou některé hrany, tzn. i vrcholy opakovat. Protože v tomto skriptu uvažujeme pouze jednoduché grafy, můžeme zjednodušit zápis posloupnosti ze zápisu vo, ei, v\, e-2, •.., en, vn na vq, vi,..., vn. Jinými slovy, nemusíme psát hrany, postačí nám zapisovat vrcholy, a protože v grafu neuvažujeme násobné hrany, můžeme vybrat mezi dvěma vrcholy jen jednu hranu. Sled je v jednoduchém grafu jednoznačně určen i posloupností hran. Na obrázku 2.1 je příklad jednoho ze sledů daného grafu. Pro sled vo, vi,..., vn můžeme použít označení (vq, un)-sled. Takové označení není jednoznačné, může existovat více (vo, ťn)-sledů. Dalším pojmem je tah. U definice tahu budeme vycházet z pojmu sled. Definice 2.2 Tah je sled, ve kterém se žádná hrana neopakuje. _ —:-:—~~———:—~ s U tahu můžeme tedy „projít" některým vrcholem vícekrát, ale pokaždé k tomu musíme použít jiné hrany. Můžeme si představit, že termín tah je spojen s úlohou nakreslit nějaký obrázek jedním 18 Kapitola 2 Cesty, cykly a souvislost 19 06 !'7 Sled: i'i, i>3. vq, vj, 04 , v5. v?, v4, 02 Označení («i, i?2)-sled Obrázek 2.1: Sled grafu U6 V7 (vi, t'2)-tah: oi, ť3,t;4,V7,o5, t'4,i'2 Obrázek 2.2: Tah grafu tahem, např. domeček. Tentokráte ale uvažujeme, že nakreslíme (projdeme) každou hranu právě jednou. Obecně tah nemusí obsahovat všechny hrany grafu. Příklad tahu je na obrázku 2.2. Pro tah jsme použili omezení, že se nesmí opakovat hrany. Nyní ještě podmínku zpřísníme, nebudou se moci opakovat ani vrcholy a tím definujeme cestu. Definice 2.3 Cesta je tah, ve kterém se neopakuje žádný vrchol. □ V cestě se neopakují vrcholy, z toho vyplývá, že se také neopakují hrany. Každá cesta je tedy tahem i sledem. Tah je vždy sledem, ale ne cestou. Příklad cesty je na obrázku 2.3. Cestu na n vrcholech budeme označovat Pn. Je-li Pn nějaká (í>i, vn)-cesta, potom vrcholy v\ a vn nazýváme koncovými vrcholy a všechny její ostatní vrcholy vnitřními vrcholy této cesty. fi~ Definice 2.4 Uzavřeným sledem resp. tahem nazýváme sled resp. tah, jehož první a poslední vrchol splývají. Z každého sledu z vrcholu u do vrcholu v lze vybrat cestu z u do v. Pokud se ve sledu vyskytuje vrchol, který si označme jako w, vícekrát, odstraníme ze sledu vše mezi prvním a posledním výskytem vrcholu w. Tímto způsobem zkracujeme sled pro každý opakující se vrchol. Ve výsledku se žádný vrchol neopakuje, tzn. že jsme získali cestu. Kapitola 2 Cesty, cykly a souvislost 20 (í'i . ť2)-cesta: Vi,Vz, v$, v?, V4. t'2 Obrázek 2.3: Cesta grafu Definice 2.5 Předpokládejme, že mezi sousedními vrcholy u a v existuje (u, v)-cesta. která má více než jednu hranu. Pak (u,v)-ccsta spolu s hranou uv tvoří cyklus. Jestliže Pn je (u, ?;)-cesta s více než jednou hranou, pak cyklus na n vrcholech označujeme Cn. [7~j Definice 2.6 Délkou tahu, cesty nebo cyklu rozumíme počet jeho hran. Cyklus Cn má tedy délku n, zatímco cesta Pn má délku n — 1. Nejkratší cesta je P2 a nejkratší cyklus C3. 2.2 Dosažitelnost, souvislost, vzdálenost v grafu, excentricita, průměr a poloměr Vzdáleností většinou chceme neformálně vyjádřit vzájemnou polohu míst, bodů, vrcholů. V teorii grafů zavedeme také pojem vzdálenost. Fakt, zda mezi dvěma místy existuje cesta, souvisí s pojmem dosažitelnost. Na základě dosažitelnosti můžeme definovat souvislý graf. |7~j Definice 2.7 Vzdálenost vrcholu u od jiného vrcholu v je délka nejkratší cesty z vrcholu u do vrcholu v. Vzdálenost vrcholu u od jiného vrcholu v označujeme dist(u, v), pokud bychom chtěli zdůraznit, Kapitola 2 Cesty, cykly a souvislost 21 že dané vrcholy patří grafu 67. potom použijeme dista(u, v). Pro vzdálenost vrcholu u od vrcholu u platí dist{u, u) = 0a to platí pro každý vrchol u libovolného grafu G. Dále pro libovolné vrcholy u, v, w platí dist(u,v) < dist(u,w) + dist(w.v) a je-li dist(u,v) > 1, pak existuje vrchol grafu w takový, že je různý od vrcholů u,v a platí dist(u, v) = dist(u, w) + dist(w, v). V jednoduchých grafech bez ohodnocení hran je délka mezi sousedními vrcholy jednotková, tzn. pokud by vrcholy reprezentovaly města Opava, Ostrava, Brno, Praha a byly by to vrcholy, které jsou spojeny hranou, tak bychom zanedbali, že skutečné vzdálenosti těchto měst navzájem nejsou stejné. i Definice 2.8 Vrchol v je v grafu G dosažitelný z vrcholu u grafu G, jestliže v grafu G bui existuje cesta z vrcholu u do vrcholu v, nebo ie u — v. - □ Funkce vzdálenosti i dosažitelnosti je symetrická. Pro vzdálenost každých dvou vrcholů u a v libovolného grafu G platí dist(u.v) = dist(v.u). Není-li vrchol u dosažitelný z vrcholu v, pak definujeme dist(u,v) = oc. Definice 2.9 Souvislý graf je graf. vc kterém jsou z libovolného vrcholu dosažitelné všechny ostatní vrcholy. --^- □ Souvislý graf bychom mohli definovat i tak, že graf je souvislý, pokud existuje cesta mezi libovolnými dvěma vrcholy. U souvislého grafu vzdálenost představuje celé nezáporné číslo. Zamysleme se, kolik hran má souvislý graf nejméně a kolik nejvíce. pV~| Věta 2.1 Je-li G souvislý graf, potom platí \E(G)\ > \V(G)\ - 1. 0 Větu a důkaz věty matematickou indukcí je možné najít v [7]. Tato věta určuje dolní mez pro počet hran souvislého grafu. Maximální počet hran bude mít graf, ve kterém bude platit, že každé dva vrcholy jsou koncovými vrcholy jedné hrany. Grafy s maximálním počtem hran nazýváme úplnými grafy. Pokud bychom si položili otázku, kdy v dané větě nastává rovnost, tak nastává pro speciální typ grafu, který nazýváme strom. Stromy popíšeme hned v další kapitole. fi~ Definice 2.10 Nesouvislý graf je graf, ve kterém existuje dvojice navzájem nedosažitelných vrcholů. □ Kapitola 2 Crsty, cykly a souvislost 22 Diagram nesouvislého grafu vypadá tak, že se skládá z několika částí. Tyto části nazýváme komponentami grafu. i Definice 2.11 Komponenta grafu je maximální souvislý podgraf daného grafu G. _ --~~--_— D Komponenta grafu je tedy souvislý podgraf, který není vlastním podgrafem žádného souvislého podgrafu grafu G. Počet komponent grafu G označujeme oj(G). Pokud je graf souvislý, obsahuje jednu komponentu, pokud je nesouvislý, obsahuje více komponent. Nesouvislý graf má minimálně dvě komponenty. Se vzdáleností souvisí i pojem excentricita, průměr a poloměr grafu. Definice 2.12 Excentricita vrcholu u je rovna vzdálenosti vrcholu u od takového vrcholu v, který je v daném grafu G od u ncjvzdálenější. _ -:-Q Excentricitu označujeme ecc(u). Z matematického hlediska můžeme excentricitu definovat ecc(u) = max^gv^G) dist(u,v). Definice 2.13 Průměr nebo také diametr grafu je maximální excentricita vrcholů v grafu. _ —-;-~~—-□ Průměr označujeme diam{G). Co se týče matematického zápisu, tak průměr vypočteme podle vzorce diam(G) = maXy^vtG) scc(v). To znamená, že určíme excentricitu každého vrcholu v daném grafu a maximum z daných excentricít je rovno průměru grafu. Definice 2.14 Poloměr nebo také rádius grálů je nejmenší excentricita vrcholu v grafu. _ -'—;-;- □ Poloměr označujeme rad(G). Určíme excentricitu každého vrcholu v daném grafu a minimum z daných excentricít je rovno poloměru, platí tedy rad(G) = mint,eí/(G) ecc(v). Příklady určení průměru a poloměru grafu jsou na obrázku 2.4. V nesouvislém grafu G platí ecc(u) = oo pro každý vrchol u grafu G. to znamená, že diarn(G) = rad(G) = oo. Pojmy poloměr a průměr máme spojené s kružnicí nebo koulí a víme, že průměr je roven dvojnásobku průměru. V další větě uvedeme, jaké vztahy platí pro poloměr a průměr v teorii grafu. Kapitola 2 Cesty, cykly a souvislost 23 ■o max ecc = 2 rnin ecc — 2 diam = rad = 2 moi ecc — 2 ítot?. ecc = 1 diam = 2 rad — 1 max ecc — 3 min ecc — 2 diam = 3 rad — 2 Obrázek 2.4: Průměr a poloměr grafu Ir1 V Věta 2.2 V každém grafu G je rad{G) < d,iarn(G) < 2 ■ rad(G). V Důkaz dané věty nalezneme v [4]. Pokud si položíme otázku, jestli může i v teorii grafů platit, že diam(G) = 2 • rad(G), tak odpovíme ano a příklad takového grafu můžete vidět na druhém grafu zleva na obrázku 2.4. Ä Řešený příklad 2.1 Silniční síť zahrnuje 2n měst, z nichž z každého města vede n silnic do ostatních měst. Existuje silniční trasa mezi libovolnými dvěma městy? Nejdříve danou úlohu přeformulujeme do teorie grafů. Máme dokázat, že graf o 2n vrcholech, z nichž každý je stupně alespoň n, je souvislý. Provedeme důkaz sporem. Budeme předpokládat, že graf není souvislý a že tedy existuje více než jedna komponenta. Potom existuje komponenta, která má nejvýše n vrcholů. Každý vrchol v této komponenty může být spojen jen s vrcholy stejné komponenty, tzn. že může být stupně nejvýše n — 1. To ale odporuje předpokladu. Vrchol v musí být tedy spojen alespoň s jedním vrcholem druhé komponenty, ale to potom je daný graf souvislý. Což jsme měli dokázat. Neřešené příklady 1. U 4-pravidelného grafu nalezněte uzavřené tahy, které obsahují: • 4 hrany, • 5 hran, • 6 hran, • 10 hran. Kapitola 2 Cesty, cykly a souvislost 21 2. Dokažte, že platí-li v jednoduchém grafu o n vrcholech (n > 3), že součet stupňů libovolných dvou nesousedních vrcholů je nejméně n, potom je graf souvislý. 3. Dokažte, že v každém grafu G se stupňovou posloupností (2,2, 2, 2,2, 2,2, 2,1,1) existuje cesta spojující oba vrcholy stupně 1. 4. Ukažte, že existuje-li v G (u, w)-slcd pro dva různé vrcholy u, v. potom tam existuje také (u, v)-cesta. 5. Dokažte, že každé dvě nejdelší cesty v souvislém grafu mají společný vrchol. 6. Nechť u je vrchol lichého stupně v grafu G. Ukažte, že potom v grafu G existuje (u, t>)-cesta do vrcholu v, který je také lichého stupně. 7. Dokažte, že je-li S > 2, potom G obsahuje cyklus. 8. Dokažte, že G(V, E) je souvislý právě tehdy, když pro libovolný rozklad vrcholové množiny V na dvě množiny U a W existuje hrana e = uw 6 E taková, že w G W. Množiny U a W tvoří rozklad V, jestliže U U W = V a U n W = 0. 9. Určete průměr úplného grafu Are. 10. Dokažte, že pro libovolná přirozená čísla n. m. splňující podmínku n < m < 2n, existuje graf G takový, že rad(G) —na díam(G) — m. - "i Kapitola a 3.1 Strom S grafem nazývaným strom se každý z nás už setkal. Minimálně v okamžiku, kdy měl za úkol na základní škole sestavit rodokmen. Se stromy se můžeme potkat i v genetice, kde se zkoumají dědičné vlastnosti živých organismů. Se stromem se můžeme setkat při sestavování algoritmů, kde se používají tzv. rozhodovací stromy, pomocí nichž lze velmi přehledně znázornit všechny možné odpovědi na určitou skupinu otázek s předem vymezenými volbami odpovědí na jednotlivé otázky. I v programování jsou stromy velmi důležitý druh datových struktur a mohou být využity například při překladu z programovacích jazyků, potom se dané stromy nazývají syntaktické stromy, nebo tzv. vyhledávací stromy, atd. V minulém století studovali stromy zejména A. Cayley, G. Kirchhof a G. K. Chr. Staudt. Kirchhof a Staudt k nim dospěli r. 1847 současně a každv z jiného podnětu; první při fvzikálním vyšetřování a vedení elektrického proudu, druhý při matematických úvahách v souvislosti s tzv. Eulerovou větou o mnohostěnech. A. Cayley věnoval stromům pozornost pro jejich úzký vztah k některým strukturním vzorcům v organické chemii. [16] Stromy patří mezi nej jednodušší typy ze všech grafů. V teorii grafů se stromem rozumí graf, jehož příklady je možno vidět na obrázku 3.1. Vlevo daný strom skutečně připomíná strom v přírodě, uprostřed se daný graf nazývá hadem a úplně vpravo hvězdou. O ô Obrázek 3.1: Příklady stromů Kapitola 3 Stromy a kostry 26 Pokud bychom se podívali na molekuly uhlovodíků CnH'2n+2, tak skutečně l/e použít reprezentaci pomocí grafů nazývaných stromy. H H H H H H I II III H — C — H H — C — C — H H — C — C — C — H I II III H H H H H H Obrázek 3.2: Molekuly uhlovodíků C„,H2n+2 |T~ Definice 3.1 Acyklický graf jc graf, ve kterém žádný jeho podgraf není cyklem. □ Strom můžeme definovat více způsoby. Asi nejběžnější definice je definování stromu na základě vlastnosti acvkličnosti a souvislosti. fi~ Definice 3.2 Strom je graf, který je acyklický a souvislý. □ Tato definice nám ale moc nepomůže zjistit, jestli je daný graf stromem. Souvislost lze ověřit snadno, s neexistencí cyklu je to ovšem horší. Proto použijeme i další charakteristiky stromů, které uvedeme později. Strom na n vrcholech označujeme Tn. Definice 3.3 Les je graf, který je acyklický. Les je tedy graf, jehož každá komponenta je stromem a neobsahuje cyklus. Strom je oproti lesu navíc souvislý. Příklad grafu, který je lesem, je na obrázku 3.3. Les tedy nemusí být souvislý a samozřejmě každý strom je také les. * <*> <*> oTo oTo oTo O o Obrázek 3.3: Les Kapitola 3 Stromy a kostry 27 Věta 3.1 Každv souvislý graf má faktor, který je stromem. _ ——■-■-;-E Důkaz: Pokud bude graf obsahovat cyklus, odstraníme libovolnou hranu tohoto cyklu. Souvislost grafu zůstane zachována. Odebírání hrany z cyklu opakujeme tak dlouho, pokud v grafu existuje alespoň jeden cyklus. Získáme tím graf, který bude acyklický a souvislý, tzn. bude stromem. □ V další větě stanovíme postačující podmínku, aby v grafu existoval vrchol stupně 1. Je zřejmé, že strom s jediným vrcholem stupně 1 neexistuje, stupně 1 jsou vždy nejméně dva vrcholy. Pro důkaz věty 3.1 nám postačí dokázat existenci jednoho vrcholu stupně 1. Věta 3.2 Každý strom s alespoň dvěma vrcholv má nejméně jeden vrchol stupně 1. _ —-"-:- 0 Důkaz: Důkaz provedeme nepřímo. Ukážeme, že z neplatnosti tvrzení by vyplývala neplatnost předpokladu. Pro strom se dvěma vrcholy je tvrzení zřejmé, oba jeho vrcholy jsou stupně 1. Předpokládejme, že počet vrcholů je n, kde n > 3, a každý z těchto n vrcholů je stupně alespoň 2. Nechť vi je libovolný vrchol a t>2 je jeden z jeho nejméně dvou sousedů, protože každý vrchol je stupně alespoň 2. Vrchol V2 má tedy nejméně jednoho dalšího souseda, nechť je to vrchol vg. Protože i vrchol t;3 je stupně alespoň 2, musí mít dalšího souseda, různého od vrcholu V2- Tímto sousedem nemůže být vrchol V\, neboť v tomto případě by Tn obsahoval cyklus c3 = i'i,t'2, V3,V\, což není podle definice stromu možné. Obecně v i-tém kroku vrchol ví sousedí kromě vrcholu v{-\ ještě s nějakým dalším vrcholem. Tím nemůže být žádný z vrcholů t'2, • • •, v,--2? protože potom by graf Tn obsahoval cyklus. V n-tém kroku přidáme vrchol vn, ten však kromě vrcholu vn—\ musí být sousední s některým dalším vrcholem, tedy s jedním z vrcholů V\,V2, ■ ■ ■ ,Vn-2< Pak ale oraf Tn obsahuje cyklus, což je spor s předpokladem, že graf Tn je strom. Situace vidíme na obrázku 3.4, kde je dobře patrná sousednost vrcholů. Z uvedeného vyplývá, že alespoň jeden vrchol musí být stupně menšího než 2. Protože strom je souvislý, tento vrchol není stupně 0, ale že je stupně 1, což jsme měli dokázat. Tím je důkaz hotov. □ Věta 3.3 Nechť Tn je graf na n vrcholech. Potom následující tvrzení jsou ekvivalentní: 1. Tn je strom; 2. T^j je acyklický a souvislý; 3. Tn je acyklický a má n — 1 hran; 4. Tn je souvislý a má n — 1 hran. -^--- E Kapitola 3 Stromy a kostry 28 Obrázek 3.4: Ilustrace k důkazu věty 3.1 - existuje vrchol stupně 1 Vidíme, že bychom měli provést důkaz ekvivalence více než dvou tvrzení. Využijeme následující zjednodušení a to, že pro provedení důkazu ekvivalence p tvrzení stačí ukázat pouze p+1 implikací: 1) => 2) 3) =»4) => ...p) 1). Důkaz: Tvrzení 1) a 2) jsou ekvivalentní, nebot' 2) je definicí stromu. 2) =4- 3) Graf Tn je acyklický a souvislý => graf Tn je acyklický a má n — 1 hran. Stačí nám ukázat, že strom má n — 1 hran. Použijeme důkaz matematickou indukcí vzhledem k počtu vrcholů. Dané tvrzení platí pro strom s jediným vrcholem, což je graf, který nemá žádné hrany. Předpokládáme, že tvrzení platí pro libovolný strom s n vrcholy, a na základě tohoto předpokladu ukážeme, že tvrzení platí pro libovolný strom s n + 1 vrcholy. Nechť Tn+i je libovolný strom s n + 1 vrcholy. Podle předchozí věty obsahuje vrchol stupně 1, označme ho jako vrchol v. Pokud vynecháme vrchol v z grafu, dostaneme graf, který je souvislý a acyklický, to znamená, že daný graf je tedy strom s n vrcholy a podle indukčního předpokladu má právě n — 1 hran. Protože původní graf Tn+i obsahoval navíc pouze jedinou hranu, je tvrzení dokázáno. 3) => 4) Graf Tn je acyklický a má n — 1 hran =>■ graf Tn je souvislý a má n — 1 hran. Stačí ukázat, že acyklický graf na n vrcholech s n — 1 hranami je souvislý. Budeme dokazovat sporem. Předpokládejme, že graf Tn není souvislý a skládá se z k komponent Si, $2,.. ■, Sfc. Každá z těchto komponent je acyklická, tedy je stromem a daný graf je vlastně lesem. Označíme-li n, počet vrcholů komponenty Si, potom počet hran grafu je rovný součtu počtu hran jednotlivých komponent a platí tedy J2i=i(ni ~~ !)• Podle předpokladu má tento graf n — 1 hran, platí tedy Ya=i{'<1í - 1) = 12í=ini ~ k = n - 1. Z toho vyplývá, že k = 1. Pokud k = 1, má Tn jednu komponentu, tedy daný graf není nesouvislý, ale souvislý, což jsme chtěli dokázat. 4) => 2) Graf Tn je souvislý a má n - 1 hran =4> graf Tn je acyklický a souvislý. Budeme dokazovat opět sporem. Kapitola 3 Stromy a kostry 29 Nechť Tn je souvislý graf na n vrcholech s n — 1 hranami. Budeme předpokládat, že daný graf není acyklický, tedy obsahuje cyklus, například cyklus v\. «2,.... vm,i>i, a ukážeme, že toto tvrzení je ve sporu s naším předpokladem. Vynecháme-li z grafu Tn hranu vmv\, dostaneme graf s n — 2 hranami, který je stále souvislý. Jestliže totiž vrchol V{ je dosažitelný z vrcholu v\ v grafu Tn po cestě Vi,Vj,...,«», kde j m, potom je po této cestě dosažitelný i v grafu Tn — V\vm. Pokud je dosažitelný po cestě v\,vm,ví, potom je v Tn — v\vm nadále dosažitelný po cestě v\.V2- ■ ■ ■, vm-\,vm, • • ■, V{. K tomu, aby graf G byl souvislý, jistě stačí, aby každý vrchol V{ byl dosažitelný z nějakého pevně zvoleného vrcholu, například v\. Jestliže graf Tn — v\vm obsahuje cyklus, opakujeme předchozí krok tak dlouho, dokud nedostaneme acyklický souvislý graf. Ten však v každém případě obsahuje nejvýše n — 2 hran, protože jsme vynechali nejméně jednu z původních n — 1 hran. To je spor s předpokladem. Proto Tn neobsahuje cyklus, a tím je důkaz hotov. □ Vztah mezi počtem hran a počtem vrcholů u stromu má pojmenování, a to Eulerův vzorec (h = n- 1). V další větě stanovíme nutnou a postačující podmínku, aby graf byl stromem. Stanovení netriviální nutné a postačující podmínky umožňuje charakterizovat grafy s danou vlastností pomocí odlišné vlastnosti nebo více vlastností. Věta 3.4 Graf je stromem právě tehdy, kdvž každé dva jeho různé vrcholy jsou spojeny jedinou cestou. _ —-—-;--- 0 Důkaz: Věta má tvar ekvivalence. Důkaz tedy bude mít dvě části, budeme dokazovat dvě implikace. Nejdříve důkaz zleva doprava (=>). Danou implikaci budeme dokazovat sporem. Je-li graf stromem, potom je graf souvislý a tedy každé dva vrcholy jsou spojeny aspoň jednou cestou. Předpokládejme, že dva různé vrcholy vq a vr jsou spojeny dvěma různými cestami: P = i\),vi,... ,'t.y-i, vr, Q = v0,ui,... ,u8-i,ua = vr. Každá z těch cest může mít různou délku, důležité je, že mají nejméně dva společné vrcholy a to vrcholy vo,vr. Společných vrcholů však může být i více. Nechť je vrchol Wj poslední takový společný vrchol před rozdělením cest P a q, tzn. v\ = u\,..., Ví = Uí,Ví+i ^ ttj+i. Může tedy platit také. že vrchol v% = vq, ale pro indexy musí platit i < s. Nechť Vj je nejbližší vrchol k vrcholu v i na cestě P takový, že j > i a přitom tu zároveň leží na cestě Q a další vrcholy před vrcholem Vj až po vrchol v^i na cestě Q už neleží, tzn. Vť+l, • ■ •, Vj-i £ Q, vrchol Vj = Vk (i < k < s, přičemž může být i v j — Potom vrcholy t»j, Wj+i,..., ty_i, Vj = Wfc, Wfe-i,«fc-2)... j tty+i,u< = v% tvoří cyklus, tím dostáváme spor s definicí stromu, protože strom je acyklický, tzn. neobsahuje cyklus. Každé dva vrcholy jsou tedy spojeny jedinou cestou. Pro snadnější pochopení důkazu je situace znázirněna na obrázku 3.5, kde je část grafu pro demonstraci cest P a Q. Kapitola 3 Stromy a kostry 30 Obrázek 3.5: Důkaz - jediná cesta Nyní důkaz zprava doleva (■$=)■ Jsou-li dva kterékoliv vrcholy spojeny cestou, je graf souvislý. Zbývá ukázat, že z toho, že taková cesta je pro libovolnou dvojici vrcholů jediná, vyplývá, že graf je acyklický. Ukážeme tedy opět nepřímo. Předpokládejme, že graf obsahuje cyklus V\,V2, — , vjfe, v i- Potom ale z vrcholu v\ do vrcholu Vk vedou dvě různé cesty, totiž V\, v%,..., Vk a hrana uiVfc, což je spor s předpokladem, že daná cesta je jediná. □ 3.2 Kostra Každý souvislý graf G obsahuje podgraf, který je stromem a nazývá se kostra grafu G. Z této věty je zřejmé, že kostra může existovat pouze tehdy, je-li graf G souvislý. Definice 3.4 Kostra je libovolný souvislý acyklický faktor grafu G. _ —'—'—_—;-;—;-;— Q Kostra grafu je jeho nejmenší souvislý faktor, mající nejméně hran při daném počtu vrcholů. V grafu, který má n vrcholů, má jeho kostra n — 1 hran. Kostra grafu není určena jednoznačně. Hledání koster souvislých grafu má mnoho aplikací. Je zajímavé hledat kostru v komunikačních sítích, dopravních sítích apod. Samozřejmě dané úlohy jsou spojeny především s náklady na údržbu dané sítě. Praktické využití nalezení kostry daného grafu ukážeme v jedné z dalších kapitol. Algoritmus nalezení minimální kostry aplikujeme na úlohu týkající se udržování sjízdnosti komunikací ve sněhové kalamitě a abychom určitým způsobem zohlednili náročnost a délku cest mezi jednotlivými městy, křižovatkami, budeme muset hranám přiřadit číslo, které bude délku a náročnost na udržení sjízdnosti reprezentovat. Definice 3.5 Hvězda je strom, který obsahuje nejvýše jeden vrchol stupně vyššího než 1. _ -'-'-'-- Q Autorem další věty je Cayley a říká nám, kolik existuje stromů na dané množině vrcholů. Kapitola 3 Stromy a kostry 31 |"v~| Věta 3.5 Počet navzájem různých stromů na pevně dané množině n vrcholů, kde n < 2, je nn_2. [4] 0 A Řešený příklad 3.1 Dokažte, že graf o n vrcholech a n hranách obsahuje cyklus. Budeme předpokládat, že se jedná o souvislý graf. Jinak by v daném grafu musela existovat alespoň jedna komponenta, která má alespoň tolik hran, jako je vrcholů. Kdyby se jednalo o strom, platilo by pro počet hran h = n — 1. Souvislý graf, který není stromem, tedy není acyklický, musí obsahovat alespoň jeden cyklus. A Neřešené příklady 1. Myš hledá potravu v bludišti podle obrázku 3.6. Předpokládejme, že ze slepé chodby se vrátí na nejbližší křižovatku a vydá se dosud nevyzkoušeným směrem. Nakreslete strom všech možných tras, které muže oběhnout. Nalezněte nejdelší a nejkratší trasu. 0 - MflII 1 i; 1 Obrázek 3.6: Bludiště - myš 2. Dokažte, že graf je stromem právě tehdy, je-li souvislý, ale odstraněním libovolné hrany přestane být souvislý. 3. Dokažte, že každý netriviální strom T má nejméně dva vrcholy stupně 1. (Nápověda: Ukažte, že je-li dist(u,v) = diam(T), potom deg(u) = deg(v) = 1). 4. Dokažte, že Tn na alespoň třech vrcholech je cesta právě tehdy, když A(Tn) = 2. 5. Dokažte, že Tn je cesta právě tehdy, když obsahuje přesně dva vrcholy stupně 1. 6. Dokažte, že v grafu G existuje kostra právě tehdy, je-li souvislý. 7. Nakreslete graf o sedmi vrcholech, ve kterém existuje pro každé dva vrcholy právě jedna cesta, která je spojuje. 8. Kolik vrcholů stupně 1 může mít strom o dvou a více vrcholech maximálně a kolik minimálně? 9. Dokažte, že každý netriviální strom má nejméně dva vrcholy stupně 1. 10. Dokažte, že graf G(V,E), který je acyklický a pro nějž platí n = h + 1, je strom, n je počet vrcholů a h je počet hran grafu. 11. Dokažte, že graf na n vrcholech s c komponentami má alespoň n — c hran. Kapitola 3 Stromy a kostry 32 12. Dokažte, že Tn je hvězdou právě tehdy, když A(Tn) = n — 1. 13. Nechť A(Tn) — k. Dokažte, že potom Tn obsahuje alespoň k vrcholů stupně 1. 14. Nechť Fn je les s k komponentami. Dokažte, že h(Fn) = n — k. 15. Dokažte, že má-li graf G s alespoň jednou hranou všechny vrcholy sudého stupně, potom G obsahuje cyklus. 16. Dokažte, že je-li S > 2, potom G obsahuje cyklus délky alespoň ó(G) + 1. 17. Je dáno k krabic. V některých je opět k krabic. Plných krabic (tj. krabic obsahujících další krabice) je rn. Když otevřeme všechny plné krabice, kolik bude prázdných (tj. zavřených) krabic? Nezapomeňte na grafovou interpretaci. 18. Jsou dány 3 listy papíru. Některé z nich rozstrihneme na 3 kusy atd. Kolik kusů papíru celkem vznikne, jestliže bylo rozstříháno k kusů papíru? Úlohu dále zobecníme tak, že listů papíru je původně m a stříháme na 4 kusy Úlohu zobecníme tak, že stříháme m listů papíru, z nichž každý stříháme na n dílů. Úlohu provedeme pro tn = 5 a n — 5. Můžeme po několika stopách stříhání dostat 71 kusů? Nezapomeňte na grafovou interpretaci dané úlohy. 19. Ukažte, že strukturní vzorec alkanů CnH2n+2 Je (Pro každé n) strom. Atom vodíku je jedno-mocný, atom uhlíku čtyřmocný. 20. Kolik koster má kompletní graf K\, K2, K3 a K4I 21. Za jakých podmínek může mít souvislý graf několik různých koster? 22. Je možné, aby v souvislém grafu existovaly dvě různé kostry, jež nemají žádnou společnou hranu? 23. Nakreslete všechny stromy s méně než osmi vrcholy. 24. Z grafu G na obrázku 3.7 odstraňte některé hrany tak, aby vznikla kostra grafu G. Kolik hran je třeba odstranit ze souvislého grafu G. který má m hran a k vrcholu, abychom dostali kostru grafu Gl Obrázek 3.7: Vytvoření kostry grafu 25. Je zadán graf podle obrázku 3.8. Jaký největší počet hran můžeme v grafu odstranit, aby zůstal souvislý? ™--^>--0 ô—ô—ô—ô—ô—ô—ô—o Obrázek 3.8: Kostra grafu - počet odstraněných hran m Kapitola I _ Speciální grafy V této kapitole definujeme úplný graf, úplný bipartitní graf, bipartitní graf, úplný r-partitní graf, multipartitní graf. 4.1 Úplné grafy | i Definice 4.1 Úplný neboli kompletní graf na n vrcholech je graf, ve kterém je každý vrchol sousední se všemi ostatními vrcholy. -■- □ Danou definici bychom mohli napsat i tak, že úplný graf je takový graf, jehož každé dva různé vrcholy jsou spojeny hranou. Každý úplný graf o n vrcholech je tedy pravidelným grafem (n — 1)-stupně. [7] Úplný graf na ;í. vrcholech označujeme Kn. Na obrázku 4.1 vidíme příklady úplných grafů. Obrázek 4.1: Příklady kompletních grafů 33 Kapitola 4 Speciální grafy 34 4.2 Bipartitní grafy nice 4.2 Úplný bipartitní nebo také kompletní bipartitní graf na n + m vrcholech je graf, jehož vrcholová množina je sjednocením dvou disjunktních podmnožin A a D. hranová množina E obsahuje všechny možné hrany, jejichž jeden koncový vrchol patří do množiny A a druhý do množiny B. a žádné dva vrcholy množiny A resp. B nejsou navzájem spojeny hranou. _ I i Množiny vrcholů A a, B bipartitního grafu nazýváme ■partitami daného grafu. Úplný bipartitní graf označujeme Knjn. Příklad úplného bipartitního grafu vidíme na obrázku 4.2. Obrázek 4.2: Úplný bipartitní graf K4)5 Obrázek 4.3: Bipartitní graf L4,6 Formálnější definice úplného bipartitního grafu je: Kn,m: \A\ = n, \B\ = m, V(Kn_m) = A U B, AnB = ) C F(Lm>n). Potom existuje nmožina Á C V'(Lm> „/) a množina b' C V'(Lm' ft<), pro které platí a'ciaB'cBa také Á n b' = 0. Protože jsme žádný vrchol nepřidávali, nebudou existovat vrcholy, které by nepatřily do množiny A nebo do množiny b. Pro každý podgraf grafu Lm^n platí É (Lm' n>) C E(Lmn). Pro množinu E(Lm^n) platí E(Lm,tn) c {aíi | a g a,6 e b} a také a' C a a b' c b, potom tedy E(Lm' n>) c {a'6' | a' s a , ď' g b}. Protože do grafu nepřidáváme žádnou hranu, nebude existovat žádná hrana, jejíž oba koncové vrcholy by ležely pouze v množině A nebo v množině b Ä rr. Neřešené příklady 1. Dokažte, že každý strom je bipartitní graf. 2. Nechť G je pravidelný bipartitní graf s partitami U a W a alespoň jednou hranou. Ukažte, že potom \U\ = \W\. 3. Určete, kolik má graf G, určený maticí sousednosti na obrázku 4.4, cyklů liché délky. 00000010101 0 0 0 0 0 0 1 1 1 0 1 00000010011 00000000111 00000011001 00000011100 1 1 1 0 1 1 0 0 0 0 0 01001100000 1 110 10 0 0 0 0 0 00110000000 1 1 1 1 1 0 0 0 0 0 0 Obrázek 4.4: Počet cyklů liché délky m Kapitola _ Izomorfizmus a automorfizmus grafů 5.1 Izomorfizmus grafu Na obrázku 5.1 máme tři diagramy. Položme otázku: Které z těchto diagramů patří témuž grafu? Je to diagram prostřední a diagram vpravo. U daných diagramů grafů lze snadno poznat, že se jedná pouze o jiné nakreslení. Na obrázku 5.2 už je rozpoznání, že se jedná o jiné nakreslení diagramu téhož grafu, složitější. První dva diagramy zleva nemohou být diagramy téhož grafu, protože na každém z těchto diagramů vidíme jinou množinu vrcholu, ale mezi danými grafy existuje jistý vztah. Dané grafy jsou izomorfní. Obrázek 5.1: Grafy tfír Definice 5.1 Grafy G (V, E) a H(U,F) nazveme izomorfní (G = H), jestliže existuje takové prosté zobrazení $ množiny V na množinu U, že pro každé dva vrcholy wi? v j £ V existují vrcholy ur,us G U takové, že ur = us — $(vj), a hrana urus = $(«t)$(f j) patří do množiny F právě tehdy, když hrana ViVj patří do množiny E. -- □ 37 Kapitola 5 Izomorfizmus a automorfizmus grafů 38 Obrázek 5.2: Různé diagramy téhož grafu Z uvedené definice vidíme, že izomorfizmus zachovává sousednost i nesousednost vrcholů. Obrazy vrcholů, které jsou v G sousední, budou v H také sousední, zatímco obrazy nesousedních vrcholů budou nezávislé. Při zjišťování izomorfizmu se používají následující porovnání: • izomorfní grafy musí mít stejný počet vrcholů a hran, • vrcholu stupně k může být izomorfizmem přiřazen opět jen vrchol stupně k, • dvojici sousedních vrcholů může být izomorfizmem přiřazena opět jen dvojice sousedních vrcholů, • některé vlastnosti grafů se izomorfizmem zachovávají (existence cest, cykly jisté délky, ...). Dva grafy nemohou být izomorfní, jestliže jeden z nich takovou vlastnost má a druhý nikoliv. Na obrázku 5.3 vidíme příklad izomorfního zobrazení. Samozřejmě, že daných izomorfizmů může existovat více. «3 «5 V4 V5 U.i —? V.\ «2 ''2 «5 —> t'l «:s -+• t*3 u i —> vr, Obrázek 5.3: Příklad izomorfního zobrazení Kapitola 5 Izomorfizmus a automorfizmus grafů 39 Stupňová posloupnost grafu může izomorfizmus grafů vyloučit. Grafy s různými stupňovými posloupnostmi nebudou izomorfní. Můžou však být neizomorfní grafy se stejnými stupňovými posloupnostmi. Na obrázku 5.4 jsou diagramy grafů, které mají stejné stupňové posloupnosti a nejsou izomorfní. U vrcholů jsou uvedeny stupně daných vrcholů a nikoliv označení. Například první dva grafy reprezentované diagramem nemohou být izomorfní, protože je v prvním diagramu grafu vrchol stupně 1 je sousední s vrcholem stupně 3 a ve druhém diagramu grafu je vrchol stupně 1 sousední s vrcholem stupně 2. Nezachovává se tady sousednost vrcholů. U následující trojice grafů první dvojice nemůže být izomorfní ze stejného důvodu a poslední dva grafy nemohou být izomorfní, protože v jednom z grafů jsou všechny tři vrcholy třetího stupně navzájem sousední a u druhého grafu sousední nejsou. (1,2,2,3,3,3) (1,2,2,3.3.3) (1,2.2,3.3.3) Obrázek 5.4: Neizomorfní grafy se stejnými stupňovými posloupnostmi Obecně zjišťování, zda dané grafy jsou izomorfní, je velmi obtížné. Pro stromy jsou známy polynomiální algoritmy pro určení izomorfismu. Polynomiální znamená, že čas potřebný k rozhodnutí, zda jsou libovolné dva grafy dané třídy izomorfní, je polynomiální funkcí počtu vrcholů těchto grafů. Není znám žádný polynomiální algoritmus, který by dokázal rozhodnout, zda dva obecné grafy jsou izomorfní. Jak jsme již napsali, zjišťování, zda dané stromy jsou izomorfní, není složité. Například v [11] je možné najít rychlý a snadný postup pro dané rozhodnutí. Každému stromu přiřadíme posloupnost nul a jedniček délky 2n, kde n je počet vrcholů daného grafu. Tuto posloupnost nazýváme kód. Izomorfním stromům se přiřadí stejný kód, neizomorfní budou mít různé kódy. To znamená, že budeme porovnávat pouze dané posloupnosti nul a jedniček. Více je možné se dozvědět o daném způsobu vyšetřování v [11]. Kapitola 5 Izomorfizmus a automorfizmus grafů 40 [y~| Věta 5.1 Dva grafy jsou izomorfní právě tehdy, když jsou jejich matice incidence stejné až na případnou permutaci řádků a sloupců. _ - 0 Předchozí věta nám určuje nutnou a postačující podmínku pro izomorfní grafy, ale je prakticky nepoužitelná, bylo by nutno prověřit ml nl možných permutací řádků o m hranách a n vrcholech. Pokud bychom si položili otázku: Kolik je navzájem neizomorfních grafů na n vrcholech pro obecné nl Určit to přesně je poměrně těžké. Jednoduchou úvahou můžeme dostat alespoň dobré odhady. Navzájem neizomorfních grafů určitě není více než všech grafů na dané konkrétní n-prvkové množině, tj. 2(2). Uvažujme jeden graf G na množině V = 1,2,... ,n. Kolik různých grafů na této množině je s grafem G izomorfních? G je izomorfní s nejvýše nl grafy na množině V, a proto (2) jich existuje minimálně ^r~- [11] Kdybychom to chtěli vyčíslit, tak na 4 vrcholech existuje 64 jednoduchých grafů, na 5 už 1 024, na 6 vrcholech 32 768 no a na 7 vrcholech už je to 2 097152. [13] Pokud bychom chtěli určit počet neizomorfních stromů s n vrcholy, tak by to bylo: n = 1 jeden graf, n = 2 jeden graf, n = 3 jeden graf, n = 4 dva grafy, n = 5 tři grafy, n, = 6 šest grafů, n = 7 jedenáct grafů, n = 8 dvacet tři grafů, n = 9 čtyřicet sedm grafů, n = 10 sto šest grafů. [13] Vedle izomorfisniu můžeme zavést pro srovnání grafů mnohem obecnější vztah, tak, že na zobrazení nebudeme požadovat bijektivnost, ale pouze převod vrcholů na vrcholy, hran na hrany a zachování incidenční relace. Takové zobrazení pak nazýváme homomorfizmem. Kromě izomorfizmu lze zavést ještě další speciální druhy morfizmů, např. monomorfizmus (injektivní zobrazení grafů), epimorfizmus (surjektivní zobrazení grafů), vnoření (injektivní zobrazení). [7] [y"| Věta 5.2 Jestliže jsou dva grafy izomorfní, pak mají totožnou stupňovou posloupnost, to znamená, že stupňová posloupnost je vzhledem k izomorfizmu invariantní. [12] 0 Důkaz:[12] Nechť G(V, E) a F(U, F) jsou dva izomorfní grafy. Jestliže u g V, pak degc(u) = o({v \ uv g E}), stupeň vrcholu u je roven mohutnosti množiny sousedních vrcholů (vrcholů spojených s u hranou). Předpokládejme, že $ : V —¥ U je izomorfizmus. Pak $ je bijektivní zobrazení a uv € E právě tehdy, když $(u)$(v) e U. degc(u) = o({v \ uv g E}) = o({*(t>) I #(ti)$(tO € F}) = degn(<Š>{u)). Z uvedeného vyplývá, že $ zachovává stupeň odpovídajících si vrcholů a tedy i stupňovou posloupnost. □ Poznámka: Věta platí pouze jedním směrem, není pravda, že každé dva grafy se stejnou stupňovou posloupností jsou izomorfní. Kapitola 5 Izomorfizmus a automorfizmus grafů 41 5.2 Automorfizmus grafů Zatím jsme zjišťovali, zdali existuje mezi dvěma různými grafy izomorfní zobrazení. Můžeme však uvažovat i pouze o jediném grafu a nadefinovat zobrazení, kde se vrchol grafu bude zobrazovat na vrchol téhož grafu. Potom nehovoříme o izomorfizmu, ale o automorfizmu. Definice 5.2 Prosté zobrazení Vř vrcholové množiny V grafu G(V. E) na sebe nazveme automorfizmem, jestliže pro každou dvojici vrcholů vt.Vj g V (G) platí, že hrana vrvs = ^(ví)9(vj) patří do množiny E právě tehdy, když hrana VjVj patří do množiny E. Pro každý graf existuje alespoň jeden automorfizmus, a to triviální, kdy každý vrchol se zobrazí sám na sebe, tzn. = v pro každý vrchol v £ V. Na obrázku 5.5 je příklad automorfizmu. A Řešený příklad 5.1 Nakreslete všechny neizomorfní obyčejné grafy s pěti vrcholy a se třemi hranami. Graf se třemi hranami musí mít součet stupňů všech vrcholů 6. Má-li být počet hran 3, pak může být stupeň vrcholu nejvýše 3. Určíme tedy vlastně možné kombinace stupňů vrcholů a to: □ U] Ví V-2 -+ V3 V3 -» l?i ''I -* «4 V-, -> VG V(; -» (.'5 Vl V2 v-ó Obrázek 5.5: Automorfizmus (0,1,1,1,3). (0,0,2,2,2), (0,1,1,2,2), (1,1,1,1,2). Na obrázku 5.6 jsou diagramy grafů odpovídající daným stupňovým posloupnostem. A Kapitola 5 Izomorfizmus a automorfizmus grafů 42 \ f / 6 o o o 6 o o Obrázek 5.6: Neizomorfní grafy na pěti vrcholech Neřešené příklady 1. Ukažte, zda grafy na obrázku 5.7 na straně 43 jsou izomorfní po dvojicích. 2. Vysvětlete, proč grafy na obrázku 5.8 na straně 44 nejsou po dvojicích izomorfní. 3. Vytvořte všechny možné neizomorfní stromy s pěti vrcholy. 4. Necht' Tn a T'n jsou dva stromy na n vrcholech, pro které platí A(Tn) = A(Tr'j = n—2. Ukažte, že potom platí Tn = Tn. 5. Dokažte, že pro libovolné n > 6 existují vždy přesně tři neizomorfní stromy Tn takové, že 6. Ukažte, že existuje 11 navzájem neizomorfních grafu na 4 vrcholech. 7. Ukažte, že každý graf na n vrcholech je izomorfní nějakému grafu Kn. 8. Nechť Tn je libovolný strom na n vrcholech a G je libovolný graf takový, že 5(G) > n — 1. Ukažte, že potom G má podgraf izomorfní s Tn. A(Tn) = n - 3. Kapitola 5 Izomorfizmus a automorfizmus grafů 44 Obrázek 5.8: Proč nejsou grafy po dvojicích izomorfní? Kapitola V7_ Vrcholová a hranová souvislost Odpovídá-li nějaký graf například schématu městské dopravy, železniční sítě, elektrického rozvodu, je určitě dobré si v takovém případě položit otázku fungování příslušné sítě i za krizových podmínek, kdy několik křižovatek, silnic, spojnic nemůžeme použít. Při grafové reprezentaci takových problémů se setkáváme s velmi důležitým pojmem teorie grafů, se souvislostí. 6.1 Vrcholová souvislost Na obrázku 6.1 jsou tři grafy. Položme otázku: Kolik nejméně vrcholů musíme z grafu odstranit, aby se daný graf stal nesouvislý nebo triviální? Zjistíme, že u prvního grafu musíme odstranit celkem čtyři vrcholy a získáme triviální graf. Pro získání nesouvislého grafu z druhého grafu musíme ostranit dva vrcholy a u posledního jeden vrchol. Co znamená nesouvislost? Například nemožnost komunikace mezi jednotlivými uzly sítě při nefunkčnosti některých uzlů. Obrázek 6.1: Vrcholová souvislost u různých grafu | i Definice 6.1 Vrcholová souvislost k(G) (souvislost grafu) je minimální počet vrcholů, jejichž vynecháním dostaneme buď nesouvislý graf. nebo izolovaný vrchol. -—-- □ 4.-> Kapitola 6 Vrcholová a hranová souvislost 46 Zdůrazněme, že vrcholová souvislost je počet vrcholů, tedy představuje číslo. Pokud je vrcholová souvislost rovna například 2, říkáme, že graf je 2-vrcholově souvislý nebo také 2-souvislý. Formálně můžeme odebírání vrcholu v a všech hran, které mají vrchol v jako jeden ze svých koncových vrcholů, definovat takto. |T~ Definice 6.2 Nechť G = (V, E) je graf. Definujme odebrání vrcholu jako grafovou operaci G - v = (V \ {v}, {e € E: v i e}), kde v € V. - □ i Definice 6.3 Vrcholový řez jc množina vrcholů, jejichž vvnecháním se graf G stane nesouvislým nebo triviálním. -■-—- □ Definice 6.4 Artikulace je řez v grafu s více než dvěma, vrcholy, obsahující jedinv vrchol. _ -;—:—:—;—~-:-□ To znamená, že artikulace je vždy jednoprvková množina obsahující vrchol, po jehož odebrání se graf stane netriviální. 6.2 Hranová souvislost V předchozí podkapitole jsme se zabývali případem, kdy jsme odebírali vrcholy. Nyní se podívejme na stejný obrázek 6.1 s tím rozdílem, že si položíme otázku: Kolik hran musíme odebrat, aby se daný graf stal nesouvislým nebo triviálním? U prvního grafu je počet hran, které musíme odebrat, čtyři, u druhého dvě a u grafu třetího v pořadí jedna. Vidíme, že si hrajeme na záškodníky, a klademe si otázku, kdy nebude možná komunikace mezi jednotlivými uzly, když budeme odebírat „spojení" mezi uzly. V praxi se budeme spíše zaobírat otázkou, kdy bude ještě například nějaká komunikační síť nebo dopravní síť použitelná, funkční. Definice 6.5 Hranová souvislost k (G) grafu G je minimální počet hran, jejichž vynecháním dostaneme nesouvislý nebo triviální graf. - □ Definice 6.6 Hranový řez je množina hran, jejichž vynecháním se graf stane nesouvislým nebo triviálním. _ --■-■- □ Kapitola 6 Vrcholová a hranová souvislost 47 Formálně odebírání hrany e můžeme definovat takto. Definice 6.7 Nechť G = (V, E) je graf. Definujme odebrání hrany jako grafovou operaci G — e — (V, E\{e}), kde e e E je hrana grafu G. —;-;-;-0 Nyní se budeme zaobírat hranami, jež nepatří do žádného cyklu. Definice 6.8 Most je řez, který obsahuje jedinou hranu. _ -—-;- □ Hrana uv grafu G se nazývá most grafu G, jestliže v grafu neexistuje žádný cyklus, který by ji obsahoval. Slovíčko most se používá i v běžném životě, a to většinou pro případ, že márne tok a chceme přejít z jednoho břehu na druhý. Ve skutečnosti to tedy znamená, že most spojuje dvě části oddělené tokem. I tady to můžeme chápat podobně, most spojuje dvě části grafu. Pokud máme graf, který je strom s alespoň dvěma vrcholy, potom každá jeho hrana je most. Nyní se podíváme na případ, jak to vypadá s mosty, kdy vytváříme kostru souvislého grafu. Věta 6.1 Každá kostra souvislého grafu G obsahuje všechny mosty v grafu G. _ —-—- 0 Důkaz této věty je možné nastudovat v [16]. Věta 6.2 Nechť G je pravidelný graf sudého stupně, potom v grafu G neexistuje žádný most. _ Tuto větu a její důkaz je možné najít v [16]. Položme si otázku, jak to vypadá u pravidelného grafu lichého stupně. Odpověď je jednoduchá, dané grafy existují a obsahují most. Věta 6.3 V libovolném grafu G platí k(G) < k'(G) < S(G). -—- □ Tato věta dává do vztahu vrcholovou a hranovou souvislost a navíc vidíme, že obě souvislosti mají horní mez, což je nejmenší stupeň daného grafu. Důkaz dané věty je v [4]. Kapttola 6 Vrcholová a hranová souvislost 48 ta? Definice 6.9 Blok je souvislý graf, který nemá artikulaci. _ —~~r~-D Blok je tedy buď úplný graf I<2, nebo je 2-souvislý. Blokem grafu nazýváme každý jeho podgraf, který je maximální s touto vlastností. [7~ Definice 6.10 Dvě (ti, u)-cesty v grafu G nazveme interně disjunktními, jestliže nemají žádný společný vnitřní vrchol, tj. žádný vrchol různv od vrcholů u a v. _ —'—'—~-;-□ Příklad dvou interně disjunktních cest najdeme na obrázku 3.5 na straně 30, jedná se o dvě cesty mezi vrcholy vi a vq. |"v~| Věta 6.4 Graf s alespoň třemi vrcholy je 2-souvislý právě tehdy, když každé dva jeho různé vrcholy jsou spojeny dvěma interně disjunktními cestami. • -~~—;-~—-0 Pokud v grafu existují ke každým dvěma rozdílným vrcholům dvě disjunktní cesty, potom aby se graf stal nesouvislým, je třeba odebrat z každé z těchto dvou cest po jedom vrcholu nebo po jedné hraně. Také platí, že dvě disjunktní cesty se společnými koncovými vrcholy tvoří cyklus. Z tohoto faktu vyplývají následující důsledky. D Důsledek 6.1 Každé dva vrcholy libovolného 2-souvislého grafu leží na společném cyklu. D D Důsledek 6.2 Každé dvě hrany libovolného 2-souvislého grafu leží na společném cyklu. D A Řešený příklad 6.1 Dokažte následující tvrzení: Platí-li v grafu G nerovnost k(G) > 2, potom každá hrana grafu G leží v cyklu. Víme, že platí věta: V libovolném grafu G platí k(G) < k (G) < S(G). K důkazu postačí první část nerovnosti, tzn. k(G) < k (G). Má-li být k(G) > 2, pak podle této věty musí platit k (G) > 2. Je-li graf G hranově dva a více souvislý, pak platí, že každá hrana leží v cyklu. Kdyby tomu tak nebylo, pak by graf byl hranově 1-souvislý a tudíž by nemusel být i podle dané nerovnosti i vrcholově 1-souvislý. To je však spor s tím, že graf má být vrcholově 2-souvislý. _ -"-"-"- Ä Kapitola 6 Vrcholová a hranová souvislost 49 m Neřešené příklady 1. Dokažte, že je-li graf G souvislý a hrana xy jeho most, pak graf G — xy, vzniklý odstraněním hrany xy z G, je nesouvislý. 2. Nechť graf G má nejméně 3 vrcholy a obsahuje most. Dokažte, že graf G má alespoň jednu artikulaci. 3. Sestrojte příklad pravidelného grafu stupně 4 s jednou artikulaci. 4. Mějme grafovou stupňovou posloupnost (4,4,4,3,3,3,3,2.2). Sestrojte souvislý graf, který odpovídá dané stupňové posloupnosti a nemá žádnou artikulaci. Potom graf s danou stupňovou posloupností, která má jedinou artikulaci a poslední případ, kdy má jediný most. 5. Dokažte, že má-li souvislý graf G most, pak má alespoň dva uzly lichého stupně. 6. Ukažte, že v každém 3-pravidclném grafu G platí k(G) = k (G). 7. Ukažte, že graf je strom právě tehdy, když každá jeho hrana je most. Platí, že graf je strom právě tehdy, když každý jeho vrchol je artikulace? 8. Dokažte, že hrana souvislého grafu je most právě tehdy, když neleží v žádném cyklu. 9. Dokažte, že každé dvě hrany bloku leží na společném cyklu. 10. Nechť souvislý graf G neobsahuje sudé cykly. Dokažte, že potom každý blok G je buď K% nebo lichý cyklus. 11. Ukažte, že každý souvislý graf G, který není blokem, má alespoň dva bloky takové, že každý z nich obsahuje přesně jednu artikulaci G. 12. Určete největší množství artikulaci, které mohou ležet v jediném bloku konečného grafu na n vrcholech. -ra Kapitola Párování a pokrytí grafu 7.1 Párování grafu V této kapitole popíšeme párování grafu. Párováním budeme nazývat množinu, kde prvky této množiny jsou hrany, které nemají žádný společný koncový vrchol. Na obrázku 7.1 jsou v grafech tučně vyznačeny hrany, které mohou tvořit párování. Množinu, která bude tvořit párování, označíme M. Z toho vyplývá, že u prvního grafu tvoří párování AI = {e^e^}, ale není to samozřejmě jediné párování, další je například M = {e-0le§} . Můžeme klidně uvažovat i jednoprvkové množiny. U prvního grafu neexistuje párování, které by obsahovalo tři hrany. U druhého grafu je párování například M — {e\, e^}. Tady také nenalezneme párování, které by obsahovalo tři hrany. Obrázek 7.1: Párování grafu Definice 7.1 Párováním nazýváme nezávislou množinu hran grafu G. - □ Vidíme, že párování nám jakoby přiřazuje vrcholy k sobě, že dané vrcholy spolu souvisí, patří k sobě. My budeme v teorii grafů říkat, že vrcholy jsou spárovány. Koncové vrcholy u,v jsou spárovány, jestliže hrana patří do množiny M, tedy uv = e € M. Žádné dvě hrany patřící do párování nemají společný vrchol. Pokud je M párování, tak M' Q M je také párování. 50 Kapitola 7 Párování a pokrytí grafu 51 [7~] Definice 7.2 Af-saturovaný vrchol nazýváme vrchol, který je koncovým vrcholem některé hrany párování Aí. □ Pokud vrchol není saturovaný, tak ho nazvváme Aí-nesaturovanv. i Definice 7.3 Úplným párováním (perfektním párováním) nazýváme takové párování, kdy je každý vrchol grafu M-saturovaný. -———-^-;-□ To znamená, že párování je perfektní, pokud neexistuje vrchol, který by nebyl koncovým vrcholem některé hrany nepatřící do množiny M. Párování v grafech na obrázku 7.1 M = {c\, e2} u prvního grafu a také M — {ei, es} u druhého grafu jsou příklady perfektního párování. Pro první graf bychom mohli najít ještě jedno úplné párování Aí = {65, eg}. Pro druhý graf však existuje jediné, které jsme již uvedli. [T~| Definice 7.4 Největším párováním M* nazveme takové párování, kdy neexistuje jiné párování M s větším počtem hran ndež je počet hran AI*. -;-D To znamená, že platí pro mohutnosti množin, které tvoří párování, \M*\ > \M\ pro každé párování M v grafu G. I 1 I Definice 7.5 Maximálním párováním nazveme párování M, kdy neexistuje párování A/', které by párování M obsahovalo jako svou vlastní podmnožinu. —~—;-;-Q To znamená, je-li M C M , potom M = M . 1 Definice 7.6 Alternující cestou vzhledem k párování M (Aí-alternující cestou) nazýváme cestu, jejíž hrany střídavě patří do množiny M a do množiny E(G) \ M. _--^- n Příkladem alternující cesty u grafu na obrázku 7.1 vlevo vzhledem k párování M — {ei,ez} je ei,e2,e3. Kapitola 7 Párování a pokrytí grafu 52 [ i Definice 7.7 M-nesaturovaná alternující cesta (M-nesaturovaná cesta) je M-alternující cesta, jejíž oba koncové vrcholy jsou M-nesaturované, tedy žádný její koncový vrchol nepatří do množiny párování M._ -—-^-:- □ Příkladem nesaturované alternující cesty u grafu na obrázku 7.1 vlevo vzhledem k párování M = {ei, e.3} je e2, e$, e±. V I Věta 7.1 Párování M v grafu G je nej větší právě tehdy, když graf G neobsahuje žádnou M- nesát ur o vanou cestu. V Důkaz dané věty nalezneme v [4]. 7.2 Párování a pokrytí v bipartitních grafech fi~ Definice 7.8 Okolí vrcholu v v grafu G definujeme jako množinu všech vrcholů, které jsou sousední s vrcholem v. □ Okolí vrcholu v v grafu G je množina a budeme ji označovat Nq(v). JTj Definice 7.9 Okolí množiny vrcholů 5, kde S C V (G), je množina všech vrcholů, které jsou sousední s alespoň jedním vrcholem množiny S, a zároveň nepatří do množiny S. Množinu vrcholů, která je okolím množiny S, označujeme Nq(S). [yj Věta 7.2 Nechť G je bipartitní graf s partitami P a K. Potom graf G obsahuje párování M, které saturuje všechny vrcholy K právě tehdy, když \S\ < \Na(S)\ pro každou množinu S C K. —-■-—^-:- 0 Důkaz dané věty nalezneme v [4]. Nyní uvedeme nutnou a postačující podmínku existence úplného párování v obecných grafech. Autorem této věty je Tuttc. Používá se v ní pojem lichá komponenta. Komponentu grafu nazýváme lichou, pokud obsahuje lichý počet vrcholů. Tato věta byla dokázána v roce 1947. Kapitola 7 Párování a pokrytí grafu 53 [v~| Věta 7.3 Graf G má úplné párování právě tehdy, když počet lichých komponent grafu G — S je menší nebo roven počtu vrcholů množiny S pro každou množinu S C V (G). V D Důsledek 7.1 Každý pravidelný graf stupně 3 bez mostů má úplné párování. D Toto tvrzení dokázal Petersen v roce 1891. Párování, jak jsme dříve uvedli, dává do určitého vztahu vrcholy. Tady u bipartitních grafů je to ještě evidentnější. Často se používá u tzv. přiřazovacích problémů. Vrcholová množina bipartitních grafů je tvořena dvěma navzájem disjunktními množinami. Jedna množina může v reálné úloze představovat například lidi, druhá množina úkoly. I v rozvrzích na školách přiřazujeme předměty k vyučujícím. Hrany budou reprezentovat tak, že daný předmět by mohl vyučující učit. Pomocí nalezení úplného párování bychom přiřadili učiteli konkrétní předmět, který bude učit. V daném grafu může existovat více úplných párování, to znamená., že může existovat více řešení dané úlohy. Nemusí však existovat žádné. Řešení existuje, pokud všechny vrcholy budou saturované, to znamená, každý pedagog bude mít přiřazen předmět a u každého předmětu bude zřejmé, kdo ho vyučuje. Zdůrazněme, že takhle bychom přiřadili vyučujícímu pouze jediný předmět. Dalším příkladem aplikace může být nalezení tanečních párů ve třídě, která se účastní tanečních. Na tomto příkladu si ukážeme algoritmus pro nalezení úplného párování. D Důsledek 7.2 Každý pravidelný bipartitní graf s alespoň jednou hranou obsahuje úplné párování. D Důkaz daného důsledku nalezneme v [ 1]. Pokrytí úzce souvisí s pojmem párování. □ i Definice 7.10 Pokrytí grafu G je taková podmnožina U vrcholové množiny V(Gf), že každá hrana z hranové množiny E{G) je incidentní s alespoň jedním vrcholem množiny U. Pokrytí je tedy množina, vrcholů, narozdíl od párování, které je množinou hran. Pokrytí označujeme U. jT~| Definice 7.11 Pokrytí U je nejmenší, pokud neexistuje pokrytí U s menším počtem vrcholů. □ Kapitola 7 Párování a pokrytí grafu i Definice 7.12 Pokrytí U je minimální, pokud žádná jeho vlastní podmnožina již není pokrytím. _ •£31 Pro libovolné párování M a pokrytí U platí \M\ < \U\. Alespoň jeden z koncových vrcholů každé z hran párování M totiž musí patřit do pokrytí U, a proto je vrcholů v pokrytí U alespoň tolik, jako je hran v párování M. Věta 7.4 V bipartitním grafu je počet hran největšího párování roven počtu vrcholů nejmenšího pokrytí. Úlohy o párování můžeme rozdělit na tři typy. Úlohy prvního typu, kdy hledáme maximální párování, tedy takové, které obsahuje největší počet hran. U druhého typu jsou hrany ohodnoceny cenami (k hraně je přiřazeno číslo) a máme najít nejlevnější maximální párování ze všech, která jsou maximální. Posledním typem jsou úlohy, kdy máme opět hrany ohodnoceny cenami a máme najít nejdražší párování, tj. párování s největším součtem cen. [8], Zajímavé úlohy nalezneme v [3]. Je zde příklad týkající se Letecké bitvy o Anglii, kdy na straně Anglie bojovala řada pilotů jiných národností. Královské letectvo mělo letadla, která vyžadovala dva piloty. Někteří piloti spolu ovšem nemohli letět pro jazykové potíže nebo pro rozdílnost výcviku. Kolik letadel (tzn. dvojic pilotů) může za tohoto omezení vzlétnout najednou? Tento problém bylo možné řešit nalezením maximálního párování v grafu, jehož vrcholy odpovídají pilotům a jehož hrany spojují piloty, kteří mohou letět spolu. Je zde i příklad zahrádkářský. Představme si ovocnou zahradu, ve které je 2n stromků a jedna hromada hnoje. Naším úkolem je přivést půl kolečka hnoje ke každému stromku. Abychom šetřili časem, chceme vždy k některému stromku vézt plné kolečko, polovinu jeho obsahu složit a pokračovat s poloprázdným kolečkem k jinému stromku. Kromě času chceme šetřit i silami a chceme, aby např. součet drah vykonaných s plným kolečkem byl co nejmenší. Tuto úlohu lze převést na hledání nejlevnějšího úplného párování v úplném grafu o 2n vrcholech. Každý vrchol odpovídá jednomu stromku. Cena hrany spojující vrcholy t?i, v-2 bude úměrná námaze spojené s jízdou plného kolečka k bližšímu z obou stromků, s následující jízdou poloprázdného kolečka ke druhému z nich a s návratem prázdného kolečka k hromadě hnoje. Je zřejmé, že každý stromek, tedy vrchol, musí být zahrnut do přesně jedné jízdy, hrany odpovídající těmto jízdám musí tvořit úplné párování. Nyní si popíšeme algoritmus pro nalezení úplného párování, resp. algoritmus hledající nesát u-rované alternující cesty, na následujícím příkladu. Řešený příklad 7.1 Třída 2. A gymnázia se rozhodla, že páry v tanečních vytvoří v rámci své třídy. Třídu tvoří deset chlapců a deset dívek. Nesmíme však zapomenout, že i když se takhle dohodli, ne každá dívka či chlapec chce tančit s každým chlapcem, či dívkou. Každý má své představy o svém tanečním partnerovi. Dané podmínky mohou vypadat takto. Někdo je do někoho zamilovaný, někdo je na někoho částečně naštvaný, někdo dobře tančí, někomu to je jedno. Úloha zní: Bude možno sestavit ■ Kapitola 7 Párování a pokrytí grafu 55 taneční páry tak, aby každý měl tanečního partnera dle svých představ? Nejprve si vytvoříme grafovou interpretaci. Bude se jednat o bipartitní graf, jednu partitu budou tvořit chlapci a druhou partitu dívky. Vytvořit taneční páry znamená vytvořit 10 dvojic. To, že spolu chlapec a dívka budou moci tančit, vyjádříme tak, že v daném grafu bude existovat hrana mezi vrcholem, který představuje chlapce a vrcholem, který představuje dívku. Úloha tedy zní najít 10 hran, odpovídající 10 párům tak, aby žádná hrana neměla společný koncový vrchol, tedy budeme hledat úplné párování. Graf, který odpovídá dané třídě a podmínkám, je na obrázku 7.2. Tomáš Dana Roheit - r Jana - j Obrázek 7.2: Příklad taneční Nalezneme libovolné párování. Hrany, které budou patřit do zvolené množiny párování, jsme označili červeně. Nalezené párování vidíme na obrázku 7.3. V grafu je v daném kroku 6 nesaturo-vaných vrcholů, a to Bedřich - b, David - d, Jirka - j, Ivana - i, Sylvie - s, Hanka - h. Najdeme libovolnou nesaturovanou alternující cestu, například: Ivana i, Šimon - š. Martina -m, Jirka - j. V dalším se už omezíme pouze na označení vrcholů daného grafu počátečními písmeny daných jmen. Nyní zaměníme hrany na této nesaturované cestě, myšleno tak, že přehodíme hrany, které patří a nepatří do párování, tzn., hranu i. š přidáme, š, m odebereme, m,j přidáme. Dostaneme tedy párování, které má o jednu hranu více než předchozí nalezené párování. To znamená, že v grafu nyní nemáme 6 nesaturovaných vrcholů, ale už 4. Situaci vidíme na obrázku 7.4. Opět zvolíme libovolnou nesaturovanou alternující cestu, například s, k, d, b. Zaměníme hranina nesaturované alternující cestě, které do párování patří a nepatří: hranu sk přidáme, kd odebereme a db přidáme. Dostaneme nové párování, které má o jednu hranu více. Po záměně stran patřících do párování je stav na obrázku 7.5. Máme 2 nesaturované vrcholy: d, h. Kapitola 7 Párování a pokrytí grafu 56 Najdeme nesáturovanou alternující cestu, například h, h, e, v, b, r, j, d. Zaměníme hrany na cestě, které do párování patří a nepatří: hranu hh přidáme, he odebereme, ev přidáme, vb odebereme, br přidáme, r j odebereme a jd přidáme. Dostaneme nové párování, které má o jednu hranu více. Nyní všechny vrcholy už jsou saturované a našli jsme hledané řešení, tedy našli jsme úplné párování grafu. Řešení dané úlohy je na obrázku 7.6. Musíme si uvědomit, že úplné párování nemusí existovat. V daném algoritmu bychom nenašli žádnou nesaturovanou alternující cestu. Existuje řada složitějších a obecnějších algoritmů pro úlohy tohoto typu. 'A m Neřešené příklady 1. Kolo Wn+i je graf, který vznikne z cyklu Cn s vrcholy V\,v2, ■ ■. ,Vn přidáním vrcholu Vq a všech hran vovi, í>o'«2, ■ • •, vovn. Určete, pro které hodnoty n má Wn+\ úplné párování. 2. Které úplné tripartitní grafy mají úplné párování? 3. Kolik různých úplných párování mají graf Kn a Kn.n? 4. Dokažte, že strom má nejvýše jedno úplné párování. 5. Pro každé k > 1 najděte příklad fe-pravidelného grafu, nemajícího úplné párování. 6. Dokažte, že platí: Nechť G je bipartitní graf s partitami P a K. Potom graf G obsahuje úplné párování právě tehdy, když IS*! < |Ag(5')| pro každou množinu S C P u K. Kapitola 7 Párování a pokrytí grafu 57 Obrázek 7.4: Příklad taneční - krok 2 7. Dokažte speciální případ Tutteovy věty: Strom T má úplné párování právě tehdy, když počet lichých komponent grafu G — v je roven 1 pro každý vrchol v G V (T). 8. Využijte Tutteovy věty k nalezení charakterizace maximálních grafů bez úplného párování. 9. Nechť má souvislý graf G 4 vrcholy lichého stupně. Dokažte, že pak existují nejméně dvě různá pokrytí. - Kapitola 7 Párování a pokrytí grafu 58 Tomáš - t Karel k Dana d Roberl Jana j Obrázek 7.5: Příklad taneční - krok 3 Tomáš - t Dana - e/ Robert Obrázek 7.6: Příklad taneční hledané řešení Hranové a vrcholové barvení grafu 8.1 Hranové barvení grafu V této kapitole definujeme hranové barvení grafu a ukážeme, jak hranové barvení využijeme při rozlosovaní turnaje, tedy určíme, kdo s kým a kdy bude hrát. Dennice 8.1 Hranové fc-barvení grafu G je zobrazení hranové množiny E(G) do množiny {1,2,..., k}, kterou nazýváme množina barev. _ ■% i Vidíme, že každé hraně je přiřazena jedna z k možných barev. Dennice 8.2 Hranové barvení nazýváme dobrým, jestliže žádné dvě sousední hrany nejsou obarveny stejnou barvou. _ —^—:—r~~~~~-:—^— □ Hranové barvení úzce souvisí s párováním. Můžeme definovat hranové barvení pomocí rozkladů množiny hran E(G). Definice 8.3 Rozkladem hranové množiny E(G) rozumíme nalezení systému podmnožin E\, E2, ■ ■•Ek množiny hran E(G) takových, že E] U E2 U ... U Ek = E (G) a E{ n Ej = pro i ^ j. -7—~-7-^-□ Potom hranové /c-barvení můžeme nadefinovat pomocí rozkladu následující definicí. 59 Kapitola 8 Hranové a vrcholové barvení grafu 60 Definice 8.4 Hranovým fe-barvením nazýváme rozklad množiny hran E(G) na množiny E\, Ez, ...Ek-Dobré barvení je pak takové, ve kterém každá množina E{, 1 < i < k tvoří párování. [4] □ i í? Definice 8.5 Graf nazýváme hranově fc-obarvitclný. jestliže existuje jeho dobré hranové barvení k barvami._ —-:—;-D Je zřejmé, že je-li fc-obarvitelný, pak je i Z-obarvitelný pro každé l > k. Definice 8.6 Chromatický index x{G) grafu G je nejmenší číslo k, pro které je graf G hranově fc-obarvitelnv. -■-- □ i Definice 8.7 Graf se nazývá hranově fc-chromatický, je-li x (G) = k, ——;—;-□ Na dobré hranové obarvení vždy potřebujeme alespoň A(G) barev, protože je zřejmé, že při dobrém hranovém barvení grafu musí být všechny hrany, které jsou incidentní s nějakým vrcholem, obarveny jinou barvou, a nejvíce barev je zapotřebí u vrcholu, který je ncjvětšího stupně. To bychom měli určenu dolní mez chromatického indexu. V roce 1964 Vizin dokázal, že budeme potřebovat nejvíce A(G) + 1 barev. [y~| Věta 8.1 Pro libovolný graf G platí A(G) < \{G) < A(G) + 1. V i | Definice 8.8 Hranové číslo nezávislosti grafu G je největší počet navzájem nezávislých (nesousedních) hran. -—-■- □ Hranové číslo nezávislosti budeme označovat (G). Můžeme napsat, že je to převlečená velikost nejvčtšího párování. Platí následující věta, kterou uvedeme bez důkazu, ten je možno najít v [4]. [v] Věta 8.2 Jestliže pro počet hran grafu G platí \E(G)\ > A(G) • @'(G), potom x'(G) = A(G) + 1. _ V Kapitola 8 Hranové a vrcholové barvení grafu Gl Pro bipartitní grafy platí věta, která říká, že chromatický index je roven největšímu stupni bipartitního grafu. V Věta 8.3 Pro každý bipartitní graf G platí x (C) — A (G). 0 Jednou ze zajímavých aplikací hranového barvení naleznete v [4], kde je použito k losování sportovních soutěží. Přestavme si, že máme soutěž - turnaj, kde se hraje systémem každý s každým, kterého se účastní celkem 6 mužstev. Budeme chtít rozdělit zápasy na pět skupin zápasů, kdy každou skupinu budou tvořit tři zápasy. Skupina zápasu může představovat například na dané soutěži půlden. To by v praxi znamenalo, že daný turnaj se bude hrát 2,5 dne. Kdybychom špatně začali určovat zápasy ve skupinách, tak mohlo by se stát, že nemůžeme určit, kdo bude hrát v poslední skupině zápasů. Jedno mužstvo by například v jednom okamžiku mělo hrát více utkání. Musíme si uvědomit, že mužstev v turnaji je 6 a situace by byla mnohem složitější, kdyby mužstev bylo daleko více. Máme tedy za úkol sestavit mužstva do 5 souborů (skupin) po třech zápasech (dvojic mužstev, která budou spolu hrát). Nebudeme hledat nic jiného než dobré hranové barvení grafu K$ a počet barev bude 5. Hrany obarvené stejnou barvou budou přestavovat zápasy jedné skupiny, to znamená, že stejnou barvou budou obarveny celkem tři hrany. Takže 6. mužstvo budeme považovat za střed kružnice a ostatní vrcholy umístíme na kružnici v pravidelných vzdálenostech. Budou tvořit vrcholy pravidelného pětiúhelníku. První barvou potom zabarvíme hranu 1-6 a všechny hrany, které jsou na ni kolmé. Samozřejmě, žc tyto hrany jsou nezávislé a budeme potřebovat jen jednu barvu. Druhou barvou obarvíme hranu 2-6 a všechny hrany, které jsou na ni kolmé, a stejně budeme pokračovat dál. Řešení dané úlohy můžeme vidět na obrázku 8.1. Obrázek 8.1: Losování sportovní soutěže Vidíme, že danou úlohu jsme řešili pro 6 vrcholů. Obdobně by se daná úloha řešila pro obecně Kapitola 8 Hranové a vrcholové barvení grafu 62 sudý počet vrcholů. Co když ale máme počet vrcholů lichý? Potom použijeme stejný postup s tím. že do středu kružnice umístíme navíc vrchol (imaginární), kde zápasy s tímto vrcholem nebudeme do řešení zahrnovat. Jinými slovy upravíme graf tak, aby počet jeho vrcholů byl sudý. 8.2 Vrcholové barvení grafu V této kapitole nebudeme barvit hrany, ale vrcholy. Příkladem použití vrcholového barvení může být tak zvaný skladovací problém. Skladovací problém můžeme formulovat takto. Máme různé druhy zboží, z nich některé nemohou být skladovány dohromady. Pro minimalizaci nákladů budeme chtít stanovit nejmenší počet oddělených skladovacích prostor, které budou zapotřebí k uskladnění všech druhů zboží při dodržení podmínky, že bude skladováno dohromady jen to zboží, u kterého je to v pořádku. V interpretaci v teorii grafů bude každé zboží reprezentováno vrcholem, a to, že zboží nemůže být ve stejném skladovacím prostoru, reprezentujeme tak, že dané zboží (vrcholy) propojíme hranou. Skladovací problém můžeme přeformulovat i na jinou úlohu a to na úlohu týkající se svatby. Máme svatební hostinu, kde svatebčané budou sedět u více stolů. Víme, že někteří nemohou sedět u jednoho stolu, třeba proto, že se dříve pohádali, že mají jiné názory na politiku apod. A ptáme se, kolik stolů nejméně budeme potřebovat, abychom eliminovali tuto skutečnost. Definice 8.9 Vrcholové A;-barvení (fc-barvení) grafu G je zobrazení množiny V(G) do množiny {1,2,..., k}, kterou nazýváme množinou barev. -;- □ Ke každému vrcholu je tedy přiřazena jedna z k možných barev. Definice 8.10 Vrcholové barvení nazýváme dobrým, jestliže žádné dva sousední vrcholy nejsou obarveny stejnou Vrcholové barvení můžeme také definovat pomocí rozkladu vrcholové množiny V(G). Definice 8.11 Rozkladem vrcholové množiny V(G) rozumíme nalezení systému podmnožin Ví, V%, ■ ■ - Vk množiny hran V{G) takových, že Vi U V2 U ... U Vk = V(G) a V n Vs = 0 pro i Ý j- -'—~-;—,——~ h Potom vrcholové fc-barvení můžeme nadefinovat pomocí rozkladu následující definicí. Kapitola 8 Hranové a vrcholové barvení grafu 63 Definice 8.12 Vrcholovým fc-barvcním nazýváme rozklad množiny hran V(G) na množiny Ví, V2, ■ ■ ■ Vfc. □ Dobré barvení je takové, ve kterém je každá množina V* nezávislá, tedy žádné dva vrcholy Ví, kde 1 < i < k, nejsou spojeny hranou. rJr Definice 8.13 Graf je vrcholově fc-obarvitelný nebo prostě ft-obarvitelný, jestliže existuje jeho dobré vrcholové barvení k barvami. Pokud je graf G fc-obarvitelný. potom je i /-obarvitelný pro každé l > k. |T~1 Definice 8.14 Chromatické číslo x{G) grafu G je nejmenší číslo k, pro které je graf G /e-obarvitelný. □ fi~ Definice 8.15 Graf se nazývá fc-chromatický, je-li y(G) = k. □ U chromatického indexu jsme určili dolní mez A < x (G). Na rozdíl od chromatického indexu, u chromatického čísla taková netriviální mez neexistuje. Jak to vypadá pro horní mez? Horní mez je pro chromatické číslo stejná jako pro chromatický index, tzn. x(@) < A(G) + 1. A navíc můžeme charakterizovat grafy, pro které platí tato horní mez, jsou to cykly liché délky a úplné grafy. pV~| Věta 8.4 Nechť G = C2m+Í nebo G = Kn, pak x(G) = A(G) + 1. V Důkaz: Nejdříve ukážeme, že každý lichý cyklus je 3-chromatický. Nechť vrcholová množina je V(C2m+i) = {^1,^2) • • ■ j V2m+i] a wchol V\ je obarven modře, vrchol v-2 bude obarven jinou barvou, např. červenou, vrchol V3 může být obarven opět modrou atd. Vrchol V2m+l nemůžeme obarvit ani modrou ani červenou. Musíme použít třetí barvu, protože daný vrchol je sousední s vrcholem, který je obarven barvou červenou, ale také s vrcholem, který je obarven barvou modrou. Z toho vyplývá, že chromatické číslo je rovno 3 a platí x(C2m+l) = 3 = Á(C2m+i). Na obrázku 8.2 vidíme případ pro pět vrcholů. □ Jak to vypadá u úplného grafu Knl U grafu Kn jsou každé dva vrcholy sousední, proto musí být vrcholy zabarveny n různými barvami a platí tedy x(Ä"„) = n = \{Kn) + 1. □ Brooksova věta nám říká, že každý graf různý od lichého cyklu nebo úplného grafu je dobře obarvitelný A(G) barvami. Kapitola 8 Hranové a vrcholové barvení grafu 64 Obrázek 8.2: Cyklus C2m+i fy] Věta 8.5 Nechť G je graf různý od úplného grafu a nechť A(G) > 3, potom x(^) < A(G). 0 Uvedeme jen myšlenku důkazu. Důkaz dané věty je možné najít v [4]. Předpokládáme, že tvrzení není pravdivé, tedy že existují grafy různé od lichých cyklů nebo úplných grafů, pro které je třeba více než A(G) barev. Označíme množinu všech grafů s touto nevyhovující vlastností. Tato množina jistě obsahuje graf, který má ze všech grafů dané množiny nejmenší počet vrcholů, protože je podmnožinou množiny všech grafů, a ta má nejmenší prvek, totiž graf K\. Přitom takových nejmenších grafů (vzhledem k počtu vrcholů) může být více než jeden, avšak všechny budou mít stejný počet vrcholů. Vybereme z těchto nejmenších grafů jeden a označíme jej G. Cílem je ukázat, že z jeho existence by vyplýval spor. Tento spor bude založen právě na. minimalitě počtu vrcholů grafu G vzhledem k vlastnosti nemožnosti zabarvit graf G dobře A(G) barvami. Vynecháním vrcholu v stupně A(G) dostaneme graf H s |V(G)| — 1 vrcholy. Ten už je dobře obarvitelný A(G) barvami, protože G byl nejmenší graf, pro který to neplatilo. Ukážeme, že můžeme barvy v H navzájem mezi sebou vyměnit tak, že na zabarvení vrcholů, které byly v G sousední s v, stačí A (G) — 1 barev. Nyní můžeme zbývající barvou zabarvit vrchol v. Tak dostaneme A (G)-barvení grafu G, což je spor s předpokladem, že G není A(G)-chromatický. □ D Důsledek 8.1 Pro každý graf G platí y(G) < A(G) + 1. D [v~| Věta 8.6 Každý strom o nejméně jedné hraně má chromatické číslo 2. V Kapitola 8 Hranové a vrcholové barvení grafu 65 Jak to bude vypadat s chromatickým číslem u bipartitních grafu? Chromatické číslo bude rovno 2, protože množinu vrcholů rozložíme obarvením na dvě podmnožiny, kde každá hrana má jeden krajní vrchol v jedné a druhý vrchol ve druhé z těchto podmmnožin. Dané množiny jsou totožné s partitami bipartitního grafu. Nyní uvedeme další meze chromatického čísla. Věta 8.7 Pro každý graf G platí x(G) < max kde maximum bereme přes všechny indukované podgrafy H grafu G. _ —-;-—-- 0 Vidíme, že tato věta vyjadřuje závislost chromatického čísla grafu na minimálním stupni indukovaných podgrafů grafu G. Další věta nám vyjadřuje mez pomocí počtu vrcholů a hran daného grafu. | V | Věta 8.8 Nechť G má p vrcholu a q hran, potom platí x(C) < 1 + \/2q(p — l)/p. —:-~~-;-0 Další větu uvedeme také bez důkazu. Ten je možno najít [4]. Věta 8.9 Nechť m(G) označuje délku nejdelší cesty v grafu G. Potom x[G) < Tn(G) + 1. - 0 Na závěr této kapitoly uvedeme několik příkladů aplikací vrcholového barvení. Skladovací problém jsme popsali v úvodu této podkapitoly. Daný problém můžeme modifikovat na počty místností, skříní, polic nebo počet aut při přepravě daného zboží, látek. Další aplikací je plánování procesů, kdy některé procesy nemohou proběhnout současně, například proto, že probíhají na stejných zařízeních. Potom úlohy spočívají ve stanovení, kolik potřebujeme časových jednotek k tomu, aby proběhly všechny procesy. Nebo úlohy typu, kolik daných procesů může probíhat současně. Můžeme řešit i problémy týkající se rozvrhu, kolik hodin je zapotřebí, když mám k sobě přiřazeny předměty, studijní skupiny a učitele, kdy chceme splnit podmínky tohoto přiřazení. Je zde zakomponováno, že učitel najednou nemůže učit dvě skupiny atd. Kapitola 8 Hranové a vrcholové barvení grafu 66 A Řešený příklad 8.1 [2] Studenti jedné zahraniční školy mají zkoušky na konci roku z každého kurzu, který si zapsali. Některé zkoušky mohou probíhat paralelně. Úkolem tedy je vypsat co nejméně termínů zkoušek pro všechny kurzy. Samozřejmě nemohou probíhat paralelně zkoušky z takových kurzů, které má současně zapsány jeden student. Abychom našli takové termíny, uspořádáme kurzy do vrcholů grafu a spojíme hranou takové kurzy, jejichž zkoušky nemohou probíhat v jednom termínu. Minimální počet vypsaných paralelních termínů pak odpovídá chromatickému číslu tohoto grafu. A A | Řešený příklad 8.2 [2] Společnost vyrábí n chemikálií C\,... ,Cn. Některé dvojice chemikálií spolu mohou reagovat a způsobit tak explozi. Společnost vybudovala nový sklad chemikálií a potřebuje ho rozdělit do jednotlivých navzájem nepropustných částí. Vzhledem k tomu, že budování takovýchto místností je velmi nákladné, je zapotřebí vytvořit jich co nejméně. Úkolem tedy je určit, kolik nejméně místností musí sklad obsahovat, aby nemohlo dojít k explozi. Problém je opět možné vyřešit pomocí grafu, jehož vrcholy tvoří jednotlivé chemikálie. Dva vrcholy jsou spojeny hranou, pokud spolu odpovídající chemikálie mohou reagovat a způsobit výbuch. Minimální počet místností pak opět odpovídá chromatickému číslu tohoto grafu. A A Řešený příklad 8.3 Dokažte, že každý strom o nejméně 1 hraně má chromatické číslo 2. Důkaz provedeme matematickou indkukcí vzhledem k počtu hran n. Pro n — 1 dostáváme strom o jedné hraně a dvou vrcholech, který má chromatické číslo 2. Vyslovíme indukční předpoklad. Nechť libovolný strom o n hranách má chromatické číslo 2. Mějme strom o n + 1 hranách. Výpustíme-li z tohoto grafu vrchol stupně 1 (takový vrchol existuje - dříve dokázáno), dostaneme strom o n hranách a ten obarvíme 2 barvami. Vypuštěný vrchol a samozřejmě i hranu opět přidáme a obarvíme ho jinou barvou než je obarven jeho jediný soused. Opět jsme vystačili se 2 barvami. I když jsme vypouštěli vrchol a tak jsme měnili počet hran, neporušili jsme fakt, že jsme vedli důkaz vzhledem k počtu hran. A -5- m Neřešené příklady 1. Dokažte, že X iKn,m) = A(ifn>m). 2. Ukažte, že v souvislém bipartitním grafu G vždy existuje hranové ó~(G)-barvení (ne nutně dobré) takové, že každý vrchol je incidentní s hranami všech 5(G) barev. 3. Dokažte, že x {Kin-\) — X (^2n) = 2n — 1. Kapitola 8 Hranové a vrcholové barvení grafu 67 4. Ukažte, že v každém pravidelném grafu G s lichým počtem vrcholů a alespoň jednou hranou jeX'(G) = A(G) + l. 5. Určete x(W„). 6. Určete chromatické číslo daných grafů na obrázku 8.3. O č> 0 0 ô ô Obrázek 8.3: Určení chromatického čísla 7. Ukažte, že jestliže libovolné dva liché cykly grafu G mají společný vrchol, potom x(G) < 5. 8. Najděte chromatické číslo a chromatický index kompletního grafu a sudobipartitního úplného grafu. 9. Jaké chromatické číslo bude mít graf s jednotkovým průměrem? 10. Jaký maximální počet hran může obsahovat obyčejný graf o 4 vrcholech (resp. 5, 6, 7 vrcholech), má-li být jeho chromatické číslo rovno 3? ... Kapitola _ Pianami a neplanární grafy 9.1 Planární grafy Podívejme se na obrázek 9.1. Vidíme, že na něm jsou diagramy stejného grafu, ale na obrázku vpravo je nakreslen tak, aby se jeho hrany neprotínaly. Grafy, které lze nakreslit tak, aby se jejich hrany neprotínaly, hrají důležitou roli v teorii grafů a v jejích aplikacích. Obrázek 9.1: Planární grafy | i i Definice 9.1 Rovinný graf je graf, jehož hrany se v diagramu grafu navzájem neprotínají. Definice 9.2 Graf, který lze nakreslit tak, že se jeho hrany navzájem neprotínají (to znamená, žc existuje rovinný diagram), se nazývá planární. —-;——-;—--□ Samozřejmě, že každý rovinný graf je grafem planárním. Vrátímc-li se k danému obrázku 9.1, tak oba diagramy patří grafům, které jsou planární. Vlevo je graf planární, nikoliv rovinný. Vpravo je graf rovinný a samozřejmě tedy planární. Rovinné nakreslení je výhodné pro znázornění grafu, například při nerovinném nakreslení by se průsečíky mohly plést s vrcholy. Při aplikaci například při návrhu jednovrstevných integrovaných 68 Kapitola 9 Planární a neplanární grafy 69 obvodu je křížení částí obvodu přímo nežádoucí. [7~ Definice 9.3 Neplanární graf je graf takový, že při jeho libovolném nakreslení se alespoň dvě hrany navzájem protínají. _ -;-n To znamená, že k takovému grafu nemůžeme najít diagram, který představuje jeho rovinný graf. Příkladem nejmenšího neplanárního grafu je graf K$ (obrázek 9.2). Obrázek 9.2: K5 Jeden ze způsobů, jak dokázat, že graf A'5 je neplanární, je pomocí Jordanovských křivek. Uvedeme tedy potřebné definice. I 1 Definice 9.4 Uzavřená Jordanovská křivka (Jordanovská křivka) je křivka, která má počátek totožný s koncem a neprotíná sebe sama. - □ Příkladem takové křivky může být kružnice nebo elipsa. Každá Jordanovská křivka J dělí rovinu na dvě části: vnitřek (interiér), který budeme označovat intJ, a vnějšek (exteriér), který budeme označovat extJ. Jejich uzávěry, tj. uzavřené množiny obsahující i křivku ./, označujeme IntJ a ExtJ. Platí IntJ n ExtJ — J. ["v"] Věta 9.1 Nechť J je Jordanovská křivka v rovině a nechť a a b jsou body roviny takové, že a £ intJ a b E extJ. potom každá křivka, spojující v rovině body a a b, protíná J alespoň v jednom bodě._ ---- 0 Kapitola 9 Planární a neplanární grafy 70 IV | Věta 9.2 Graf iv,5 není planární. _ -0 Důkaz: Vrcholová množina grafu K5 je V{K§) = {v\, t'2, v$, V4, U5}. Protože v úplném grafu jsou všechny vrcholy navzájem sousední. K*, obsahuje cyklus vi,V2,vs,Vi. Budeme předpokládat, že dvě sousední hrany tvoří spolu jedinou spojitou křivku. Hrany cyklu tvoří Jordanovskou křivku, kterou označíme J. (obrázek 9.3 a)) ('i l'l t'2 V1 V 2 a) b) Obrázek 9.3: Důkaz neplanárnosti grafu K5 Vrchol v,-i potom leží buď v intJ nebo v extJ. (f4 e intJ nebo 1:4 e extJ). Uvažujme případ, kdy vrchol ľ4 e intJ. Hrany V4V1, v4v2, V4V3 dělí intJ na tři části IntJ], IntJ2, IntJz. (obrázek 9.3 b)) Předpokládejme, že vrchol v5 nyní leží v extJ. (obrázek 9.4 a)) Potom ale hrana v5v4 musí podle předchozí věty protínat křivku J a tudíž A'5 není planární. 1'3 Ca a) b) Obrázek 9.4: Důkaz neplanárnosti grafu K5 Leží-li vrchol v5 v některé z oblastí míJi; i = 1,2,3, např. intJu potom hrana v5v3 protíná křivku Ji, což dokazuje naši větu. (obrázek 9.4 b)) Podobně bychom postupovali i pro ostatní oblasti. Stejně i v případě, kdy na začátku vrchol V4 € extJ. (obrázek 9.5) □ Kapitola 9 Planární a neplanární grafy 71 ''i Obrázek 9.5: Důkaz neplanárnosti grafu Ä'5 Věta 9.3 Graf K3 3 není planární. -1- 0 Graf, který obsahuje nebo není planární. Věta 9.4 Graf G je planární právě tehdy, když neobsahuje jako podgraf žádnou subdivizi grafu K5 nebo Ä'3,3. V_ Jinými slovy, kdybychom chtěli nakreslit diagram určitě neplanárního grafu, nakreslíme jeden z těchto grafů a poté třeba další vrcholy a hrany. I 1 \ Definice 9.5 Oblast rovinného grafu G je část roviny, jejíž libovolné dva body můžeme spojit nějakou křivkou, která neprotíná žádnou hranu grafu G. ----;-□ intJi, intJ-2, intJ-i nazýváme vnitřními oblastmi a extJ vnější oblastí, (obrázek 9.6) Obrázek 9.6: Oblasti Kapitola 9 Planární a neplanární grafy 72 Plocha vnitřních oblastí je vždy konečná. Plocha vnější oblasti je v rovině vždy nekonečná. Základní kvantitativní vztah pro rovinné grafy vyjadřuje Eulerúv vzorec. Je to také nejstarší vztah tohoto typu, Euler ho znal v roce 1752. Eulerův vzorec dává do vztahu počet vrcholil, hran a oblastí souvislého rovinného grafu. V Věta 9.5 Pro libovolný souvislý rovinný graf G platí v(G) — h(G) + o(G) = 2. V Důkaz: Důkaz provedeme indukcí vzhledem k počtu oblastí grafu G. Pro počet oblastí o(G) = 1 platí, že jediná oblast je vnější oblast, která je nekonečně velká. Graf G tedy nemá žádnou vnitřní oblast, proto neobsahuje cyklus, daný graf je strom. Platí h(G) = v(G) - 1 a v(G) - h(G) + o{G) = v(G) - (v(G) - 1) + 1 = 2. Budeme předpokládat, že dokazovaný vztah platí pro všechny grafy s o{G) < k oblastmi. Ukážeme, že z toho plyne platnost tohoto vztahu pro libovolný graf s k + 1 oblastmi. Nechť tedy graf G má k + 1 > 2 oblastí. Potom v něm určitě existuje hrana, oddělující dvě oblasti. Označme tuto hranu e a zkoumejme graf G — e. Tento graf má o jednu oblast méně, než graf G, protože dvě oblasti grafu G oddělené hranou e, v grafu G — e splynou v jedinou. o(G - e) = o(G) - l = k Podle indukčního předpokladu v grafu G — e platí Eulerův vzorec. Je tedy v(G - e) - h(G - e) + o{G - e) = 2 Protože graf G — e vznikl z G vynecháním jediné hrany, má stejný počet vrcholů. v(G) = v(G - e) h(G) = h(G - e) + 1 o(G) =o(G-e) + l. Dosadíme v(G)~h{G) + o{G) =v{G-c)-(h(G-e) + l) + (o{G-e) + l) = v(G-e)-h(G-e) + o(G-e) = 2. Důkaz je hotov. □ Pokud vyjádříme z Eulerova vzorce počet oblastí o(G) = 2 — v(G — e) + h(G — e), zjišťujeme následující: 2 je konstanta, v(G) a ani h(G) se při různém nakreslení grafu nemění, je konstantní, z toho plyne, že i počet oblastí musí být pro různé nakreslení stejný, což nám vlastně říká následující důsledek Eulerova vzorce. D Důsledek 9.1 Všechna nakreslení planárního grafu v rovině mají stejný počet oblastí. _ Kapitola 9 Planární a neplanární grafy 73 D Důsledek 9.2 Pro každý planární graf G s více než dvěma vrcholy platí h(G) < 3v(G) — 6. D Důkaz: Nechť G je souvislý planární graf. Hranicí každé oblasti je cyklus délky alespoň 3, proto sečteme-li hrany ležící na hranicích oblastí, přes všechny oblasti, dostaneme číslo alespoň Zo(G). Každá hrana, ležící na hranici nějaké oblasti, je však v tomto součtu započítána dvakrát - jednou pro každou z obou oblastí, které od sebe odděluje, proto pro počet hran v grafu G platí h{G) > 3o(G)/2. Upravíme daný vztah na tvar 2h(G)/'i > o(G). Platí Eulerův vzorce v(G) - h(G) + o(G) = 2. Nyní ke každé straně předchozí nerovnice přičteme a odečteme v(G) a h(G). v(G) - h{G) + 2h(G)/3 > v(G) - h(G) + o(G) Na pravé straně nerovnice jsme získali levou stranu rovnice Eulerova vzorce a můžeme tedy místo tohoto trojčlenu psát 2. v[G) - h(G)/'i > 2 Nyní už jen danou nerovnici vynásobíme číslem 3 a dostáváme vztah, který jsme měli dokázat. h(G) > 3v(G) - 6 □ D Důsledek 9.3 Pro každý planární graf G platí ó~(G) < 5. D Důkaz: Pro grafy s jedním nebo dvěma vrcholy je zřejmé, že tvrzení platí. Předpokládejme, že v(G) > 3. Kdyby každý vrchol byl nejmenšího stupně, tak určitě dostaneme minimum pro součet všech stupňů v daném grafu a platí níže uvedená nerovnice. Kromě toho platí věta o součtu stupňů všech vrcholů v daném grafu. S(G)v(G) 3v(G) — 6. kde danou nerovnici vynásobíme 2, abychom získali na levé straně nerovnice výraz 2h(G). 2h{G) > 6v(G) - 12 Jestliže platí Ô(G)v(G) < 2h(G) a také 2h(G) > 6v(G) - 12, potom můžeme psát: 5{G)v{G) < 6v(G) - 12. Vydělíme danou nerovnici v(G) (můžeme, protože v(G) je nenulové, triviální graf obsahuje jeden vrchol). 6{G) < 6 - 12/v(G) Výraz na pravé straně nerovnice nabývá nejlepší meze pro v(G) = 12, proto platí: S(G) < 5. □ Věta 9.6 Pro libovolný rovinný graf G s lu(G) komponentami platí v(G) — h(G) + o(G) = 1 + uj(G). _ —'-;-0 Kde se například Eulerňv vzorec: používá? Popíšeme si příklad využití v počítačové grafice. V systémech CAD si můžeme vymodelovat, popsat takové objekty, které ve skutečném světě nelze vyrobit, tyto objekty nazýváme nonmanifoldy. (Vyrobitelné = manifoldy). Co to znamená „nelze vyrobit'"? Dokážeme si představit, že přímka je nekonečně tenká nebo že se dva objekty dotýkají v jednom bodě. Ve skutečném světě však nejsme schopni vyrobit nekonečně tenké vlákno, stejně tak nedokážeme spojit dvě tělesa ideálně bodovým svarem. Manifold z praktického hlediska je těleso, jehož každá hrana inciduje právě se dvěma plochami a jehož hrany neprotínají jiné plochy. Obdobně platí, že vrchol nesmí spojovat dvě části tělesa. Velká třída prakticky používaných těles se nazývá mnohostěny. Mnohostěn je těleso, které je ohraničeno množinou mnohoúhelníkových stěn, každou hranu sdílí vždy sudý počet stěn a splňuje další podmínky. Jednoduchý mnohostěn je těleso, které lze volnou plastickou deformací převést na kouli, je to těleso bez děr. Tím se dostáváme k danému vzorci. Hraniční reprezentace jednoduchého mnohostěnu splňuje Eulerúv vzorec, přičemž udává vztah mezi počtem vrcholů v(G), hran h(G) a stěn o{G) (počet oblastí) a platí: v(G) — h(G) + o(G) = 2. Platnost Eulerovy rovnosti sama o sobě neprokazuje, že jistá množina vrcholů, stěn a hran tvoří jednoduchý mnohostěn, který je hranicí uzavřeného objemu. Navíc musí platit, že každá hrana propojuje dva vrcholy, a stěny a hrany se nesmějí protínat. Pro manifoldy, které mají otvory, platí zobecněná Eulerova rovnost, kde ještě musíme brát v úvahu počet vnitřních smyček hran r, počet oblastí neboli samostatných komponent tělesa c a počet otvorů procházejících tělesem d. Vnitřní smyčky vymezují otvory ve stěnách, nikoliv otvory v tělese. Daný vztah potom má tvar: o + v = h + 2(c -d) + r. Kapitola 9 Planární a neplanární grafy 75 V [il] se můžeme dočíst o aplikaci Eulerova vzorce pro důkaz neexistence dalších pravidelných mnohostěnů než jsou: pravidelný čtyřstěn, krychle, pravidelný osmistěn, dvanáctistěn a dvacetistěn, tzv. platónská tělesa. Jedním ze známých problémů v teorii grafů je problém čtyř barev. Tento problém zůstával dlouhou dobu nevyřešen. První zmínka o tomto problému je v roce 1852 a řešení, jak jsme v úvodu tohoto skripta napsali, pochází z roku 1976 a je spojeno s jmény Appel a Haken. Původní formulace problému čtyř barev zní: Jaký je nejmenší počet barev, kterými je možno zabarvit libovolnou geografickou mapu tak, aby žádné dva státy mající společnou hranici (ve více než k konečném počtu izolovaných bodů - případy států, hraničících v jednom bodě, můžeme skutečně na světě nalézt - některé státy USA) nebyly zabarveny stejnou barvou? Takové mapy bývají označovány často za politické mapy, kde sousední státy jsou obarveny různou barvou. V roce 1890 Heawod dokázal, že 5 barev bude stačit, ale dva pánové Appel a Haken dokázali, že skutečně postačují 4 barvy. Pro důkaz této věty byl použit počítač. Formulace daného problému do teorie grafů je: najděte barvení oblastí rovinného grafu tak, aby žádné dvě oblasti, mající společnou hranu, neměly stejnou barvu. My daný problém můžeme přeformulovat takto: Jaké je největší chromatické číslo rovinného grafu? Další věta nám dává odpověď a nazývá se věta o čtyřech barvách. Věta 9.7 Nechť G je planární graf, potom x(G) < 4. _ —:-—~—:-0 Co platí pro chromatický index planárních grafů, nám říká další věta. Věta 9.8 Je-li G planární graf a A(G) > 8. potom je x (G) = A(G). _ -:—-~~~~~~~~— 0 Pro rovinné nakreslení a rovinné grafy lze formulovat tyto základní typy úloh [3]: 1. Zjistit, zda daný graf je rovinný. 2. Je-li graf rovinný, najít jeho rovinné nakreslení. 3. Pro daný graf najít nakreslení s co nejmenším počtem křížení stran. 4. Rozložit daný graf na co nejmenší počet hranově disjunktních rovinných faktorů. Takové úlohy hrají důležitou roli například v elektrotechnice při návrhu tištěných spojů a při návrhu integrovaných obvodů. Kapitola 9 Planární a neplanární grafy 76 9.2 Neplanární grafy Položme si otázku: Jak je nějaký neplanární graf vzdálen od planárnílio? Někoho by napadlo: pojďme daný graf „co nejlépe'* nakreslit a měřit míru neplanarity pomocí počtu průsečíků jeho hran při nejlcpším nakreslení. Musíme si ale stanovit pravidla pro nejlepší nakreslení. Pravidla pro kreslení grafu jsou: 1. Sousední hrany se neprotínají. 2. Dvě ncsousední hrany se protínají nejvýše jednou. 3. Žádná hrana neprotíná sama sebe. 4. V jednom bodě roviny se protínají nejvýše dvě hrany. i Definice 9.6 Průsečíkové číslo u(G) grafu G je nejmenší počet průsečíků jeho hran ze všech možných nakreslení grafu G, vyhovujících předešlým podmínkám. _ -"-■- □ Graf G je tedy planární právě tehdy, je-li v(G) = 0. Je-li graf G podgrafem H, potom pro průsečíková čísla platí v{G) < v[H). V Věta 9.9 Pro úplné grafy Kn platí: u(Kn) < \ |_|J [2=iJ [^J [^J, přičemž pro 1 < n < 10 nastává rovnost. _ -;- 0 Pro úplné bipartitní grafy v obecnosti není znám ani rozumný netriviální odhad průsečíkového čísla. Pouze v případě, že jedna z partit nemá více než šest vrcholů, platí následující věta. [4] |v~| Věta 9.10 Nechť 1 < n < m a n < 6, potom is(K\m) = [f J [^J [f J V Jinou možností, jak měřit ncplanaritu grafu, je hledat nejmenší možný počet planárních faktorů, na které ho lze rozložit. Dané číslo se nazývá tloušťkou grafu G a jeho označení je 6 (G). [y~| Věta 9.11 Pro úplné grafy Kn, kde n ^ 9,10 platí 9 (Kn) = [u-ql\ • pro grafy K§ a K\§ platí - 0 Kapitola 9 Planární a neplanární grafy 77 Nakreslení planárního grafu v rovině je ekvivalentní jeho nakreslení na kulovou plochu neboli sféru. Graf G nazveme vnořitelným do plochy i?, jestliže ho můžeme nakreslit v ploše /?,, aby se jeho hrany neprotínaly. Graf, vnořitelný do roviny, je tedy planární graf. ["v~| Věta 9.12 Graf G je vnořitelný do roviny právě tehdy, je-li vnořitelný do sféry. 0 A Řešený příklad 9.1 Nalezněte alternativní důkaz neplanárnosti grafu K^. Pro každý planární graf G s více než dvěma vrcholy platí h(G) < 3v(G) — 6. To znamená, že 10 < 3,5 - 6 10 < 9 Což neplatí, tím pádem je dokázáno, že graf K§ je neplanární. Pro důkaz neplanárnosti grafu můžeme použít průsečíkové číslo. = I LIJ L¥J L¥J L¥J u(K5) = 1 Tb znamená, že při nakreslení graf K§ bude existovat jeden průsečík (za splnění podmínek pro nejlepší nakreslení diagramu daného grafu). Dále můžeme použít pro důkaz neplanárnosti větu o čtyřech barvách. Nechť G je planární graf, potom y(G) < 4. Pro graf K~, platí x{Kb) — 5, protože každý vrchol je čtvrtého stupně a pro obarvení budeme potřebovat pět barviček. Tím jsme dokázali, že graf K$ je neplanární. A ■■ŕ Neřešené příklady 1. Dokažte, že každá subdivize ncplanárního grafu je neplanární. 2. Dokažte, že každý podgraf planárního grafu je planární. 3. Ukažte, že graf Á'3.3 — e je planární. 4. Určete všechny planární úplné tripartitní grafy. 5. Určete všechny planární úplné r-partitní grafy pro r > 3. 6. Pět domů je třeba spojit (každý s každým) cestami, které se neprotínají. Je to možné? 7. Nalezněte alternativní důkaz neplanárnosti grafu ^"3,3. 8. Sestrojte planární grafy G, i7, J, pro které platí: graf G je pravidelný stupně 6, graf H je pravidelný stupně 3 a přitom počet vrcholů je 5, a pro graf J platí S(.J) = 2 a A( J) = 6. 9. Dokažte Eulerúv vzorec indukcí vzhledem k počtu hran. Kapitola 9 Planární a nrplanární grafy 78 10. Dokažte, že planární graf G s více než třemi vrcholy a 5 > 3 má alespoň 4 vrcholy stupně 5 nebo menšího. 11. Je možno vyslovit nějaké tvrzení o planaritě stromů? 12. Následující hru vynalezli J. H. Conway a M. S. Paterson. Anglicky se nazývá sprouts (výhonky). Na papíře je na začátku nakresleno n puntíků (hra je zajímavá už pro malá n, třeba 5). Hráči se střídají v tazích, kdo nemá tah, prohraje. V každém tahu hráč spojí dva puntíky obloukem, a někam na tento oblouk se nakreslí nový puntík. Puntík se smí použít jako konec nového oblouku jen tehdy, pokud z něj vycházejí nanejvýš 2 již nakreslené čáry, a nový oblouk nesmí protnout již nakreslené oblouky (v každém okamžiku máme tedy rovinné nakreslení grafu s maximálním stupněm 3, puntík na nově přidaném oblouku má už stupeň 2). Příklad vidíme na obrázku 9.7. Dokažte, že pro n počátečních puntíků má hra nanejvýš 3n — 1 tahů (při jakékoliv strategii hráčů). Dokažte, že pro n počátečních puntíků má hra nejméně 2n tahů (při jakékoliv strategii hráčů). Modifikujme hru následovně: Místo puntíků se kreslí křížky, a nové oblouky se připojují k ramenům křížků (vrcholy mohou tentokrát mít maximálně stupeň 4). Na nový oblouk se přikresluje křížek přeškrtnutím, viz obrázek 9.8. Dokažte, že tato hra má vždy přesně 5n — 2 tahů (takže se dá snadno předem určit, kdo vyhraje). [11] O o 0 1 2 3 4 Obrázek 9.7: Hra šprouti 5 (i 7 8 Obrázek 9.8: Hra podvodní šprouti Kapitola a. Vy_ Eulerovské grafy Každý z nás v dětství řešil úlohy, kdy se snažil nakreslit jedním tahem určitý obrázek za podmínek bez zvednutí tužky z papíru a žádnou hranu neobtahovat dvakrát. Asi nejznámější příklad je nakreslení domečku jedním tahem, (obrázek 10.1) V teorii grafů řešíme úlohu, kde hledáme otevřený tah daného grafu procházející všemi hranami tohoto grafu. Otevřený je proto, že počáteční vrchol je různý od koncového vrcholu. Takový tah nazýváme otevřený eulerovský tah. Obrázek 10.1: Domeček Definice 10.1 Otevřený eulerovský tah je tah, který prochází všemi hranami grafu právě jednou a počáteční a koncový vrchol jsou navzájem různé. —-;- □ Často ale budeme chtít navíc splnit podmínku, že počáteční vrchol byl totožný s koncovým vrcholem. V teorii grafů lze tuto úlohu interpretovat tak, že máme nakreslit graf jedním uzavřeným tahem. Každá hrana se zde bude vyskytovat jednou a každý vrchol alespoň jednou. Daný tah se nazývá uzavřený eulerovský tah nebo eulerovský tah. 79 Kapitola 10 Eulerovské grafy 80 Definice 10.2 Uzavřený eulerovský tah (eulerovský tah) je tah, který prochází všem hranami grafu právě jednou a počáteční vrchol je totožný s koncovým vrcholem daného tahu. Někdy bývá uzavřený eulerovský tah nazýván eulerovskou kružnicí. Definice 10.3 Graf, ve kterém existuje uzavřený eulerovský tah, pak nazýváme eulerovským grafem. Vraťme se k našemu domečku. Graf odpovídající domečku nelze nakreslit uzavřeným eulerovským tahem. Zjišťujeme, že každý otevřený eulerovský tah začíná v jednom a končí ve druhém z obou vrcholů stupně tři. Ostatní vrcholy grafu jsou sudého stupně. Procházíme-li totiž grafem po eulerovském tahu, při každém průchodu vrcholem použijeme ke vstupu do vrcholu jednu hranu a k výstupu z něj hranu jinou. Jistě tedy všechny vrcholy s výjimkou počátečního a koncového vrcholu našeho eulerovského tahu jsou sudého stupně. Pokud jde o otevřený tah, potom u počátečního vrcholu při prvním výstupu použijeme jednu hranu a při každém dalším průchodu dvě. Podobně u koncového vrcholu použijeme při každém průchodu dvě hrany a jednu při posledním vstupu. Tyto dva vrcholy tedy jsou nutně lichého stupně. Pokud jde o uzavřený tah, je koncový vrchol totožný s počátečním a jeho stupeň je určitě sudý, neboť při každém průchodu použijeme dvě hrany a po jedné při prvním výstupu a posledním vstupu. Obsahuje-li graf G uzavřený eulerovský tah, potom má všechny vrcholy sudého stupně. Obsahujc-li otevřený eulerovský tah, potom má právě dva vrcholy lichého stupně. Nyní formulujeme nutnou a postačující podmínku, aby graf byl eulerovský. V Věta 10.1 Souvislý graf G je eulerovský právě tehdy, má-li všechny vrcholy sudého stupně. _ —"-:—~~-~~ 0 Důkaz: ([4]) Stačí ukázat, že ze sudosti stupňů všech vrcholů plyne existence eulerovského uzavřeného tahu. Opačná implikace vyplývá z předešlých odstavců. Nechť je tedy G libovolný souvislý graf, mající m hran a všechny vrcholy sudého stupně. Předpokládáme, že každý souvislý graf s méně než m hranami, mající všechny vrcholy sudého stupně, je eulerovský, chceme ukázat, že pak je eulerovský i náš graf G. Tento graf jistě obsahuje cyklus. Platí tvrzení: má-li graf G s alespoň 1 hranou všechny vrcholy sudého stupně, potom obsahuje cyklus. Důkaz necháme čtenáři jako cvičení. Pokud G kromě tohoto cyklu neobsahuje žádné další hrany, jc důkaz ukončen, neboť tento cyklus je hledanou eulerovskou kružnicí. Předpokládejme tedy, že kromě cyklu C graf G obsahuje další hrany. Vynecháme-li hrany patřící do C z grafu G, dostaneme graf G', jehož všechny vrcholy jsou buď opět sudého stupně, nebo stupně nula. Kapitola 10 Eulerovské grafy 81 V případě kdy cyklus procházel vrcholem v, platí degG'(v) = degdv) — 2. Pokud vrchol v nepatřil do cyklu C, pak degG(v) = degoiv). Graf g má méně než m hran. Pokud je g souvislý, obsahuje podle indukčního předpokladu uzavřený eulerovský tah U . Zvolíme libovolný vrchol vq ležící na cyklu C a projdeme nejprve po uzavřeném tahu u' všechny hrany grafu g . Poté pokračujeme po hranách cyklu C, až se vrátíme zpět do vrcholu Vq. Prošli jsme každou hranou grafu g právě jednou a nalezli jsme hledaný uzavřený eulerovský tah grafu g. Pokud je graf g' nesouvislý, postupujeme podobně. Označíme Hi,fÍ2,... ,Hr netriviální komponenty grafu g . Každá komponenta obsahuje vrchol ležící v původním grafu g na cyklu. Nechť tedy pro každou komponentu H{, i = 1,2,..., r, je v.-L takovým vrcholem. Obsahuje-li některá komponenta Hj více vrcholů z C, potom zvolíme kterýkoliv z nich. Protože každá komponenta Hi je souvislým grafem se všemi vrcholy sudého stupně a má méně než m hran, obsahuje uzavřený eulerovský tah ř7j. Konstrukci eulerovského tahu u grafu g zahájíme tím, že projdeme komponentu H\ po tahu U\ tak, že začneme a skončíme ve vrcholu v\. Nyní pokračujme po hranách cyklu C do té doby, než narazíme na některý z vrcholů i>2,..., vr. Bez újmy na obecnosti můžeme předpokládat, že je to vrchol r>2. Vstoupíme tedy do komponenty Hi a opět ji projdeme po uzavřeném eulerovském tahu U2; až se vrátíme do vrcholu V2- Opět pokračujeme po hranách cyklu C, dokud nenarazíme na další z vrcholů Ví. Celý proces opakujeme do té doby, dokud podobně neprojdeme poslední komponentu Hr. Potom pokračujeme po hranách cyklu C až do vrcholu v\. Tak jsme prošli právě jednou všechny hrany netriviálních komponent H\,H2, ■■ - ,Hr, jakož i všechny hrany cyklu C, a tedy všechny hrany grafu g uzavřeným tahem u. To je hledaný eulerovský uzavřený tah grafu g, čímž je důkaz věty ukončen. □ Kde najdou Eulerovské grafy uplatnění? Můžeme se představit úlohy typu, kdy chceme projet nějakou sítí ulic ve městě, např. by takhle mohl projíždět kropicí vůz. Nemusíme se omezit pouze na město. Obecně v souvislosti s eulerovskými tahy můžeme řešit následující úlohy [3]: 1. Máme rozhodnout, zda v daném grafu existuje eulerovský tah (popř. uzavřený eulerovský tah). 2. V daném grafu máme sestrojit eulerovský tah (popř. uzavřený eulerovský tah), jestliže existuje. 3. V daném grafů máme najít nejmenší počet tahů (nikoli eulerovských), které pokrývají hrany grafu. 4. V daném souvislém grafu, jehož hrany jsou ohodnoceny kladnými čísly, máme najít nejkratší uzavřený sled, který obsahuje (alespoň jednou) každou hranu grafu. Kapitola 10 Eulerovskŕ grafy 82 Uvedeme větu, která je podmínkou pro to, aby daný graf neobsahoval most. Věta 10.2 Nechť G je graf, jehož všechny stupně jsou sudé. Potom graf G neobsahuje most. _ ---■-■- E Důkaz této věty je možno najít v [11]. Vrátíme se nyní k pokrytí grafu a uvedeme následující větu z [7]. Věta 10.3 Nechť G je souvislý graf, který má právě 2n vrcholů lichého stupně, n > 1. Pak každé minimální pokrytí grafu G se skládá z n (otevřených) tahů, z nichž každý spojuje dvojici vrcholů lichého stupně. Důkaz: Doplňme graf G o n hran, které je budou spojovat dvojice vrcholů lichého stupně. Každý z těchto vrcholů bude incidovat s právě jednou z těchto hran. Takto vzniklý graf bude zřejmě opět souvislý a navíc Eulerův, takže lze pokrýt jediným uzavřeným tahem. Nyní opět odebereme z tahu dříve přidaných n hran, tah se tím rozpadne na n otevřených tahů, jež reprezentují pokrytí původního grafu G. Mějme nyní libovolné pokrytí grafu G. Potom tento graf musí obsahovat alespoň n otevřených tahů, aby pokrylo 2n vrcholů lichého stupně. Obsahuje-li více než n otevřených nebo uzavřených tahů, pak už není minimální. Obsahujc-li právě n otevřených tahů, musí to být tahy požadované vlastnosti. [7] Uvedeme zde algoritmus pro hledání uzavřeného tahu. Algoritmus je jednoduchý, problém nastává v okamžiku, pokud bychom chtěli daný algoritmus naprogramovat. Při hledání uzavřeného tahu začneme v libovolném vrcholu a po hraně s ním incidující přijdeme do některého sousedního vrcholu. Použitou hranu z grafu odebereme a postupujeme stejným způsobem dále, až se vrátíme do výchozího vrcholu. Výběr hrany je vázán pouze tou podmínkou, aby jejím vypuštěním nevznikl nesouvislý graf (izolované vrcholy připouštíme) a rovněž návrat do výchozího vrcholu po jediné hraně je možný až v posledním kroku. [7] V případě otevřeného tahu musíme začít v jednom z vrcholů lichého stupně a skončíme v druhém. Při odebírání hran sledujeme pouze souvislost vznikajícího grafu. □ Existuje řada úloh příbuzných s hledáním minimálního pokrytí grafu. Příkladem může být tzv. problém čínského listonoše. 10.1 Úlohy typu bludiště Sestavování labyrintů a bludišť patří k oblíbeným hříčkám už od starověku. K nejstarším patří známý řecký Labyrint. V současné době mezi mistry v tvorbě bludišť Angličan Greg Bright (vydal několik knih, podle jeho návrhů byla řada bludišť realizována). Existují i časopisy obsahující bludiště, např. francouzský časopis „Jeux et stratégie'- (Hry a strategie) a samozřejmě počítačové hry. KAPTTOLA 10 EULEROVSKÉ GRAFY 83 Jak bloudit v bludišti? Motoristé pravděpodobně znají pravidlo pravé ruky: Při postupu bludištěm držíme stále pravou ruku na stěně. Formulace tohoto pravidla je velmi jednoduchá. Mezi jeho výhody patří fakt, že se podle něho lze řídit i ve tmě. Bohužel obecně ve složitějším bludišti (kde nevede ven jediná cesta) vůbec nemusí vést k cíli. Můžeme formulovat dvě základní úlohy: 1. Máme plánek bludiště. Často se dané úlohy vyskytují v časopisech a souvisí s prohledáváním grafu. 2. Jsme v bludišti a plánek neznáme. Tyto úlohy jsou dobrodružnější. Máme za úkol uniknout z labyrintu. Grafová interpretace je následující. Neznáme-li plánek bludiště, neznáme ani odpovídající graf. Vrcholy grafu odpovídají křižovatkám a větvení. Chodby představují hrany v grafu. Na obrázku 10.2 vidíme příklad bludiště a vpravo odpovídající diagram grafu. Obrázek 10.2: Bludiště Algoritmy řešící úlohy typu bludiště uvedeme dva. 1. Tarryho algoritmus z roku 1895, který je založen na dvou axiomech: (a) Každou hranou můžeme v jednom směru projít nejvýše jednou. (b) Po té hraně, po které jsme do nějakého vrcholu přišli poprvé, smíme jít zpět jedině tehdy, pokud není jiná možnost. 2. Trémauxův algoritmus z roku 1882, kde se jedná ve své podstatě o Tarryho algoritmus doplněný o třetí pravidlo (c) Pokud přijdeme poprvé procházenou hranou do známého uzlu, vracíme se ihned v následujícím kroku stejnou hranou zpět. Kapitola 10 Eulerovské grafy 81 V rámci tohoto skripta nebudeme řešit uvedené bludiště pomocí těchto algoritmů. U daného bludiště by se jednalo o 53 kroků. Ponecháváme to na čtenáři, který si může vyzkoušet průchod daným bludištěm pomocí těchto algoritmů. A | Řešený příklad 10.1 Dokažte: Graf lze nakreslit otevřeným eulcrovským tahem právě tehdy, když graf obsahuje právě 2 vrcholy lichého stupně. Veta má tvar ekvivalence, to znamená, že důkaz bude obsahovat dvě části, důkaz zleva doprava a naopak. (=0 Při průchodu každým vrcholem potřebujeme dvě hrany, pouze v počátečním vrcholu z něj jednou jen vystupujeme (bude lichého stupně) a v koncovém vrcholu do něj pouze vstupujeme (tzn., opět bude lichého stupně). Nemusí být stejného stupně jako je počáteční vrchol. Vidíme, že v grafu máme dva vrcholy lichého stupně. M j Nechť v grafu existují právě dva vrcholy lichého stupně. Označme tyto vrcholy u a v. Přidáním hrany uv do grafu G vznikne graf ď, ve kterém mají všechny vrcholy sudý stupeň. Tedy podle věty: Souvislý graf G je eulerovský právě tehdy, má-li všechny vrcholy sudého stupně, což znamená, že obsahuje uzavřený eulerovský tah. Vynecháním hrany uv dostaneme z uzavřeného eulerovského tahu tah otevřený eulerovský. Dokázali jsme tedy, že graf obsahuje otevřený eulerovský tah. A i Neřešené příklady 1. Dokažte, že má-li graf G s alespoň 1 hranou všechny vrcholy sudého stupně, potom obsahuje cyklus. 2. Lze nakreslit úplný graf o sedmi vrcholech jedním tahem? 3. Dokažte: Nechť G je souvislý graf a C je jeho hranový řez. Potom každá komponenta grafu G — G — C obsahuje vrchol, který je koncovým vrcholem některé hrany z C. 4. Dokažte: Graf G lze nakreslit k hranově disjunktními otevřenými eulerovskými tahy, přičemž počáteční a koncové vrcholy každých dvou tahů jsou navzájem různé právě tehdy, obsahuje-li 2k vrcholů lichého stupně. 5. Nakreslete eulerovský graf sc sudým počtem vrcholů a lichým počtem hran. Pokud to není možné, zdůvodněte to. 6. Je dáno deset kostek domina s následujícími počty bodů na jednotlivých kostkách: (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5). Je možné seřadit všechny tyto kostky za sebou podle pravidel domina (kostky sc dotýkají částmi sc stejným počtem bodů)? 7. Pro které přirozené číslo n má kompletní graf Kn uzavřený a otevřený eulerovský tah? 8. Ukažte, že dva uzavřené tahy v grafu, které mají společný alespoň jeden vrchol, lze spojit v jediný uzavřený tah. Kapitola 10 Eulerovské grafy 85 9. Kolik tahů je nutně potřeba k pokrytí všech hran grafu, o kterém víme, že má 3 komponenty, 2 vrcholy lichého stupně a žádný izolovaný vrchol? Mohli byste určit potřebný počet tahů, kdyby počet vrcholů lichého stupně nebyl 2, ale 4? 10. Nakreslete jedním tahem grafy na obrázku 10.3. Obrázek 10.3: Jedním tahem -8 m Kapitola 11 Hamiltonovské grafy V předchozí kapitole jsme se zabývali otázkou, kdy je možno projít grafem tak, abychom každou hranou prošli právě jednou. Nyní budeme řešit úlohy typu, kdy jednotlivými městy (vrcholy) budeme chtít procházet právě jednou, tedy, že žádnou obcí nebude projíždět dvakrát. Obecně se daný problém nazývá problém obchodního cestujícího. Jeho přesná formulace je tato: cestující má projít všechny obce své přidělené oblasti a vrátit se zpět domú, a to tak, aby celkově projetá vzdálenost byla co nej menší. Ve formulaci se nachází podmínka, aby celkově projetá vzdálenost byla co nej menší. Momentálně pracujeme s grafy, které nemají ohodnocené hrany, nereprezentují vzdálenost mezi jednotlivými místy. Proto budeme předpokládat že vzdálenosti všech vrcholů jsou jednotkové. Zní to sice zvláštně, že uvažujeme, že vzdálenost mezi Ostravou a Opavou je stejná jako vzdálenost mezi Opavou a Prahou, ale pro nastínění problému nám to bude stačit. Omezíme se tedy na požadavek, abychom prošli každým vrcholem právě jednou a vrátili se zpět do místa, odkud jsme vyšli. U eulerovských grafů existuje nutná a postačující podmínka pro to, aby graf byl eulerovský. Tady u hamiltonovských grafů se s takovou podmínkou nesetkáme. Věty budou mít tvar postačujících podmínek, což znamená, že pokud je něco splněno, pak daný graf je hamiltonovský. Pokud daná podmínka splněna není, znamená to, že daný graf může, ale taky nemusí být hamiltonovský. Je nejvyšší čas nadefinovat hamiltonovský cyklus, cestu a graf. [7~ Definice 11.1 Hamiltonovský cyklus je cyklus procházející všemi vrcholy grafu. _ ---;- □ Definice 11.2 Hamiltonovská cesta je cesta obsahující všechny vrcholy grafu. 80 Kapitola 11 Hamiltonovské grafy 87 Definice 11.3 Hamiltonovský graf je graf, který obsahuje hamiltouovský cyklus. □ i Definice 11.4 Nehamiltonovský graf je graf, který neobsahuje hamiltonovský cyklus. □ Na první pohled se skutečně zdá, že hamiltonovský cyklus (prochází bez opakování všemi vrcholy) je pojem podobný uzavřenému eulerovskému tahu (prochází všemi hranami bez opakování). Ale musíme upozornit, že matematická a algoritmická obtížnost obou pojmů je úplně jiná. Problém hamiltonovské kružnice je matematicky i algoritmicky obtížný. Hamiltonovský graf je nazvaný podle irského matematika W. R. Hamiltona, který v polovině minulého století zveřejnil a vyřešil tuto hádanku: Lze po hranách pravidelného dvanáctistěnu projít všemi jeho dvaceti vrcholy a vrátit se do výchozího bodu, aniž bychom některým vrcholem prošli vícekrát? (Stěny pravidelného dvanáctistěnu jsou pravidelné pětiúhelníky - viz obrázek 11.1). [3] Obrázek 11.1: Hamilton ova hádanka Dále uvedeme Oreho včtu. Kapitola 11 Hamiltonovské grafy ss Věta 11.1 Nechť G je graf s n vrcholy, kde n > 3, a nechť pro každé dva různé nesousední vrcholy u, v platí deg(u) + deg(v) > n. Potom G je hamiltonovský. _ -—=-"- 0 Důkaz: [4] Použijeme důkaz sporem. Předpokládejme, že věta neplatí, tedy, že existuje nehamiltonovský graf G s n vrcholy, n > 3, ve kterém pro každé dva různé nesousední vrcholy u, v platí deg(u) + de g (v) > n. Existuje maximální graf Go s touto vlastností, to znamená, že přidáním hrany uv mezi libovolné dva nesousední vrcholy, pro které platí deg{u) + deg(v) > n, dostaneme graf Go + uv, který je již hamiltonovský. Protože Go nebyl hamiltonovský, každý hamiltonovský cyklus v Go + uv obsahuje hranu uv. Potom ale v grafu Go existuje hamiltonovská cesta P z vrcholu u do vrcholu v s vrcholy u = u\,U2, ■ ■ ■ ,un-i,un = v. Naším cílem je ukázat, že na této cestě existují dva sousední vrcholy um a um+\ takové, že um je sousední s vrcholem v a Um+i je sousední s u, a v důsledku toho graf Go obsahuje hamiltonovský cyklus u = 111,1x2, ixm,v — un,un-i,un-2, ■ ■ ■,um+i,u. (obrázek 11.2) Pokud se nám to podaří, dostaneme se do sporu s předpokladem, že Go není hamiltonovský. U — tí2> .... U„,,V = «„,«„_], U„._2, .. ., Um+1 • « ÍÍ7 = V U = Ui u3 = um Obrázek 11.2: Hamiltonovský cyklus Nechť vrchol u stupně k je sousední s vrcholy Uil, ttÍ2..... «ifc. Pro každé j = 1,2,..., k nazveme vrchol ležící na cestě P bezprostředně před vrcholem m, tedy vrchol it^-i, zakázaným vrcholem. Pochopitelně, že zakázaným vrcholem může být i některý z vrcholů U{, tedy sousedů vrcholu u, a to v případě, když dva nebo více sousedů vrcholu u leží na cestě P bezprostředně za sebou. Zakázaným je také samotný vrchol u = U], neboť předchází vrchol U2- Kapitola 11 Hamiltonovské grafy 89 Zakázaných vrcholů je zřejmě právě tolik, kolik je sousedů vrcholů u, tedy k. Nyní chceme ukázat, že vrchol v je sousední s alespoň jedním zakázaným vrcholem. Pokud by tomu tak nebylo, vrchol v by mohl být sousední s nejvýše s n—k—1 vrcholy (neboť Go obsahuje n—k vrcholů, které nejsou zakázané, ale jedním z nich je samotný vrchol v). To by znamenalo, že je deg(v) < n-k-1. a tedy by muselo platit deg(u) + deg(v) < k + (n-k-1) = n 1, což je spor s předpokladem, že deg(u) + deg(v) > n. Je tedy vrchol v sousední s jedním ze zakázaných vrcholů, třeba um a vrchol um+i je sousední s u. Určitě platí um ^ u, neboť G$ neobsahuje hranu uv. Potom ale graf Go obsahuje hamiltonovský cyklus u = ui, «2, ■ - ■, um,v = un, un-i,un-2, ■ ■ ■, «m+i,«, což je spor s předpokladem, že Go není hamiltonovský. Tím je důkaz hotov. □ Následující věta je věta Diracova a je speciálním případem Oreho věty. |v~| Věta 11.2 Nechť G je graf s n vrcholy, n > 3, a nechť S(G) > n/2. Potom G je hamiltonovský. 0 Ve věku pouhých 17 let dokázal Pós následující větu. 0 V j Věta 11.3 Nechť G je graf s n > 3 vrcholy takový, že pro každé přirozené číslo j < n/2 obsahuje méně než j vrcholů stupně menšího nebo rovného j. Potom G je hamiltonovský. V Nutná a postačující podmínka pro to, aby graf byl hamiltonovský, neexistuje, mohli bychom napsat, že neexistuje přímo, protože taková podmínka existuje pro graf, který se nazývá uzávěr daného grafu. 0 Definice 11.5 Uzávěr grafu G, který označujeme G(G), nazýváme graf, který vznikne z grafu G postupným přidáváním hran tak, že vždy spojíme dva nesousední vrcholy, jejichž součet stupňů je alespoň v(G). —- 0 Uzávěr G s n vrcholy tedy zkonstruujeme tak, že vyhledáme dva nesousední vrcholy mající součet stupňů alespoň n (pokud takové vrcholy existují), a spojíme je hranou. Opět vyhledáme dva nesousední vrcholy se součtem stupňů nejméně n a spojíme je hranou. Tak pokračujeme, dokud můžeme najít dvojici vrcholů splňující shora uvedené předpoklady. Takto vzniklý graf je uzávěrem grafu G. Nezáleží na tom, v jakém pořadí hrany přidáváme, dostaneme vždy stejný graf. Kapitola 11 Hamiltonovské grafy 90 V Věta 11.4 Nechť G(G) a C'(G) jsou libovolné uzávěry grafu G, potom G(G) = G'(G). Důkaz dané věty může čtenář najít v [4]. Nyní uvedeme nutnou a postačující podmínku týkající se uzávěru grafu. V V Věta 11.5 Graf G je hamiltonovský právě tehdy, když je hamíltonovský jeho uzávěr G(G). V Důkaz této věty je v [4]. 0 Věta 11.6 Je-li uzávěrem grafu G s více než dvěma vrcholy úplný graf, potom je graf G hamiltonovský. [y~| Věta 11.7 Nechť |V(G)| > 3. Jestliže k(G) > ,3(G), potom G je hamiltonovský. k(G) je souvislost grafu a /3(G) je číslo nezávislosti grafu. Dále platí tyto další věty. 0 0 V Věta 11.8 Nechť G je souvislý graf s nejméně třemi vrcholy. Jestliže pro každé dva různé nesouscdní vrcholy u, v platí deg(u) + deg(v) > m, kde rn je přirozené číslo, potom G obsahuje cestu délky m. V i Definice 11.6 Hamiltonovský souvislý graf je graf, ve kterém každé dva jeho vrcholy jsou spojeny hamiltonovskou cestou. _ - □ [y"| Věta 11.9 Nechť G je graf s n vrcholy, n > 3, a nechť pro každé dva různé nesousední vrcholy u, v platí deg(u) + deg(v) > n + 1, potom G je hamiltonovský souvislý. V Kapitola 11 Hamiltonovské grafy 91 Definice 11.7 Graf Gk nazýváme A-tou mocninou grafu G, jestliže V{Gk) = V(G), E(G) C E(Gk), a hrana uv e E(Gk) - E(G) patří do E(Gk) právě tehdy, když 1 < distG{u,v) < k. □ Graf Gk sestrojíme z grafu G tak, že do něj přidáme hrany, které z každého vrcholu u vedeme do všech vrcholů G, mající v G od u vzdálenost nejvýše k. V Věta 11.10 Nechť G je souvislý graf, potom G je hamiltonovsky souvislý. V Protože každý hamiltonovsky souvislý graf je současně hamiltonovsky, je samozřejmě třetí mocnina každého grafu hamiltonovská. |"v~] Věta 11.11 Nechť G je 2-souvislý graf, potom G2 je hamiltonovsky souvislý. [y~| Věta 11.12 Každý 4-souvislý planární graf je hamiltonovsky. Základní typy úloh u hamiltonovských grafů jsou [3]: 1. Najít hamiltonovsky cyklus. 2. Najít hamiltonovskou cestu (mezi libovolnými dvčma vrcholy). 3. Najít hamiltonovskou cestu, jejíž jeden krajní vrchol je fixován. 4. Najít hamiltonovskou cestu, jejíž oba krajní vrcholy jsou fixovány. Na začátku kapitoly jsme napsali, že problém obchodního cestujícího úzce souvisí právě s ha-miltonovskými grafy. Problém obchodního cestujícího má mnohé aplikace, například rozvoz zboží ze skladu do jednotlivých prodejen nebo například vrtání děr pomocí určitého stroje, kde chceme minimalizovat přesuny. Postup můžeme také využít pro plánování procesů, kdy máme výrobní zařízení, pomocí kterého se mají opakovaně vyrábět nějaké produkty. Má-li nějaký produkt následovat bezprostředně po výrobě určitého produktu, někdy je třeba výrobní zařízení vyčistit, nastavit, seřídit. Naším úkolem by potom bylo najít plán výroby (tzn. pořadí produktů), aby časové ztráty (čistění, nastavení, apod.) nebyly, nebo ukázat, že takový plán neexistuje. Kapitola 11 Hamiltonovské grafy 92 A Řešený příklad 11.1 Kůň na šachovnici 8x8 má vyjít z určitého pole, navštívit postupně všechna pole a vrátit se na původní políčko. Je to možné? Interpretujte úlohu v teorii grafů. Vytvoříme graf, kde vrcholy jsou 64 polí šachovnice. Hranami jsou možné skoky jezdce. Zjistíme, že daný graf je hamiltonovský, tedy, že daná úloha je řešitelná. Ä Neřešené příklady 1. Dokažte, žc každý hamiltonovský graf je nejméně 2-souvislý. 2. Dokažte, že každý bipartitní hamiltonovský graf má partity stejné velikosti. 3. Jednání u kulatého stolu je přítomno n osob, přičemž každé dvě z nich dohromady znají všech n — 2 ostatních. Ukažte, že mohou okolo stolu sedět tak, že každá osoba sedí mezi dvěma lidmi, které zná. 4. Ukažte, že každý fc-pravidelný graf na 2k — 1 vrcholech je hamiltonovský. 5. Dokažte, že kolo Wn je hamiltonovský graf pro libovolné n. 6. Ukažte, že hamiltonovský souvislý graf na více než třech vrcholech má všechny vrcholy stupně nejméně 3. 7. Nalezněte příklad 2-souvislého grafu, který není hamiltonovský, a ukažte, že jeho druhá mocnina je hamiltonovská. - —T Kapitola 12 Orientované grafy V předchozích kapitolách jsme uvažovali grafy, kde hrany nebyly orientované. Znamenalo to, že hrana uv byla totožná s hranou vu. Pokud připustíme, že dané hrany jsou různé, potom hrany jsou uspořádané dvojice vrcholů. Než uvedeme definici orientovaného grafu, zkusme se zamyslet nad orientovanými a neorientovanými grafy. Orientované grafy nám budou především sloužit k reprezentaci procesu, děje, který probíhá od počátečního do koncového vrcholu šipky. Vrcholy orientovaného grafu představují stavy, mezi kterými orientace znázorňuje volbu, postupy nebo pochody. Orientovaným grafem lze znázornit průběh hry, výrobní proces, výpočetní proces počítače, vývojový diagram algoritmu, cestu automobilu, řešení hádanky, průtok soustavou potrubí, vztahy podřízenosti a nadřízenosti apod. Neorientovaný graf zpravidla znázorňuje stav nějakého systému, pozici jednotlivých vrcholů, jejich blízkost nebo vzdálenost, jejich porovnatelnost nebo ncsoumčřitclnost. Neorientovaným grafem lze znázornit dopravní schéma, schéma propojení elektrického zařízení, vztah nezávislosti. [13] Obecně řečeno, neorientovaný graf představuje většinou statický model, zatímco orientovaný graf představuje většinou model dynamický. [13] i Definice 12.1 Orientovaným grafem D nazýváme dvojici [V, A) — D(V, A), kde V je množina vrcholů a A množina uspořádaných dvojic vrcholů (dvouprvkových uspořádaných podmnožin množiny V) zvaných orientované hrany. □ O orientované hraně a = uv říkáme, že má počáteční vrchol u a koncový vrchol v. Definice 12.2 Opačné hrany jsou dvě hrany uv a vu se stejnými vrcholy, avšak opačně orientované. Budeme uvažovat orientovaný graf bez smyček a násobných hran, tedy jednoduchý orientovaný graf. 93 Kapitola 12 Orientované grafy [T~| Definice 12.3 Smíšený graf je graf, ve kterém se mohou vyskytovat současně jak orientované, tak neorientované hrany. _ —- □ Příklad diagramu smíšeného grafu vidíme na obrázku 12.1. o-o o o Obrázek 12.1: Smíšený graf Smíšený graf převedeme na orientovaný graf tak, že každou neorientovanou hranu nahradíme dvojící opačně orientovaných hran. Orientovaný graf k obrázku 12.1 vidíme na obrázku 12.2. o- o Obrázek 12.2: Orientovaný graf Definice 12.4 Stupeň vrcholu v je počet hran, se kterými je daný vrchol v incidentní. Stupeň vrcholu budeme označovat deg(v) a pokud budeme chtít zdůraznit, že vrchol v je vrcholem grafu D tak degoi^)- fi~ Definice 12.5 Vnějším stupněm (odcházejícím stupněm) vrcholu v budeme nazývat počet hran odcházejících z v. Vnější stupeň budeme označovat odeg(v). |T~| Definice 12.6 Vnitřním (přicházejícím) stupněm vrcholu v budeme nazývat počet hran přicházejících do v. i Kapitola 12 Orientované grafy 95 Vnitřní stupeň budeme označovat ideg(v). Symboly S+(D) (Ô~(D)) a A+(G) (A~(G)) označují nejmenší a největší vnější (vnitřní) stupeň vrcholu v orientovaném grafu D. Věta 12.1 Nechť D je orientovaný graf s n vrcholy v\,v%,vn a h(D) nechť je počet jeho hran, potom E?=i odeg(Vi) = Eti ideg(vi) = h(G). ~ —---;-"-0 Důkaz je triviální, každá orientovaná hrana přispívá jedničkou do součtu všech vnějších stupňů a jedničkou do součtu všech vnitřních stupňů, to znamená, že se dané součty rovnají počtu orientovaných hran v daném grafu. □ Definice 12.7 Orientovaná cesta délky k v orientovaném grafu D jc posloupnost vo,ai, v\, (12,1)2, ■ ■ ■ ,&fc, i?fe, kde k > 0 a vq, vi, ... ,Vk jsou navzájem různé vrcholy a ai,...,a& jsou hrany, přičemž pro každé i = 1,2.....k je a,i hrana s počátečním vrcholem ví-i a koncovým vrcholem wÍ7 tedy a» = ví_i«í. -;-~~—:—^— □ Orientovaná cesta je jednoznačně určena posloupností svých vrcholů, tj. Vq, v\, v2, ■ ■ ■, Vk ze stejného důvodu jako u neorientovaného grafu, neuvažujeme násobné hrany, to znamená, že můžeme zvolit pouze jedinou hranu s příslušným počátečním a koncovým vrcholem. Definice 12.8 Neorientovaná cesta (polocesta) jc posloupnost vo,a\,V\,a,2;v2, ■. ■ ,ak,Vk, ve které orientace hran jc libovolná. ——;-;-;-□ Neorientovaná cesta není jednoznačně určena svými vrcholy. Na neorientované cestě tedy nebereme ohled na orientaci hran. Definice 12.9 Orientovaný cyklus je posloupnost vq, a±, V\, a2, v2, ■ ■ ■, afc,U/t, 01, v\. kde k > 2,v\,v2, ...,Vk jsou navzájem různé vrcholy a a\, a.2, ■ ■ ■, ák jsou hrany, přičemž pro každé i = 2,3,..., k je a,; hrana s počátečním vrcholem Vi-i a koncovým vrcholem ví, tedv a,; = ví-iVí a 01 — v^vi. -:-'-—-D V neorientovaném cyklu je hrana a; kteroukoliv z dvojice hran Ví-iVí, víVí-i. Definice 12.10 Vrchol v je dosažitelný z vrcholu u, jestliže existuje orientovaná cesta z vrcholu u do vrcholu v,_ -- □ Kapitola 12 Orientované grafy 9tí □ i 5 Definice 12.11 Vrcholy u a v jsou navzájem dosažitelné, existuje-li v orientovaném grafu D současně orientovaná (u, t-')-cesta i (v, w)-cesta. Na obrázku 12.3 vidíme dvojici vrcholů, které jsou navzájem dosažitelné. O-O □ Obrázek 12.3: Navzájem dosažitelné vrcholy JT~; Definice 12.12 Vzdálenost vrcholu v od vrcholu u je délka nejkratší orientované cesty z « do ť. □ Budeme ji označovat dist(u, v) a obecně to není symetrická funkce. U neorientovaných grafů je vzdálenost symetrická. □ Definice 12.13 Silně souvislý graf je orientovaný graf, ve kterém pro každé dva jeho vrcholy u a v je vrchol u dosažitelný z v. Na obrázku 12.3 vidíme příklad silně souvislého grafu. V silně souvislém orientovaném grafu je pro každou dvojici u, v dosažitelný nejen vrchol u z vrcholu v, ale také v je dosažitelný z u. [7~| Definice 12.14 Orientovaný graf D nazveme jednostranně souvislý, jestliže pro každé dva jeho vrcholy u a v je buď vrchol u dosažitelný z vrcholu v, nebo vrchol v je dosažitelný z vrcholu u, ale mohou nastat i obě možnosti zároveň. _ - □ Kapitola 12 Orientované grafy 97 Každý silně souvislý graf je jednostranně souvislý. |T~ Definice 12.15 Orientovaný graf D nazveme slabě souvislým, jestliže pro každé dva jeho vrcholy u a v existuje v D neorientovaná cesta z u do v. _ - □ iv Definice 12.16 Symetrizací orientovaného grafu D nazveme neorientovaný multigraf U(D), který vznikne z D zanedbáním orientace ieho hran. -~~-~-_ □ Je také možné definovat syrnetrizaci jako jednoduchý graf, kde se dvojice opačných hran uv a vu zobrazí na jedinou hranu. Slabě souvislý graf je pak každý orientovaný graf, jehož symctrizace je souvislý graf. Libovolný graf G můžeme orientovat, každé jeho hraně přiřadíme jednu ze dvou možných orientací. Vzniklý orientovaný graf D{G) pak nazýváme orientací grafu G. Definice 12.17 Asociovaný orientovaný graf B(G) je graf. který vznikne z grafu G nahrazením každé hrany dvojicí opačně orientovaných hran. -:- □ Věta 12.2 Nechť D je silně souvislý orientovaný graf, potom jeho symetrizace Ú(D) je hranově 2-souvislý graf. V_ Důkaz: Použijeme důkaz sporem. Předpokládejme, že U{D) není hranově 2 souvislý. Potom je buď nesouvislý (tedy i graf D je nesouvislý, což není podle předpokladu možné), nebo obsahuje most. Nechť tento most má koncové vrcholy u a v. Tento most odpovídá v D jedné z hran uv, vu. Předpokládejme, že se jedná o hranu uv. Vynecháním mostu uv dostaneme nesouvislý graf U (D)—uv, který je symetrizací orientovaného grafu D — uv. Vrcholy u a v leží v různých komponentách grafu U(D) — uv. Podle našeho předpokladu je ovšem D silně souvislý, a proto v něm existuje orientovaná cesta z v do u. Ta zajisté neobsahuje hranu uv, a tedy existuje i v orientovaném grafu D — uv. Potom ale existuje cesta z v do m i v grafu U(D — uv). To je však spor, protože U(D — uv) = U(D) — uv. ale vrcholy u a v leží v různých komponentách U(D) — uv, což jsme již ukázali. □ Kapitola 12 Orientované grafy 98 i Definice 12.18 Graf G nazveme silně orientovatelným, jestliže existuje taková jeho orientace D(G), která je silně souvislá. ["vj Věta 12.3 Každý hranově 2-souvislý graf je silně orientovatelný. V Důkaz: Nechť G je hranově 2-souvislý s vrcholovou množinou V. Protože je hranově 2-souvislý, obsahuje cyklus, řekněme v\.t'2,... ,Vk, který můžeme orientovat tak, že každé jeho hraně přiřadíme orientaci fjťj+i (případně t'fct'i), tedy vrchol je počáteční a v;+i koncový. Ostatní hrany mezi vrcholy ležícími v tomto cyklu orientujeme libovolně. Jsou-li nyní ví a v j dva vrcholy cyklu takové, že i < j, potom v j je z vt dosažitelný po cestě ví, Vi+i, • ■ •, Vj-i.Vj, zatímco v% je z vj dosažitelný po cestě Vj,Vj+i, ■ • ■, Ví-i,Ví. Vrcholy v\,v2, ■ ■ ■ ,Vk zařadíme do množiny M, která indukuje silně orientovaný podgraf grafu G. Pokud se množina M rovná vrcholové množině V(G), je důkaz ukončen. Pokud ne, zvolíme libovolný vrchol W\ z množiny V — M. který je sousední s některým vrcholem množiny M. Takový vrchol ví vždy existuje, neboť graf G je souvislý. Hranu ViWi orientujeme z ví do wi. Protože G je hranově 2-souvislý, určitě existuje cesta w\,w2, ...,wi = Ví z wi do v%, která neobsahuje hranu Nechť Vj = wm je první vrchol této cesty, který nepatří do množiny M. Hrany cesty w\. íl'2, ..., wm nyní orientujeme opět ve směru wrwr+) pro r - 1,2,..., m. — 1. Nyní potřebujeme ukázat, že můžeme rozšířit množinu M o vrcholy VJí. 11-2■} ■ ■ • i Wm,5 tedy, že každý vrchol množiny M je dosažitelný z každého z vrcholů w\. iv%...., wm a naopak, a že všechny dvojice vrcholů wr, w9 jsou navzájem dosažitelné. Protože vrchol wm — v j je dosažitelný z každého vrcholu wr, 1 < r < m — 1 (po cestě wr, wr+i, ■ ■ ■ w-m) a všechny vrcholy množiny M jsou dosažitelné z každého vrcholu z m, tedy i z vrcholu vj, jsou všechny vrcholy z M dosažitelné z každého z vrcholu u>i, u^...., wm. Naopak, vrchol v,; je dosažitelný z každého vrcholu z M a každý z vrcholů ici,ir>2,... ,wm je dosažitelný z vť po cestě t»j. W\,w2, ■ ■ ■, wr a tedy je každý wr dosažitelný ze všech vrcholů množiny M. Protože současně je každý vrchol z Ad dosažitelný i ze všech vrcholů ws, s < rn, je vrchol wr pro r < s dosažitelný z ws. Vrchol ws je dosažitelný z wr po cestě wr,wr+\,... ,ws, je-li r < s. Nyní můžeme rozšířit množinu M o vrcholy u.'i, w%,..., wm a všechny hrany mezi vrcholy této množiny, které dosud nemají určenu orientaci, můžeme orientovat libovolně. Je-li nyní M — V (G), je důkaz ukončen, v opačném případě opět vybereme vrchol z V — M a opakujeme celý postup tak dlouho, dokud do množiny M nepatří všechny vrcholy grafu G. □ pV~| Věta 12.4 Každý 2-souvislv graf je silně orientovatelný. _ —-■- [7J Kapitola 12 Orientované grafy 99 12.1 Turnaje V této sekci se budeme zabývat typem grafů, který můžeme použít například pro reprezentaci situace na soutěžích a turnajích. i Definice 12.19 Turnaj je orientovaný graf, ve kterém pro každou dvojici vrcholil u, v existuje právě jedna z hran uv. vu. --□ Věta 12.5 D je turnaj právě tehdy, když jeho symetrizace U(D) je úplný graf. _ -—-"- 0 Situaci, že družstvo u zvítězilo nad družstvem v reprezentujeme orientovanou hranou uv. | i | Definice 12.20 Turnaj nazýváme acyklickým, neobsahuje-li žádný orientovaný cyklus. —-—-■--- □ Definice 12.21 Turnaj nazýváme tranzitivním, jestliže z existence hran uv a vw vyplývá existence hrany uw. Vlastnost acykličriost a tranzitivnost u turnajů jsou ekvivalentní, což vyjadřuje následující věta. Věta 12.6 Turnaj D je tranzitivní právě tehdy, když je acyklický. _ —---———-;-0 Důkaz: Předpokládejme, že graf D je acyklický a uv a vw jsou jeho libovolné hrany. Protože graf D je acyklický, nemůže obsahovat hranu wu, neboť tato by spolu s hranami uv a vw tvořila cyklus. Proto v grafu D existuje hrana uw a graf D je tranzitivní (obrázek 12.4, kde přeškrtnutí hrany znamená, že takto hrana nemůže být orientovaná). Pro opačnou implikaci použijeme důkaz sporem. Předpokládejme, že graf D je tranzitivní a současně obsahuje orientovaný cyklus v\, i'2, ■ ■ ■, Ufc, Z tranzitivity grafu D vyplývá, že hrana v\vs patří do množiny orientovaných hran A(D). Potom ale z existence hran v\v% a v3v4 vyplývá, že také v\v± G A(D) (obrázek 12.5). V této úvaze pokračujeme, až dospějeme k závěru, že z existence hran viv^-t a Vk-iVk vyplývá, že také hrana v\v^ € A(D), což je spor. Na začátku jsme předpokládali, že graf obsahuje cyklus f 1 ,v2, ■ ■ ■, i'k, vi■ Tedy graf D je acyklický. □ Kapitola 12 Orientované grafy 100 Obrázek 12.4: Acykličnost a tranzitivnost turnaje v2 Q-»0 V-i Obrázek 12.5: Acykličnost a tranzitivnost turnaje - existence hrany v\v^ V Věta 12.7 Pro každé přirozené číslo n existuje jediný tranzitivní turnaj na n vrcholech (až na izomorfizmus) [y~| Věta 12.8 Každý turnaj obsahuje orientovanou hamiltonovskou cestu. Důkaz: Daný důkaz provedeme sporem. Budeme předpokládat, že nejdelší cesta v turnaji D na n vrcholech má délku k < n — 1 a nechť jsou vrcholy této cesty označeny vo, v\,...,, %. Protože k < n — 1, existuje nejméně jeden vrchol u, který neleží na této cestě. Graf D je však turnaj, a proto vrchol u musí být sousední se všemi vrcholy í'o,íT, ■ • • ,Vk- Hrana mezi vrcholy u a vq musí být právě vqu, neboť v opačném případě by v grafu D existovala cesta u,vq,vi, .... i:^ délky k + 1, což je spor s tím, že maximální délka cesty v grafu D je podle našeho předpokladu k. Podobně nemůže v grafu D existovat hrana uvi, neboť potom by graf D obsahoval opět cestu Vq, ,..., ví-\,u, ví, Vk délky k+1. Tak po i + 1 krocích ukážeme, že v grafu D nemůže existovat hrana uví, neboť potom by graf D obsahoval opět cestu vq.vi, v»_i,«, v-i,..., vk délky k+1, Protože však z toho plyne, že graf D obsahuje (pro i = k) hranu VkU, dostáváme spor, neboť jsme v grafu D nalezli cestu vq,v\, ...,Vk,u délky k+1, což je spor s naším předpokladem, že nejdelší cesta obsahuje k+1 < n vrcholů, a tedy graf D obsahuje hamiltonovskou cestu. □ Kapitola 12 Orientované grafy 101 12.2 Sítě Jedním z příkladů využití teorie grafů v praxi, které jsme uvedli, je údržba sjízdnosti komunikací. Potřebujeme určitým způsobem vyjádřit např. náročnost údržby příslušné komunikace. K tomu nám v teorii grafu bude sloužit ohodnocení hran grafu, kde danou náročnost bude právě vyjadřovat dané ohodnocení. V teorii grafů můžeme použit i ohodnocení vrcholů. JT~ Definice 12.22 Hranově ohodnocené orientované grafy jsou orientované grafy, ve kterých je každé hraně přiřazeno reálné číslo. ------------------........-----■ □ i Definice 12.23 Vrcholově ohodnocené jsou grafy, kde je určité reálné číslo přiřazeno každému vrcholu daného grafů. □ [T~| Definice 12.24 Totálně ohodnocené grafv jsou grafy, které jsou jak hranově, také vrcholově ohodnocené. _ ——.—~~~~—:—-□ Grafy, kterými jsme se zabývali doposud, můžeme považovat za speciální případ ohodnocených grafů, kde ohodnocení každé hrany i vrcholu je rovno jedné. Definice 12.25 Síť je hranově ohodnocený graf N, jehož vrcholová množina V(N) se skládá ze tří disjunktních podmnožin: množiny zdrojů 5*, množiny ústí T a množiny průchozích vrcholů X. _ -—-■- □ Pro každý vrchol s e S platí ideg(s) = 0. Pro každý vrchol í € T platí odeg(t) = 0. To znamená, že pro každý vrchol patřící do množiny zdrojů platí, že hrany z daného vrcholu „vystupují" a pro každý vrchol patřící do množiny ústí hrany pouze „vstupují". Definice 12.26 Kapacitou hrany a nazýváme ohodnocení každé této hrany, vždy jde o kladné reálné číslo. □ Kapacitu hrany budeme označovat c(a). Totálně ohodnocené grafy lze snadno transformovat na hranově ohodnocené. Hranově ohodnocené jsou z hlediska, tvorby algoritmů hledání optimálních toků v sítích výhodnější. Daný převod provedeme tak, že každý vrchol v sítě N můžeme nahradit dvojicí vrcholů v+ a v~, spojených hranou v~v+, přičemž všechny hrany vstupující do původního vrcholu v, budou nyní vstupovat do vrcholu v~, a všechny hrany vystupující z původního vrcholu v budou nyní vystupovat Kapitola 12 Orientované grafy 102 z vrcholu v~. Ohodnocení vrcholu v se pak stane kapacitou nové hrany v~v+. V teorii grafů je výhodné, aby kapacity hran byly celočíselné a množiny zdrojů a ústí byly jednoprvkové. Teorie toků patří k často aplikovaným oblastem. Pomocí toků v sítích můžeme modelovat velké množství praktických situací, úloh. Dále proto definujeme tok v síti. Definice 12.27 Tok v síti N je celočíselná funkce / definovaná na množině hran A(N), splňující následující podmínky (X je množina průchozích vrcholů) 1. 0 < f (a) < c(a) pro všechny a E A, 2. f~(v) = ,/+('<-") pro všechny v £ X, 3. /"(*) =/+(*), kde funkce f~{v) je definována jako součet f(xv) přes všechny hrany vstupující do vrcholu v, f+(v) je definována jakou součet f {vy) přes všechny hrany vystupující z vrcholu v. ----------------------- ' il Hodnota toku f (a) vyjadřuje množství produktu, které za časovou jednotku proteče hranou a. První podmínka nám říká, že za časovou jednotku hranou o může protéci nejvíce tolik produktu, jaká je její kapacita. Druhá podmínka stanovuje, že množství přitékajícího produktu se musí rovnat množství produktu odtékajícího. Poslední podmínka říká, že do ústí přiteče tolik produktu, kolik ho odteklo ze zdroje. Je-li Z libovolná podmnožina V(N), potom symbolem Z označíme její doplněk vzhledem k množině V(N), tedy množinu V(N) — Z. Definice 12.28 Řezem K v síti N nazveme množinu hran uv, u £ Z, v £ Z, jejímž vynecháním se ústí t stane nedosažitelným ze zdroje s, přičemž s £ Z a t g'Z ■ ---------------------------------------- S « rír! Definice 12.29 Kapacitou řezu K nazveme součet kapacit všech hran obsažených v řezu K. Kapacitu řezu budeme označovat cap(K). Určitě si představíme, že pokud budeme mít potrubí, kterým proudí nějaká kapalina, budeme omezeni kapacitou daného potrubí, kapacitou hrany. |~V~| Věta 12.9 Pro libovolný tok / a libovolný řez K v síti N platí val(f) < cap(K). V Kapitola 12 Orientované grafy 103 [T~ Definice 12.30 Tok /'* nazveme největší, platí-li val(f*) > val(f) pro každý tok / v Ar. Definice 12.31 Rez K nazveme nejmenším, jestliže pro každý řez K v síti N piati cap(K) < cap(K jy| Věta 12.10 V každé síti je hodnota nejvčtšího toku rovna kapacitě nejmenšího řezu. □ 0 Je zřejmé, že žádný tok. kde je splněna podmínka 0 < f (a) < c(a) pro všechny hrany o, € A, nemůže být větší než kapacita kteréhokoliv řezu oddělujícího zdroj a ústí. Význam nalezení řezu s nejmenší kapacitou vyplývá z faktu, že nejmenší kapacita řezu oddělujícího zdroj a ústí je rovna velikosti největšího toku od zdroje k ústí. Úlohy o tocích lze řešit i v neorientovaných grafech. Směr toku neorientovanou hranou je libovolný, ale musíme ho určit. Jednou z možností je nahradit orientovanou hranu dvojicí opačně orientovaných hran. Příkladem aplikace toků v sítích může být propustnost silniční sítě mezi dvěma místy. Na úlohu o tocích sítí lze převézt i úlohy o párování v bipartitních grafech. Více je možno se dočíst v [3]. Neřešené příklady 1. Definujte pro orientované grafy další pojmy, které jsme definovali pro neorientované grafy: podgraf, faktor, indukovaný podgraf, vnější a vnitřní stupňová posloupnost orientovaného grafu. [4] 2. Definujte incidenční matici a matici sousednosti orientovaného grafu. V čem se liší od těchto matic pro neorientované grafy? [4] 3. Nechť D je orientovaný graf, neobsahující žádný orientovaný cyklus. Ukažte, že potom ô+(D) = 0. 4. Odvoďte a dokažte nutnou a postačující podmínku pro existenci uzavřeného orientovaného tahu v orientovaném grafu D. 5. Určete, zda je graf z obrázku 12.6 silně souvislý. 6. V grafu na obrázku 12.6 stanovte silně souvislé komponenty. 7. V grafu 12.6 změňte orientaci jediné hrany tak, abychom získali silně souvislý graf. Které hrany je výhodné zkoumat? 8. Určete, zda graf na obrázku 12.7 je silně souvislý. 9. Nechť G je konečný orientovaný graf, v němž platí <5+ (u) > 0 pro každý jeho vrchol u. Dokažte, že G obsahuje alespoň jeden cyklus. Kapitola 12 Orientované grafy 104 A B D Obrázek 12.6: Vyšetření silné souvislosti Obrázek 12.7: Vyšetření silné souvislosti 10. Nechť v konečném orientovaném grafu G platí > 1 a současně 5(u) > 1 pro každý jeho vrchol u. Je možné tvrdit, že každým vrcholem pak prochází nějaký cyklus orientovaného grafu Gl Kapitola X _ Grafové algoritmy V této kapitole popíšeme některé grafové algoritmy. 13.1 Nalezení minimálni kostry grafu Problém nalezení minimálni kostry si ukážeme na úloze týkající se udržování sjízdnosti komunikací v situaci sněhové kalamity. [8] Představme si. že je hlášeno silné sněžení v oblasti Severní Moravy. Očekává se, že během krátké doby napadne několik desítek centimetrů nového sněhu. Silničáři se budou snažit, aby udrželi hlavní tahy sjízdné a aby udrželi dostupnost jednotlivých měst a obcí. Je zřejmé, že v období velké sněhové kalamity se nemůže podařit udržet sjízdné všechny silnice. Bude rozhodnuto, že se budou udržovat alespoň silnice uvedené v krizovém plánu, aby žádná obec nezůstala odříznuta od světa. Nebudou tedy sjízdné všechny cesty. Do některých částí, obcí se bude muset jezdit oklikou. Krizový plán musí být vypracován a znám dopředu, aby jej měla k dispozici rychlá záchranná služba, hasiči, policie a další instituce. Pro vypracování plánu údržby silnic budeme potřebovat údaje od silničářů, mapu obcí a silnic, které jsou v zimním období udržované. Údaje o nákladech na údržbu každé silnice. Musíme si uvědomit, že náklady nemusí vždy odpovídat délce. Je vhodné každé silnici přiřadit například obtížnost v rozsahu od 1 do 10. Pro krizový plán tedy vybereme pouze některé tak, aby všechny obce byly dostupné a součet nákladů na udržování vybraných silnic byl co nejmenší. V grafové interpretaci budou představovat města, obce a důležité křižovatky vrcholy a silnice hrany grafu. Náklady na údržbu vyjádříme ohodnocením hran čísly 1 až 10. Vybereme si určitou část území. Mapu dané oblasti vidíme na obrázku 13.1. Grafová interpretace je na obrázku 13.2. Daný graf je jednoduchý neorientovaný s celočíselným ohodnocením. Musíme upozornit, že některé vrcholy v grafu odpovídají křižovatkám. Ohodnocení grafu neodpovídá vzdálenosti, ale předpokládejme, že náročnosti údržby dané komunikace. Výsledkem bude graf, který bude mít stejný počet vrcholů, bude souvislý, acyklický, což zna- 105 Kapitola 13 Grafové algoritmy 106 Obrázek 13.1: Mapa Ostrava Příbor Obrázek 13.2: Mapa - grafová interpretace Kapitola 13 Grafové algoritmy 107 mená. že nebudou v grafu existovat dvě různé cesty mezi dvěma vrcholy a také daný graf bude s minimálním ohodnocením. Daná úloha se nazývá úloha nalezení minimální kostry grafu. Kostra vždy u souvislého grafu existuje a má n — 1 hran. J. P. Kruskal vypracoval tři postupy pro hledání minimální kostry. Své výsledky publikoval v roce 1956. R.. C. Prim vypracoval podobný algoritmus pro hledání minimální kostry. Svou práci publikoval v roce 1957. Dané algoritmy se nazývají Kruskalův algoritmus a Primův algoritmus. Brněnský matematik Otakar Borůvka řešil otázku optimální výstavby elektrické sítě. Jeho algoritmus pochází z roku 1926. O. Borůvka jej však neformuloval jako úlohu teorie grafů, ale v jazyku matic. Kruskal na jeho práci navazoval. Jeho postup vylepšil roku 1929 Vojtěch Jarník. Nezávisle na něm ke stejným výsledkům dospěl později Prim a také Dijkstra. Jeden z algoritmů si vybereme, a to Primův algoritmus. Uvedeme zde zjednodušený popis algoritmu. Minimální kostru grafu vytvoříme v několika krocích. Předpokládáme, že graf je konečný a souvislý, tj. má minimální kostru. Začneme od grafu, který neobsahuje žádnou hranu. Zvolíme si libovolný vrchol jako výchozí „část grafu"'. Obsahuje-li náš graf o jednu hranu méně než je vrcholů, skončíme. Našli jsme minimální kostru grafu. Jinak ke grafu přidáme další hranu tak, by vedla z již získaného grafu do nového vrcholu, který jsme do daného grafu ještě nezahrnuli. Ze všech hran vybereme takovou, která má co nejmenší ohodnocení, a znovu zkontrolujeme, zdali počet hran je o jednu menší než je počet vrcholu. Pokud ano, skončíme a našli jsme hledanou kostru. Pokud ne, pokračujeme tak, že opět přidáme hranu tak, aby vedla z již získaného grafu do nového vrcholu, který tam ještě nepatří, s nejnižším ohodnocením. Tyto kroky opakujeme, dokud počet vrcholů není o jeden větší než počet hran. Vraťme se k našemu příkladu. Na obrázku 13.3 vidíme, že byla k lesu přidána hrana 26 s ohodnocením 1. V dalším kroku algoritmu byla přidána hrana 27 s ohodnocením 2, jak vidíme na obrázku 13.4. V dalším kroku byla přidána hrana 78 s ohodnocením 2, situace je na obrázku 13.5. Takto bychom pokračovali tak dlouho, dokud počet hran by nebyl o jednu menší, než jc počet vrcholů. Výsledný graf, který je kostrou, najdeme na obrázku 13.6. Stejným způsobem můžeme najít minimální silniční síť pro celý region, kraj, komunikace ve městech apod. Hotový krizový plán pro údržbu silnic by měli znát silničáři, rychlá záchranná služba, hasiči, policie, dopravní podniky a v případě nutnosti by měly informace padnout i ve sdělovacích prostředcích. Oba algoritmy dávají stejné výsledky (až na případné záměny hran stejného ohodnocení). Výsledek je někdy přizpůsoben dalším faktorům, například, že přednost dostanou cesty do větších měst. Existují algoritmy pro nalezení k nejmenších koster, což je složitější problém a tady se mu nebudeme věnovat. 13.2 Prohledávání grafu Dalšími algoritmy, kterými se budeme zabývat, se týkají prohledávání grafu, což patří v teorii grafů mezi často řešené problémy. Prohledáváním grafu rozumíme systematický postup, který umožňuje řešit některé (nebo všechny) následující úlohy: Kapitola 13 Grafové algoritmy 108 Ostrava Příbor Obrázek 13.3: Primův algoritmus - krok 1 Ostrava Příbor Obrázek 13.4: Primův algoritmus krok 2 Kapitola 13 Grafové algoritmy 109 Ostrava Příbor Obrázek 13.5: Primúv algoritmus - krok 3 1. Zjištění, zda je vrchol dostupný z daného vrcholu. 2. Nalezení množiny všech vrcholů dostupných z daného vrcholu. 3. Nalezení jakékoliv cesty z jednoho vrcholu do vrcholu jiného, pokud tedy existuje. 4. Nalezení cesty z vrcholu do všech vrcholů, které jsou z něj dostupné. 5. Pro všechny vrcholy, které jsou dostupné z vrcholu, provést určitou operaci, a to na základě lokálních vlastností grafu, tj. s využitím pouze okolí jednotlivých vrcholů. Uvedeme zde tři způsoby prohledávání, a to: 1. značkování, 2. hledání do hloubky, 3. hledání do šířky. Dané algoritmy uvedeme pro grafy, které budou orientované. Značkování vrcholů znamená, že vrcholům grafu postupně přiřazujeme značky. Označkujeme-li vrchol, znamená to, že do něj vede cesta z daného výchozího vrcholu. Nyní popíšeme algoritmus značkování. První krok je takový, že označkujeme vrchol r, ostatní vrcholy jsou beze značek. Poté provedeme výběr hrany. Vybereme libovolnou hranu e, jejíž počáteční vrchol má značku a koncový vrchol nikoliv. Jestliže taková hrana neexistuje, algoritmus končí. Nyní Kapitola 13 Grafové algoritmy 110 Ostrava Příbor Obrázek 13.6: Primův algoritmus - výsledek provedeme značkování, tedy označkujeme koncový vrchol hrany e a pokračujeme dále krokem, který nazýváme výběr hrany. Věta 13.1 Výpočet algoritmu značkování vrcholů grafu s n vrcholy skončí nejvýše po n — 1 opakováních kroků výběr hrany a a značkování. Po ukončení výpočtu budou označkovaný právě ty vrcholy, do nichž existuje orientovaná cesta z vrcholu r. - 0 Při úloze hledání cest je často třeba nejen zjistit existenci cesty, ale navíc tuto cestu sestrojit. Pro tento účel lze značkovací algoritmus upravit: Každému vrcholu v, který je v daném kroku značkován, přiřadíme navíc hodnotu Odkud(v) = e, kde e je hrana vybraná v kroku výběr hrany. Je-li označkován vrchol v, který je různý od vrcholu r, pak hodnota Odkud(v) je jménem poslední hrany v (některé) cestě vedoucí z vrcholu r do vrcholu v. Cestu z vrcholu v nižného od vrcholu r lze po skončení značkovacího algoritmu snadno nalézt zpětným postupem pomocí hodnot Odkud: hodnota Odkud(v) je poslední hranou v hledané cestě. Označme w počáteční vrchol hrany Odkud(v). Je-li vrchol w různý od vrcholu r, pak hodnota Odkud{w) je předposlední hranou v cestě z vrcholu r do vrcholu v, atd. Zajímá-li nás pouze cesta z daného vrcholu r do daného vrcholu s, můžeme samozřejmě ukončit výpočet značkovacího algoritmu ihned po označkovaní vrcholu s. Nyní si popíšeme prohledávání do šířky. Kapitola 13 Grafové algoritmy 111 V prohledávání grafu do šířky použijeme značkování vrcholů. Nejdříve označkujeme vrchol r, pak všechny jeho sousedy, pak všechny dosud neoznačkované sousedy těchto sousedů atd. Nejdůleži-tější vlastností metody je, že pomocí tohoto algoritmu hledáme nejkratší cestu, tj. cestu s nejmenším počtem hran. Vstupem daného grafu je orientovaný graf G a jeho vrchol r a výstupem neboli úkolem je najít všechny vrcholy, do nichž vede orientovaná cesta z vrcholu r a do každého z nich najít cestu o nejmenším počtu hran. Všechny vrcholy, do nichž bude nalezena cesta, budou označkovaný a budou jim přiřazeny hodnoty Odkud a Vzdálenost. U proměnných nebudeme používat diakritiku. Dále použijeme seznam Fronta obsahující ty vrcholy, které již byly označkovaný, ale z nichž jsme ještě nezkoumali možnosti dalšího postupu. Nyní si popíšeme jednotlivé kroky algoritmu formálněji. Algoritmus prohledávání grafu do šířky. 1. Inicializace: označkujeme vrchol r, ostatní vrcholy jsou bez značek. Nyní Vzdalenost(r) — 0 a seznam Fronta obsahuje jediný vrchol r. 2. Test ukončení: Je-li seznam Fronta prázdný, výpočet ukonči. 3. Volba vrcholu: Ze začátku seznamu Fronta odebereme vrchol a označíme jej v. 4. Postup do šířky: Pro každého následníka w vrcholu v, který není označkován, provedeme tyto operace: Označkujeme vrchol w, Odkud(w) = hrana vedoucí z v do w, Vzdalenost(w) = Vzdalenost(v) + 1, vrchol w připíšeme na konec seznamu Franta. Pro zpracování všech následníků pokračujeme podle kroku 2. Pro hledání do šířky je podstatné, že ze seznamu Fronta odebíráme vždy ten vrchol, který je v něm nejdéle. Právě taková datová struktura bývá označována termínem fronta. j V | Věta 13.2 Algoritmus skončí práci po konečném počtu kroků. Po zastavení jsou označkovaný právě ty vrcholy, do nichž vede orientovaná cesta z vrcholu r. Je-li označkován vrchol v různý od vrcholu r, pak Odkud(v) je poslední hranou v nejkratší cestě z vrcholu r do vrcholu v a Vzdalenost(v) je délka (tj. počet hran) této nejkratší cesty. —-■- 0 Důkaz: Každý vrchol, který je označkován, je zařazen do seznamu Fronta a poté, co je odtud odebrán, nemůže do něj být znovu zařazen, neboť je již označkován. Proto kroky 2 až 4 mohou být provedeny nejvýše tolikrát, kolik je vrcholů v množině vrcholů, a algoritmus se tedy zastaví. Zbývající část věty vyplývá z faktu, že algoritmus označkuje nejprve všechny vrcholy ve vzdálenosti 1 od r, pak všechny vrcholy ve vzdálenosti 2 atd. □ Další algoritmus, který si popíšeme, bude prohledávání grafů do hloubky. Vstupem algoritmu prohledávání grafu do hloubky bude orientovaný graf G a jeho vrchol r. Úkolem bude znovu najít všechny vrcholy, do nichž vede orientovaná cesta z vrcholu r. Pomocnou proměnnou bude seznam Trasa obsahující vždy posloupnost hran tvořících cestu z výchozího vrcholu Kapitola 13 Grafové algoritmy 112 r do právě zkoumaného vrcholu v. Kromě toho budeme vrcholy, do nichž byla nalezena cesta, značkovat podobně jako v předešlém algoritmu. Algoritmus prohledávání grafu do hloubky 1. Inicializace: v = r, Trasa = 0, označkujeme vrchol r, ostatní vrcholy jsou bez značek. 2. Volba hrany e: Vezmeme některou dosud nepoužitou hranu e začínající ve vrcholu v a pokračujeme podle kroku 3. Pokud taková hrana neexistuje, pokračujeme podle kroku 5. 3. Test vhodnosti hrany e: Označme w koncový vrchol hrany e. Je-li vrchol w označkován, pokračujeme podle kroku 2, v opačném případě podle kroku 4. 4. Postup do hloubky: Hranu e připíšeme na konec seznamu Trasa, dosadíme v = w a označkujeme vrchol v. Pokračujeme krokem 2. 5. Návrat z vrcholu v: Je-li seznam Trasa neprázdný, odebereme z jeho konce hranu e a její počáteční vrchol označíme v. Pokračujeme podle kroku 3. Je-li seznam Trasa prázdný, výpočet končí. Pro algoritmus je podstatné, že ze seznamu Trasa hrany odebíráme na témže konci, jako přidáváme, odebíráme tedy vždy hranu, která je v seznamu nejkratší dobu. Tato datová struktura je označována jako zásobník. I V | Věta 13.3 Algoritmus hledání do hloubky skončí práci po konečném počtu kroků. Po jeho zastavení jsou označkovaný právě ty vrcholy, do nichž vede z vrcholu r orientovaná cesta. ——-"- 0 Orientovaná cesta z vrcholu r do vrcholu v je obsažena v seznamu Trasa, vždy ve chvíli, kdy jc vrchol v značkován. Obsah seznamu Trasa se však během výpočtu mění. Požadujeme-li zachovaní informací o nalezených cestách i po ukončení výpočtů, lze algoritmus doplnit o vytváření hodnot Odkud. Po provedení této úpravy je seznam Trasa zbytečný, neboť v kroku 5 lze k návratu z vrcholu v použít hodnotu Odkud(v). Pro hledání do hloubky v neorientovaných grafech bychom upravili krok 2, v němž volíme libovolnou dosud nepoužitou hranu, jejíž jeden koncový vrchol je v. Další možností je převod daného grafu na symetrický orientovaný graf, kde každá hrana původního grafu je nahrazena dvojicí opačně orientovaných hran, a potom bychom nemuseli na algoritmu nic upravovat. Metoda prohledávání do hloubky je základem poměrně obecné metody řešení kombinatorických úloh (tzv. backtraekingu). Metodu lze použít v těch případech, kdy řešení úlohy můžeme považovat za konečnou posloupnost omezené délky, přičemž každý prvek posloupnosti musí být vybrán z předem dané konečné množiny. Všech posloupností je tedy konečně mnoho. Některé posloupnosti pokládáme za tzv. přípustná řešení. Úkolem je najít nějaké přípustné řešení, popř. takové přípustné řešení, pro které předem daná, tzv. účelová funkce, nabývá minima nebo maxima. Množinu všech posloupností pokládejme za vrcholy orientovaného grafu. Následníky posloupnosti (vrcholu) jsou všechna její prodloužení o jeden prvek. Tento graf nazýváme stromem řešení. Každý vrchol je v něm dostupný Kapitola 13 Grafové algoritmy 113 z prázdné posloupnosti po jediné cestě. Nejjednodušší verze backtrackingu spočívá v prohledávání stromu řešení do hloubky, přičemž evidujeme vždy nejlepší dosud nalezené přípustné řešení. Má smysl prodlužovat jen ty posloupnosti, u nichž je naděje, že mohou být prodlouženy na přípustné řešení. Pokud jsme tedy schopni s jistotou určit, že žádné prodloužení nějaké posloupnosti není přípustné, můžeme ušetřit čas tím, že prohledávání příslušného podstromu přeskočíme. Řešený příklad 13.1 Ukážeme si prohledávání grafu do šířky na orientovaném grafu, jehož diagram je na obrázku 13.7. 3 Obrázek 13.7: Graf - prohledávání do šířky Za výchozí vrchol vezmeme 1. Silně jsou vytažené hrany, které jsou po skončení algoritmu obsaženy v hodnotách Odkud a které vytvářejí systém nejkratších cest do všech dostupných vrcholů. Vrcholy byly značkovány v pořadí 1, 2, 3, 5,8, 7,4, 9,10,11. Vrchol 6 nebyl označkován, neboť není dostupný po orientované cestě z vrcholu 1. Dále si ukážeme prohledávání grafu do hloubky na orientovaném grafu. Graf s výsledkem k prohledávání do hloubky je na obrázku 13.8. Silně jsou vyznačeny hrany, které byly použity k postupu do hloubky. V kroku 2 jsme přitom volili hrany vycházející z vrcholu v vždy v pořadí, ve kterém jsou uvedeny v seznamu hran E(G). Vrcholy byly značkovány v pořadí: 1, 2,3, 7,10, 8,9,11,5,4. _ Kapitola 13 Grafové algoritmy 114 Obrázek 13.8: Graf - prohledávání do hloubky Literatura [1] Arthur Cayley - Mathematician Biography. Facts and Pictures, [online], [cit. 2013-11-13]. Dostupné z: http://www.famous-mathematicians.com/arthur-cayley. [2] B ondy, Adrian, MuRTY. U. S. R. Graph theory. New York: Springer. 2008. xii, 651 s. ISBN 978-1-84628-969-9. [3] Demel, Jiří: Grafy. Praha: ČVUT, 1988, s. 184, ISBN 04-006-88. [4] Fronček. Dalibor. Úvod do teorie grafů. Opava: Slezská univerzita, 1999, 105 s. ISBN 80-724-8044-8. [5] Gustav Robert Kirchhoff. [online], [cit. 2013-11-13]. Dostupné z: http://th.physik.uni-frankfurt.de/ jr/gif/phys/kirchhof.jpg. [6] História de la matematica - Johann Benedict Listing, [online], [cit. 2013-11-13]. Dostupné z: http://timerime.com/en/event/2207911/Johann+Benedict+Listing/. [7] Kolář, Jiří: Grafy. Praha: Ediční středisko ČVUT, 1984, s. 213. [8] kovář, Petr. Grafové algoritmy. [online]. [cit. 2013-11-13]. Dostupné z: http://homel.vsb.cz/kovl6/talks/algoritmy/obsah.html. [9] Leonhard Euler. [online], [cit. 2013-11-13]. Dostupné z: http://www.nndb.com/people/954/000048810/. [10] Math Year 2013: Dr. Kenneth Appel and the Four Color Map Theorem: Part 1. [online], [cit. 2013-11-13]. Dostupné z: http://mathyear2013.blogspot.cz/2013/04/dr-kenneth-appel-and-four-color-map.html. [11] Matoušek, Jiří, Nešetřil, Jaroslav. Kapitoly z diskrétní matematiky. 2. upr. vyd. Praha: Karolinum. 2000, 377 s. ISBN 80-246-0084-6. [12] Merris. Russell. Graph theory. New York: John Wiley, c2001, xi, 237 p. ISBN 04-713-8925-0. [13] Nešetřil, Jaroslav. Teorie grafů. 1. vyd. Praha: SNTL, 1979, s. 316. 115 Literatura 116 [14] Optimization Entera y Dinámica: Algoritmo de PRIM. [online], [cit. 2013-11-13]. Dostupné z: http://oed2012.blogspot.cz/2012/09/algoritmo-de-prim.html. [15] Otakar Borůvka, [online], [cit. 2013-11-13]. Dostupné z: http://www.muni.cz/history/gallery/194/4?lang=cs. [16] Sedláček, Jiří. Úvod do teorie grafů. 3. vyd. Praha: Academia, 1981, 271 s. ISBN ISBN 21-102-81. [17] Urban Omnibus: Moonlighter Presents... Bjarke Ingels, Neil Freeman and Anthony Graves. [online], [cit. 2013-11-13]. Dostupné z: http://urbanomnibus.net/2011/02/moonlighter-presents-bjarke-ingels-neil-freeman-and-anthony-graves/. [18] William Bmvan Hamilton - Mathematician Biography, Facts and Pictures, [online], [cit. 2013-11-13]. Dostupné z: http://www.famous-mathematicians.com/william-rowan-hamilton/. Teorie grafů a grafové algoritmy RNDr. Luděk Cienciala Ph.D., RNDr. Lucie Ciencialová, Ph.D. Tato inovace předmětu Teorie grafů je spolufinancována Evropským sociálním fondem a Státním rozpočtem ČR, projekt číslo CZ.1.07/2.2.00/28.0014, „Interdisciplinární vzdělávání v ICT s jazykovou kompetencí". Skripta Teorie grafů slouží primárně jako vzdělávací materiál pro cílovou skupinu projektu. Recenzenti: RNDr. Šárka Vavrečková, Ph.D. ing. Richard Pečonka Vydavatel: Ustav informatiky, Výzkumný ústav Centra excelence IT4Innovations Filozoficko-přírodovědecká fakulta v Opavě Slezská univerzita v Opavě Bezručovo náměstí 13 746 01 Opava Typesetted with L^TjľJÍPočet stran: 115 Vydání: první, 2014 Autorská práva: © autoři, 2014 Obálka: (5) Lucie Ciencialová, 2014 Tisk: Z+M Partner, spol. s. r. o., Ostrava Vydáno v Opavě v srpnu 2014 ISBN: 978-80-7510-060-3