MASARYKOVA UNIVERZITA Přírodovědecká fakulta TEORIE GRAFŮ EDUARD FUCHS Brno 2003 1 2 PŘ EDMLUVA Prvotní impulzy, které posléze lidstvo přivedly k vybudování matematiky, byly bezpochyby dvojího druhu: početní a geometrické. Tyto impulzy také předznamenaly jeden z centrálních protikladů, které lze vypozorovat v celé dosavadní historii matematiky ­ vztah diskrétního a spojitého. Typickými reprezentanty matematických objektů nacházejících se na straně diskrétního proudu jsou přirozená, respektive celá čísla, konečné množiny, konečné geometrie apod., spojitý směr reprezentují objekty jako množina všech reálných čísel, přímka, eukleidovská rovina, spojitá funkce apod. Jak již název napovídá, zabývá se diskrétní matematika první z výše uve- dených stránek našich modelů reality. Je svým způsobem paradoxní, že poté, co matematika na sklonku 19. sto- letízvládla v Cantorově teorii množin problematiku matematického nekonečna, patří mezi matematické disciplíny, které se ve 20. století rozvíjely nejdynamič- těji, právě diskrétní matematika, jejíž značná část se zabývá studiem konečných množin. To, že zejména v poslední třetině 20. století prodělala diskrétní matematika přímo bouřlivý rozvoj, bylo způsobeno řadou faktorů. Mezi klíčové patří: ˇ neustále se rozšiřující škála aplikací nejen v matematice samotné, přede- vším však mimo ni, a to nejen v ,,tradičních" přírodovědných oblastech, ale zejména v nových a mnohdy nečekaných souvislostech; ˇ intenzívní rozvoj výpočetní techniky, která umožňuje provádět výpočty a analýzy, které se ještě před několika desetiletími zdály nemožné a nadlouho přesahující hranice lidských možností. V předloženém textu jsou vyloženy úvodní partie centrální disciplíny mo- derní diskrétní matematiky ­ teorie grafů. K základnímu textu jsou připojeny dva dodatky. V prvním jsou uvedeny základní biografické údaje osobností, které jsou v textu zmiňovány, ve druhém jsou tabulky některých studovaných funkcí. 3 4 Čtenářům budu vděčný, když případné chyby a nedostatky, které v textu zjistí, zašlou na mou mailovou adresu: fuchs@math.muni.cz. Za jejich připomínky jim předem děkuji. OBSAH PŘ EDMLUVA 3 1 TEORIE GRAFŮ 7 1 Co to je teorie grafů a kdy vznikla . . . . . . . . . . . . . . . 7 2 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Souvislé grafy . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Stromy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Mosty, artikulace a některé grafové charakteristiky . . . . . . 32 6 Eulerovské a hamiltonovské grafy . . . . . . . . . . . . . . . 38 7 Rovinné grafy . . . . . . . . . . . . . . . . . . . . . . . . . . 46 8 Barvení grafů . . . . . . . . . . . . . . . . . . . . . . . . . . 56 9 Zobecnění pojmu graf . . . . . . . . . . . . . . . . . . . . . . 65 DODATEK 1: BIOGRAFIE 68 DODATEK 2: TABULKY 73 5 Kapitola 1 TEORIE GRAFŮ 1 Co to je teorie grafů a kdy vznikla Teorie grafů je relativně samostatná část diskrétní matematiky; pochopení zá- kladních pojmů této teorie nevyžaduje hluboké znalosti jiných matematických disciplín. Většina pojmů o nichž budeme hovořit, má vcelku jednoduchou a názornou interpretaci. Musíme si včšak uvědomit, že se budeme zabývat pouze těmi nejjednoduššími pojmy a že jednoduchá formulace problematiky vůbec nepředznamenává jednoduchost řešení daných problémů. V matematice se s pojmem ,,graf" setkáváme často a v nejrůznějších sou- vislostech. Běžně například hovoříme o ,,grafech funkcí". Teorie grafů se však zabývá objekty zcela jiného druhu. V tomto paragrafu ještě nepodáme zcela přesnou definici pojmu ,,graf". Pokusíme se pouze o vysvětlení intuitivního velmi názorného smyslu tohoto pojmu, stručně uvedeme, jak a kdy se tento pojem v matematice objevil a naznačíme, proč má teorie grafů četné aplikace nejen v matematice, ale i v řadě nematematických oborů. Ve světové literatuře patrně neexistuje učebnice teorie grafů, v níž by se dříve nebo později neobjevila známá úloha o sedmi mostech města Královce, nebot'v souvislosti s touto úlohou se v matematice pojem ,,graf" objevil poprvé. Jak tato úloha zní? Městem Ko¨nigsberg (česky Královec, dnešní Kali- ningrad v Rusku) teče řeka Pregel. V této řece jsou dva ostrovy, které byly s pevninou a vzájemně propojeny sedmi mosty. Schéma této situace je na obrázku 1.1. Úkolem je zjistit, zda je možné vyjít z jednoho místa, projít po každém mostě právě jednou a skončit procházku ve výchozím bodě. Tuto úlohu řešil (a vyřešil) v roce 1736 L. Euler. Ten samozřejmě dobře věděl, že řešení nezávisí na délce mostů, šířce řeky a podobně, ale pouze na tom, které části města jsou jednotlivými mosty propojeny. Znázorníme-li si 7 8 I. TEORIE GRAFŮ Obr. 1.1: Schéma 7 mostů v Ko¨nigsbergu jednotlivé části města jako kroužky v rovině a mosty jako spojnice příslušných částí, je okamžitě zřejmé, že vyřešit uvedenou úlohu znamená, názorně řečeno, ,,namalovat jedním tahem" ,,graf" na obr. 1.2. Obr. 1.2: Grafová interpretace úlohy o 7 mostech Euler samozřejmě řešil nejen uvedenou úlohu (čtenář pravděpodobně ví, že požadovanou procházku uskutečnit nelze), ale vyřešil obecně, které ,,grafy" lze jedním tahem namalovat (jak o tom budeme hovořit v paragrafu 6). Po uvedeném Eulerově výsledku se více než 100 let ,,grafová" problematika v matematice neobjevila. Až v polovině 19. století se anglický matematik A. Cayley zabýval otázkou, kolik existuje izomerů uhlovodíku CnH2n+2. (Jak čtenář patrně ví, první tři členy uhlovodíkové řady, tj. metan, etan, propan, mají jediný izomer, čtvrtý člen již má izomery dva ­ butan a izobutan). Cayley udělal v podstatě tutéž abstrakci jako Euler. Když si znázornil jednotlivé atomy jako kroužky v rovině a spojil ,,hranou" kroužky znázorňující ty atomy, mezi nimiž je chemická vazba, převedl ,,chemický" problém na problém nalezení počtu ,,různých" grafů předepsaného typu, jak je uvádíme na obr. 1.3. (Kroužky, z nichž ,,vycházejí" čtyři hrany, odpovídají atomům uhlíku, kroužky, z nichž vychází jediná hrana, odpovídají atomům vodíku. Jak uvidíme v paragrafu 4, jsou uvedené grafy případem tzv. ,,stromů".) Analogicky se přirozeným způsobem k pojmu ,,graf" dostal G. Kirchhoff 1. Co to je teorie grafů a kdy vznikla? 9 metan (a) etan (b) propan (c) butan (d) izobutan (e) Obr. 1.3: Grafy izomerů uhlovodíku ve svých pracech o elektrických obvodech. V téže době, tj. zhruba v polovině 19. století, začíná historie jednoho z nejslavnějších problémů teorie grafů, tzv. problému čtyř barev. O tomto problému budeme podrobněji hovořit v paragrafu 8. První ,,grafovou" práci v české matematické literatuře publikoval v roce 1926 O. Borůvka, když vyřešil otázku, jak elektrifikovat danou skupinu měst sítíminimálnídélky (o tomto problému budeme obecněji hovořit v paragrafu 4). První monografii o teorii grafů uveřejnil v roce 1936 mad'arský matematik D. Ko¨nig. Jeho kniha Theorie der endlichen und unendlichen Graphen byla vpravdě průkopnická a po dlouhá desetiletí ve světě prakticky jediná. Doslova bouřlivý rozvoj prodělává teorie grafů v posledních zhruba čtyři- ceti letech, kdy se neustále rozšiřuje spektrum aplikací této teorie. Nyní je snad již alespoň částečně zřejmé, jaké objekty se tedy v teorii grafů studují. Bud'dána nějaká množina V = (ve většině případů konečná). Její prvky nazveme vrcholy nebo též uzly. Představme si tyto vrcholy jako malé kroužky v rovině. Některé dvojice vrcholů mohou být vzájemně spojeny tzv. hranou. V některých ,,grafech" mohou být dva vrcholy spojeny i více než jednou hranou (takový je například graf na obr. 1.2), někdy je přípustná mezi vrcholy nejvýše jedna hrana (jako například v grafech na obr. 1.3). V některých grafech jsou hrany ,,orientovány", tj. je vyznačen směr, od kterého uzlu ke kterému příslušná hrana vede; takové hrany nazýváme šipky. V některých grafech se připouštějí tzv. smyčky, tj. hrany vedoucí z uzlu do sebe samého. Někdy se dokonce připouštějí ,,hrany" spojující více než dva uzly. (Pak hovoříme obvykle o tzv. hypergrafu.) Přitom je jistě zřejmé (a později to přesně ukážeme), že ,,grafy" ve výše uvedeném smyslu lze definovat abstraktně, nezávisle na způsobu jejich kon- krétního ,,nakreslení". Toto kreslení bude důležité jen v některých případech 10 I. TEORIE GRAFŮ (například v paragrafu 7, kde se budeme zabývat tzv. rovinnými grafy). Některé případy, které lze popsat pomocí grafů, jsme uvedli na začátku tohoto paragrafu. Čtenář si jistě dovede představit řadu dalších situací, které lze takto charakterizovat. Grafem je například automapa ČR. Vrcholy jsou jednotlivé obce, hrany jsou příslušné silnice. Tento graf je navíc tzv. ohodnocený ­ jednotlivým hranám jsou připsána kladná čísla (vzdálenosti). Grafem je schéma zapojení barevného televizoru i plán vodovodní sítě města Brna. Pomocí grafů lze popsat výrobní procesy i vztahy mezi pracovníky v daném závodě. Pomocí pojmů teorie grafů lze charakterizovat strukturu programu pro počítač i rozpis sportovní soutěže atd. Za grafy lze považovat hasseovské diagramy uspořádaných množin a vůbec každou množinu, na níž je definována binární relace. I pro teorii grafů platí to, co jsme uvedli již v 1. kapitole. Chceme-li například v konečném ohodnoceném grafu najít ,,nejkratší cestu" z jednoho vrcholu do druhého, mohlo by se zdát nejjednodušší všechny cesty vypsat (je jich přece pouze konečně mnoho), a pak mezi nimi vybrat tu nejkratší. Nemožnost tohoto postupu vyplývá z toho, že již pro poměrně ,,malé" grafy je všech možností tak mnoho, že ani pomocí počítačů není uvedený postup realizovatelný. U řady jednoduše fomulovatelných úloh není dodnes nalezen ,,efektivní" algoritmus pro jejich řešení. Jmenujme za mnohé alespoň tzv. problém obchod- ního cestujícího: Obchodní cestující má projít danou množinou měst a vrátit se tam, odkud vyšel. Náklady na jeho cestu přitom mají být co nejmenší. Je zřejmé, že tuto situaci lze popsat ohodnoceným grafem, v němž vrcholy jsou jednotlivá města, hranou spojíme města mezi nimiž je přímé dopravní spojení a každé hraně přiřadíme náklady spojené s cestováním mezi danými vrcholy. Jakkoliv jednoduchý se uvedený problém zdá, jde o jeden z nejkompliko- vanějších problémů diskrétní matematiky. V závěru tohoto paragrafu je nutno ještě uvést, že terminologie v této oblasti není ustálená a jednotná ani ve světové ani v české matematické literatuře. Dokonce i samotný pojem ,,graf" může mít v různých knihách odlišný význam, podle toho, jaký cíl autor sleduje. My budeme v dalším grafem rozumět to, co se často nazývá obyčejný graf (neorientovaný graf bez smyček a bez násobných hran). Vzájemný poměr jed- notlivých typů grafů (orientovaných, neorientovaných, multigrafů, hypergrafů atd.) popíšeme v paragrafu 9. 2. Základní pojmy 11 2 Základní pojmy 2.1 Definice. Bud'U = libovolná množina, bud'H P2(U). Uspořádanou dvojici [U, H] nazýváme graf. Prvky množiny U nazýváme uzly (nebo též vrcholy) grafu, prvky množiny H hrany grafu [U, H]. 2.2 Poznámka. (a) Uvědomme si, že podle definice je množina uzlů vždy neprázdná, avšak množina hran může být prázdná. (b) Necht' U je tříprvková množina {x, y, {x, y}}, H bud' množina {{x, y}, {x, {x, y}}}. Pak je podle definice 2.1 [U, H] graf. Popis tohoto grafu je však nepřehledný, nebot' {x, y} je současně jeden z uzlů i jedna z hran. Abychom se vyhnuli podobným nepříjemnostem, budeme nadále automaticky předpokládat (respektive označení volit tak), že U H = . (c) Uvědomme si, že v grafu [U, H] každé dva uzly tvoří nejvýše jednu hranu. (d) Je-li [U, H] graf, pak jsou hrany dvouprvkové podmnožiny množiny U. Místo {x, y} H budeme obvykle užívat jednoduššího zápisu xy H, tj. budeme hovořit o hranách xy, uv, ab a podobně. (Přitom je zřejmé, že xy H právě tehdy, když yx H, tj. hrany jsou podle definice ,,neorientované".) Je-li x U, není xx hrana (tj. v našem grafu neexistují ,,smyčky"). (e) Podle definice může být množina uzlů grafu [U, H] konečná i neko- nečná. Ř íkáme, že [U, H] je konečný graf, je-li U konečná množina. V dalším budeme převážně hovořit o konečných grafech. (f) Grafy si budeme často představovat tak, jak jsme to uvedli již v paragrafu 1. Je-li [U, H] graf, představíme si uzly jako malé kroužky v rovině, dva uzly x, y pak spojíme nějakou křivkou (nejčastěji ­ ne však nutně ­ úsečkou) právě tehdy, když xy H. Získaný obrázek je v mnoha případech užitečný, uvědo- mme si však, že jeden a tentýž graf lze znázornit obrázky, z nichž nemusí být vůbec zřejmé, že jsou to nakreslení téhož grafu. Je-li například U = {a, b, c, d} a H = P2(U), je na všech obrázcích 2.4a­c nakreslen tento graf [U, H]. (g) Terminologie teorie grafů často vychází z takto konstruovaných ob- rázků. Tak například říkáme, že x, y jsou koncové uzly hrany xy, o uzlech u, v U říkáme, že jsou sousední, pokud uv H, hrana ab spojuje uzly a, b, hrana xy je incidentní s uzly x, y atd. 12 I. TEORIE GRAFŮ a b dc (a) a b c d (b) a b c d (c) Obr. 2.4: Různá nakreslení grafu K4 2.3 Definice. Úplným grafem na množině U = rozumíme graf [U, P2(U)]. (Tzn., že v úplném grafu jsou každé dva uzly spojeny hranou.) Ú plný graf na množině U je obvyklé značit symbolem Kn, kde n = |U|. Na obrázcích 2.4a­c je tedy nakreslen graf K4. 2.4 Definice. Bud'te dány grafy G1 = [U1, H1], G2 = [U2, H2]. Pak říkáme, že: (a) G1 = G2, jestliže U1 = U2, H1 = H2, (b) G1 je podgrafem grafu G2, jestliže U1 U2, H1 H2, (c) G1 je faktorem grafu G2, je-li podgrafem grafu G2 a U1 = U2, (d) G1 je vlastním podgrafem grafu G2, je-li podgrafem tohoto grafu a přitom G1 = G2, (e) G1, G2 jsou disjunktní, jestliže U1 U2 = , (f) G1, G2 jsou komplementární, jestliže U1 = U2, H1 H2 = , H1 H2 = = P2(U). 2. Základní pojmy 13 2.5 Příklad. Na obr. 2.5a,b jsou vzájemně komplementární vlastní podgrafy grafu K4. Oba uvedené grafy jsou současně faktory grafu K4. a b c d (a) a b c d (b) Obr. 2.5: Komplementární podgrafy grafu K4 2.6 Definice. Bud' [U, H] graf. Ř ekneme, že uzel x U je konečného stupně, jestliže inciduje s konečným počtem hran. V opačném případě je x uzel nekonečného stupně. Je-li x uzel konečného stupně, označíme počet hran, které s tímto uzlem incidují, symbolem st x. Toto číslo nazýváme stupeň uzlu x. Je-li st x = 0, nazývá se uzel x izolovaný. 2.7 Poznámka. (a) Platí st x = |{y U; xy H}| . (b) V grafu na obr. 2.5a platí st a = st b = st d = 2, st c = 0, takže c je izolovaný uzel tohoto grafu. V grafu na obr. 2.5b platí st a = st b = st d = 1, st c = 3. V grafu Kn je zřejmě stupeň každého uzlu roven číslu n - 1. (c) Je zřejmé, že v konečném grafu je každý uzel konečného stupně. I v ne- konečném grafu však mohou být samozřejmě všechny uzly konečného stupně. Například na obr. 2.6 je nekonečný graf, jehož každý uzel má stupeň 2. Zvolíme-li však za množinu uzlů například množinu R všech reálných čísel a definujeme-li množinu H hran takto: x, y R, xy H |x - y| Q, je zřejmě [R, H] nekonečný graf, v němž jsou všechny uzly nekonečného stupně. Tento graf samozřejmě nakreslit (ani schématicky) dost dobře není možné. 14 I. TEORIE GRAFŮ Obr. 2.6: Graf, jehož všechny uzly mají stupeň 2 2.8 Věta. Bud'[U, H] konečný graf. Pak platí xU st x = 2 |H| . Důkaz. Indukcí vzhledem k číslu |H|. Je-li |H| = 0, tj. H = , je tvrzení zřejmé, nebot'st x = 0 pro každý uzel x U. Necht'tvrzení platí pro každý graf na množině uzlů U, který má nejvýše h hran. Bud'nyní G = [U, H] takový graf, že |H| = h+1. Bud'xy H libovolná hrana. V grafu G = [U, H -{x, y}] je h hran, takže v G platí xU st x = 2h. Stupně všech uzlů v G a G jsou však stejné až na uzly x, y, které mají v G stupeň o jedničku větší než v G . Odtud zřejmě plyne, že v G platí xU st x = 2 h + 2 = 2 (h + 1). ˇ V důkazu věty 2.11 využijeme následujícího označení. 2.9 Definice. Bud' G = [U, H] konečný graf, k N0 bud' libovolné. Pak klademe k(G) = |{x U; st x = k}| . Symbol k(G) tak udává počet uzlů stupně k v grafu G. Je evidentní, že pouze pro konečně mnoho k N0 je k(G) = 0. (Předpokládáme, že G je konečný!) Například v grafu na obrázku 2.5a je 0 = 1, 2 = 3, k = 0 pro 0 = k = 2. V grafu na obr. 2.5b platí 1 = 3, 3 = 1, k = 0 pro ostatní k. Z definice čísel k je zřejmé, že platí 2.10 Pomocná věta. Bud'G = [U, H] konečný graf. Pak xU st x = k=0 k k(G). Následujícího elementárního tvrzení budeme často využívat. 2.11 Věta. Počet uzlů lichého stupně v každém konečném grafu je sudý. 2. Základní pojmy 15 Důkaz. Bud'G = [U, H] konečný graf. Počet uzlů lichého stupně je roven číslu j=0 2 j+1. Přitom j=0 j j = j=0 2 j 2 j + j=0 (2 j + 1) 2 j+1 = = j=0 2 j (2 j + 2 j+1) + j=0 2 j+1. Odtud celkem j=0 2 j+1 = 2 |H| - j=0 2 j (2 j + 2 j+1). Protože na pravé straně poslední rovnosti stojí prokazatelně číslo sudé, je i číslo j=0 2 j+1 sudé. ˇ 2.12 Poznámka. (a) Pro nekonečné grafy tvrzení 2.11 zřejmě neplatí. Napří- klad v grafu na obr. 2.7 existuje právě jeden uzel lichého stupně. Obr. 2.7: Graf s jediným uzlem lichého stupně (b) Stupně uzlů grafu hrají důležitou roli v řadě úvah. Jedna z typických úloh spočívá v následujícím: bud' dána konečná posloupnost a1, a2, . . . , an nezáporných celých čísel. Tato posloupnost se nazývá grafová, když existuje graf [U, H] takový, že U = {u1, . . . , un}, st ui = ai , i = 1, . . . , n. Snadno lze ukázat, že existují posloupnosti, které nejsou grafové. Nutná a dostatečná podmínka toho, aby posloupnost byla grafová, je uvedena například v [6], str. 37. 2.13 Definice. Ř ekneme, že graf [U, H] je pravidelný graf k-tého stupně (nebo stručně jenom k-pravidelný graf), jestliže st x = k pro každý uzel x U. 16 I. TEORIE GRAFŮ 2.14 Příklad. (a) Ú plný graf Kn je pravidelný graf stupně n - 1. (b) Na obr. 2.8a je konečný a na obr. 2.8b nekonečný pravidelný graf 3. stupně. (a) (b) Obr. 2.8: Pravidelné grafy 3. stupně 2.15 Poznámka. Z věty 2.11 bezprostředně plyne, že v konečném pravidelném grafu lichého stupně je počet uzlů sudý. V závěru tohoto paragrafu se stručně zmíníme o tom, jakým způsobem je možno graf zadat. Uvažujme například graf na obr. 2.9. Tento graf je jistě přehledný a z ob- rázku je čtenáři okamžitě jasné, o jakém grafu hovoříme. Zadání grafu jeho nakreslením je proto jedno z nejčastějších. Mnohdy je však nutno volit zadání jiné. Obrázek může být nepřehledný a například jako vstup do počítače je (ale- spoň prozatím) prakticky nepoužitelný. V těchto případech je nejobvyklejší graf zadat pomocí vhodně sestavené posloupnosti nebo pomocí jistých matic. Ukažme si alespoň některé z nejběžnějších možností. Pro zadání grafu je vhodné označit uzly přirozenými čísly 1, . . . , n (jak jsme to udělali na obr. 2.9). Označíme-li graf na obr. 2.9 jako [U, H], je U = {1, 2, 3, 4, 5, 6} H = {{1, 4}, {1, 5}, {2, 5}, {3, 5}, {3, 6}, {5, 6}} Zápis tohoto grafu lze ,,zakódovat" následující posloupností: (6, 6, 1, 4, 1, 5, 2, 5, 3, 5, 3, 6, 5, 6). 2. Základní pojmy 17 2 64 5 1 3 Obr. 2.9: (Jak čtenář jistě postřehl, udává první číslo počet uzlů, druhé počet hran, a pak následuje soupis všech hran, přičemž závorky v označení hran můžeme pochopitelně vynechat.) Tentýž graf však můžeme popsat i jinou posloupností například takto: (6, 6, 2, 4, 5, 1, 5, 2, 5, 6, 1, 1, 4, 1, 2, 3, 6, 2, 3, 5). První číslo udává počet uzlů, druhé počet hran; pak postupně následuje stupeň uzlu 1 (který je roven 2) a výčet s ním sousedících uzlů (což jsou uzly 4 a 5), dále stupeň uzlu 2 (který je roven 1) a sousední uzel (tj. 5) atd. Matici sousednosti grafu [U, H] sestavíme z nul a jedniček tak, že aij = 1 právě tehdy, když i j H. Matice sousednosti grafu na obr. 2.9 je uvedena v tabulce 2.1. 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 Tab. 2.1: Matice sousednosti grafu z obr. 2.9 Tak zvanou znaménkovou matici obdržíme tak, že v matici sousednosti místo jedniček napíšeme znaménko + a místo nul znaménko -. Dalšími možnostmi ­ a je jich celá řada ­ se nebudeme zabývat. 18 I. TEORIE GRAFŮ 3 Souvislé grafy 3.1 Definice. Bud'[U, H] graf, x0, xn U bud'te libovolné uzly. Posloupnost uzlů a hran tvaru x0, x0x1, x1, x1x2, . . . , xn-1, xn-1xn, xn se nazývá sled začínající v uzlu x0 a končící v uzlu xn. Uzly x1, . . . , xn-1 nazýváme vnitřní uzly tohoto sledu, číslo n (tj. počet hran ve sledu) nazýváme délkou tohoto sledu. 3.2 Příklad. V grafu na obr. 2.9 je například 1, 15, 5, 52, 2, 25, 5, 53, 3 sled délky 4 začínající v uzlu 1 a končící v uzlu 3. 3.3 Poznámka. (a) Podle definice je každý uzel sledem nulové délky. (b) Existuje-li mezi dvěma různými uzly sled, existuje mezi nimi zřejmě nekonečně mnoho sledů. Můžeme totiž, jednoduše řečeno, kteroukoliv hranu v daném sledu libovolně mnohokrát opakovat. Například v grafu na obr. 2.9 existují mezi uzly 1 a 2 sledy 1, 15, 5, 52, 2 1, 15, 5, 52, 2, 25, 5, 52, 2 1, 15, 5, 52, 2, 25, 5, 52, 2, 25, 5, 52, 2 atd. Vzhledem k tomu, že ve sledu se mohou hrany i uzly opakovat, má smysl následující definice. 3.4 Definice. Sled, v němž se neopakuje žádná hrana, se nazývá tah v daném grafu. Je-li počáteční uzel tahu roven koncovému, nazývá se tah uzavřený. V opačném případě se tento tah nazývá otevřený. Sled, v němž se neopakuje žádný uzel, se nazývá cesta. 3. Souvislé grafy 19 3.5 Poznámka. Je zřejmé, že každá cesta je tahem, avšak opačné tvrzení obecně neplatí. Například v grafu na obrázku 2.9 je 2, 25, 5, 53, 3, 36, 6, 65, 5, 51, 1 ote- vřený tah, avšak není to cesta, nebot'se opakuje uzel 5. 3.6 Věta. Necht'v grafu [U, H] existuje mezi uzly x, y U, x = y sled. Pak mezi nimi existuje v daném grafu alespoň jedna cesta. Důkaz. Tvrzení je vcelku zřejmé. Necht'je dán sled mezi uzly x, y: x = x0, x0x1, . . . , xn-1, xn-1xn, xn = y. Pokud tento sled není cestou, existují xi , xj , i < j, tak, že xi = xj . Pak ale je x0, . . . , xi , xj xj+1, xj+1, . . . , xn opět sled mezi uzlu x, y. (Z původního sledu jsme ,,vyškrtli" úsek od xi do xj .) Není-li takto získaný sled cestou, musí se v něm nějaký uzel opakovat. Příslušnou část sledu pak můžeme opět vyškrtnout. Po konečném počtu kroků pak z původního sledu jistě zůstane cesta z x do y. ˇ 3.7 Příklad. V grafu na obr. 2.9 existují mezi uzly 1 a 3 dvě cesty: jedna má délku 2, druhá délku 3. 3.8 Definice. Graf, v němž mezi každými dvěma uzly existuje sled, se nazývá souvislý. 3.9 Poznámka. Podle poznámky 3.3a je každý graf tvořený jediným uzlem souvislý. Souvislý je i graf na obr. 2.9, avšak graf na obr. 2.5a souvislý není, nebot'v něm neexistuje sled například mezi uzly a a c. V dalším budeme potřebovat následující tvrzení. 3.10 Věta. Bud'[U, H] souvislý graf, x U, st x = 1, xy H hrana incidentní s uzlem x. Pak je graf [U - {x}, H - {xy}] souvislý. Důkaz. Bud'te u, v U - {x} libovolné dva navzájem různé uzly. (Kdyby ta- kové dva uzly neexistovaly, bylo by U = {x, y}, H = {xy} a graf [U - {x}, H - {xy}] by byl [{y}, ], což je souvislý graf podle poznámky 3.9). Protože je [U, H] souvislý, existuje v něm sled mezi uzly u, v a podle věty 3.6 existuje mezi těmito uzly alespoň jedna cesta. Nyní si stačí uvědo- mit, že na žádné cestě mezi uzly u, v nemůže ležet hrana xy. (Uzel x by totiž musel být vnitřním uzlem této cesty. Protože x inciduje pouze s hranou xy, obsahuje daná cesta úsek . . . , y, yx, x, xy, y, . . . . Pak to ale není cesta, ne- bot' v daném sledu se opakuje uzel y.) Každá cesta mezi u, v je tedy sledem v [U - {x}, H - {xy}], takže tento graf je souvislý. ˇ 20 I. TEORIE GRAFŮ 3.11 Poznámka. Graf [U - {x}, H - {xy}] je tedy souvislý vlastní podgraf grafu [U, H] (za předpokladů věty 3.10). Bud'[U, H] libovolný graf. Definujeme-li na množině U relaci takto: x y existuje sled mezi uzly x, y, je zřejmé, že relace je ekvivalence na množině U. (Reflexivita plyne z po- známky 3.9, symetrie a tranzitivita je zřejmá.) Tato ekvivalence určuje rozklad U/ na množině U. Pro každý uzel x U označme U(x) tu třídu tohoto rozkladu, v níž leží uzel x. Je tedy U(x) = {t U; existuje sled mezi uzly t, x}. Označíme-li H(x) = {uv H; u U(x), v U(x)}, je zřejmě [U(x), H(x)] podgraf grafu [U, H] (pro každý uzel x U). 3.12 Definice. Bud'[U, H] graf, x U libovolný uzel. Podgraf [U(x), H(x)] grafu [U, H] se nazývá komponenta grafu [U, H] příslušná uzlu x. 3.13 Poznámka. Je zřejmé, že graf [U, H] je souvislý právě tehdy, když má právě jednu komponentu. Komponenty grafu jsou ­ jinak řečeno ­ maximální souvislé podgrafy daného grafu. 3.14 Poznámka. Souvislé grafy lze rovněž považovat za metrické prostory. Je-li totiž [U, H] souvislý graf a x, y U libovolné uzly, existuje mezi těmito uzly podle věty 3.6 alespoň jedna cesta. Mezi cestami z uzlu x do uzlu y jistě existuje cesta minimální délky. Označme její délku (x, y). Pro čtenáře bude jistě snadným cvičením ověření toho, že pro každé tři uzly x, y, z U platí: (a) (x, y) = 0 právě tehdy, když x = y, (b) (x, y) = (y, x), (c) (x, y) + (y, z) (x, z). To však právě znamená, že (U, ) je metrický prostor. Lze tedy na souvislé grafy aplikovat i metody teorie metrických prostorů. 3. Souvislé grafy 21 Jak uvidíme, budou v dalším hrát souvislé grafy důležitou roli. Zvláště významné pak budou souvislé pravidelné grafy. Například na obr. 2.6 je souvislý pravidelný graf 2. stupně. Nás však budou zajímat především konečné souvislé pravidelné grafy 2. stupně. 3.15 Definice. Konečný souvislý pravidelný graf druhého stupně se nazývá kružnice. Počet uzlů v kružnici nazýváme její délkou. 3.16 Příklad. Na obrázku 3.10a je kružnice délky 3, na obrázku 3.10b kružnice délky 6. (a) (b) Obr. 3.10: Kružnice Graf na obrázku 3.10a se ­ vcelku pochopitelně ­ rovněž nazývá trojúhel- ník. (V teorii grafů je tak trojúhelník zvláštním případem kružnice.) V dalších úvahách uvidíme, že jednou z důležitých charakteristik grafu bude to, zda obsahuje jako podgraf nějakou kružnici. Například graf na obr. 2.9 obsahuje právě jednu kružnici (trojúhelník o vrcholech 3,5,6), graf na obr. 2.8a obsahuje kružnic celou řadu, avšak grafy na obr. 1.3 neobsahují jako podgraf žádnou kružnici. Právě takovými grafy se nyní budeme zabývat. 22 I. TEORIE GRAFŮ 4 Stromy Stromy tvoří jednu z nejdůležitějších tříd grafů. Mají řadu aplikací v nejrůz- nějších oborech. Jak jsme uvedli již v paragrafu 1, patří mezi první grafy, které byly v matematice zkoumány. 4.1 Definice. Konečný souvislý graf neobsahující jako podgraf žádnou kruž- nici, se nazývá strom. Graf, jehož každá komponenta je stromem, se nazývá les. 4.2 Poznámka. Les je tedy graf neobsahující žádnou kružnici. Strom je ko- nečný souvislý les. Pojmenování ,,strom" a ,,les" souvisí s tím, jak lze tyto objekty nakreslit. Příklad ,,odpovídajícího" nakreslení je na obr. 4.11. b b b b b b b b b b b b b e e e r rr ¨ ¨¨ b b b b b b b b b b b b b b bb bb b b b b b b b b b b b b b b b bb dd d d d dd e e e d d d dd e e e ¨ ¨¨ dd e e e e e e ¨¨¨ dd e e e e e e e e e e e e b b b b dd b b bb b b b b bb b dd dd Obr. 4.11: Les Stromy lze charakterizovat různými způsoby. V následujícím tvrzení uve- deme některé nutné a dostatečné podmínky toho, aby graf byl stromem. 4.3 Věta. Bud'[U, H] konečný graf. Pak jsou následující tvrzení ekvivalentní: 4. Stromy 23 (a) [U, H] je strom. (b) Mezi každými dvěma uzly v [U, H] existuje právě jedna cesta. (c) [U, H] je souvislý a platí |H| = |U| - 1. (d) [U, H] neobsahuje kružnici a |H| = |U| - 1. Důkaz. Dokážeme postupně implikace (a)(b), (b)(c), (c)(d), (d)(a). (a) (b): Strom [U, H] je souvislý, takže podle věty 3.6 existuje mezi každými dvěma uzly alespoň jedna cesta. Potřebujeme proto pouze dokázat, že nemohou existovat dva uzly, mezi nimiž je více cest. To je však zřejmé. Kdyby totiž existovaly uzly u, v U, mezi nimiž by existovaly dvě různé cesty, pak by zřejmě v [U, H] existovala kružnice, což podle definice stromu není možné. (b) (c): Existuje-li mezi každými uzly u, v U cesta, je [U, H] souvislý. Zbývá tedy pouze dokázat rovnost |H| = |U| - 1. Důkaz provedeme indukcí vzhledem k |U|. Pro |U| = 1 je tvrzení zřejmé. Necht'tedy uvedená rovnost platí pro všechny grafy splňující (b) s počtem uzlů nejvýše n. Necht'[U, H] je graf splňující (b) takový, že |U| = n + 1. Bud'uv H libovolná hrana. Graf [U, H - {xy}] není souvislý a zřejmě má právě dvě komponenty (jsou to U(x) a U(y)). Podle indukčního předpokladu je v každé z těchto komponent počet hran o jedničku menší než počet uzlů. V grafu [U, H - {xy}] je tedy n - 1 hran, tj. v grafu [U, H] je n = |U| - 1 hran, což jsme chtěli dokázat. (c) (d): Necht'graf [U, H] splňuje podmínku (c). Potřebujeme dokázat, že v tomto grafu neexistuje kružnice. Připust'me tedy, že v grafu [U, H] kruž- nice existuje. Je-li xy H libovolná hrana ležící na této kružnici, pak jejím vynecháním vznikne souvislý graf [U, H - {xy}]. (Souvislost tohoto grafu je zřejmá; libovolné dva uzly dovedeme v tomto grafu jistě spojit vhodným sledem, roli hrany xy v případě potřeby supluje zbylá část kružnice.) Kdyby v grafu [U, H - {xy}] opět existovala nějaká kružnice, vynecháme v ní rovněž některou hranu. Po konečném počtu kroků obdržíme souvislý graf neobsahu- jící žádnou kružnici, tj. strom. Počet hran v tomto stromu je však menší než |U| - 1, nebot'tolik hran měl podle předpokladu graf [U, H]. To je však spor, nebot'jsme již dokázali, že (a)(c), tj. strom obsahuje nutně |U| - 1 hran. (d) (a): Potřebujeme dokázat, že graf splňující (d) je nutně souvislý. Předpokládejme tedy, že graf [U, H] splňuje podmínku (d) a není souvislý. Pak je tvořen komponentami G1, . . . , Gn (n 2). Každá z těchto komponent je stromem (nebot' [U, H] je podle (d) les). Označme Gi = [Ui, Hi]. Protože (a)(c), platí |Hi| = |Ui| - 1 pro i = 1, . . . , n. Odtud |H| = n i=1 |Hi| = n i=1 (|Ui| - 1) = |U| - n, 24 I. TEORIE GRAFŮ kde n 2. To je však spor, nebot'podle předpokladu platí |H| = |U| - 1. ˇ 4.4 Věta. Každý strom s alespoň dvěma uzly obsahuje alespoň dva uzly prvního stupně. Důkaz. Bud'[U, H] strom, |U| 2. Podle vět 2.8 a 4.3 platí xU st x = 2 |H| = 2 (|U| - 1) = 2 |U| - 2. Přitom st x 1 pro každý uzel x U. Kdyby alespoň dva uzly neměly stupeň 1, bylo by číslo xU st x větší než 2 |U| - 2. ˇ 4.5 Příklad. Bud'n 2 libovolné přirozené číslo. Pak jistě existuje strom o n uzlech, který obsahuje právě dva uzly 1. stupně. Takový strom se nazývá had. Pro n 3 může ve stromu o n uzlech evidentně existovat nejvýše n - 1 uzlů 1. stupně. Strom, který má právě n - 1 uzlů 1. stupně (z celkového počtu n), se nazývá hvězda. Na obr. 4.12a je had a na obr. 4.12b hvězda pro n = 6. (a) (b) Obr. 4.12: Had a hvězda V definici 2.4 jsme definovali faktor grafu [U, H] jako podgraf, jehož množina uzlů je rovněž U. V dalším nás budou zajímat podgrafy a faktory bez kružnic. 4.6 Definice. Kostrou grafu [U, H] rozumíme takový faktor [U, H1], který je stromem. 4.7 Příklad. (a) Graf z obr. 2.9 obsahuje tři kostry, které jsou znázorněny na obr. 4.13. (b) Kružnice délky n zřejmě obsahuje n koster; každá kostra vznikne vy- necháním právě jedné hrany. (c) Strom obsahuje právě jednu kostru ­ sebe sama. 4. Stromy 25 Obr. 4.13: Kostry grafu z obr. 2.9 Nyní je přirozená otázka, které grafy kostru obsahují. Protože kostra grafu je souvislý podgraf, nemůže samozřejmě kostru obsahovat graf, který sám není souvislý. Jak je tomu v souvislých grafech uvádí následující tvrzení. 4.8 Věta. Každý konečný souvislý graf obsahuje alespoň jednu kostru. Důkaz. Bud'[U, H] konečný souvislý graf. V tomto grafu jistě existuje nějaký podgraf, který je stromem. Stačí totiž zvolit libovolný uzel x U a podgraf [{x}, ] je strom. Označme S množinu všech stromů v [U, H]. Protože je graf [U, H] konečný, obsahuje pouze konečně mnoho podgrafů, takže tím spíše je i množina S konečná (a víme, že neprázdná). Protože S je konečná, obsahuje alespoň jeden maximální prvek (tj. strom, který není podgrafem žádného jiného stromu). Bud'tedy [U , H ] některý maximálníprvek v S. Zřejmě stačídokázat, že U = U (pak je totiž [U , H ] faktor a tedy kostra v [U, H]). Připust'me, že je U = U , tj. existuje y U - U . Zvolme x U libovolně. Protože je [U, H] souvislý, existuje v něm cesta z x do y. V této cestě pak ale nutně existuje alespoň jedna hrana vw H taková, že v U , w U . Pak je ale zřejmě [U {w}, H {vw}] strom v [U, H]. (Souvislost je zřejmá, nebot'[U , H ] je souvislý; přidáním hrany vw jsme přitom evidentně nemohli uzavřít žádnou kružnici.) To je však spor, nebot'[U , H ] je vlastním podgrafem takto vzniklého stromu a tak není maximální v S. ˇ V příkladu 4.7 jsme viděli, že graf může mít více koster. Proto je přirozená otázka, jak určit počet koster daného grafu. Jeden ze základních poznatků v tomto směru dokázal již v roce 1899 Cayley. 4.9 Věta. Počet koster v úplném grafu Kn je roven číslu nn-2 . Důkaz. Důkaz tohoto tvrzení nebudeme provádět. ˇ 26 I. TEORIE GRAFŮ 4.10 Poznámka. Jak v dalším uvidíme, je zdánlivě jednoduchý postup, totiž postupné prověřování všech možností, již u poměrně ,,malých" grafů prakticky neuskutečnitelný (i při použití počítačů). Obecná metoda, pro praktický výpočet však nepříliš pohodlná, je založena na výpočtu determinantu vytvořeného z tzv. Laplaceovy matice sousednosti daného grafu. Tato matice je definována následovně: Je-li [U, H] konečný graf, U = {1, . . . , n}, je příslušná matice (aij )n i, j=1 definována takto: aij = -1, jestliže i j H, st i, jestliže i = j, 0, jestliže i = j, i j H. 4.11 Poznámka. S určováním počtu koster v daném grafu úzce souvisí pro- blém, kolik vlastně existuje grafů na dané množině uzlů. Takto zformulovaná otázka je ovšem jednoduchá. Je-li [U, H] graf na n uzlech, je podle definice H P2(U), přičemž víme, že |P2(U)| = n 2 . Všech grafů s množinou uzlů U je tedy tolik, kolik má množina P2(U) podmnožin. Označíme-li gn počet grafů na n uzlech, platí podle uvedeného gn = 2(n 2). Jak rychle roste posloupnost (gn) n=1, plyne z následující tabulky: n 1 2 3 4 5 6 7 8 . . . gn 1 2 8 64 1 024 32 768 2 097 152 2 684 354 544 . . . Nyní je snad zřejmé, proč řešení grafových úloh nakreslením nebo vypsá- ním ,,všech možností" nemá ve většině případů naději na úspěch. Určování počtu grafů na n uzlech je však přirozené následujícím způsobem ,,zkomplikovat". Z právě uvedené tabulky plyne, že na třech uzlech existuje celkem 8 grafů. Všechny tyto grafy jsou uvedeny na obr. 4.14. Z uvedeného obrázku je patrné, že některé z uvedených 8 grafů jsou si natolik ,,podobné", že je nerozlišíme, pokud se nedíváme na označení uzlů. (Čtenář si jistě okamžitě uvědomil, že jde o grafy nakreslené ,,pod sebou".) Tuto ,,podobnost" nyní precizujme. 4. Stromy 27 Obr. 4.14: Grafy na třech uzlech 4.12 Definice. Bud'te [U1, H1], [U2, H2] grafy. Zobrazení f : U1 U2 se nazývá izomorfismus grafu [U1, H1] na graf [U2, H2], když platí: 1. f je bijekce, 2. xy H1 právě tehdy, když f (x) f (y) H2. Dva grafy jsou izomorfní, když mezi nimi existuje alespoň jeden izomorfis- mus. Čtenář si jistě okamžitě uvědomuje, že izomorfismus je ekvivalence na třídě všech grafů. V jistém slova smyslu důležitější než otázka, kolik existuje na n uzlech všech grafů, je problém, kolik na n uzlech existuje neizomorfních grafů. Tak například na čtyřech uzlech existuje 64 grafů, avšak jen 11 neizomorních grafů, jak je patrno z obr. 4.15. Odvození metody pro výpočet počtu hn neizomorfních grafů na n uzlech přesahuje naše možnosti. (Je to tzv. Pólyova enumerační metoda.) Existuje však jednoduchý odhad pro čísla hn; je totiž zřejmé, že platí hn 2(n 2) n! , nebot' na n-prvkové množině jistě existuje nejvýše n! vzájemně izomorfních grafů. Uvedený odhad je při své jednoduchosti pro velká n velmi přesný. Lze 28 I. TEORIE GRAFŮ Obr. 4.15: Neizomorfní grafy na čtyřech uzlech totiž dokázat, že lim n hn - 2(n 2) n! = 0. I posloupnost (hn) n=1 roste ,,velmi rychle", jak lze vyčíst z následující tabulky: n 1 2 3 4 5 6 7 8 9 . . . hn 1 2 4 11 34 156 1 034 12 344 308 168 . . . Dokonce i počet tn neizomorfních stromů na n uzlech (při veškeré ,,jedno- duchosti" stromů) roste pořád ještě tak rychle, že i jejich systematický přehled pro poměrně malá n je nemožný (viz tabulku na straně 75). 4. Stromy 29 Jak jsme uvedli již ve větě 4.8, obsahuje každý konečný souvislý graf alespoň jednu kostru. Viděli jsme, že kostra grafu obecně není určena jedno- značně. Uvědomme si však, že podle věty 4.3 mají všechny kostry stejný počet hran (roven početu uzlů zmenšený o jedničku). Abychom konečně uviděli nějakou aplikaci teorie grafů, budeme se nyní zabývat hledáním vhodných koster v tzv. ohodnocených grafech. K tomu však potřebujeme nejprve následující definici. 4.13 Definice. Necht' je [U, H] graf. Bud' dáno zobrazení f : H R (respektive f : U R). Trojici [U, H, f ] nazýváme hranově ohodnocený (respektive uzlově ohodnocený) graf. Číslo f (t) nazýváme ohodnocení hrany (respektive uzlu) t. 4.14 Definice. Bud' [U, H, f ] hranově ohodnocený konečný souvislý graf. Kostra [U, H ] grafu [U, H] se nazývá minimální kostra v [U, H, f ], když pro každou kostru [U, H1] grafu [U, H] platí hH f (h) hH1 f (h). 4.15 Poznámka. Protože konečný souvislý graf obsahuje pouze konečně mnoho koster, obsahuje nutně každý konečný souvislý hranově ohodnocený graf alespoň jednu minimální kostru. Současně je evidentní, že minimální kostra obecně není jednoznačně určena. 4.16 Příklad. Bud'dána množina měst A, B, C, D, E, F. V tabulce 4.2 necht'jsou uvedeny náklady na vybudování železnice mezi jednotlivými městy (v milió- nech Kč). Naším úkolem je nyní navrhnout mezi uvedenými městy železniční sít' tak, aby každá dvě města byla vzájemně po železnici dosažitelná a aby přitom náklady na vybudování železnice byly minimální. Grafová formulace zadané úlohy je jednoduchá. Naším úkolem je zřejmě nalezení minimální kostry v úplném grafu K6 s uzly A, B, C, D, E, F, jehož hranové ohodnocení je dáno uvedenou tabulkou. Ke konkrétnímu řešení této úlohy se vrátíme za chvíli. Uvědomme si, že v zadaném případě bychom pravděpodobně minimální kostru našli poměrně brzy i bez nějaké teorie. V komplikovanějším případě je však nalezení mi- nimální kostry bez znalosti vhodného algoritmu velmi obtížné. Proto si nyní 30 I. TEORIE GRAFŮ A B C D E F A 0 13 27 18 5 30 B 13 0 7 18 4 12 C 27 7 0 3 8 11 D 18 18 3 0 9 24 E 5 4 8 9 0 15 F 30 12 11 24 15 0 Tab. 4.2: Náklady na vybudování železnice mezi městy jednoduchý algoritmus pro konstrukci minimální kostry uvedeme. (První algo- ritmus pro nalezeníminimálníkostry nalezl již v r. 1926 O. Borůvka. Podrobněji o historii tohoto algoritmu viz např. v [7]). 4.17 Věta. Algoritmus pro hledání minimální kostry: Bud'[U, H, f ] konečný souvislý hranově ohodnocený graf. Všechny hrany sestavme do posloupnosti (h1, . . . , hn) tak, aby posloupnost ( f (h1), . . . , f (hn)) byla neklesající. (Takové uspořádání hran vzhledem ke konečnosti grafu jistě existuje i když obecně není určeno jednoznačně.) Požadovaný algoritmus nyní můžeme popsat takto: (1) Polož H0 = , i = 1. (2) Obsahuje graf [U, Hi-1 {hi}] kružnici? Pokud ano, přejdi k bodu (4). Pokud ne, přejdi k bodu (3). (3) Polož Hi = Hi-1 {hi}. Přejdi k bodu (5). (4) Polož Hi = Hi-1. (5) Je i = n? Pokud ano, pokračuj podle bodu (6). Pokud ne, přejdi k bodu (8). (6) Polož Hi = K. (7) KONEC. [U, K] je minimální kostra. (8) Zvětši hodnotu i o jedničku a vrat'se k bodu (2). Popsaným způsobem skutečně v [U, H] sestrojíme minimálníkostru [U, K]. 4. Stromy 31 To, že [U, K] je kostra, je evidentní. Nyní je však nutno dokázat, že tato kostra je minimální, tj. že pro každou kostru [U, L] v [U, H] platí hK f (h) hL f (h). Tento důkaz nebudeme provádět. Jednoduše jej lze provést například po- mocí teorie tzv. matroidů, o nichž v tomto textu nehovoříme. Ř ešení příkladu 4.16. Hrany grafu K6 uspořádáme do vhodné posloupnosti například následovně: (CD, BE, AE, BC, CE, DE, CF, BF, AB, EF, AD, BD, DF, AC, AF). Ohodnocení příslušných hran tvoří posloupnost (3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 18, 18, 24, 27, 30). Nyní podle algoritmu do kostry postupně vybereme hrany CD, BE, AE, BC, CF. (Viz obr. 4.16.) (Víme, že kostra musí obsahovat 5 hran.) A B DE F C A B DE F 7 3 11 4 5 C Obr. 4.16: Minimální kostra Minimální náklady na železniční sít'jsou tak 30 milionů Kč. 4.18 Příklad. Na obr. 4.17a je hranově ohodnocený graf, na obr. 4.17b jeho minimální kostra. Ponecháme čtenáři, aby si promyslel, zda je tato minimální kostra určena jednoznačně. POZNÁ MKY A CVIČENÍ 1. Najděte sedm neizomorfních podgrafů grafu K3. 32 I. TEORIE GRAFŮ 8 8 12 7 5 10 9 2 5 12 6 5 5 4 Obr. 4.17: Minimální kostra v ohodnoceném grafu 5 Mosty, artikulace a některé grafové charakteristiky V předcházejícím paragrafu jsme hovořili převážně o grafech neobsahujících žádnou kružnici. ,,Většina" grafů však pochopitelně kružnice obsahuje. V řadě úvah o grafech je nutno hrany rozlišovat podle toho, zda leží na nějaké kružnici nebo nikoliv. 5.1 Definice. Hrana grafu se nazývá most, když neleží na žádné kružnici. 5.2 Příklad. (a) Ve stromu je každá hrana mostem. (b) Graf na obr. 5.18 obsahuje právě jeden most ­ hranu xy. x y Obr. 5.18: Graf s jediným mostem 5. Mosty, artikulace a některé grafové charakteristiky 33 5.3 Věta. Bud'xy most v souvislém grafu [U, H]. Pak je graf [U, H - {xy}] nesouvislý a má právě dvě komponenty. Důkaz. V grafu [U, H - {xy}] neexistuje sled mezi uzly x, y, takže tento graf je nesouvislý. Množina uzlů se rozpadne evidentně na dvě disjunktní množiny U(x) a U(y) (při označení z definice 3.12). ˇ 5.4 Důsledek. Každá kostra konečného souvislého grafu obsahuje všechny mosty tohoto grafu. 5.5 Definice. Ř ekneme, že uzel x U grafu [U, H] je artikulace, když existují hrany xy, xz H, xy = xz, které neleží současně na žádné kružnici. 5.6 Příklad. (a) Ve stromu je artikulací každý uzel, jehož stupeň je alespoň 2. (b) Graf na obr. 5.19 má právě jednu artikulaci ­ uzel x. a b c de x Obr. 5.19: Graf s jednou artikulací 5.7 Definice. Bud' G = [U, H] graf, uv H libovolná hrana. Množinu H(uv) H definujeme takto: je-li hrana uv mostem, je H(uv) = {uv}. Pokud uv mostem není, pak H(uv) = {xy H; existuje kružnice v G obsahující xy i uv }. Dále položme U(uv) = {t U; t inciduje s některou hranou z H(uv)}. Pak je zřejmě [U(uv), H(uv)] podgrafem grafu G. Tento podgraf nazýváme člen grafu G příslušný hraně uv. 34 I. TEORIE GRAFŮ 5.8 Příklad. Člen grafu z obr. 5.19 příslušný hraně ab je trojúhelník o vrcholech a, b, x, člen příslušný hraně cd je kružnice o vrcholech c, d, e, x. Bud'[U, H] graf a uv, xy jeho libovolné navzájem různé hrany takové, že H(uv) H(xy) = . Necht' například ab H(uv) H(xy). Pak v [U, H] existuje kružnice R1 obsahující hrany uv i ab. Necht' R1 = [U1, H1], R2 = = [U2, H2]. Podle předpokladu je |U1 U2| 2, nebot'a, b U1 U2. Bud'te r, s U1 U2 libovolné navzájem různé uzly. Pak existuje v R1 cesta z r do s obsahující hranu uv. Protože U1 U2 je konečná množina, existují prvky r0, s0 U1 U2 takové, že délka uvedené cesty je minimální. Označme tuto minimální cestu C1. Protože však r0, s0 U2, existuje mezi r0, s0 cesta C2 v R2 obsahující hranu xy. Spojením cest C1 a C2 však zřejmě v [U, H] obdržíme kružnici obsahující hranu uv i hranu xy. To však znamená, že xy H(uv) a současně uv H(xy). Odtud plyne H(uv) = H(xy). Právě jsme tak dokázali, že pro dvě hrany uv, xy H platí bud'to H(uv) H(xy) = nebo H(uv) = H(xy). Protože pro libovolnou hranu uv H platí uv H(uv), je H(uv) = . Odtud celkem plyne 5.9 Věta. Systém množin {H(uv); uv H} tvoří rozklad na množině H. Zatímco komponenty grafu tvoří disjunktní podgrafy, členy grafu obecně disjunktní podgrafy daného grafu nejsou. Platí totiž 5.10 Věta. Uzel x je artikulací grafu [U, H] právě tehdy, když existují hrany xy = xz, z nichž každá patří do jiného členu grafu. Důkaz. Je-li x artikulace, pak existují hrany xy, xz neležící na jedné kružnici. Pak ale H(xy) = H(xz). Patří-li naopak hrany xy, xz různým členům grafu, neexistuje kružnice, která by obě hrany obsahovala. To však znamená, že x je artikulace. ˇ Důležitou charakteristikou grafů je tzv. ,,cyklomatické číslo", nazývané též Bettiho číslo daného grafu. 5.11 Definice. Bud'G = [U, H] konečný graf. Cyklomatickým číslem grafu nazýváme číslo (G) = |H| - |U| + k, kde k je počet komponent grafu G. 5.12 Věta. Cyklomatické číslo každého konečného grafu je nezáporné. 5. Mosty, artikulace a některé grafové charakteristiky 35 Důkaz. Bud'[U, H] konečný souvislý graf, tj. k = 1. Podle věty 4.8 existuje v [U, H] kostra [U, H1]. Podle věty 4.3 platí |H1| = |U| - 1. Protože |H1| |H|, plyne odtud |H| |U| - 1, tj. |H| - |U| + 1 0. (b) Necht' [U, H] je konečný nesouvislý graf s komponentami [U1, H1], . . . , [Uk, Hk]. Podle (a) pro každé i = 1, 2, . . . , k platí |Hi| - |Ui| + + 1 0, takže k i=1 (|Hi| - |Ui| + 1) = |H| - |U| + k 0. ˇ Z důkazu věty 5.12 a věty 4.3 okamžitě plyne 5.13 Věta. Cyklomatické číslo konečného grafu je rovno nule právě tehdy, když je tento graf lesem. 5.14 Poznámka. Z výše uvedeného je zřejmé, že cyklomatické číslo grafu udává v jistém smyslu ,,míru složitosti" tohoto grafu. Názorně řečeno, (G) udává, kolik hran je v G nutno odstranit, aby v G nezůstala žádná kružnice. Tak jsme výše popsaným způsobem charakterizovali, alespoň v jistém smyslu, ,,složitost" grafu. Je samozřejmě účelné umět vhodným způsobem popsat i jiné grafové charakteristiky. Ukažme si takovou charakteristiku alespoň na případě souvislosti grafů. Elementární odhad ,,míry souvislosti" grafu je evidentní ­ touto mírou je počet komponent. Popis ,,míry souvislosti" souvislého grafu je komplikova- nější, i když čtenář patrně má jistou intuitivní představu o tom, co to znamená, že jeden graf je ,,souvislejší" než druhý. 5.15 Definice. Bud' G = [U, H] souvislý graf. Množina A U se nazývá uzlový řez grafu [U, H], jestliže se souvislost grafu poruší, vyškrtneme-li z [U, H] všechny uzly množiny A a všechny hrany, které s těmito uzly incidují. (Tj. graf [U - A, H - {xy H; xy A = }] je nesouvislý.) Uzlový stupeň souvislosti u(G) grafu G je minimální mohutnost uzlového řezu v G. 5.16 Poznámka. Podle definice 5.15 lze určit uzlový stupeň souvislosti kaž- dého konečného souvislého grafu kromě úplných grafů Kn (promyslete si, 36 I. TEORIE GRAFŮ které hrany musíme podle definice 5.15 vyškrtnout!). Pro tyto grafy definito- ricky klademe u(Kn) = n - 1. Podobně jako uzlový se definuje i hranový stupeň souvislosti. 5.17 Definice. Bud'G = [U, H] souvislý graf. Množina H1 H se nazývá hranový řez v G, je-li graf [U, H - H1] nesouvislý. Hranový stupeň souvislosti h(G) grafu G je minimální mohutnost hranového řezu v G. 5.18 Poznámka. Podle definice 5.17 lze určit h(G) pro každý konečný souvislý graf kromě grafu K1 (tj. grafu o jednom uzlu). Pro tento graf definitoricky klademe h(K1) = 0. 5.19 Příklad. Pro graf G na obr. 5.20a platí u(G) = 2, h(G) = 3. Jeden z minimálních uzlových řezů je vyznačen plnými kroužky, jeden z minimálních hranových řezů je vyznačen tučnými hranami. Na obr. 5.20b, respektive 5.20c, je graf vzniklý ,,odstraněním" příslušného uzlového, respektive hranového, řezu. (a) (b) (c) Obr. 5.20: Hranový a uzlový řez v grafu 5.20 Věta. Bud'G = [U, H] konečný souvislý graf. Pak platí u(G) h(G) min {st x; x U}. Důkaz. Je-li h(G) = 0, je také u(G) = 0, nebot' G je v tom případě K1. Je-li h(G) = 1, existuje hrana xy H taková, že [U, H - {xy}] je nesouvislý graf. 5. Mosty, artikulace a některé grafové charakteristiky 37 Pak je však zřejmě G = K2 (a tedy u(G) = 1 podle poznámky 5.16) nebo je {x}, respektive {y} uzlový řez v G (takže opět u(G) = 1). Předpokládejme proto, že h(G) > 1. Bud' H1 hranový řez, |H1| = h(G). Zvolme hranu h H1 libovolně. Na každé další hraně e H1 zvolme uzel xe tak, že xe není incidentní s hranou h. Nyní z grafu G odečteme všechny uzly xe (e H1 - {h}) a hrany s těmito uzly incidentní. Je-li takto vzniklý graf nesouvislý, platí u(G) < h(G). V opačném případě obdržíme nutně uzlový řez, přidáme-li k uzlům xe ještě jeden z uzlů tvořících hranu h. Pak ale u(G) = h(G). Dokázali jsme tak, že u(G) h(G). Druhá nerovnost ve větě je však zřejmá, nebot'pro každý uzel x U tvoří množina všech hran incidentních s x evidentně hranový řez. ˇ Ve větě 2.8 jsme dokázali, že v konečném grafu [U, H] platí xU st x = = 2 |H|. Odtud však okamžitě plyne, že min {st x; x U} 2|H| |U| . Z této nerovnosti a z věty 5.20 plyne důsledek. 5.21 Důsledek. Bud'G = [U, H] konečný souvislý graf. Pak h(G) 2 |H| |U| . Pro uzlovou i hranovou souvislost jsou známy významné charakterizační věty (Mengerova a Fordova-Fulkersonova). Vzhledem k jejich závažnosti v řadě aplikací je uvedeme, i když jejich důkazy přesahují rámec našeho textu. K formulaci těchto vět však potřebujeme následující jednoduchou definici. 5.22 Definice. Graf G se nazývá uzlově, respektive hranově k-souvislý, jestliže platí u(G) k, respektive h(G) k. 5.23 Věta. (Mengerova věta.) Graf G je uzlově k-souvislý právě tehdy, když pro každé dva uzly x, y existuje k cest z x do y, které jsou až na uzly x, y vzájemně disjunktní. 5.24 Důsledek. Graf G je uzlově 2-souvislý právě tehdy, když ke každým dvěma uzlům x, y existuje kružnice v G, která je obsahuje. 5.25 Věta. (Fordova-Fulkersonova věta.) Graf G je hranově k- souvislý právě tehdy, když pro každé dva uzly x, y existuje k cest z x do y, které jsou hranově disjunktní. 38 I. TEORIE GRAFŮ 6 Eulerovské a hamiltonovské grafy Kreslení obrázků ,,jedním tahem" je obvyklou součástí tzv. rekreační matema- tiky. Pravděpodobně každý čtenář si již jako dítě vyzkoušel, že ,,domeček" na obr. 6.21a lze jedním tahem nakreslit; a snadno lze ověřit, že obr. 6.21b jedním tahem nakreslit nelze. (a) (b) Obr. 6.21: Kreslení grafů jedním tahem Jak jsme uvedli již v paragrafu 1, vyřešil tuto problematiku již v 18. století Euler v souvislosti s problémem sedmi mostů města Královce. Připomeňme si ještě, že ,,tah" v grafu jsme definovali v definici 3.4. 6.1 Definice. Ř ekneme, že graf G lze sestrojit jedním tahem, když v G existuje tah obsahující všechny hrany tohoto grafu. V dalším udáme popis všech grafů, které lze jedním tahem sestrojit. 6.2 Definice. Konečný graf bez izolovaných uzlů, jehož každý uzel je sudého stupně, se nazývá eulerovský. 6.3 Věta. Každý uzel eulerovského grafu je obsažen alespoň v jedné kružnici. Důkaz. Bud' [U, H] eulerovský graf, x U libovolný uzel. Protože x není izolovaný, existuje hrana xy s tímto uzlem incidentní. Tato hrana však nemůže být mostem, nebot' v tom případě by podle věty 5.3 graf [U, H - {xy}] byl nesouvislý a komponenta obsahující bod x by obsahovala jediný uzel lichého 6. Eulerovské a hamiltonovské grafy 39 stupně (totiž uzel x). To však podle věty 2.11 není možné. Odtud plyne, že hrana xy leží na nějaké kružnici, a tedy i x leží na kružnici. ˇ 6.4 Věta. Konečný souvislý graf lze sestrojit jedním uzavřeným tahem právě tehdy, když je tento graf eulerovský. Důkaz. I. Lze-li konečný graf sestrojit jedním uzavřeným tahem, je tento graf nutně souvislý. V uzavřeném tahu přitom z každého uzlu tolikrát vystoupíme, kolikrát jsme do něj vstoupili. Je tedy stupeň každého uzlu sudý. II. Bud'G = [U, H] souvislý eulerovský graf. Dokážeme, že G lze sestrojit jedním uzavřeným tahem. Zvolme libovolně uzel u U. Podle věty 6.3 leží tento uzel na nějaké kruž- nici, přičemž kružnice je uzavřeným tahem v G. Množina A všech uzavřených tahů obsahujících uzel u je tedy neprázdná. Protože je A konečná, obsahuje tahy maximální délky. Necht'tedy 0 A je některý tah maximální délky. Předpokládejme nyní, že existuje hrana xy H, která není obsažena v tahu 0. Označme H = {xy H; xy není obsažena v tahu 0}, U = {x U; existuje y U tak, že xy H }. Pak je [U , H ] podgraf grafu G. Z definice grafu [U , H ] je přitom okamžitě zřejmé, že je to eulerovský graf. Protože je G souvislý, existuje nutně uzel v U , který je obsažen v tahu 0. Protože je [U , H ] eulerovský, je uzel v obsažen v nějaké kružnici C grafu [U , H ]. Když nyní v G utvoříme sled začínající v u, pokračujeme v něm až do uzlu v, nyní projdeme kružnici C až do uzlu v a pak dokončíme tah 0 až do uzlu u, vytvoříme v G uzavřený tah obsahující uzel u, jehož délka je větší než délka tahu 0. To je však spor s definicí 0. To znamená, že H = , a tak 0 obsahuje všechny hrany. ˇ Pomocí věty 6.4 nyní snadno popíšeme i ty grafy, které lze sestrojit jedním otevřeným tahem. 6.5 Věta. Bud'G konečný souvislý graf. Pak lze G sestrojit jediným otevřeným tahem právě tehdy, když G obsahuje právě dva uzly lichého stupně. Obsahuje-li G právě dva uzly lichého stupně, pak otevřený tah v jednom z těchto uzlů nutně začíná a ve druhém končí. Důkaz. I. Necht'lze souvislý graf G sestrojit jedním otevřeným tahem začína- jícím v uzlu x a končícím v uzlu y. Pak jsou uzly x, y evidentně lichého stupně a všechny ostatní uzly jsou stupně sudého. 40 I. TEORIE GRAFŮ II. Necht'G = [U, H] je konečný souvislý graf obsahující právě dva uzly x, y lichého stupně. Bud' z U libovolný prvek. Položme U1 = U {z}, H1 = H {xz, yz}. Pak je [U1, H1] souvislý eulerovský graf, takže podle věty 6.4 lze tento graf sestrojit jedním uzavřeným tahem. Uvažme takový uzavřený tah; jistě můžeme předpokládat, že začíná a končí v uzlu z. Když nyní z tohoto tahu ,,vyškrtneme" hrany xz, yz, dostaneme zřejmě požadovaný otevřený tah. ˇ Jak si čtenář jistě mnohokrát povšimnul i v jiných matematických dis- ciplínách, lze tutéž skutečnost často popsat na první pohled zcela odlišnými způsoby. Samozřejmě, že je tomu tak i v teorii grafů. Proto i tak jednodu- chá tvrzení jako jsou věty 6.4 a 6.5 lze v literatuře najít ve zcela odlišných formulacích. Ukažme si to alespoň na jednom příkladu. 6.6 Definice. Jsou-li [U, H], [U1, H1] grafy, nazveme zobrazení f : U U1 homorfismem grafu [U, H] do grafu [U1, H1], jestliže pro každou hranu xy H platí, že f (x) f (y) H1 (tj. hrana se zobrazí na hranu). (Srovnej s definicí izomorfismu uvedenou v definici 4.12.) Vcelku snadno lze dokázat následující tvrzení, jehož důkaz přenecháme čtenáři. 6.7 Věta. Souvislý graf [U, H] je eulerovský právě tehdy, když je homorfním obrazem kružnice délky |H|. Přeformulování vět 6.4 a 6.5 je nyní zřejmé. Problematika, kterou se nyní budeme zabývat, jakkoliv je jednou z nej- komplikovanějších částí teorie grafů, má svůj prapůvod v hříčce, kterou v roce 1859 vymyslel irský matematik W. R. Hamilton (známý především objevem tzv. kvaternionů). Jak dobře víme, jedním z pěti pravidelných mnohostěnů je pravidelný dvanáctistěn, jehož povrch je tvořen shodnými pětiúhelníky. (O pravidelných mnohostěnech budeme podrobněji hovořit v poznámce 7.17.) Povrch tohoto dvanáctistěnu rozvinutý do roviny je na obr. 6.22a. Hamilton připojil ke kaž- dému z dvaceti vrcholů tohoto dvanáctistěnu jméno některého světového vel- koměsta a 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, každým z dalších měst se projde právě jednou a cestovatel se nakonec vrátí do výchozího města. Grafová formulace tohoto ,,hlavolamu" je evidentní. Je dán graf o 20 uzlech (vrcholy dvanáctistěnu), hrany grafu odpovídají hranám dvanáctistěnu (jak 6. Eulerovské a hamiltonovské grafy 41 v paragrafu 7 odvodíme, je těchto hran 30) a naším úkolem je v tomto grafu najít kružnici procházející všemi uzly. Na obr. 6.22b je znázorněno jedno z řešení. Hrany ležící na kružnici jsou vytaženy silněji. (Graf 6.22b jsme již viděli na obr. 2.8a.) (a) (b) Obr. 6.22: Povrch dvanáctistěnu Nyní uved'me standardní terminologii. 6.8 Definice. Graf se nazývá hamiltonovský, když v něm existuje kružnice procházející všemi uzly. Tato kružnice se nazývá hamiltonovská. 6.9 Poznámka. (a) V definici 2.13 jsme definovali pravidelný graf. Faktor, který je pravidelným grafem, nazýváme pravidelným faktorem. Pravidelný faktor 2. stupně obvykle nazýváme kvadratickým faktorem. Můžeme tedy říci, že hamiltonovská kružnice je souvislý kvadratický faktor daného grafu. 42 I. TEORIE GRAFŮ (b) Graf na obr. 6.22b je hamiltonovský. Je však zřejmé, že existují grafy, které hamiltonovské nejsou. Takové jsou například všechny stromy; protože v nich neexistuje žádná kružnice, neexistuje v nich tím spíše kružnice hamil- tonovská. Jakkoliv se na první pohled může zdát problém charakterizace hamilto- novských grafů jednoduchý, není dodnes známa žádná nutná a dostatečná podmínka této skutečnosti. Před uvedením některých známých výsledků ještě uved'me jeden příklad. 6.10 Příklad. S Eulerovým jménem je spojována i následující úloha: Může jezdec projít šachovnici (o 64 polích) tak, aby každým polem prošel právě jednou a posledním tahem se vrátil na výchozí pole? Grafová formulace je snadná. Uvažujeme graf, jehož uzly jsou jednotlivá pole na šachovnici. Dva uzly jsou pak spojeny hranou právě tehdy, když jezdec může skočit z jednoho pole na druhé. Naším úkolem je nyní v tomto grafu najít hamiltonovskou kružnici ­ pokud ovšem existuje. Již dávno je známo, že popsaný graf je opravdu hamiltonovský. Dodnes se však například neví, kolik hamiltonovských kružnic vlastně v tomto grafu existuje. Nakreslit daný graf nemá smysl, nebot'obrázek by byl značně nepřehledný. Popsat v něm hamiltonovskou kružnici je však velmi jednoduché. Do polí schématicky znázorněné šachovnice vepíšeme čísla 1, 2, . . . , 64 v takovém pořadí, v jakém jimi bude jezdec postupně procházet. Ř ešení, které uvádíme v tabulce 6.3 (popsal je v roce 1862 šachista Jaenisch je mimořádně důvtipné tím, že je současně polomagickým čtvercem; součet čísel v každém řádku a každém sloupci je roven 260. 50 11 24 63 14 37 26 35 23 62 51 12 25 34 15 38 10 49 64 21 40 13 36 27 61 22 9 52 33 28 39 16 48 7 60 1 20 41 54 29 59 4 45 8 53 32 17 42 6 47 2 57 44 19 30 55 3 58 5 46 31 56 43 18 Tab. 6.3: Jaenischův polomagický čtverec Nyní tedy uved'me některé vlastnosti hamiltonovských grafů. Následující nutná podmínka plyne bezprostředně z důsledku 5.24. 6. Eulerovské a hamiltonovské grafy 43 6.11 Věta. Je-li G hamiltonovský graf, je jeho uzlový stupeň souvislosti u(G) 2. Snadno však lze ukázat, že podmínka z věty 6.11 není pro existenci hamil- tonovské kružnice postačující. Například graf na obr. 6.23 má uzlový stupeň souvislosti roven 2, je však snadné se přesvědčit, že není hamiltonovský. Obr. 6.23: Graf s u(G) = 2, který není hamiltonovský Nalezení dostatečných podmínek toho, aby graf byl hamiltonovský, bylo velmi obtížné. Jednu z nejznámějších odvodil v roce 1952 Dirac. 6.12 Věta. Necht'G = [U, H] je konečný graf, |U| = n 3 a st x n 2 pro každý uzel x U. Pak je G hamiltonovský. Důkaz. Uvědomme si nejprve, že každý konečný graf je podgrafem něja- kého hamiltonovského grafu. Zejména můžeme graf [U, H] doplnit o množinu uzlů V a o množinu hran {xy; x U, y V} na hamiltonovský graf. Je-li totiž U = {u1, . . . , un}, stačí položit V = {v1, . . . , vn} (kde U V = ) a hamiltonovskou kružnicí je zřejmě kružnice procházející postupně uzly u1, v1, u2, v2, . . . , un, vn, u1. Necht' nyní graf G = [U, H] splňuje předpoklady věty a připust'me, že není hamiltonovský. Označme k nejmenší možný počet uzlů, o které když doplníme spolu s hranami výše uvedeným způsobem graf G, tak obdržíme hamiltonovský graf G . Je-li U = {u1, . . . , un}, V = {v1, . . . , vk}, U = U V, H = H {uivj ; ui U, vj V}, je G = [U , H ]. V G tedy podle předpokladu existuje hamiltonovská kružnice C, procházející postupně uzly x1, x2, . . . , xm, kde m = n + k 4, nebot'podle předpokladu je n 3, k 1. Označení uzlů jistě můžeme zvolit tak, že x1 = u1, x2 = v1, x3 = u2 (tj. kružnice začíná ,,doplněnou" hranou). V H nyní nemůže být hrana x1x3 (= u1u2). Kdyby 44 I. TEORIE GRAFŮ totiž x1x3 H, bylo by doplnění grafu G o uzel x2 = v1 zbytečné a to je spor s minimalitou čísla k. Označme nyní K množinu hran z H , které neleží na kružnici C. Je-li x1xi K pro některé i = 3, pak x3xi+1 K, tj. x3xi+1 H , nebot' x3xi+1 jistě není hrana kružnice. Kdyby totiž x3xi+1 K, mohli bychom v G sestrojit kružnici procházející postupně uzly x1, xi , xi-1, xi-2, . . . , x3, xi+1, xi+2, . . . , x1. Tato kružnice je však hamiltonovská v grafu, který obdržíme z G odečte- ním uzlu x2 = v1 a všech hran s tímto uzlem incidentních. To je však spor s předpokladem, že k je nejmenší nutný počet dodaných uzlů. Nyní určíme, kolik je v K hran tvaru x1xi . Uvědomme si, že v G platí st u j n 2 + k pro každý uzel u j U. (V G je st u j n 2 , v G s uzlem u j navíc sousedí uzly v1, . . . , vk.) Protože v kružnici C sousedí s uzlem x1 dva uzly, je v K alespoň n 2 + k - 2 hran tvaru x1xi . Podle výše uvedeného to však znamená, že v H není minimálně n 2 +k -2 hran tvaru x3xj (kromě hran x3xi+1 pro x1xi K je to, jak již víme, ještě hrana x3x1.) Nyní uvažme, co všechno o uzlu x3 víme. Vychází z něho alespoň n 2 + k hran x3xi , přitom však v G nesousedí minimálně s n 2 + k - 1 uzly xi = x3. Protože však všech uzlů xi = x3 je n + k - 1, musí platit n 2 + k + n 2 + k - 1 n + k - 1. Odtud však plyne, že k 0, což je spor s předpokladem, že G není hamilto- novský, takže k 1. ˇ V roce 1960 odvodil norský matematik O. Ore ještě obecnější dostateč- nou podmínku existence hamiltonovské kružnice v daném grafu. Je okamžitě zřejmé, že Diracova věta je důsledkem následujícího Oreho tvrzení. 6.13 Věta. Bud' [U, H] konečný graf, |U| 3. Necht' pro každé dva uzly x, y U, které nejsou sousední, platí st x + st y |U| . Pak je graf [U, H] hamiltonovský. Důkaz. Důkaz tohoto tvrzení nebudeme provádět. ˇ 6.14 Poznámka. Jak jsme již uvedli, není dosud známa pro hamiltonovské grafy charakterizační věta, která by udávala nutnou a dostatečnou podmínku. Proto byly hledány takové podmínky alespoň pro některé důležité třídy grafů. 6. Eulerovské a hamiltonovské grafy 45 Dlouho byla například nevyřešena Taitova hypotéza, že každý rovinný uzlově 3-souvislý 3-pravidelný graf je již nutně hamiltonovský. (O rovinných grafech budeme podrobněji hovořit v paragrafu 7. Jsou to jednoduše řečeno grafy, které lze v rovině nakreslit tak, že se jejich hrany neprotínají.) Z platnosti Taitovy hypotézy by mimochodem plynulo kladné řešení problému čtyř barev ­ viz paragraf 7. V roce 1956 však jeden z nejvýznamnějších odborníků v teorii grafů W. T. Tutte uvedenou hypotézu vyvrátil. Tutteův protipříklad je uveden na obr. 6.24. Obr. 6.24: 3-souvislý 3-pravidelný nehamiltonovský graf Tutte však dokázal, že každý rovinný uzlově 4-souvislý graf je již nutně hamiltonovský. 6.15 Poznámka. Existuje-li v grafu cesta procházející všemi uzly, nazývá se tato cesta hamiltonovská. Graf, v němž existuje hamiltonovská cesta, se nazývá polohamiltonovský. Je zřejmé, že každý hamiltonovský graf je současně polohamiltonovský; stejně tak je evidentní, že obrácené tvrzení obecně neplatí. Například graf K2 je polohamiltonovský, avšak není hamiltonovský. POZNÁ MKY A CVIČENÍ 1. Najděte tři neizomorfní hamiltonovské grafy na čtyřech uzlech. 2. Najděte dva neizomorfní hamiltonovské grafy na pěti uzlech, které mají nejvýše šest hran. 3. Najděte v K7 tři hamiltonovské kružnice, v nichž je obsaženo všech 21 hran grafu K7. 46 I. TEORIE GRAFŮ 7 Rovinné grafy V průběhu dosavadního výkladu jsme sice grafy ,,kreslili", intuitivně je jistě každému čtenáři zřejmé, jak se toto kreslení provádí, avšak fakticky jsme se mohli bez tohoto kreslení obejít, nebot'žádná definice ani žádné tvrzení nebylo na tomto kreslení závislé. (I když je nutno si uvědomit, že právě možnost názorného kreslení je jedním z hlavních důvodů četnosti a rozmanitosti aplikací teorie grafů.) V tomto paragrafu však bude kreslení grafů hrát centrální roli. Proto je nutno některé pojmy precizovat. Nejprve však uzavřeme následující domluvu. 7.1 Dohoda. V celém paragrafu 7 pojem ,,graf" značí ,,konečný graf". 7.2 Definice. Bud' dán graf [U, H]. Nakreslení tohoto grafu (v rovině) vznikne tak, že uzly znázorníme jako body eukleidovské roviny E2 a hranu xy H znázorníme jako oblouk v E2 s koncovými body x, y. 7.3 Poznámka. (a) V teorii grafů se studují nakreslení grafů na různých plo- chách (například na sféře, na anuloidu apod.). Přes důležitost těchto nakreslení se v dalším budeme zabývat pouze nakreslením grafů v rovině. (b) Oblouk, jak známo, je topologický obraz úsečky. (Oblouk v rovině je tedy obraz intervalu [a, b] E1 při zobrazení f : E1 E2, které je prosté, spojité a má tu vlastnost, že inverzní zobrazení f -1 je rovněž spojité.) Protože oblouků mezi dvěma body x, y E2 existuje nekonečně mnoho, plyne odtud, že graf může mít v rovině nekonečně mnoho nakreslení. Na obr. 7.25a­d jsou oblouky mezi uzly x, y. Na obr. 7.25e je křivka s koncovými body x, y, která však není obloukem. (c) Grafy samozřejmě většinou kreslíme tak, že hrany znázorňujeme jako úsečky nebo jiné ,,jednoduše vyhlížející" křivky a nikoliv tak, jak je to pro- vedeno například na obr. 7.25d. Přesto má obecně graf nekonečně mnoho nakreslení, nebot'není jednoznačně předem dáno ani rozmístění uzlů v rovině. Ponecháme na čtenáři, aby si promyslel, že na obr. 7.26a­e je nakreslen tentýž graf. To, že je na výše uvedených obrázcích nakreslen jeden a tentýž graf, lze jinými slovy zformulovat tak, že každé dva grafy, které mají nakreslení na některém z obr. 7.26, jsou izomorfní. 7. Rovinné grafy 47 x y (a) x y (b) yx (c) x y (d) x y (e) Obr. 7.25: Křivky s koncovými body x, y Uvážíme-li, že na těchto obrázcích jsme kreslili jednoduchý graf na šesti uzlech, není jistě překvapující, že obecně rozeznat, zda dané dva grafy jsou izo- morfní, je jednou z nejtěžších otázek teorie grafů. Dodnes není znám efektivní algoritmus pro řešení tohoto problému. Při nakreslení grafu se hrany mohou, avšak nemusí, vzájemně křížit. Při některých úvahách a aplikacích je důležité zjistit, zda lze daný graf nakreslit tak, aby se hrany nekřížily. (Například v problematice tištěných spojů apod.) Tím je motivována následující definice. 7.4 Definice. Graf se nazývá rovinný (též planární), když existuje takové jeho nakreslení, že každé dvě různé hrany mají nejvýše jeden společný bod ­ uzel, který je případně s oběma hranami incidentní. Na první pohled je zřejmé, že například stromy nebo kružnice jsou ro- vinnými grafy. Dokázat, že nějaký graf je rovinný je však zřejmě jednodušší, než dokázat, že daný graf rovinný není. Častou hříčkou je například nalezení rovinného nakreslení grafu na obr. 7.26a. (Podle této známé rekreační úlohy se 48 I. TEORIE GRAFŮ (a) (b) (c) (d) (e) Obr. 7.26: Izomorfní grafy na šesti uzlech také tomuto grafu často říká tři domy a tři studně.) Jak v dalším uvidíme, nemá tato úloha řešení, nebot'graf na obr. 7.26a není rovinný. 7.5 Příklad. Graf K4 je rovinný, i když jeho ,,běžné" nakreslení je takové, že se hrany protínají (obr. 7.27a). Důležité totiž je, že existuje nakreslení, v němž se hrany neprotínají (obr. 7.27b). Tentýž graf lze však nakreslit ještě mnohem ,,elegantněji" (obr. 7.27c). Existence nakreslení grafu K4 z obr. 7.27c zákonitě vyplývá z následujícího tvrzení, které odvodil Wagner v roce 1936. Důkaz tohoto tvrzení nebudeme uvádět. 7.6 Věta. Graf je rovinný právě tehdy, když existuje jeho rovinné nakreslení takové, že všechny jeho hrany jsou znázorněny úsečkami. Jedním z nejdůležitějších tvrzení o rovinných grafech je tzv. Eulerova věta. K její formulaci však potřebujeme následující definici. 7.7 Definice. Bud'[U, H] rovinný souvislý graf. Bud'dáno některé jeho ro- vinné nakreslení. Označme W množinu všech oblastí, na něž je tímto nakres- lením rovina rozdělena (včetně ,,vnějšku"). Pak trojici [U, H, W] nazveme mapou. 7. Rovinné grafy 49 (a) (b) (c) Obr. 7.27: Různá nakreslení grafu K4 7.8 Poznámka. Oblast, jak známo, je otevřená souvislá množina. Například každá kružnice rozdělí rovinu na dvě oblasti ­ vnitřek a vnějšek. Mapa určená nakreslením grafu K4 na obr. 7.27c obsahuje 4 oblasti. Nakreslení téhož grafu na obr. 7.27a žádnou mapu neurčuje, nebot'uvedené nakreslení není rovinné. 7.9 Věta. (Eulerova věta.) Bud'[U, H, W] libovolná mapa. Pak |W| + |U| - |H| = 2. (7.1) Důkaz. Indukcí vzhledem k číslu |H|. Je-li H = , je nutně |U| = 1, nebot' graf [U, H] je souvislý. Pak ale |W| = 1 a rovnost 7.1 je splněna triviálně. Předpokládejme nyní, že rovnost 7.1 platí pro všechny mapy [U, H, W] takové, že |H| n. Bud'[U, H, W] mapa, |H| = n +1. Rozlišíme dva případy: (a) Graf [U, H] obsahuje most xy. Podle věty 5.3 je graf [U, H - {xy}] nesouvislý a má dvě komponenty [U1, H1], [U2, H2]. Protože |H1| n, |H2| n, platípodle indukčního předpokladu pro mapy [U1 , H1, W1] a [U2, H2, W2] |W1| + |U1| - |H1| = |W2| + |U2| - |H2| = 2. Dále platí |H1| + |H2| + 1 = |H| (nebot'od H jsme odečetli hranu xy) a |U1| + + |U2| = |U|. Odečtením mostu se v dané mapě počet oblastí nezměnil, avšak v součtu |W1|+|W2| je ,,vnějšek" započítán dvakrát. Proto |W1|+|W2| = |W|+1. Odtud celkem dostáváme: |W| + |U| - |H| = (|W1| + |W2| - 1) + (|U1| + |U2|) - - (|H1| + |H2| + 1) = (|W1| + |U1| - |H1|) + (|W2| + |U2| - |H2|) - 2 = = 2 + 2 - 2 = 2. 50 I. TEORIE GRAFŮ V případě, že [U, H] obsahuje most, je tak věta dokázána. (b) Necht'[U, H] neobsahuje most. Bud'h H libovolná hrana. Protože h není most, leží na nějaké kružnici. Označme C kružnici maximální délky, která obsahuje hranu h. Uvnitř kružnice C je nutně nějaká oblast, která vynecháním hrany h v mapě [U, H, W] zanikne. V mapě [U, H1, W1] vzniklé z mapy [U, H, W] odečtením hrany h je tedy o jednu hranu a jednu oblast méně než v mapě původní. Protože |H1| = n, platí pro mapu [U, H1, W1] rovnost 7.1, tj. |W1| + |U| - |H1| = 2. Odtud však plyne platnost 7.1 i pro mapu [U, H, W]. ˇ Pomocí Eulerovy věty lze snadno dokázat následující důležité tvrzení. 7.10 Věta. Graf K5 (tj. úplný graf na pěti uzlech) ani graf z obr. 7.26a (tj. graf ,,3 domy a 3 studně") není rovinný. Důkaz. (a) Připust'me, že graf K5 je rovinný. Necht'tedy [U, H, W] je mapa vzniklá některým jeho rovinným nakreslením. Platí |U| = 5, |H| = 10, tj. |W| = 2 + |H| - |U| = 7. Každá oblast přitom musí mít hranici alespoň ze tří hran a každá hrana odděluje alespoň dvě oblasti (protože v K5 neexistují mosty). Platí tak 2 10 3 |W| , tj. |W| < 7, což je spor. (b) Analogicky. Kdyby [U, H, W] byla mapa vzniklá rovinným nakresle- ním grafu ,,3 domy a 3 studně", platilo by v této mapě, |U| = 6, |H| = 9, tj. |W| = 5. Každá oblast je opět omezena alespoň třemi hranami. Každá kruž- nice v [U, H] má jistě sudou délku (pravidelně se v ní musí střídat ,,domy" a ,,studně"), takže každá kružnice má délku nejméně 4. Odtud plyne 2 9 4 |W| , tj. |W| < 5, což je spor. ˇ 7.11 Poznámka. Jak dokázal v roce 1930 významný polský matematik K. Ku- ratowski, hrají grafy z věty 7.10 v charakterizaci planárních grafů zcela zásadní roli (viz věta 7.16). Proto se těmto grafům často také říká Kuratowského grafy. Pro jejich důležitost si tyto grafy ještě jednou nakresleme (obr. 7.28), i když jsme se s nimi již nejednou setkali. 7.12 Definice. Bud' [U, H] libovolný graf, xy H jeho libovolná hrana. Bud' z U H libovolný prvek. Položme U = U {z}, H = (H - {xy}) {xz, yz}. Pak řekneme, že graf [U , H ] vznikl z grafu [U, H] půlením hrany xy. 7. Rovinné grafy 51 (a) (b) Obr. 7.28: Kuratowského grafy (a) (b) Obr. 7.29: Půlení hrany 52 I. TEORIE GRAFŮ 7.13 Příklad. Graf na obr. 7.29b vznikl z grafu na obr. 7.29a půlením jedné z hran. I z názoru je zřejmé, že při kreslení grafů se takové dva grafy, z nichž jeden vznikl z druhého postupným půlením hran, ,,chovají stejně". Tím je motivována následující definice. 7.14 Definice. Ř ekneme, že grafy G, H jsou homeomorfní, jestliže existují konečné posloupnosti grafů G, G1, G2, . . . , Gn H, H1, H2, . . . , Hm takové, že : (a) Gn je izomorfní s Hm; (b) v každé z těchto posloupností vznikl následující graf z předcházejícího půlením některé hrany. 7.15 Příklad. Každé dvě kružnice jsou homeomorfní. Nyní uvedeme bez důkazu již zmiňovanou Kuratowského větu. 7.16 Věta. Graf je rovinný právě tehdy, když neobsahuje podgraf homeomorfní s některým Kuratowského grafem (tj. s některým grafem z obr. 7.28). 7.17 Poznámka. Ukažme si, jak lze pomocí teorie rovinných grafů jednoduše zodpovědět jeden z klasických geometrických problémů. Již staří Ř ekové znali pět typů pravidelných mnohostěnů (tzv. Platónových těles): (a) pravidelný čtyřstěn, (b) krychli, (c) pravidelný osmistěn, (d) pravi- delný dvanáctistěn, (e) pravidelný dvacetistěn. (Viz obr. 7.30). Neuměli však dokázat, zda existují ještě jiné pravidelné mnohostěny. Me- todami teorie grafů nyní ukážeme, že žádné další pravidelné mnohostěny ne- existují. K tomu však potřebujeme několik jednoduchých pojmů. Omezená množina T E3 se nazývá hvězdovitá, když existuje bod s T takový, že každá polopřímka s počátečním bodem s má s hranicí množiny T právě jeden společný bod. Je zřejmé, že ,,běžná" konvexní tělesa (koule, hranol, válec apod.) jsou hvězdovité množiny. Snadno však lze ukázat, že existují i nekonvexní hvězdovitá tělesa. Z definice hvězdovité množiny okamžitě plyne, že její hranici lze zobrazit spojitou bijekcí na sféru. (Protože je T omezená, je částí nějaké koule v E3. 7. Rovinné grafy 53 (a) (b) (c) (d) (e) Obr. 7.30: Platónova tělesa Uvedená bijekce je realizována ,,promítáním" hranice na příslušnou kulovou plochu ze středu s.) Mnohostěn, který je zároveň hvězdovitou množinou, nazveme hvězdovitým mnohostěnem. Jak dobře víme, hvězdovitý mnohostěn se nazývá pravidelný, jestliže všechny jeho stěny jsou navzájem shodné pravidelné mnohoúhelníky. Ke každému pravidelnému mnohostěnu existují přirozená čísla n, p taková, že všechny stěny jsou shodné pravidelné n-úhelníky a v každém jeho vrcholu se stýká p hran. Uspořádaná dvojice [n, p] se nazývá Schla¨fliův symbol daného pravidelného mnohostěnu. Schla¨fliův symbol Platónových těles je následující: pravidelný čtyřstěn má symbol [3, 3], krychle [4, 3], pravidelný osmistěn [3, 4], pravidelný dvanácti- stěn [5, 3] a konečně pravidelný dvacetistěn [3, 5]. Jak jsme uvedli, lze hranici každé hvězdovité množiny zobrazit spojitou bijekcína sféru. Zejména tedy lze takto na sféru zobrazit hranici (tj. povrch) kaž- dého pravidelného mnohostěnu. Uvedeným zobrazením povrchu mnohostěnu vznikne na sféře ,,mapa". (Definice mapy na sféře je analogická definici 7.7 54 I. TEORIE GRAFŮ mapy v rovině.) Užitím tzv. stereografické projekce však lze snadno dokázat, že pro mapy na sféře rovněž platí Eulerova věta 7.9. (Připomeňme si, že stereografická projekce je zobrazení sféry s vyjmutým jedním bodem na rovinu, definované následovně: Necht'se sféra S dotýká roviny E2 v bodě P. Bud' PN průměr sféry S (viz obr. 7.31). Bud'x S libovolný bod různý od N. Bod f (x) E2 je průsečík polopřímky Nx s rovinou E2. Je zřejmé, že stereografická projekce f je bijekcí množiny S-{N} na E2 a zobrazení f i f -1 jsou spojitá. Nyní je také zřejmé, že při stereografické projekci se mapa na sféře zobrazí na mapu v rovině, přičemž se uzly zobrazí na uzly, hrany na hrany a oblasti na oblasti. Proto evidentně platí Eulerova věta i pro mapy na sféře.) y N P x f (x) f (y) Obr. 7.31: Stereografická projekce Bud'nyní T pravidelný mnohostěn. Označme R počet jeho stěn, M počet hran, N počet vrcholů, n počet stran jedné stěny, p počet hran sbíhajících se v jednom vrcholu. Protože každá hrana spojuje dva vrcholy a v každém vrcholu se sbíhá p hran, platí Np = 2M. (7.2) Protože každá stěna je omezena n hranami a každá hrana sousedí se dvěma stěnami, platí Rn = 2M. (7.3) 7. Rovinné grafy 55 Konečně, podle Eulerovy věty platí N + R - M = 2. (7.4) Rovnice 7.2, 7.3, 7.4 jsou rovnice o neznámých M, N, R s parametry n, p přičemž tyto parametry jsou přirozená čísla větší nebo rovna 3. Z 7.2 ­ 7.4 dostáváme M = 2np 2p + 2n - np , N = 4n 2p + 2n - np , R = 4p 2p + 2n - np . (7.5) Protože všechna čísla M, N, P jsou kladná, musí platit 2p + 2n - np > 0, tj. (n - 2)(p - 2) < 4, n 3, p 3. Protože n - 2 > 0, p - 2 > 0, platí nutně (n - 2)(p - 2) {1, 2, 3}. Odtud dostáváme: (a) (n - 2)(p - 2) = 1 n = 3, p = 3, (b) (n - 2)(p - 2) = 2 n = 3, p = 4 nebo n = 4, p = 3, (c) (n - 2)(p - 2) = 3 n = 3, p = 5 nebo n = 5, p = 3. Pravidelným mnohostěnů proto existuje nejvýše pět druhů, tj. právě pět druhů. Hodnoty M, N, R, n, p těchto pravidelných mnohostěnů udává tabulka 7.4. R M N n p Pravidelný čtyřstěn 4 6 4 3 3 Krychle 6 12 8 4 3 Pravidelný osmistěn 8 12 6 3 4 Pravidelný dvanáctistěn 12 30 20 5 3 Pravidelný dvacetistěn 20 30 12 3 5 Tab. 7.4: Tabulka hodnot R, M, N, n, p pro Platónova tělesa POZNÁ MKY A CVIČENÍ 1. Podle Wagnerovy věty 7.6 lze každý planární graf namalovat bez protí- nání hran, jimiž jsou úsečky. Namalujte tak Kuratowského grafy, z nichž je odebrána jedna hrana. 56 I. TEORIE GRAFŮ 8 Barvení grafů Nejprve si na dvou jednoduchých problémech ilustrujme důvody, které vedly k problematice ,,barvení" grafů. 8.1 Problém. Mějme dánu množinu L různých druhů léků. Přitom je známo, které dvojice různých léků se pacientům nesmějí podávat současně. Na mno- žině L chceme definovat rozklad tak, že léky ležící v jedné třídě rozkladu se sočasně podávat mohou. (Takový rozklad jistě existuje ­ například rozklad na jednoprvkové třídy.) Náš problém nyní zní: Jaký je minimální počet tříd takového rozkladu? Přeformulujme si problém následovně: Bud'[L, H] graf, v němž pro x, y L platí xy H právě tehdy, když se léky x, y nesmějí podávat současně. Nyní si představme, že uzly grafu [L, H] obarvíme barvami (modře, červeně atd.) tak, že žádné dva sousední uzly nebudou obarveny stejnou barvou. Problém 8.1 nyní můžeme přeformulovat takto: Jaký minimální počet barev k výše uvedenému obarvení potřebujeme? 8.2 Problém. Je dána množina V rádiových vysílacích stanic a každá stanice x V má určenu množinu Vx V stanic, s nimiž má udržovat spojení. Ptáme se, jaký je minimální možný počet různých frekvencí, které musí být k dispozici, chceme-li zajistit, aby každá stanice x V udržovala s každou ze stanic z množiny Vx spojení na jiné frekvenci? Grafová formulace je opět jednoduchá. Utvořme graf, v němž V je množina uzlů a dva uzly jsou spojeny hranou právě tehdy, když příslušné stanice mají udržovat spojení. Hledáme minimální počet barev nutný k takovému obarvení hran tohoto grafu, že každé dvě hrany, které mají společný uzel, jsou obarveny různě. Před uvedením základních výsledků o barvení grafů uzavřeme, podobně jako v paragrafu 7, následující dohodu. 8.3 Dohoda. V celém paragrafu 8 slovo ,,graf" značí ,,konečný graf". 8. Barvení grafů 57 8.4 Definice. Bud' [U, H] graf. Zobrazení f : U N nazveme obarvení uzlů, jestliže pro každé dva sousední uzly x, y U platí f (x) = f (y) (tj. xy H f (x) = f (y)). Ř ekneme, že graf [U, H] je uzlově k-chromatický, existuje-li obarvení f uzlů takové, že | f (U)| k. Uzlové chromatické číslo (G) grafu G je nejmenší číslo k N0 takové, že G je uzlově k-chromatický. Z definice je zřejmé, že každý graf má jednoznačně určené uzlové chroma- tické číslo. Jeho nalezení v konkrétních případech však může být velmi obtížné. Důkaz následujícího tvrzení je však jednoduchý, a proto ho přenecháme čtenáři. 8.5 Věta. Bud'G = [U, H] graf. Pak platí: (a) (G) = 1 H = . (b) Je-li G strom a |H| 1, pak (G) = 2. Grafy s uzlovým chromatickým číslem 2 hrají v řadě aplikací důležitou roli. Jak nyní uvedeme, je charakteristika těchto grafů velmi jednoduchá. 8.6 Věta. Bud'G = [U, H] graf, H = . Pak (G) = 2 právě tehdy, když neobsahuje kružnici liché délky. Důkaz. I. Nutnost podmínky je zřejmá, nebot'k obarvení kružnice liché délky je nezbytné užít alespoň tří barev. II. Necht'G = [U, H] neobsahuje kružnici liché délky. Dostatečnost této podmínky budeme dokazovat indukcí vzhledem k počtu kružnic v G. Uvě- domme si přitom, že důkaz stačí provést pro souvislé grafy, nebot' obarvení uzlů v jednotlivých komponentách můžeme provádět samostatně a nezávisle na sobě. Neobsahuje-li G žádnou kružnici, je G strom a podle věty 8.5(b) platí (G) = 2. Necht'tedy tvrzení platí pro každý souvislý graf obsahující nejvýše n kružnic sudé délky. Bud'nyní G = [U, H] graf obsahující n + 1 kružnic sudé délky. Bud'C libovolná kružnice v G. Zvolme v C libovolně hranu xy. Graf G = [U, H - {xy}] obsahuje nejvýše n kružnic, takže podle předpokladu platí (G ) = 2. Odtud plyne existence obarvení uzlů f : U {1, 2} grafu G . Kružnice C bez hrany xy je had, v němž se obarvení uzlů pravidelně střídá. Protože tento had obsahuje sudý počet uzlů, je f (x) = f (y). To však znamená, že f je současně obarvením grafu G, čímž je důkaz hotov. ˇ 58 I. TEORIE GRAFŮ 8.7 Definice. Necht'G = [U, H] je graf a necht'lze množinu U rozložit na dvě neprázdné disjunktní podmnožiny U1, U2 tak, že každá hrana má jeden uzel v U1 a druhý uzel v U2. Pak se graf G nazývá bipartitní. Uvedený bipartitní graf se obvykle zapisuje ve tvaru [U1, U2, H]. Bipartitní graf [U, V, H] se nazývá úplný, když pro každé dva uzly x U, y V platí xy H. Je-li |U| = m, |V| = n, značí se úplný bipartitní graf [U, V, H] symbolem Km,n. Tak například Kuratowského graf ,,3 domy a 3 studně" na obr. 7.28b je graf K3,3. Pro bipartitní graf G s neprázdnou množinou hran zřejmě platí (G) = 2. Bipartitní grafy jsou studovány zejména v souvislosti s tzv. párováním v grafech, což je jedna z nejzávažnějších částí kombinatoriky a teorie grafů. Zformulujme si nejprve jeden z klasických kombinatorických problémů, tzv. problém o svatbách. 8.8 Příklad. Je dána množina H hochů a množina D dívek, |D| |H|. Každý hoch zná alespoň jednu dívku. Jaká je nutná a dostatečná podmínka toho, aby se každý hoch mohl oženit s dívkou, kterou zná? Nalezení jednoduché nutné podmínky je snadné: kdyby existovala nějaká k-tice chlapců (k |H|) taková, že všech dívek, které by znal alespoň jeden chlapec z této k-tice, by bylo méně než k, pak by jistě nebylo možné požadované svatby uskutečnit. Jak dokázal v roce 1935 Ph. Hall, je tato jednoduchá nutná podmínka sou- časně také podmínkou dostatečnou. Hallova věta je jedním z nejdůležitějších kombinatorických tvrzení. Důkaz tohoto tvrzení nebudeme provádět. 8.9 Věta. (Hallova věta.) Bud'dána množina Si, i = 1, . . . , n, neprázdných konečných množin. Pak jsou následující tvrzení ekvivalentní: (a) Existuje prosté zobrazení f : {1, . . . , n} n i=1 Si takové, že f (i) Si pro každé i = 1, . . . , n. (b) Pro každou podmnožinu = A {1, . . . , n} platí |A| iA Si . Grafová interpretace Hallovy věty je jednoduchá. Bud'dán bipartitní graf [U, V, H], |U| |V|. Pro každý uzel x U označme Vx = {y V; xy H}. 8.10 Definice. Párováním v daném bipartitním grafu [U, V, H] nazveme každý jeho podgraf [U , V , H ], který je pravidelným grafem 1. stupně (tj. z každého uzlu vychází právě jedna hrana). 8. Barvení grafů 59 Z Hallovy věty okamžitě plyne, že v bipartitním grafu [U, V, H] existuje alespoň jedno párování [U, V , H ] právě tehdy, když pro každou podmnožinu = U1 U platí |U1| xU1 |Vx| . (8.1) Párování v bipartitním grafu se nazývá úplné, je-li faktorem daného grafu (tj. V = V). Je zřejmé, že v [U, V, H] úplné párování existuje právě tehdy, když kromě podmínky 8.1 navíc platí |U| = |V|. Jestliže v bipartitním grafu [U, V, H] párování neexistuje, je přirozené hledat maximální (vzhledem k počtu hran) podgraf v [U, V, H], který je pra- videlným grafem 1. stupně. Takové podgrafy mají řadu aplikací v operačním výzkumu, v lineárním programování apod1 . Na obr. 8.32a je bipartitní graf, v němž neexistuje párování (je to faktor grafu K5,5). Na obr. 8.32b je jeden z maximálních pravidelných podgrafů 1. stupně. (a) (b) Obr. 8.32: Maximální pravidelný podgraf 1. stupně v daném grafu Nyní se vrat'me k problematice barvení uzlů v grafu. Jakkoliv je obecně určení čísla (G) obtížné, je jednoduchá jeho následující majorizace. 8.11 Věta. Bud'G = [U, H] graf. Označme = max {st x; x U}. Pak platí (G) + 1. 1Nejběžnější z algoritmů pro hledání tohoto maximálního podgrafu je tzv. mad'arský algo- ritmus. 60 I. TEORIE GRAFŮ Důkaz. Indukcí vzhledem k číslu |U|. Pro |U| = 1 je tvrzení zřejmé. Necht' tedy tvrzení věty platí pro všechny grafy [U, H] takové, že |U| n. Bud' nyní G = [U, H] graf, |U| = n + 1. Označme G graf, který vznikne z grafu G odečtením některého uzlu x a všech hran s tímto uzlem incidentních. Podle předpokladu platí (G ) + 1, takže existuje obarvení uzlů grafu G f : (U - {x}) {1, . . . , + 1}. V grafu G však s uzlem x sousedí nejvýše uzlů, takže uzly v G můžeme obarvit následovně: g(t) = f (t), pro t = x, p pro t = x, kde p {1, . . . , + 1} je takový prvek, že p = f (u) pro všechny uzly u U, tu H. Pak je g obarvení daného grafu nejvýše + 1 barvami. ˇ Nyní se budeme zabývat barvením hran. 8.12 Definice. Bud'[U, H] graf. Zobrazení f : H N nazveme obarvením hran, jestliže pro každé dvě hrany h1, h2 H, h1 = h2, takové, že h1h2 = , platí f (h1) = f (h2). Ř ekneme, že graf [U, H] je hranově k-chromatický, když existuje obarvení f hran takové, že | f (H)| k. Hranové chromatické číslo h(G) grafu G je nejmenší číslo k N0 takové, že G je hranově k-chromatický. Ve větě 8.11 jsme uvedli horní odhad uzlového chromatického čísla. Má-li symbol týž smysl jako ve větě 8.11, je z definice okamžitě zřejmé, že pro hranové chromatické číslo platí h(G) . Jak v roce 1964 dokázal ruský matematik G. V. Vizing, platí dokonce následující věta, kterou uvedeme bez důkazu. 8.13 Věta. Pro libovolný graf G platí h(G) + 1. 8.14 Poznámka. Hranové chromatické číslo daného grafu tedy může nabýt jen dvou hodnot: nebo + 1. Ř ekneme, že graf G patří do první, respektive do druhé třídy, je-li h(G) = , respektive h(G) = + 1. Je zřejmé, že například každá kružnice sudé délky patřído prvnítřídy, každá kružnice liché délky do druhé třídy. Dodnes však není známa charakterizace příslušnosti grafů k těmto třídám. Přitom není zastoupení grafů v těchto třídách ani zdaleka rovnoměrné. Jak v roce 1977 dokázali P. Erdo¨s a R. J. Wilson, platí následující tvrzení: 8. Barvení grafů 61 Označíme-li pi (n) počet grafů na n uzlech patřících do i-té třídy, platí lim n p2(n) p1(n) = 0. Podle [6] existuje například 143 souvislých grafů s nejvýše šesti uzly a pouze 8 z nich patří do druhé třídy. Těchto 8 grafů je na obr. 8.33. Obr. 8.33: Grafy druhé třídy na nejvýše šesti uzlech 8.15 Příklad. Důležitým grafem patřícím do druhé třídy je tzv. Petersenův graf (obr. 8.34a). J. Petersen uveřejnil v roce 1891 práci v níž podrobně po- psal vlastnosti pravidelných grafů; především pak studoval problém existence pravidelných faktorů v těchto grafech. 62 I. TEORIE GRAFŮ (a) (b) Obr. 8.34: Petersenův graf a jeho kvadratický faktor Jak je okamžitě zřejmé, je Petersenův graf pravidelným grafem 3. stupně. Obsahuje pravidelný faktor 1. stupně (tzv. lineární faktor) ­ hrany tohoto fak- toru jsou na obr. 8.34a vyznačeny tučně. Petersenův graf obsahuje i pravidelný faktor 2. stupně (tj. kvadratický faktor); tento faktor je na obr. 8.34b. Tento kvadratický faktor však není souvislý. Ponecháme čtenáři, aby si promyslel, že souvislý kvadratický faktor (tj. hamiltonovská kružnice) v Pe- tersenově grafu neexistuje. Petersenův graf proto není hamiltonovský. Lehce však lze ukázat, že je polohamiltonovský (viz poznámka 6.15). Na dokreslení toho, co jsme o znázorňování grafů uvedli v poznámce 7.3, necht' si čtenář promyslí, že všechny tři grafy na obr. 8.35 jsou izomorfní s Petersenovým grafem. 8.16 Poznámka. S problematikou barvení grafů úzce souvisí jeden z nejzná- mějších matematických problémů 20. století, tzv. problém čtyř barev. Formu- lace tohoto problému je jednoduchá: Mějme v rovině zeměpisnou mapu, na níž je několik států. Chceme, aby mapa byla vybarvena tak, jak je to obvyklé, tj. aby každý stát byl vybarven nějakou barvou tak, že žádné dva sousední státy nejsou obarveny stejně. Naším úkolem je zjistit, jaký počet barev nezbytně potřebujeme, abychom mohli takto vybarvit každou zeměpisnou mapu. Aby formulace problému byla regulérní, je nutno upřesnit dvě skutečnosti: (a) předpokládáme, že území každého státu je ,,souvislé" (což v praxi není vždy splněno ­ viz například USA (Aljaška)); (b) dva státy považujeme za sousední, když mají společnou hraniční ,,čáru" (tj. nedotýkají se jen v izolovaných bodech). Lehce lze ukázat, že je nutno mít k dispozici alespoň čtyři barvy (obr. 8.36). Ve všech konkrétních příkladech se vždy podařilo najít obarvení čtyřmi barvami. 8. Barvení grafů 63 (a) (b) (c) Obr. 8.35: Různá nakreslení Petersenova grafu Nalezení důkazu, že tomu tak je zákonitě, se však ukázalo být jedním z nejobtížnějších problémů moderní matematiky. Přeformulujme si nyní uvedený problém do grafové terminologie. Mějme dánu nějakou zeměpisnou mapu (splňující výše uvedené podmínky). Nyní zkonstruujme graf G = [U, H] následovně. Na území každého státu zvolme jeden bod; tyto body tvoří množinu U. Dva uzly spojíme hranou právě tehdy, když příslušné státy sousedí. Takto získaný graf je jistě rovinný, nebot'hrany můžeme kreslit tak, aby neprocházely územím žádného dalšího státu (hra- nici dvou států můžeme ,,překročit" v hraniční čáře). Tak například státům na I II III IV Obr. 8.36: Příklad mapy 64 I. TEORIE GRAFŮ obr. 8.36 odpovídá graf K4. Obarvení zeměpisné mapy je nyní ekvivalentní s obarvením uzlů takto sestrojeného rovinného grafu. V grafové terminologii lze tedy problém čtyř barev přeformulovat takto: Platí pro každý rovinný graf G nerovnost (G) 4? To, že i relativně komplikované grafy uvedenou podmínku splňují, samo- zřejmě ještě nic neznamená. Historie toho problému sahá až do let 1840 ­ 1850, kdy se tímto problémem zabývali A. F. Mo¨bius, A. de Morgan a další. Mnohokrát byl uvedený problém zdánlivě ,,vyřešen", vždy se však ukázalo, že v důkazu byla nějaká chyba. V roce 1890 dokázal P. J. Heawood (právě při rozboru jednoho z chybných důkazů), že pro každý rovinný graf G platí (G) 5 (tzv. věta o pěti barvách). Definitivně problém čtyř barev vyřešili (pozitivně) až v roce 1976 K. Apple a W. Haken z univerzity v Illinois (USA), když dokázali, že vskutku pro každý rovinný graf G platí (G) 4. Důkaz tohoto tvrzení převedli na prověření vlastností téměř dvou tisíc speciálních grafů. Samotné prověření pak provedli na počítači, který na to spotřeboval 1200 hodin strojového času. I tyto údaje demonstrují obtížnost celého problému. Podrobněji o historii tohoto problému viz například v knize [7] . POZNÁ MKY A CVIČENÍ 1. Permanent matice A = aij typu m/n, m n je definován jako per(A) = a1i1 a2i2 . . . amim , kde se sčítá přes všechny variace m prvků z množiny {1, 2, . . . , n}. Vypočtěte permanent matic: a) A = 1 1 1 1 b) B = 1 2 3 1 2 3 c) C = 1 1 1 1 1 2 3 4 1 1 1 1 9. Zobecnění pojmu graf 65 9 Zobecnění pojmu graf Jak jsme uvedli již v paragrafu 1, není grafová terminologie v literatuře zda- leka jednotná. Ustálený význam nemá ani pojem graf. Nyní uvedeme definici tzv. ,,obecného grafu", která zahrnuje většinu běžně studovaných grafů jako speciální případy. 9.1 Definice. Obecným grafem nazýváme trojici [U, H, ], kde U, H jsou disjunktní množiny, U = a : H U2 U P2(U). Prvky množiny U nazýváme uzly, prvky množiny H hrany a je tzv. inci- denční zobrazení. Je-li (h) U2 , nazývá se h orientovaná hrana, je-li (h) U P2(U), je h neorientovaná hrana. Orientovaná hrana h se nazývá orientovaná smyčka, je-li (h) = [x, x] pro nějaký uzel x U. Neorientovaná hrana se nazývá smyčka, je-li (h) U. Orientované hrany h, k se nazývají souhlasně rovnoběžné, je-li (h) = (k) a nesouhlasně rovnoběžné, je-li (h) = [x, y] = [y, x] = (k). Neorientované hrany h, k se nazývají rovnoběžné, je-li (h) = (k). Násobností hrany h H nazýváme číslo |{k H; (k) = (h)}|. V obecném grafu tak mohou existovat současně hrany orientované i ne- orientované, mezi dvěma uzly nemusí existovat žádná hrana, ale může jich existovat i více než jedna atd. Možných ,,typů" grafů tak existuje celá řada. Nejdůležitější rozdělení grafů obdržíme podle toho, zda v nich existují více- násobné hrany či nikoliv a podle toho, zda jsou všechny hrany orientované respektive všechny neorientované. 9.2 Definice. Bud' G = [U, H, ] obecný graf. Existuje-li alespoň jedna hrana h H s násobností větší než jedna, nazývá se G multigraf (nebo též pseudograf). Je-li násobnost všech hran rovna jedné, nazývá se G prostý graf. Obsahuje-li G pouze neorientované hrany, nazývá se neorientovaný graf. Jsou-li všechny hrany v G orientované, je G tzv. orientovaný graf. Ř ekneme, že G je smíšený graf, není-li ani orientovaný ani neorientovaný. (Ve smíšeném grafu tedy existuje alespoň jedna orientovaná a alespoň jedna neorientovaná hrana.) 66 I. TEORIE GRAFŮ 9.3 Poznámka. Formální popis prostého grafu můžeme snadno zjednodušit. Incidenční zobrazení je podstatné u multigrafů. V prostém grafu můžeme přímo předpokládat, že H U2 U P2(U) a je pak identické zobrazení (tj. (h) = h pro každou hranu h H). (Tzn., že prostý graf můžeme definovat jako dvojici [U, H], kde U = , H U2 U P2(U), U H = .) Orientovaný i neorientovaný graf přitom může a nemusí být prostý. Důležitou charakteristikou grafu je v mnoha situacích skutečnost, zda daný graf obsahuje smyčky či nikoliv. Prostý neorientovaný graf bez smyček se nazývá obyčejný graf. Prostý orientovaný graf bez smyček nazýváme obyčejný orientovaný graf. 9.4 Poznámka. V paragrafech 2 ­ 8 jsme tedy ,,grafem" rozuměli obyčejný graf. Kromě obyčejných grafů, které jsme dosud studovali, tvoří druhou nej- častěji studovanou třídu grafů prosté orientované grafy, respektive obyčejné orientované grafy. Místo prostý orientovaný graf, respektive obyčejný orientovaný graf, se často stručně říká jen ,,orientovaný graf". Uvažme, že když [U, H] je prostý orientovaný graf, je H U 2 , tj. H je binární relace na U. Tento graf je pak obyčejným orientovaným grafem právě tehdy, když je relace H areflexivní. Prosté orientované grafy tedy nejsou nic jiného než množiny s binárnírelací. Všechno, co známe o binárních relacích, proto můžeme na tyto grafy přenést. Mohlo by se proto zdát, že studium orientovaných grafů jako samostatných objektů je zbytečné. Z tradičních důvodů a vzhledem k specifičnosti metod teorie grafů se však orientované grafy intenzivně studují. 9.5 Poznámka. Prostý orientovaný graf je podle výše uvedeného dvojice [U, H], kde U = , H U2 . V teorii grafů jsou však tyto grafy obvykle zadávány jiným způsobem. Ke každému uzlu x U je zadána množina (x) těch uzlů, do nichž z x vede orientovaná hrana, kterou nazýváme šipkou. 9.6 Definice. Bud'U = libovolná množina, : U P(U) bud'libovolné zobrazení. Pak se dvojice [U, ] nazývá orientovaný graf. U je množina uzlů. Z uzlu x vede do uzlu y orientovaná hrana - xy právě tehdy, když y (x). 9.7 Poznámka. Z výše uvedeného je zřejmé, co to znamená, že orientovaný graf [U, ] je reflexivní, symetrický, antisymetrický, tranzitivní a podobně. 9. Zobecnění pojmu graf 67 Ř adu pojmů lze z obyčejných grafů přenést na neorientované grafy prak- ticky beze změny ­ například pojem ,,podgraf", ,,izomorfismus grafů" atd. U některých pojmů dochází k jistým modifikacím. Tak například roli stupně uzlu x hrají dva tzv. polostupně | (x)| a -1 (x) (tj. počty hran z uzlu x vycházejících a v uzlu x končících). Roli kružnice v orientovaných grafech hraje tzv. cyklus. Acyklický graf je orientovaný graf neobsahující jako podgraf žádný cyklus. Důležitou třídou orientovaných grafů jsou tzv. turnaje. Areflexivní orien- tovaný graf se nazývá turnaj, jestliže pro každé dva různé uzly x, y platí, že jsou spojeny hranou - xy, respektive - yx. Přes veškeré odlišnosti mezi jednotlivými typy grafů však lze říci, že pro toho, kdo zvládne teorii pro jeden z typů, je snadné pochopení pojmů i pro zbývající typy. V aplikacích se pochopitelně užívá různých typů grafů, podle toho, jaký typ je pro popis zadané situace nejvýhodnější. Zobecnění pojmu graf je však možno provést i jiným způsobem, než jak jsme to provedli v definici 9.1. Někdy je výhodné a potřebné studovat ,,grafy", jejichž hrany spojují více než dva uzly. Takovým grafům se říká obvykle hyper- grafy. (V posledních letech se v české literatuře ujímá pro hypergrafy termín společnost, místo o hranách hypergrafu se pak hovoří o týmech společnosti.) 9.8 Definice. Hypergraf je trojice [U, H, ], kde U = je množina uzlů, H je množina hran a : H (P(U) - {}) je incidenční zobrazení. 9.9 Poznámka. Hypergraf je tedy ­ jednoduše řečeno ­ systém neprázdných podmnožin množiny uzlů. Některé množiny se přitom v tomto systému mohou opakovat. Existuje-li číslo k takové, že pro každou hranu h H platí |(h)| = k, říkáme, že hypergraf je uniformní (respektive k-uniformní). Je zřejmé, že 2-uniformní hypergraf je totéž jako neorientovaný graf bez smyček. Je-li incidenční zobrazení prosté (tj. ,,násobnost" každé hrany je rovna jedné), nazývá se hypergraf prostý. Podobně jako u prostého grafu můžeme předpokládat, že prostý hypergraf je dvojice [U, H], kde H (P(U) - {}). Přenesení řady pojmů z grafů na hypergrafy je jednoduché. DODATEK 1: BIOGRAFIE V tomto dodatku uvádíme základní biografické údaje osobností, které jsou v textu zmíněny. Podrobnější životopisy včetně obrazových materiálů lze nalézt např. na CD-ROM [1]. d'ALEMBERT Jean Baptiste Le Rond (1717­1783) Francouzský matematik a fyzik, osvícenský filozof, jeden z encyklopedistů. BELL Eric Temple (1883­1960) Americký matematik skotského původu. BERNOULLI Jacob I. (1654­1705) Švýcarský matematik a fyzik, první z plejády slavných Bernoulliů. BETTI Enrico (1823­1892) Italský matematik. BORŮVKA Otakar (1899­1995) Významný český matematik, profesor univerzity v Brně. CATALAN Eug`ene Charles (1814­1894) Belgický matematik. CAYLEY Arthur (1821­1895) Anglický matematik. DESCARTES René (latinsky Renatus CARTESIUS) (1596­1650) Francouzský filozof, matematik, fyzik a přírodovědec, jeden ze zakladatelů novověké filozofie a vědy. DIRICHLET Peter Gustav Lejeune (1805­1859) Německý matematik. 68 Dodatek 1: Biografie 69 DU¨ RER Albrecht (1471­1528) Německý malíř a grafik. ERDO¨ S Paul (1913­1996) Mad'arský matematik. EUKLEIDÉ S z Alexandrie (asi 340­270 př. Kr.) Starořecký matematik, autor nejvýznamnější matematické knihy dosavadní historie. EULER Leonhard (1707­1783) Švýcarský matematik, fyzik a fyziolog, jeden z nejvýznamnějších matematiků všech dob. FERMAT Pierre (1601­1665) Francouzský matematik a právník. FERRERS Norman Macleod (1829­1903) Anglický matematik. FIBONACCI (vl. jménem Leonardo Pisánský) (asi 1170­po 1240) První velký matematik evropského středověku. FRANKLIN Benjamin (1706­1790) Americký státník, přírodovědec a filozof. Vzděláním samouk se vlastní pílí vypracoval na jednoho z předních osvícenských myslitelů. FULKERSON Delbert Ray (1924­1976) Americký matematik. GALILEI Galileo (1564­1642) Italský fyzik, astronom, matematik a filozof, zakladatel experimentálních me- tod zkoumání přírody, kritik scholastiky, představitel renesančního mechanis- tického pojetí přírody. HALL Phillip (1904­1982) Anglický matematik. 70 DODATKY HAMILTON William Rowan, sir (1805­1865) Irský matematik a astronom. HARDY Godfrey Harold (1877­1947) Anglický matematik, největší světový odborník v teorii čísel první poloviny 20. století. HASSE Helmut (1898­1979) Německý matematik. HEAWOOD Percy John (1861­1955) Anglický matematik. HUYGENS Christian (1629­1695) Nizozemský matematik a fyzik. JANG Hui (asi 1238­asi 1298) Čínský matematik. KEMPE Alfred Bray (1849­1922) Anglický matematik. KIRCHHOFF Gustave-Robert (1824­1887) Německý fyzik a mechanik. KIRKMAN Thomas Penyngton (1806­1895) Anglický kněz. Ve volných chvílích se zabýval matematikou. KO¨ NIG Dénes (1884­1944) Mad'arský matematik. KURATOWSKI Kazimierz (1896­1980) Polský matematik. LAPLACE Pierre Simon (1749­1827) Francouzský matematik, fyzik a astronom. Dodatek 1: Biografie 71 LEIBNIZ Gottfried Wilhelm von (1646­1716) Německý matematik, filozof, právník, historik, jazykovědec, diplomat, vyná- lezce a polyhistor, zakladatel moderní matematické analýzy. LUCAS Francois Edouard Anatole (1842­1891) Francouzský matematik. MacMAHON Percy Alexander (1854­1929) Anglický matematik. MENGER Karl (1902­1985) Rakousko-americký matematik. MO¨ BIUS August Ferdinand (1790­1869) Německý matematik a astronom. de MORGAN Augustus (1806­1909) Skotský matematik a logik. NETTO Eugen Otto Erwin (1848­1919) Německý matematik. ORE Oystein (1899­1968) Americký matematik norského původu. OZANAM Jacques (1640­1717) Francouzský matematik, chemik a teolog. PARKER Ernest Tilden (1926­1991) Americký matematik. PASCAL Blaise (1623­1662) Francouzský matematik, fyzik a filozof. PETERSEN Julius Peter Christian (1839­1910) Dánský matematik. 72 DODATKY PLATÓ N (427­347 př. Kr.) Starořecký filozof, jeden z největších antických myslitelů. PÓ LYA Gyergy (1887­1985) Mad'arský matematik. RADEMACHER Hans (1892­1969) Německý matematik. RAMANUJAN Srinivasa Aaiangar (1887­1920) Indický matematik. ROTA Gian-Carlo (1932­1999) Americký matematik italského původu. SCHLA¨ FLI Ludwig (1814­1895) Švýcarský matematik. STEINER Jacob (1796­1863) Německý matematik. STIFEL Michael (1487­1567) Německý matematik. STIRLING James (1692­1770) Skotský matematik. TAIT Peter Guthrie (1831­1901) Skotský matematik a filozof. TARRY Gaston (1843­1913) Francouzský matematik­amatér. TARSKI Alfred (1901­1977) Americký matematik a logik polského původu. YOUNG John Wesley (1879­1932) Americký matematik. DODATEK 2: TABULKY 73 74 DODATKY n! n 1 1 2 2 6 3 24 4 120 5 720 6 5 040 7 40 320 8 362 880 9 3 628 800 10 39 916 800 11 479 001 600 12 6 227 020 800 13 87 178 291 200 14 1 307 674 368 000 15 ... 2 432 902 008 176 640 000 20 ... 15 511 210 043 330 985 984 000 000 25 Tab. 1.1: Tabulka hodnot n ! Dodatek 2: Tabulky 75 n t(n) n t(n) 1 1 14 3 159 2 1 15 7 741 3 1 16 19 320 4 2 17 48 629 5 3 18 123 867 6 6 19 317 955 7 12 20 823 065 8 23 21 2 144 505 9 47 22 5 623 756 10 106 23 14 828 074 11 235 24 39 299 897 12 551 25 104 636 890 13 1 301 26 279 793 450 Tab. 1.2: Počet tn neizomorfních stromů na n uzlech REJSTŘ ÍK k-pravidelný graf, 15 k-uniformní hypergraf, 67 acyklický graf, 67 artikulace, 33 Bettiho číslo, 34 bipartitní graf, 58 cesta, 18 cyklomatické číslo, 34 cyklus, 67 disjunktní grafy, 12 délka kružnice, 21 délka sledu, 18 Eulerova věta, 48 eulerovský graf, 38 faktor grafu, 12 graf, 11 graf ,,tři domy a tři studně", 48 grafová posloupnost, 15 grafy druhé třídy, 60 grafy první třídy, 60 had, 24 Hallova věta, 58 hamiltonovská cesta, 45 hamiltonovská kružnice, 41 hamiltonovský graf, 41 homeomorfní grafy, 52 homomorfismus grafů, 40 hrana, 9, 65 hrana grafu, 11 hranové chromatické číslo, 60 hranově k-chromatický graf, 60 hranově k-souvislý graf, 37 hranově ohodnocený graf, 29 hranový stupeň souvislosti, 36 hranový řez, 36 hvězda, 24 hvězdovitá množina, 52 hvězdovitý mnohostěn, 53 hypergraf, 9, 67 incidenční zobrazení, 65, 67 izolovaný uzel, 13 izomorfismus grafů, 27 izomorfní grafy, 27 komplementární grafy, 12 komponenta grafu, 20 koncové uzly hrany, 11 konečný graf, 11 kostra grafu, 24 kružnice v grafu, 21 Kuratowského grafy, 50 kvadratický faktor, 41, 62 kvaternion, 40 Laplaceova matice sousednosti, 26 les, 22 lineární faktor, 62 mapa, 48 matice sousednosti grafu, 17 76 Rejstřík 77 matroid, 31 mad'arský algoritmus, 59 minimální kostra, 29 množina hran, 67 množina uzlů, 66, 67 most, 32 multigraf, 65 nakreslení grafu, 46 neizomorfní stromy, 28 neorientovaná hrana, 65 neorientovaný graf, 65 nesouhlasně rovnoběžné hrany, 65 násobnost hrany, 65 obarvení hran, 60 obarvení uzlů, 57 obecný graf, 65 obyčejný graf, 10, 66 obyčejný orientovaný graf, 66 ohodnocení hrany (uzlu), 29 ohodnocený graf, 10 orientovaná hrana, 65 orientovaná smyčka, 65 orientovaný graf, 65, 66 otevřený tah, 18 permanent matice, 64 Petersenův graf, 61 planární graf, 47 Platónova tělesa, 52 podgraf grafu, 12 polohamiltonovský graf, 45 polostupeň uzlu, 67 pravidelný faktor, 41 pravidelný graf, 15 pravidelný mnohostěn, 53 problém o svatbách, 58 problém obchodního cestujícího, 10 problém čtyř barev, 9, 62 prostý graf, 65 prostý hypergraf, 67 pseudograf, 65 párování, 58 půlení hrany, 50 rovinný graf, 10, 47 rovnoběžné hrany, 65 Schla¨fliův symbol, 53 sled, 18 smyčka, 9, 65 smíšený graf, 65 souhlasně rovnoběžné hrany, 65 souvislý graf, 19 společnost, 67 stereografická projekce, 54 strom, 22 stupeň uzlu, 13 tah v grafu, 18 trojúhelník, 21 turnaj, 67 tým, 67 uniformní hypergraf, 67 uzavřený tah, 18 uzel, 65 uzel grafu, 9, 11 uzel konečného stupně, 13 uzel nekonečného stupně, 13 uzlové chromatické číslo, 57 uzlově k-chromatický graf, 57 uzlově k-souvislý graf, 37 uzlově ohodnocený graf, 29 uzlový stupeň souvislosti, 35 uzlový řez, 35 vlastní podgraf grafu, 12 vnitřní uzel, 18 vrchol grafu, 9, 11 věta o pěti barvách, 64 znaménková matice, 17 78 REJSTŘÍK šipka, 9, 66 člen grafu, 33 úloha o sedmi mostech města Krá- lovce, 7 úplné párování, 59 úplný bipartitní graf, 58 úplný graf, 12 LITERATURA [1] E. FUCHS: Diskrétní matematika a teorie množin pro učitele, CD-ROM, Brno 2000 [2] E. FUCHS: Diskrétní matematika pro učitele, Brno 2001 [3] J. E. GRAVER, M. E. WATKINS: Combinatorics with Emphasis on the Theory of Graphs, Springer - Verlag, New York ­ Heidelberg ­ Berlin 1977 [4] J. NEČAS: Grafy a jejich použití, SNTL, Praha 1978 [5] J. NEŠETŘ IL: Teorie grafů, SNTL, Praha 1979 [6] J. SEDLÁ ČEK: Úvod do teorie grafů, Academia, Praha 1981 [7] P. ŠIŠMA: Teorie grafů 1736­1963, Prometheus, Praha 1997 79 80 Poznámky