Masarykova univerzita • Přírodovědecká fakulta
Eduard Fuchs
DISKRÉTNÍ MATEMATIKA
PRO UČITELE
Leonhard Tjuier
Brno 2001
*-ovi a
vídá
Obsah
:jich
předmluva 3
Obsah 5
1 Kombinatorika 7
1 Co to je kombinatorika a kdy vznikla.............. 7
2 Základní kombinatorické funkce................ 11
3 Základní kombinatorické pojmy................ 19
4 Rozklady konečných množin.................. 32
5 Princip inkluze a exkluze.................... 40
6 Rozklady přirozených čísel na sčítance............. 48
7 Rozdělování do přihrádek.................... 55
8 Řešení rekurentních formulí .................. 59
9 Vytvořující funkce ....................... 71
10 Bloková schémata, latinské čtverce a konečné roviny..... 81
2 Teorie grafů 97
1 Co to je teorie grafů a kdy vznikla............... 97
2 Základní pojmy......................... 101
3 Souvislé grafy.......................... 108
4 Stromy.............................. 112
5 Mosty, artikulace a některé grafové charakteristiky ...... 125
6 Eulerovské a hamiltonovské grafy............... 131
7 Rovinné grafy.......................... 139
8 Barvení grafů.......................... 149
9 Zobecnění pojmu graf...................... 159
Dodatek 1: Biografie 162
Dodatek 2: Tabulky 167
Rejstřík 173
Literatura 177
5
Kapitola 2
Teorie grafů
1   Co to je teorie grafů a kdy vznikla
Odpověď na uvedené otázky je tentokrát poněkud jednodušší než tomu bylo u analogických otázek v 1. kapitole.
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 v této kapitole hovořit, má vcelku jednoduchou a názornou interpretaci. Podobně jako v 1. kapitole si však musíme 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 souvislostech. 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, neboť v souvislosti s touto úlohou se v matematice pojem „graf' objevil poprvé.
Jak tato úloha zní? Městem Königsberg (česky Královec, dnešní Kaliningrad 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ě.
97
98
//. TEORIE GRAFŮ
Obr. 1.1: Schéma 7 mostů v Konigsbergu
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 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.
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 C„H2„+2. (Jak čtenář patrně ví, první tři členy uhlovodíkové řady, tj. metan, etan, propan, mají jediný izomer, čtvrtý člen již má izoméry 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ž
Obr. 1.2: Grafová interpretace úlohy o 7 mostech
1. Co to je teorie grafů a kdy vznikla?
99
vychází jediná hrana, odpovídají atomům vodíku. Jak uvidíme v paragrafu 4, jsou uvedené grafy případem tzv. „stromů".)
ô
metan
(a)
propan
butan
(b) (c) (d)
Obr. 1.3: Grafy izomerů uhlovodíku
izobutan
(e)
Analogicky se přirozeným způsobem k pojmu „graf dostal G. Kirchhoff 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 maďarský matematik D. Kö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řiceti 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 /0 (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.)
100
//. TEORIE GRAFŮ
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 konkrétního „nakreslení". Toto kreslení bude důležité jen v některých případech (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 obchodní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 paragrafuje 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 jednotlivých typů grafů (orientovaných, neorientovaných, multigrafů, hypergrafů atd.) popíšeme v paragrafu 9.
2. Základní pojmy
101
2  Základní pojmy
2.1. Definice. Buď U ý 0 libovolná množina, buď H C ^2(í/)- Uspořádanou dvojici [t/, //] nazýváme gra/.
Prvky množiny U nazývame wz/y (nebo též vrcholy) grafu, prvky množiny // /irarcy grafu [t/, 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) Nechť U je tříprvková množina {x, y, {x, y}}, H buď množina {{x, y], {x, {x, y}}}. Pak je podle definice 2.1 [U, H] graf. Popis tohoto grafu je však nepřehledný, neboť [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 n H = 0.
(c) Uvědomme si, že v grafu [£/, 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] g H budeme obvykle užívat jednoduššího zápisu xy e H, tj. budeme hovořit o hranách xy,uv,ab a podobně. (Přitom je zřejmé, žexy e H právě tehdy, když y x e H, tj. hrany jsou podle definice „neorientované".) Je-li x e 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 nekonečná. Říkáme, že [Í7, 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ědomme 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 = 3*2{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 obrázků. Tak například říkáme, že x, y jsou koncové uzly hrany xy, o uzlech u,v e U říkáme, že jsou sousední, pokud uv e H, hrana ab spojuje uzly a, b, hrana xy je incidentní s uzly x, y atd.
102
II. TEORIE GRAFŮ
d
(a) (b)
d
(C)
Obr. 2.4: Různá nakreslení grafu K4
2.3. Definice. Úplným grafem na množině U ý 0 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. Buďte dány grafy %x = [Uu //,], %2 = [U2, H2]. Pak říkáme, že:	
(a) »1 = #2, jestliže tf, = £72, tfj = H2,	
(b)     je podgrafem grafu §,2, jestliže Č7i C U2, Hx C #2,	
(c) #1 Je faktorem grafu $2, je-li podgrafem grafu $2 a C/i	= u2,
(d) §1 je vlastním podgrafem grafu #2, je-li podgrafem přitom £1 ^g2,	tohoto grafu a
(e) §1, §-2 jsou disjunktní, jestliže í/j D U2 = 0,	
CO # 1 > $2 jsou komplementární, jestliže t/j = U2, H\D H2	= 0, H\U H2 =
2. Základní pojmy
103
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.
d o
(a) (b) Obr. 2.5: Komplementární podgrafy grafu K4
2.6. Definice. Buď [U, H] graf. Řekneme, že uzel x e 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 g 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 nekoneč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 g K, xy e H     <=>■     \x - y\ e Q,
je zřejmě [E, 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é.
104
77. TEORIE GRAFŮ
Obr. 2.6: Graf, jehož všechny uzly mají stupeň 2
2.8. Věta. Buď[U, H] konečný graf. Pak platí
J]stx=2-|/7|.
xeU
Důkaz. Indukcí vzhledem k číslu \H\. Je-li \H\ = 0, tj. H = 0, je tvrzení zřejmé, neboť st x = 0 pro každý uzel x e U. Nechť tvrzení platí pro každý graf na množině uzlů U, který má nejvýše h hran. Buď nyní % = [U, H] takový graf, že \H\ = h+l. Budxy e H libovolná hrana. V grafu g* = [U, H-{x, y}] je h hran, takže v §,* platí VJ st x = 2 ■ h. Stupně všech uzlů v %, a %,* jsou však
stejné až na uzly x, y, které mají v $ stupeň o jedničku větší než v $*'. Odtud
zřejmě plyne, že v % platí YJ st x = 2 ■ h + 2 = 2 ■ (h + 1). •
xeU
V důkazu věty 2.11 využijeme následujícího označení.
2.9. Definice. Buď % = [U, H] konečný graf, k 6 No buď libovolné. Pak klademe
= l{* € í/; stx = *}|.
Symbol <rk{§) tak udává počet uzlů stupně k v grafu %. Je evidentní, že pouze pro konečně mnoho k e N0 je Okify) ¥ 0. (Předpokládáme, že % je konečný!)
Například v grafu na obrázku 2.5a je ct0 = 1, cr2 = 3, ak - 0 pro 0 i- k i- 2. V grafu na obr. 2.5b platí ax = 3, <r3 = 1, ak = 0 pro ostatní k.
Z definice čísel ak je zřejmé, že platí
2.10. Pomocná věta. Bud'% = [U, H] konečný graf. Pak
oo
]T)st x = J^kcrk{$).
xeU k=0
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
105
Důkaz. Buď §t = [U, H] konečný graf. Počet uzlů lichého stupně je roven číslu
00
X>2/+i. Přitom
;=0
00 00 00
;=0 j'=0 ;=0
00 oo
;=0 ;=0
Odtud celkem
oo oo
^ er2;+i = 2 • |# i - £ 2; • (ct2j- + a2j+i).
;=0 y=0
Protože na pravé straně poslední rovnosti stojí prokazatelně číslo sudé, je i
oo
číslo    alj+\ sudé. •
j=0
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: buď dána konečná posloupnost a\,a2,... ,an nezáporných celých čísel. Tato posloupnost se nazývá grafová, když existuje graf [U, H] takový, že U = {u\,..., un], st wř = a,, i = l,... ,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 [12], 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 e U.
106
II. 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)
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 obrá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 (alespoň prozatím) prakticky nepoužitelný. V těchto případech je nej obvyklejší 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
107
4 5 6
1 2 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 a^ = 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.
108
II. TEORIE GRAFŮ
3  Souvislé grafy
3.1. Definice. Buď [U, H] graf, x0, xn e U buďte libovolné uzly. Posloupnost uzlů a hran tvaru
Xq, XoX{, x\, x\X2, . . . , xn-i, xn-{xn, xn
se nazývá sled začínající v uzlu xq a končící v uzlu xn. Uzly x\,..., x„_i 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ýva se tah uzavřeny. 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
109
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 otevřený tah, avšak není to cesta, neboť se opakuje uzel 5.
3.6. Věta. Nechťv grafu [U, H] existuje mezi uzly x, y e U, x ^ y sled. Pak mezi nimi existuje v daném grafu alespoň jedna cesta.
Důkaz. Tvrzení je vcelku zřejmé. Nechť je dán sled mezi uzly x, y:
x = xq, xqXi, ..., jc„_i, x„^ixn, xn = y.
Pokud tento sled není cestou, existují x,-, x j, i < j, tak, že jc, = x j. Pak ale je Xo,..., Xi, XjXj+i, Xj+i,... iX„ opět sled mezi uzlu x, y. (Z původního sledu jsme „vyškrtli" úsek od x, do x j.) 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í, neboť 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. Buď [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. Buďte u, v e U — {x} libovolné dva navzájem různé uzly. (Kdyby takové dva uzly neexistovaly, bylo by U = {x, y}, H = {xy} a graf [U - {x}, H - {xy}] by byl [{y}, 0], 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ědomit, ž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, neboť 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ý. •
110
//. TEORIE GRAFŮ
3.11. Poznámka. Graf [U - {x}, H — {xy}] je tedy souvislý vlastní podgraf grafu [f/, H] (za předpokladů věty 3.10).
Buď [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 poznámky 3.9, symetrie a tranzitivita je zřejmá.) Tato ekvivalence určuje rozklad 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) = {f e U; existuje sled mezi uzly t, x).
Označíme-li
H (x) = {uv e H; u e U(x), v e U(x)}, je zřejmě [U(x), H (x)] podgraf grafu [U, H] (pro každý uzel x e U).
3.12. Dennice. Buď [U, H] graf, x e 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 e 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 q(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 e U platí:
(a) q{x, y) = 0 právě tehdy, když x = y,
(b) Q(x,y) = g(y,x),
(c) q(x, y) + o(y, z) > q(x, z).
To však právě znamená, že (Í7, q) je metrický prostor.
Lze tedy na souvislé grafy aplikovat i metody teorie metrických prostorů.
3. Souvislé grafy
111
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.
Obr. 3.10: Kružnice
Graf na obrázku 3.10a se - vcelku pochopitelně - rovněž nazývá trojúhelní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.
112
U. 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 koneč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.
Obr. 4.11: Les
Stromy lze charakterizovat různými způsoby. V následujícím tvrzení uvedeme některé nutné a dostatečné podmínky toho, aby graf byl stromem.
4.3. "Veta. Buď[U, H] konečný graf. Pak jsou následující tvrzení ekvivalentní:
4. Stromy
113
(a) [í/, 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\-\.
(d) [U, H] neobsahuje kružnici a \H\ - \U\ — 1.
Důkaz. Dokážeme postupně implikace (a)=*-(b), (b)=»(c), (c)=Kd), (d)=Ka).
(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 m, v e 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 e 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é. Nechť tedy uvedená rovnost platí pro všechny grafy splňující (b) s počtem uzlů nejvýše n. Nechť [U, H] je graf splňující (b) takový, že \U\ = n + 1. Buď uv e 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): Nechť graf [U, H] splňuje podmínku (c). Potřebujeme dokázat, že v tomto grafu neexistuje kružnice. Připusťme tedy, že v grafu [U, H] kružnice existuje. Je-li xy e 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 neobsahující žádnou kružnici, tj. strom. Počet hran v tomto stromu je však menší než \U\ — 1, neboť tolik hran měl podle předpokladu graf [U, H]. To je však spor, neboť jsme již dokázali, že (a)=S>(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 [i7, H] splňuje podmínku (d) a není souvislý. Pak je tvořen komponentami %\,... ,%n (n > 2). Každá z těchto komponent je stromem (neboť [U, H] je podle (d) les). Označme % = [Uit H{\. Protože (a)=Kc), platí \Hi\ = \Ut\ - 1 pro i = 1,...., n. Odtud
\H\ = J2\Hi\ = J^(\Ui\ - 1) = \U\ - n,
114
//. TEORIE GRAFŮ
kde n > 2. To je však spor, neboť 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. Buď [U, H] strom, \U\ > 2. Podle vět 2.8 a 4.3 platí J]st jc = 2- |H|=2.(|Í/| - 1) = 2-\U\ -2.
jceí/
Přitom st x > 1 pro každý uzel x e U. Kdyby alespoň dva uzly neměly stupeň 1, bylo by číslo     st x větší než 2 • \U\ — 2. •
JC€Í/
4.5. Příklad. Buď 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/V
o o o
(a)
Obr. 4.12: Had a hvězda
V definici 2.4 jsme definovali faktor grafu [ř/, //] 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, Hi), 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 vynecháním právě jedné hrany.
(c) Strom obsahuje právě jednu kostru - sebe sama.
4. Stromy
115
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. Buď [U, H] konečný souvislý graf. V tomto grafu jistě existuje nějaký podgraf, který je stromem. Stačí totiž zvolit libovolný uzel x e U a podgraf [{x}, 0] 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 4 je konečná, obsahuje alespoň jeden maximální prvek (tj. strom, který není podgrafem žádného jiného stromu). Buď 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řipusťme, že je U i- U*, tj. existuje y e U — U*. Zvolme x e 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 e H taková, že u € U*, w g U*. Pak je ale zřejmě [UU{w}, HU{vw}] strom v [U, H], (Souvislost je zřejmá, neboť [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, neboť [£/*, 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 K„ je roven číslu n"~2.
Důkaz. Důkaz tohoto tvrzení nebudeme provádět. •
116
//. 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 (ay)"^ definována takto:
— 1,   jestliže i j € H, st í,   jestliže i = j, 0,     jestliže i ^ j, i j & H.
Následující příklad uvádíme z toho důvodu, že ilustruje užitečnost vytvořujících funkcí zavedených v 1. kapitole.
4.11. Příklad. Žebřík Z„ je graf s 2n uzly definovaný tak, jak je znázorněno na obr. 4.14.
x2 -o—
*3
-o—
xn-l
-o—
-o
y 2
ľ3
y„-i
Obr. 4.14: Žebřík
Naším úkolem je určit počet An koster v žebříku Z„.
<pn-faktorem v Z„ nazveme takový faktor, který je utvořen dvěma disjunktními stromy (viz definici 2.4), z nichž jeden obsahuje uzel xn a druhý uzel yn. (Příkladem ^„-faktoru v Z„ je faktor, jehož jeden strom obsahuje všechny uzly Xi a druhý všechny uzly y,-.) Počet <pn-faktorů v Z„ označme Bn.
Je zřejmé, že platí A\ = B\ — 1.
Nyní odvodíme rekurentní formule pro výpočet hodnot An, Bn. Předpokládejme, že známe A\, ..., A„, B\,..., B„. Uvažme, jak můžeme zkonstruovat kostru v Z„+i. Je zřejmé, že to lze právě jedním z následujících dvou způsobů:
(a) K některé kostře v Z„ přidáme některé dvě z hran x„xn+i, xn+1yn+i, y„y„+i. Z každé kostry v Z„ tak získáme tři kostry v Zn+\.
(b) K některému ^„-faktoru v Z„ přidáme všechny tři hrany xnxn+\,xn+\yn+i,
ynyn+\-
4. Stromy
117
Odtud plyne formule An+\ = 3An + Bn. Stejně jednoduše lze odvodit formuli Bn+\ = 2An + Bn. Takto získané rekurentní formule nyní vyřešíme pomocí vytvořujících funkcí. Položme
oo oo
F{x) = YJ^nxn,      G(x) = J2B»xn-
n=\ n=\
Pak platí
oo oo
3F(x) + G(x) = £(3A„ + Bn)xn = £ A„+i*»,
n=l n=l 00 oo
x[3F(x) + G(x)] = x ■ ^2 An+lxn = ^ A„xn = F(x) - Axx = F(x) - x. Analogicky
x[2F(x) + G(x)] = G(x) - x.
Budeme-li stručně místo F(x) psát pouze F amísto G(x) pouze G, obdrželi jsme následující dvě rovnice pro neznámé F, G:
x(3F + G)   = F-x x(2F + G)   = G-x.
Úpravou dostáváme
FQx- 1)+jc(G + 1) = O x(2F + 1) + G(x - 1)   = 0.
Ze druhé rovnice plyne
x(2F +1) 1 — x
takže dosazením do první rovnice máme
x(2F + 1) + 1 - x
F(3x -l)+x- —---=0.
1 — x
Odtud
F(x) =
x1 — 4x + 1'
Funkci F(x) nyní rozložíme v mocninnou řadu. Platí
x2 - 4x + 1 = (x - a)(x -B),   kde a = 2 + VŠ, 6 = 2 - VŠ.
118
II. TEORIE GRAFŮ
Rozložme funkci F(x) na parciální zlomky: x x
F(x) =
A B
+ ■
x2-4x + \    (x-a)(x~P)    x — a x-fi Konstanty A, B určíme porovnáním koeficientů v rovnosti
x = A{x - B) + B(x-a).
Protože
2 +V3 2VŠ '
B =
V3-2 2^3
dostáváme
V3 + 2      1       73-2  _ 1 2V3    x-ot      2*/3 x
1   / 1
j_ = J_ (_a___P_\ =
-p   %J3 \x-a x-p)
l/l 1 \
Protože zlomky v závorce můžeme (pro vhodné jc) považovat za součty geo-
XX
metrických řad s kvocientem —, respektive —, dostáváme
P a
F(x) =
/ x\ X   n 1 /l l\
1      JÍL ~   R-"_n/-n °° a-n_„-n
a-p
a - P
n=0 n=0       " n=l
Protože qíj6 = 1, platí pro všechna n rovnost anpn = 1. Odtud plyne, že
F(x) = --rzi,-* = L
n=l
a-p ^ a-p
x .
Protože však podle definice F(x) = £ Anxn, dokázali jsme tak
«=1
An =
a" - pn 1
"     a-p 2V3
[(2 + n/3)"-(2-n/3)"]
4. Stromy
119
4.12. Poznámka. S určovaním počtu koster v daném grafu úzce souvisí problém, kolik vlastně existuje grafu 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 c IP^iU), přičemž víme, že \3*2(JJ)\ = (^j' ^z
věta 3.4 z 1. kapitoly.) Všech grafů s množinou uzlů U je tedy tolik, kolik má množina 3*2(11) podmnožin. Označíme-li gn počet grafů na n uzlech, platí podle uvedeného
* = 2©.
Jak rychle roste posloupnost (gn)%ii, plyne z následující tabuľky:
n	1	2	3	4	5	6	7	8	
gn	1	2	8	64	1024	32768	2097152	2684354 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.15.
Obr. 4.15: Grafy na třech uzlech
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.
120
II. TEORIE GRAFŮ
4.13. Definice. Buďte [Uu Hi), [U2, H2] grafy. Zobrazení /: U\ -*■ U2 se nazývá izomorfismus grafu [U\, Hy] na graf [í/2. #2]» když platí:
1. / je bijekce,
2. xy e Hi právě tehdy, když f(x)f(y) e #2.
Dva grafy jsou izomorfní, když mezi nimi existuje alespoň jeden izomorfismus.
Č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.16.
Odvození metody pro výpočet počtu h„ neizomorfních grafů na n uzlech přesahuje naše možnosti. (Jde o tzv. Pólyovu enumerační metodu, o níž jsme se zmiňovali již v paragrafu 1 1. kapitoly.) Existuje však jednoduchý odhad pro čísla hn; je totiž zřejmé, že platí
2®
K > —,
ni
neboť 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 totiž dokázat, že
. hm   K---
n-*oo \ n\
I posloupnost (A„)~j 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	1034	12344	308168	
Dokonce i počet tn neizomorfních stromů na n uzlech (při veškeré .jednoduchosti" 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ě 172).
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 jednoznač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).
4. Stromy
121
Obr. 4.16: Neizomorfní grafy na čtyřech uzlech
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.14. Definice. Nechť je [U, H] graf. Buď dáno zobrazení / : 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)
122
//. TEORIE GRAFŮ
4.15. Definice. Buď [£/, H, f] hranově ohodnocený konečný souvislý graf. Kostra [U, H*] grafu [U, H] se nazývá minimální kostra v [U, H, /], když pro každou kostru [U, Hi] grafu [U, H] platí
4.16. 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.17. Příklad. Buď dána množina měst A, B, C, D, E, F. V tabulce 4.2 nechť 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 želez-
	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
niční síť 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í minimální kostry bez znalosti vhodného algoritmu velmi obtížné. Proto si nyní jednoduchý algoritmus pro konstrukci minimální kostry uvedeme. (První algoritmus pro nalezení minimální kostry nalezl již v r. 1926 O. Borůvka, jak jsme se již zmínili v paragrafu 1 1. kapitoly. Podrobněji o historii tohoto algoritmu viz. např. v [13]).
4. Stromy
123
4.18. Veta. Algoritmus pro hledání minimální kostry: Buď[U, H, f] konečný souvislý hranově ohodnocený graf. Všechny hrany sestavme do posloupnosti (hi,..., h„) tak, aby posloupnost (f (h\),..., 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) PoM H0 = 0, i = 1.
(2) Obsahuje graf[U,       U {hi}] kružnici? Pokud ano, přejdi k bodu (4). Pokud ne, přejdi k bodu (3).
(3) Polož Ht =       U {A,}. Přejdi k bodu (5).
(4) Polož Hi =
(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 vrať se k bodu (2).
Popsaným způsobem skutečně v [U, H] sestrojíme minimální kostru [U, K]. 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í J2 fW ^
< E f (h).
h&L
Tento důkaz nebudeme provádět. Jednoduše jej lze provést například pomocí teorie tzv. matroidů, o nichž v tomto textu nehovoříme.
Řešení příkladu 4.17. 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.17.) (Víme, že kostra musí obsahovat 5 hran.) Minimální náklady na železniční síť jsou tak 30 milionů Kč.
4.19. Příklad. Na obr. 4.18a je hranově ohodnocený graf, na obr. 4.18b jeho minimální kostra. Ponecháme čtenáři, aby si promyslel, zda je tato minimální kostra určena jednoznačně.
124
//. TEORIE GRAFŮ
a b a b
d e d
Obr. 4.17: Minimální kostra
Obr. 4.18: Minimální kostra v ohodnoceném grafu
Poznámky a cvičení
1. Najděte sedm neizomorfních podgrafů grafu ^3.
5. Mosty, artikulace a některé grafové charakteristiky
125
5   Mosty, artikulace a některé grafové charakteristiky
V předcházejícím paragrafu jsme hovorili 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.19 obsahuje právě jeden most - hranu xy.
Obr. 5.19: Graf s jediným mostem
5.3. Věta. Buď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 e U grafu [U, H] je artikulace, když existují hrany xy, xz e 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.20 má právě jednu artikulaci - uzel x.
126
//. TEORIE GRAFŮ
b
o
a
x
e o-
■ód
Obr. 5.20: Graf s jednou artikulací
5.7. Definice. Buď % = [U, H] graf, uv g H libovolná hrana. Množinu H(uv) c H definujeme takto: je-li hrana uv mostem, je H(uv) = {uv}. Pokud uv mostem není, pak
H(uv) = {xy e H; existuje kružnice v %, obsahující xy i uv }.
Dále položme
U (uv) - {t e U; t inciduje s některou hranou z H(uv)}.
Pak je zřejmě [U(uv), H(uv)] podgrafem grafu Tento podgraf nazýváme člen grafu %, příslušný hraně uv.
5.8. Příklad. Člen grafu z obr. 5.20 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.
Buď [U, H] graf auv,xy jeho libovolné navzájem různé hrany takové, že H(uv) n H(xy) i- 0. Nechť například ab e H(uv) n H(xy). Pak v [U, H] existuje kružnice R\ obsahující hrany uv i ab. Nechť Ri = [U\, H\], R2 = = Wz, Hz\. Podle předpokladu je |ř/i D U2\ > 2, neboť a, b C U\ n U2. Buďte r, s € Ui r\U2 libovolné navzájem různé uzly. Pak existuje v R\ cesta z r do s obsahující hranu uv. Protože U\ n U2 je konečná množina, existují prvky r0, s0 e Ui n U2 takové, že délka uvedené cesty je minimální. Označme tuto minimální cestu C\. Protože však ro, sq g í/2, existuje mezi ro, cesta C2 v i?2 obsahující hranu jcy. Spojením cest C\ 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 g H(uv) a současně uv g H(xy). Odtud plyne //(mu) = //(xy).
Právě jsme tak dokázali, že pro dvě hrany uv, xy g H platí buďto H(uv) Pí n H(xy) = 0 nebo H(uv) = H(xy). Protože pro libovolnou hranu uv e H
5. Mosty, artikulace a některé grafové charakteristiky
127
platí uv € //(mu), je H(uv) ^ 0. Odtud celkem plyne
5.9. Věta. Systém množin {H(uv); uv e H} tvoří rozklad na množine 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. Buď % = [U, H] konečný graf. Cyklomatickým číslem grafu nazýváme číslo
v($) = \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é.
Důkaz. Buď [U, H] konečný souvislý graf, tj. k = 1. Podle věty 4.8 existuje v [U, H] kostra [U, H{\. Podle věty 4.3 platí \Hi\ = \U\-l. Protože \Hi\ < <\H\, plyne odtud\H\>\U\-l, tj.
\H\ -\U\ + 1 > 0.
(b) Nechť [U, H] je konečný nesouvislý graf s komponentami [Uu H{\,[Uk, Hk]. Podle (a) pro každé i = 1,2,..., k platí \Ht\- \Ut\ + + 1 > 0,takže
k
£(|tf,|-|t/,| + l) = |//|-|ř/|+A:>0.
Z důkazu věty 5.12 a věty 4.3 okamžitě plyne
128
77. TEORIE GRAFŮ
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, v($) udává, kolik hran je v §, nutno odstranit, aby v $ 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 komplikovaně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. Buď $ = [U, 77] souvislý graf. Množina A C U se nazývá uzlový řez grafu [U, H], jestliže se souvislost grafu poruší, vyškrtneme-li z [U, 77] všechny uzly množiny A a všechny hrany, které s těmito uzly incidují. (Tj. graf [V — A, 77 — {xy e 77; xy D A ý 0}] je nesouvislý.) Uzlový stupeň souvislosti w($) grafu % je minimální mohutnost uzlového řezu
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, 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. Buď %, = [U, 77] souvislý graf. Množina 77i c 77 se nazývá hranový řez v    je-li graf [U, 77 — H\] nesouvislý.
Hranový stupeň souvislosti h{%) grafu % je minimální mohutnost hranového řezu v
5.18. Poznámka. Podle definice 5.17 lze určit h(%) pro každý konečný souvislý graf kromě grafu K\ (tj. grafu o jednom uzlu). Pro tento graf definitoricky klademe h(K\) = 0.
5. Mosty, artikulace a některé grafové charakteristiky
129
5.19. Příklad. Pro graf % na obr. 5.21a platí «(£) = 2, h{%) = 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.21b, respektíve 5.21c, je graf vzniklý „odstraněním" příslušného uzlového, respektíve hranového, řezu.
(c)
Obr. 5.21: Hranový a uzlový řez v grafu
5.20. Věta. Bud'%, = [U, H] konečný souvislý graf. Pak platí
"($) < h{%) < min{st x; x e U}.
Důkaz. Je-li h (g) = 0, je také u ($) = 0, neboť $ je v tom prípade K\. Je-li h(fy) = 1, existuje hrana xy e H taková, že [U, H — {xy}] je nesouvislý graf. Pak je však zřejmě §, = Kí (a tedy = 1 podle poznámky 5.16) nebo je {x}, respektive {y} uzlový řez v g, (takže opět «(g) = 1).
Předpokládejme proto, že h{%) > 1, Buď #1 hranový řez, \H\\ = Zvolme hranu h e H\ libovolně. Na každé další hraně e e H\ zvolme uzel xe tak, že xe není incidentní s hranou h. Nyní z grafu $ odečteme všechny uzly xe {e g H\ — {h}) a hrany s těmito uzly incidentní. Je-li takto vzniklý graf nesouvislý, platí u($) < h(§.).V opačném prípade 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 m (g,) = M$).
Dokázali jsme tak, že w($) < h(fy). Druhá nerovnost ve větě je však zřejmá, neboť pro každý uzel x e 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 [í/, H] platí     st jc =
xeU
= 2\H\. Odtud však okamžitě plyne, že min {st x; x e U} < ^Q. z této nerovnosti a z věty 5.20 plyne důsledek.
130
//. TEORIE GRAFŮ
5.21. Důsledek. Buď% - [U, H] konečný souvislý graf. Pak
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 % se nazývá uzlově, respektive hranově k-souvislý, jestliže platí «($) > k, respektive h{%) > k.
5.23. Věta. (Mengerova věta.) Graf % 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 % je uzlově 2-souvislý právě tehdy, když ke každým dvěma uzlům x, y existuje kružnice v %,, která je obsahuje.
5.25. Věta. (Fordova-Fulkersonova věta.) Graf% 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í.
6. Eulerovské a hamiltonovské grafy
131
6   Eulerovské a hamiltonovské grafy
Kreslení obrázků „jedním tahem" je obvyklou součástí tzv. rekreační matematiky. Pravděpodobně každý čtenář si již jako dítě vyzkoušel, že „domeček" na obr. 6.22a lze jedním tahem nakreslit; a snadno lze ověřit, že obr. 6.22b jedním tahem nakreslit nelze.
(a) (b) Obr. 6.22: 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 % lze sestrojit jedním tahem, když v $ 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. Buď [U, H] eulerovský graf, x e 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, neboť 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
132
//. TEORIE GRAFŮ
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. Buď $ = [U, H] souvislý eulerovský graf. Dokážeme, že % lze sestrojit jedním uzavřeným tahem.
Zvolme libovolně uzel u e 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 %. 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. Nechť tedy ao € A je některý tah maximální délky.
Předpokládejme nyní, že existuje hrana xy e H, která není obsažena v tahu «0- Označme
H*  =  {xy 6 H; xy není obsažena v tahu ao}, U*   =   {x € U; existuje y e U tak, že xy e H*}.
Pak jé [U*, H*] podgraf grafu %. Z definice grafu [[/*, H*\ je přitom okamžitě zřejmé, že je to eulerovský graf.
Protože je %, souvislý, existuje nutně uzel v e U*, který je obsažen v tahu ao- Protože je [U*, H*] eulerovský, je uzel v obsažen v nějaké kružnici C grafu [U*, H*]. Když nyní v %, 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 ao až do uzlu u, vytvoříme v %, uzavřený tah obsahující uzel u, jehož délka je větší než délka tahu ao- To je však spor s definicí ao. To znamená, že H* = 0, a tak ao 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'% konečný souvislý graf. Pak lze % sestrojit jediným otevřeným tahem právě tehdy, když % obsahuje právě dva uzly lichého stupně.
Obsahuje-li %, 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. Nechť lze souvislý graf $ sestrojit jedním otevřeným tahem začínají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.
6. Eulerovské a hamiltonovské grafy
133
II. Nechť % = [U, H] je konečný souvislý graf obsahující právě dva uzly x, y Uchého stupně. Buď z & U libovolný prvek. Položme U\ = U U {z}, Hi = H U [xz, yz}- Pak je [U\, H\\ 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 disciplí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 jednoduchá 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], [U[, Hy] grafy, nazveme zobrazení / : U -> U\ homorfismem grafu [U, H] do grafu [U\,H{], jestliže pro každou hranu xy e H platí, že f(x)f(y) e H\ (tj. hrana se zobrazí na hranu). (Srovnej s definicí izomorfismu uvedenou v definici 4.13.)
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.23a. Hamilton připojil ke každému z dvaceti vrcholů tohoto dvanáctistěnu jméno některého světového velkomě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
134
//. TEORIE GRAFŮ
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.23b je znázorněno jedno z řešení. Hrany ležící na kružnici jsou vytaženy silněji. (Graf 6.23b jsme již viděli na obr. 2.8a.)
(b)
Obr. 6.23: Povrch dvanáctistěnu Nyní uveď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.
6. Eulerovské a hamiltonovské grafy
135
(b) Graf na obr. 6.23b 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ě uveď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, neboť 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. (Srovnej s Eulerovým magickým čtvercem ve cvičení k paragrafu 10, kap. 1.)
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 uveďme některé vlastnosti hamiltonovských grafů. Následující nutná podmínka plyne bezprostředně z důsledku 5.24.
136
U. TEORIE GRAFŮ
6.11. Věta. Je-li fy hamiltonovský graf, jejeho uzlový stupeň souvislosti u(fy) > > 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.24 má uzlový stupeň souvislosti roven 2, je však snadné se přesvědčit, že není hamiltonovský.
Obr. 6.24: Graf s u(fy) = 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.
n
6.12. Věta. Nechť fy = [U, H] je konečný graf |t/|=rc>3astjc>— pro každý uzel x e U. Pak je fy hamiltonovský.
Důkaz. Uvědomme si nejprve, že každý konečný graf je podgrafem nějakého hamiltonovského grafu. Zejména můžeme graf [U, H] doplnit o množinu uzlů V a o množinu hran {xy; x e U, y e V} na hamiltonovský graf. Je-li totiž U = {«i,..., un), stačí položit V = {v\,... ,vn) (kde U D V = 0) a hamiltonovskou kružnicí je zřejmě kružnice procházející postupně uzly «1, u[, u2, vi, ■. ■, un, v„, Ui.
Nechť nyní graf % = [U, H] splňuje předpoklady věty a připusť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 tak obdržíme hamiltonovský graf §,*. Je-li U = {«!,,,., un), V = {vu ..., vk}, U* - U U V, H* = H U {uiVj-; u i e U, vj e V}, je %* = [U*, H*]. V %* tedy podle předpokladu existuje hamiltonovská kružnice C, procházející postupně uzly x\, xi, ..., xm, kde m = n + k > 4, neboť podle předpokladu je n > 3, k > 1. Označení uzlů jistě můžeme zvolit tak, že x\ =u\,x2 = V\,x^ = u2 (tj. kružnice začíná „doplněnou" hranou). V H nyní nemůže být hrana X]X3 (= U]U2). Kdyby
6. Eulerovské a hamiltonovské grafy
137
totiž x\x-$ € H, bylo by doplnění grafu % o uzel x2 = vi 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 x\Xj € # pro některé i ^ 3, pak x^Xi+\ & K, tj. x^Xi+i € //*, neboť x3x;+i jistě není hrana kružnice. Kdyby totiž x^Xj+i e K, mohli bychom v $* sestrojit kružnici procházející postupně uzly
Tato kružnice je však hamiltonovská v grafu, který obdržíme z $* odečtením uzlu X2 = V] 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 x\Xi. Uvědomme si, že v %* platí st u j > I + k pro každý uzel u j e U. (V % je st u j > |, v gt* s uzlem u j navíc sousedí uzly V\,..., vk.) Protože v kružnici C sousedí s uzlem x\ dva uzly, je v AT alespoň | + k — 2 hran tvaru x\Xi. Podle výše uvedeného to však znamená, lev H* není minimálně j+k — 2 hran tvaru j^jcj (kromě hran x-}Xj+\ pro xi*,- e K je to, jak již víme, ještě hrana xjxy.)
Nyní uvažme, co všechno o uzlu x3 víme. Vychází z něho alespoň | + k hran ^3*;, přitom však v $* nesousedí minimálně s | +& — 1 uzly x, ^ *3-Protože však všech uzlů xt ^ xj, je n + k — 1, musí platit
Odtud však plyne, že k < 0, což je spor s předpokladem, že % není hamilto-
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. Nechť pro každé dva uzly x, y e U, které nejsou sousední, platí
x\, Xj, Xj-\, jc,'_2, • • •, x3, Xj+i, Xi+2> •••> Xi-
novský, takže k > 1.
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ů.
138
II. TEORIE GRAFŮ
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 nej vý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.25.
Obr. 6.25: 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 K-i tři hamiltonovská kružnice, v nichž je obsaženo všech 21 hran grafu Ky.
7. Rovinné grafy
139
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, neboť žádná dennice 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. Buď 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 plochá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] c Ei při zobrazení /: Ei -» E2, které je prosté, spojité a má tu vlastnost, že inverzní zobrazení f~x je rovněž spojité.) Protože oblouků mezi dvěma body x, y e E2 existuje nekonečně mnoho, plyne odtud, že graf může mít v rovině nekonečně mnoho nakreslení.
Na obr. 7.26a-d jsou oblouky mezi uzly x, y. Na obr. 7.26e 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 provedeno například na obr. 7.26d. Přesto má obecně graf nekonečně mnoho nakreslení, neboť 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.27a-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.27, jsou izomorfní.
140
//. TEORIE GRAFŮ
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 izomorfní, 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 rovinný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.27a. (Podle této známé rekreační úlohy se
7. Rovinné grafy
141
(c)
Obr. 7.27: 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í, neboť graf na obr. 7.27a 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.28a). Důležité totiž je, že existuje nakreslení, v němž se hrany neprotínají (obr. 7.28b). Tentýž graf lze však nakreslit ještě mnohem „elegantněji" (obr. 7.28c).
Existence nakreslení grafu K4 z obr. 7.28c 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. Veta. 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. Buď [U, H] rovinný souvislý graf. Buď dáno některé jeho rovinné nakreslení. Označme W množinu všech oblastí, na něž je tímto nakreslením rovina rozdělena (včetně „vnějšku"). Pak trojici [17, H, W] nazveme mapou.
142 II. TEORIE GRAFU
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.28c obsahuje 4 oblasti. Nakreslení téhož grafu na obr. 7.28a žádnou mapu neurčuje, neboť uvedené nakreslení není rovinné.
7.9. Veta. (Eulerova věta.) Bud'[U, H, W] libovolná mapa. Pak
\W\ + \U\-\H\ = 2. (7.1)
Důkaz. Indukcí vzhledem k číslu Je-li H = 0, je nutně \U\ = 1, neboť 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'[ř7, 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 [U\, H\], [U2, H2]. Protože \Hi\ < n, l/fel < < n, platí podle indukčního předpokladu pro mapy [U\, H\, Wi]a[ř/2» ^2> W2J
|Wl| + |t/i|-|/í1| = |W2| + |í/2|-|//2|=2.
Dále platí \H\\ + \H2\ + 1 = \H\ (neboť od H jsme odečetli hranu xy) a \U\\ + + |í/2| = \U\. Odečtením mostu se v dané mapě počet oblastí nezměnil, avšak v součtu I Wi j+| W21 je „vnějšek" započítán dvakrát. Proto | Wi |+| W21 = | W\+1. Odtud celkem dostáváme:
\W\ + \U\ - \H\ = (\Wi\ + \Wi\ - 1) + (|ř/il + IÍ/2I) --      I + \H2\ + 1) = (|Wi| + |t/,| - |//i|) + (|W2| + |í/2| - \H2\) -2 =
= 2 + 2-2 = 2.
7. Rovinné grafy 143
V prípade, že [U, H] obsahuje most, je tak věta dokázána.
(b) Nechť [U, H] neobsahuje most. Buď h e 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, H\, W\] 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 \ Hi\ = n, platí pro mapu [U, H\, W\] rovnost 7.1, tj. \Wi\ + \U\ - \Hi\ = 2. Odtud však plyne platnost 7.1 i pro mapu [U, Hf W]. •
Pomocí Eulerovy věty lze snadno dokázat následující důležité tvrzení.
7.10. Věta. Graf K$ (tj. úplný graf na pěti uzlech) ani graf z obr. 7.27a (tj. graf „3 domy a 3 studně") není rovinný.
Důkaz, (a) Připusťme, že graf K5 je rovinný Nechť 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 K$ 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 nakreslení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.29), i když jsme se s nimi již nejednou setkali.
7.12. Definice. Buď [U, H] libovolný graf, xy e H jeho libovolná hrana. Buď z ^ U U H libovolný prvek. Položme U* = U U {z}, H* = (H — {xy}) U {xz, yz). Pak řekneme, že graf [t/*, H*] vznikl z grafu [ř7, H] půlením hrany xy.
7. Rovinné grafy
145
7.13. Příklad. Graf na obr. 7.30b vznikl z grafu na obr. 7.30a 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 Jť jsou homeomorfní, jestliže existují konečné posloupnosti grafů
$1 > $2< ■ ■ ■ >%n
10   if    IP IP ďí, Jt\, Jli, . . . , ďlm
takové, že :
(a) g„ je izomorfní s Jťm;
(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. Veta. 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.29).
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) pravidelný dvanáctistěn, (e) pravidelný dvacetistěn. (Viz obr. 7.31).
Neuměli však dokázat, zda existují ještě jiné pravidelné mnohostěny. Metodami teorie grafů nyní ukážeme, že žádné další pravidelné mnohostěny neexistují. K tomu však potřebujeme několik jednoduchých pojmů.
Omezená množina T c e3 se nazývá hvězdovitá, když existuje bod seľ 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.
146
//. TEORIE GRAFŮ
(a) (b)
Obr. 7.31: 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á Schlafliův symbol daného pravidelného mnohostěnu.
Schlafliů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áctistě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
7. Rovinné grafy
147
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ě:
Nechť se sféra S dotýká roviny E2 v bodě P. Buď P N průměr sféry S (viz obr. 7.32). Buď* e S libovolný bod různý od N. Bod f (x) e E2 je průsečík polopřímky N x s rovinou E2. Je zřejmé, že stereografická projekce / je bijekcí množiny S — {N} na E2 a zobrazení / i f~x 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.)
N
Obr. 7.32: Stereografická projekce
Buď 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)
148
II. TEORIE GRAFŮ
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
N =
4n
R =
Ap
(7.5)
2p + 2n — np 2p + 2n — np 2p + 2n — np
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) g {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,
(c) (n	-2)(p	-2)	= 3	=^   n = 3, p	= 5	nebo	71 = 5,
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.
8. Barvení grafu
149
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 € G L platí xy e 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 e V má určenu množinu Vx c 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 e 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.
150
II. TEORIE GRAFŮ
8.4. Definice. Buď [U, H] graf. Zobrazení /: U -* N nazveme obarvení uzlů, jestliže pro každé dva sousední uzly x,y € U platí f(x) ý f (y) (tj. xyeH f(x)yíf(y)).
Řekneme, že graf [í/, //] je uzlově k-chromatický, existuje-Ii obarvení / uzlů takové, že < k.
Uzlové chromatické číslo x ($) grafu % je nejmenší číslo k e No takové, že % je uzlově k -chromatický.
Z definice je zřejmé, že každý graf má jednoznačně určené uzlové chromatické čí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'%, = [U, H] graf. Pak platí:
(a) = !  <=► H=0.
(b) Je-li % strom a \H\ > 1, pak x($) = 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. Veta. Buď % = [U, H] graf, H jí 0. Pak X(%) = 2 právě tehdy, když neobsahuje kružnici liché délky.
Důkaz. I. Nutnost podmínky je zřejmá, neboť k obarvení kružnice liché délky je nezbytné užít alespoň tří barev.
II. Nechť % = [U, H] neobsahuje kružnici liché délky. Dostatečnost této podmínky budeme dokazovat indukcí vzhledem k počtu kružnic v %. Uvědomme si přitom, že důkaz stačí provést pro souvislé grafy, neboť obarvení uzlů v jednotlivých komponentách můžeme provádět samostatně a nezávisle na sobě.
Neobsahuje-li % žádnou kružnici, je % strom a podle věty 8.5(b) platí X ($) = 2. Nechť tedy tvrzení platí pro každý souvislý graf obsahující nejvýše n kružnic sudé délky. Buď nyní $ = [U, H] graf obsahující n + 1 kružnic sudé délky. Buď C libovolná kružnice v %,. Zvolme v C libovolně hranu xy. Graf %* = [U, H — {xy}] obsahuje nejvýše n kružnic, takže podle předpokladu platí /($*) = 2. Odtud plyne existence obarvení uzlů /: U -> {1,2} grafu %,*. 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 / je současně obarvením grafu    čímž je důkaz hotov. •
8. Barvení grafu
151
8.7. Definice. Nechť $ = [U, H] je graf a nechť lze množinu U rozložit na dvě neprázdné disjunktní podmnožiny Ui,U2 tak, že každá hrana má jeden uzel v í/i a druhý uzel v f/2- Pak se graf % nazývá bipartitní. Uvedený bipartitní graf se obvykle zapisuje ve tvaru [U\, U2, H], Bipartitní graf [U, V, H] se nazývá úplný, když pro každé dva uzly x e U, y e V platí xy e H. Je-li \U\ = m, \ V\ = n, značí se úplný bipartitní graf [U, V, H] symbolem Kmn.
Tak napríklad Kuratowského graf „3 domy a 3 studně" na obr. 7.29b je graf AT3,3. Pro bipartitní graf % s neprázdnou množinou hran zřejmě platí x($) = 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-úce chlapců (k < \H\) taková, že všech dívek, které by znal alespoň jeden chlapec z této £;-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 5,-, i = 1, ..., n, neprázdných konečných množin. Pak jsou následující tvrzení ekvivalentní:
n
(a) Existuje prosté zobrazení f: {1,...,«}     |JS; takové, že f (i) e 5; pro každé i = 1,..., n.
(b) Pro každou podmnožinu 0/AC{1,...,b) platí \A\ <
U St
Grafová interpretace Hallovy věty je jednoduchá. Buď dán bipartitní graf [U, V, H],\U\ < \V\. Pro každý uzel* e U označme Vx = {y e V; xy e 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).
152
II. TEORIE GRAFŮ
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 0 J Vi c U platí
\Ux\<Y,W*\- (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 pravidelný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.33a je bipartitní graf, v němž neexistuje párování (je to faktor grafu K5 5). Na obr. 8.33b je jeden z maximálních pravidelných podgrafů 1. stupně.
(a) (b) Obr. 8.33: Maximální pravidelný podgraf 1. stupně v daném grafu
Nyní se vraťme k problematice barvení uzlů v grafu. Jakkoliv je obecně určení čísla / (§,) obtížné, je jednoduchá jeho následující majorizace.
8.11. Věta. Buď% - [u, H] graf. Označme q = max {st x; x e u}. Pak platí
x (SO <e + i-
'Nejběžnější z algoritmů pro hledání tohoto maximálního podgrafů je tzv. maďarský algoritmus.
8. Barvení grafů
153
Důkaz. Indukcí vzhledem k číslu \U\. Pro \U\ = 1 je tvrzení zřejmé. Nechť tedy tvrzení věty platí pro všechny grafy [U, H] takové, že \U\ < n. Buď nyní fy = [U, H] graf, \U\ = n + 1. Označme fy* graf, který vznikne z grafu fy odečtením některého uzlu x a všech hran s tímto uzlem incidentních. Podle předpokladu platí x(fy*) < Q + 1> takže existuje obarvení uzlů grafu fy* f:(u — {x}) -> {1,..., q + 1}. V grafu fy však s uzlem x sousedí nejvýše q uzlů, takže uzly v fy můžeme obarvit následovně:
t*\    ( f®> Proí
s CO =
p pro r = x,
kde p € {1,..., g + 1} je takový prvek, že p ^ f{u) pro všechny uzly u e U, tu € H. Pak je g obarvení daného grafu nejvýše g + 1 barvami. •
Nyní se budeme zabývat barvením hran.
8.12. Definice. Buď[ř/, H] graf. Zobrazení /: H —► N nazveme obarvením hran, jestliže pro každé dvě hrany h\,h2 e //, /z i ^ /*2> takové, T&h\C\hi ^ 0, platí /(Ai)^/(ä2).
Řekneme, že graf [f/, //] je hranově k-chromatický, když existuje obarvení / hran takové, že |/(//)| < fc.
Hranové chromatické číslo Xk(§>) grafu %, je nejmenší číslo £ e No takové, že $ je hranově k-chromatický.
Ve větě 8.11 jsme uvedli horní odhad uzlového chromatického čísla. Má-li symbol q týž smysl jako ve větě 8.11, je z definice okamžitě zřejmé, že pro hranové chromatické číslo platí xa($) > q- 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 % platí q < Xh($) 5 q + 1-
8.14. Poznámka. Hranové chromatické číslo daného grafu tedy může nabýt jen dvou hodnot: q nebo q + 1. Řekneme, že graf fy patří do první, respektive do druhé třídy, je-li Xhify) = Q, respektive Xhify) = Q + l.
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. Erdôs a R. J. Wilson, platí následující tvrzení:
154
//. TEORIE GRAFŮ
Označíme-li pt (n) počet grafů na n uzlech patřících do i-té třídy, platí
n->oo pi(n)
Podle [12] 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.34.
Obr. 8.34: Grafy druhé třídy na nejvýše šesti uzlech
8.15. Přiklad. Důležitým grafem patřícím do druhé třídy je tzv. Petersenův graf (obr. 8.35a). J. Petersen uveřejnil v roce 1891 práci v níž podrobně popsal vlastnosti pravidelných grafů; především pak studoval problém existence pravidelných faktorů v těchto grafech.
8. Barvení grafu
155
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 faktoru jsou na obr. 8.35a vyznačeny tučně. Petersenův graf obsahuje i pravidelný faktor 2. stupně (tj. kvadratický faktor); tento faktor je na obr. 8.35b.
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, nechť si čtenář promyslí, že všechny tři grafy na obr. 8.36 jsou izomorfní s Petersenovým grafem.
8.16. Poznámka. Hranové obarvení grafů překvapivě souvisí s latinskými čtverci, o nichž jsme hovořili v 1. kapitole, paragraf 10.
Lehce lze dokázat, že úplné bipartitní grafy patří do první třídy. Evidentně platí
Xh(Km.n) = Q =max(m,n).
Buď n e N libovolné. Pak platí x>, (#,,,„) = n. Označme Kntt = [U, V, H], U = {«!,..., un}, V = {vu vn), tj. H = {uiVj\ i = \,...,n, j = = 1,...,«}. Buď /: H —> {1,..., n} obarvení hran. Definujme čtvercovou matici («/;•)" ,=i takto: a,;- = f(ujV,). Pak je zřejmé, že tato matice je latinským čtvercem řádu n.
Na obr. 8.37 je uvedené přiřazení provedeno pro obarvení hran grafu ^3,3.
Hranové obarvení grafu K,un n barvami však současně evidentním způsobem určuje n různých úplných párování v Knjl (Každá barva určuje jedno takové párování). Protože počet úplných párování v Kn „ lze algebraickými metodami vypočítat (tento počet udává tzv. permanent matice sousednosti daného grafu - viz cvičení), lze odtud rovněž odvodit, že latinských čtverců řádu
156
II. TEORIE GRAFŮ
(a) (b)
(c)
Obr. 8.36: Různá nakreslení Petersenova grafu
n je alespoň
n!-(/i-l)!-(n-2)!-...-l!. Například latinských čtverců 6. řádu je alespoň 6! • 5! • 4! • 3! ■ 2! = 24 883 220.
8.17. 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. Formulace 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ě.
V.. ,,\	
	
	
	\ 1
	'• o
1 2 3
2 3 2
3 1 1
Obr. 8.37: Obarvení grafu      a příslušný latinský čtverec
8. Barvení grafu
157
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.38).
Obr. 8.38: Příklad mapy
Ve všech konkrétních příkladech se vždy podařilo najít obarvení čtyřmi barvami.
Nalezení důkazu, že tomu tak je zákonitě, se však ukázalo být jedním z nej obtíž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 §, = [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ý, neboť hrany můžeme kreslit tak, aby neprocházely územím žádného dalšího státu (hranici dvou států můžeme „překročit" v hraniční čáře). Tak například státům na obr. 8.38 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% nerovnost x(&) < 4?
To, že i relativně komplikované grafy uvedenou podmínku splňují, samozř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. Möbius, A. de Morgan a další. Mnohokrát byl uvedený problém
158
//. TEORIE GRAFŮ
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 % platí x ($) < 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 $ platí x ($) < 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 [13] .
kde se sčítá přes všechny variace m prvků z množiny {1, 2,..., n). Vypočtěte permanent matic:
Poznámky a cvičení
1. Permanent matice A = (a.ij) typu m/n, m < n je definován jako
9. Zobecnění pojmu graf
159
9   Zobecnění pojmu graf
Jak jsme uvedli již v paragrafu 1, není grafová terminologie v literatuře zdaleka 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, <p], kde U, H jsou disjunktní množiny, í/^0a<p://^-í/2UC/U P2(U). Prvky množiny U nazýváme uzly, prvky množiny H hrany a <p je tzv. incidenční zobrazení.
Je-li (p{h) e U2, nazývá se h orientovaná hrana, je-li <p(h) e U U /P2(U),je h neorientovaná hrana.
Orientovaná hrana h se nazývá orientovaná smyčka, je-li <p(h) = [x, x] pro nějaký uzel x e U.
Neorientovaná hrana se nazývá smyčka, je-li cp(h) € U. Orientované hrany h, k se nazývají souhlasně rovnoběžné, je-li (p(h) = epik) a nesouhlasně rovnoběžné, je-li q>(h) = [x, y] ^ [y, x] = <p{k). Neorientované hrany h, k se nazývají rovnoběžné, je-li <p(h) = <p(k). Násobností hrany h e H nazýváme číslo \{k e H; (p(k) = <p(h)}\.
V obecném grafu tak mohou existovat současně hrany orientované i neorientované, 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ícenásobné hrany či nikoliv a podle toho, zda jsou všechny hrany orientované respektive všechny neorientované.
9.2. Definice. Buď % = [U, H, (p] obecný graf. Existuje-li alespoň jedna hrana h e H s násobností větší než jedna, nazývá se % multigraf (nebo též pseudograf). Je-li násobnost všech hran rovna jedné, nazývá se %, prostý graf: Obsahuje-li $ pouze neorientované hrany, nazývá se neorientovaný graf. Jsou-li všechny hrany v % orientované, je g tzv. orientovaný graf. Řekneme, že % 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.)
160
II. 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, ze H C U2 U U U íPiiU) a <p je pak identické zobrazení (tj. <p(h) = h pro každou hranu h e H). (Tzn., že prostý graf můžeme definovat jako dvojici [U, H], kde U 4 0, H c U2 U U U       ), í/ n # = 0.)
Orientovaný i neorientovaný graf pritom 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 c U2, 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 i- 0, H Q U2. V teorii grafů jsou však tyto grafy obvykle zadávány jiným způsobem. Ke každému uzlu x e U je zadána množina r(x) těch uzlů, do nichž z x vede orientovaná hrana, kterou nazýváme šipkou.
9.6. Definice. Buď U ^ 0 libovolná množina, r: U -> P(U) buď libovolné zobrazení. Pak se dvojice [U, T] nazývá orientovaný graf'. U je množina uzlů. Z uzlu x vede do uzlu y orientovaná hrana xy právě tehdy, když y e T (x).
9.7. Poznámka. Z výše uvedeného je zřejmé, co to znamená, že orientovaný graf [U, T] je reflexivní, symetrický, antisymetrický, tranzitivní a podobně.
9. Zobecnění pojmu graf
161
Řadu pojmů lze z obyčejných grafů přenést na neorientované grafy prakticky 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ě \T{x)\ a |r_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í orientovaný 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.)
Je zřejmé, že pojem hypergrafu úzce souvisí například s blokovými schématy, o nichž jsme hovořili v 1. kapitole, paragrafu 10.
9.8. Definice. Hypergraf je trojice [U, H, <p], kde U i- 0 je množina uzlu, H je množina hran a <p: H —► (tP(U) — {0}) 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 e H platí \cp{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 c (P(U) — {0}). 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 [3].
d'ALEMBERT Jean Baptisté 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ěne 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.
162
Dodatek 1: Biografie
163
DÜRER Albrecht (1471-1528) Německý malíř a grafik.
ERDÖS Paul (1913-1996) Maď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 fyziológ, 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 metod zkoumání přírody, kritik scholastiky, představitel renesančního mechanistického pojetí přírody.
HALL Phillip (1904-1982) Anglický matematik.
164
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.
KÖNIG Dénes (1884-1944) Maďarský matematik.
KURATOWSKI Kazimierz (1896-1980) Polský matematik.
LAPLACE Pierre Simon (1749-1827) Francouzský matematik, fyzik a astronom.
Dodatek 1: Biografie
165
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.
MÖ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.
166
DODATKY
PLATÓN (427-347 př. Kŕ.)
Starořecký filozof, jeden z největších antických myslitelů.
PÓLYA Gyergy (1887-1985) Maď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.
SCHLÄ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
167
168
DODATKY
				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
307	674	368	000	15
008	176	640	000	20
985	984	000	000	25
Tab. 1.1: Tabulka hodnot n !
Dodatek 2: Tabulky
169
C)	k = 0 1	2	3-	4	5	6	7	8	9	10
n = 0	1 0	0	0	0	0	0	0	0	0	0
1	1 1	0	0	0	0	0	0	0	0	0
2	1 2	1	0	0	0	0	0	0	0	0
3	1 3	3	1	0	0	0	0	0	0	0
4	1 4	6	4	1	0	0	0	0	0	0
5	1 5	10	10	5	1	0	0	0	0	0
6	1 6	15	20	15	6	1	0	0	0	0
7	1 7	21	35	35	21	7	1	0	0	0
8	1 8	28	56	70	56	28	8	1	0	0
9	1 9	36	84	126	126	84	36	9	0	0
10	1 10	45	120	210	252	210	120	45	10	1
Tab. 1.2: Pascalův trojúhelník
p(n, k)	n = 1	2	3	4	5	6	7	8	9	10
k = l	1	1	1	1	1	1	1	1	1	1
2	0	1	1	2	2	3	3	4	4	5
3	0	0	1	1	2	3	4	5	7	8
4	0	0	0	1	1	2	3	5	6	9
5	0	0	0	0	1	1	2	3	5	7
6	0	0	0	0	0	1	1	2	3	5
7	0	0	0	0	0	0	1	1	2	3
8	0	0	0	0	0	0	0	1	1	2
9	0	0	0	0	0	0	0	0	1	1
10	0	0	0	0	0	0	0	0	0	1
Tab. 1.3:
Počet p(n,k) rozkladů čísla n na. k sčítanců
170
DODATKY
n	pin)	n	p(ri)	n	Pin)	n	pin)
1	1	21	792	41	44 583		
2	2	22	1 002	42	53 174	70	4 087 968
3	3	23	1 255	43	63 261		
4	5	24	1575	44	75 175	80	15 796 476
5	7	25	1 958	45	89 134		
6	11	26	2 436	46	105 558	90	56 634 173
7	15	27	3 010	47	124 754		
8	22	28	3 718	48	147 273	100	190 569 292
9	30	29	4 565	49	173 525		
10	42	30	5 604	50	204 226	110	607 163 746
11	56	31	6 842	51	239 943		
12	77	32	8 349	52	281 589	120	1 844 349 560
13	101	33	10 143	53	329 931		
14	135	34	12 310	34	386 155	125	3 163 127 352
15	176	35	14 833	55	451 276		
16	231	36	17 977	56	526 823	200	3 972 999 029 388
17	297	37	21 637	57	614 154		
18	385	38	26 015	58	715 220		
19	490	39	31 185	59	831 820		
20	627	40	37 338	60	966 467		
Tab. 1.4: Počet p(n) rozkladu čísla n
s{n, k)	k = 0	1	2	3	4	5	6
n = 1	0	1	0	0	0	0	0
2	0	-1	1	0	0	0	0
3	0	2	-3	1	0	0	0
4	0	-6	11	-6	1	0	0
5	0	24	-50	35	-10	1	0
6	0	-120	274	-225	85	-15	1
Tab. 1.5: Tabulka hodnot Stirlingových čísel prvního druhu
Dodatek 2: Tabulky
171
S(n,k)	k = 1 2	3	4	5	6	7	8	9	10
n = 1	1 0	0	0	0	0	0	0	0	0
2	1 1	0	0	0	0	0	0	0	0
3	1 3	1	0	0	0	0	0	0	0
4	1 7	6	1	0	0	0	0	0	0
5	1 15	25	10	1	0	0	0	0	0
6	1 31	90	65	15	1	0	0	0	0
7	1 63	301	350	140	21	1	0	0	0
8	1 127	966	1701	1050	266	28	1	0	0
9	1 255	3025	7770	6951	2646	462	36	1	0
10	1 511	9330	34105	42525	22827	5580	750	45	1
Tab. 1.6: Tabulka hodnot Stirlingových čísel druhého druhu
k	h
2	0,16667
4	0,033 33
6	0,023 81
8	0,03333
10	0,07576
12	0,25311
14	1,16667
16	7,09216
18	54,97118
20	529,12424
22	6192,12319
24	86580,25311
26	1425 517,166 67
28	27298231,067 82
30	601580873,90064
Tab. 1.7: Bernoulliova čísla
172 _DODATKY
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.8: Počet tn neizomorfních stromu na n uzlech
Rejstřík
(3n + l)-funkce, 69 3-síť, 84
^-pravidelný graf, 105 £>uniformní hypergraf, 161
acyklický graf, 161 adjungovaný rozklad, 51 anagram, 23 artikulace, 125
Bellova čísla, 32 Bemoulliova čísla, 69 Bettiho číslo, 127 binomický koeficient, 12 bipartitní graf, 151 blokové schéma, 81 blokové schéma typu (v, b, k, r, A), 81
bloky blokového schématu, 81 bod konečné afinní roviny, 86 bod v projektivní rovině, 91
cesta, 108
charakteristická rovnice formule, 63 cyklomatické číslo, 127 cyklus, 161 člen grafu, 126
design, 81
Dirichletův princip, 55 disjunktní grafy, 102 délka kružnice, 111 délka sledu, 108 dělení řetězce, 74
ekvivalentní latinské čtverce, 84 Eulerova funkce, 45 Eulerova funkce gama, 11 Eulerova identita, 79 Eulerova věta, 141 Eulerova čísla, 70 Eulerova úloha o 36 důstojnících, 85
eulerovský graf, 131
faktor grafu, 102 Ferrersovův diagram, 51 Fibonacciova posloupnost, 65 Fibonacciova čísla, 65 fluktuační permutace, 70 funkcionál, 37
graf, 101
graf „tři domy a tři studně", 141 grafová posloupnost, 105 grafy druhé třídy, 153 grafy první třídy, 153
had, 114
Hallova věta, 151 hamiltonovská cesta, 138 hamiltonovská kružnice, 134 hamiltonovský graf, 134 Hanojská věž, 67 homeomorfní grafy, 145 homomorfismus grafů, 133 hrana, 99, 159 hrana grafu, 101
173
174
REJSTŘÍK
hranové chromatické číslo, 153 hranově A:-chromatický graf, 153 hranově ^-souvislý graf, 130 hranově ohodnocený graf, 121 hranový stupeň souvislosti, 128 hranový řez, 128 hvězda, 114
hvězdo vitá množina, 145 hvězdo vitý mnohostěn, 146 hypergraf, 99, 161
incidenční zobrazení, 159, 161 izolovaný uzel, 103 izomorfismus grafů, 120 izomorfní grafy, 120
Kirkmannův problém 15 dívek, 83 koeficient řady, 71 kombinace A:-té třídy, 21 kombinace s opakováním, 25 kombinatorická identita, 16 kombinační číslo, 13 komplementární grafy, 102 komponenta grafu, 110 kompozice, 48 koncové uzly hrany, 101 konečná afinní rovina, 86 konečná geometrie, 86 konečná projektivn rovina, 91 konečný graf, 101 konfigurace, 7, 81 konvergence řady funkcí na množině, 71 konvergence řady v bodě, 71 kostra grafu, 114 kružnice v grafu, 111 Kuratowského grafy, 143 kvadratický faktor, 134, 155 kvaternion, 133
Laplaceova matice sousednosti, 116 latinský čtverec řádu n, 83
les, 112
lineární faktor, 155
lineární funkcionál, 37
lineární rekurentní formule &-tého řádu s konstantními koeficienty, 60
Lo-šu, 9
Lucasova posloupnost, 67
magický čtverec, 92 mapa, 141
matice sousednosti grafu, 107 matroid, 123
maďarský algoritmus, 152 minimální kostra, 122 množina hran, 161 množina uzlů, 160, 161 mocninná řada, 71 most, 125 multigraf, 159
nakreslení grafu, 139 neizomorfní stromy, 120 nekonečná řada funkcí, 71 neorientovaná hrana, 159 neorientovaný graf, 159 nesouhlasně rovnoběžné hrany, 159 násobnost hrany, 159
obarvení hran, 153 obarvení uzlů, 150 obecný graf, 159 obyčejný graf, 100, 160 obyčejný orientovaný graf, 160 ohodnocení hrany (uzlu), 121 ohodnocený graf, 100 orientovaná hrana, 159 orientovaná smyčka, 159 orientovaný graf, 159, 160 ortogonální latinské čtverce, 84 otevřený tah, 108
Rejstřík
175
Pascalův trojúhelník, 15 permanent matice, 158 permutace, 20
permutace s opakováním, 23 Petersenův graf, 154 planární graf, 140 Platónova tělesa, 145 podgraf grafu, 102 polohamiltonovský graf, 138 polomagický čtverec, 93 poloměr konvergence, 71 polostupeň uzlu, 161 pravidelný faktor, 134 pravidelný graf, 105 pravidelný mnohostěn, 146 pravidlo součinu, 19 princip duality, 91 princip inkluze a exkluze, 40 princip vylučování a zapojování prvků, 40
problém o svatbách, 151
problém obchodního cestujícího, 100
problém čtyř barev, 99, 156
prostý graf, 159
prostý hypergraf, 161
pseudograf, 159
pseudomagický čtverec, 95
párování, 151
přímka v afinní rovině, 86
přímka v projektivní rovině, 91
půlení hrany, 143
rovinný graf, 100, 140 rovnoběžky v afinní rovině, 86 rovnoběžné hrany, 159 rozklad daného typu, 33 rozklad množiny, 32 rozklad čísla, 49 Říční mapa, 9 řez, 74
řešení rekurentní formule, 59
řád konečné afinní roviny, 88 řád konečné projektivní roviny, 92 řád rekurentní formule, 59
samoadjungovaný rozklad, 51 Saturn, 9
Schlafliův symbol, 146
sled, 108
smyčka, 99, 159
směr v afinní rovině, 86
smíšený graf, 159
souhlasně rovnoběžné hrany, 159
souvislý graf, 109
součet konečné řady, 11
součet řady, 71
společnost, 161
Steinerův systém trojic, 81
stereografická projekce, 147
Stirlingova formule, 12
Stirlingova čísla 1. druhu, 14
Stirlingova čísla 2. druhu, 34
Stirlingův trojúhelník, 35
strom, 112
stupeň uzlu, 103
supermagický čtverec, 95
svaz k-tic, 24
systém trojic, 81
šipka, 99, 160
tah v grafu, 108 trojúhelník, 111 turnaj, 161 třídy rozkladu, 32 tým, 161
uniformní hypergraf, 161 uzavřený tah, 108 uzel, 159
uzel grafu, 99, 101 uzel konečného stupně, 103 uzel nekonečného stupně, 103 uzlové chromatické číslo, 150
176
REJSTŘÍK
uzlově ^-chromatický graf, 150 uzlově A:-souvislý graf, 130 uzlově ohodnocený graf, 121 uzlový stupeň souvislosti, 128 uzlový řez, 128 úloha o hostech, 43 úloha o sedmi mostech města Královce, 97 úplné párování, 152 úplný bipartitní graf, 151 úplný graf, 102
variace k-té třídy, 19 variace s opakováním, 22 variace, permutace a kombinace bez
opakování, 22 Veliký Lo-šu, 93 vlastní podgraf grafu, 102 vnitřní uzel, 108 vrchol grafu, 99, 101 vytvořující funkce, 73 věta o pěti barvách, 158
Youngův svaz, 52
zjemnění rozkladu, 32 znaménková matice, 107 žebřík, 116
Literatura
[1] C. berge: Principles of Combinatorics, Academie Press, New York -San Francisco - London 1971
[2] J. B. dence - t. P. dence: Elements of the Theory of Numbers, Acade-micPress, London 1998
[3] E. FUCHS: Diskrétní matematika a teorie množin pro učitele, CD-ROM, Brno 2000
[4] E. FUCHS: Teorie množin pro učitele, Brno 2000
[5] J. E. Graver, M. E. Watkins: Combinatorics with Emphasis on the Theory of Graphs, Springer - Verlag, New York - Heidelberg - Berlin 1977
[6] M. hall, jr.: Combinatorial Theory, Blaisdel PC., Waltham - Toronto - London 1967; ruský překlad 1970
[7] J. Herman, R. Kučera, J. ŠimŠA: Metody řešení matematických úloh II, Brno 1997
[8] J. KAUCKÝ: Kombinatorické identity, Veda, Bratislava 1975
[9] j. Nečas: Grafy a jejich použití, SNTL, Praha 1978
[10] R. MerriS: Combinatorics, PWS Publishing Company, Boston - London -Tokyo 1996
[11] J. Nešetřil: Teorie grafů, SNTL, Praha 1979
[12] J. Sedláček: Úvod do teorie grafů, Academia, Praha 1981
[13] P. ŠiŠma: Teorie grafů 1736-1963, Prometheus, Praha 1997
[14] N. J. Vilenkin: Kombinatorika, SNTL, Praha - Moskva 1977
177
DISKRÉTNI MATEMATIKA PRO UČITELE
Doc. RNDr. Eduard Fuchs, CSc.
Vydala Masarykova univerzita v Brně roku 2001
Vydání první, 2001 Vysázeno systémem ĽTtä Tisk: Grafex Blansko 178 stran
10,17 AA—10,71 VA Náklad 500 výtisků
Pořadové číslo 3468/PřF — 9/01 — 17/31 ISBN 80 - 210 - 2703 - 7 Doporučená cena: 90 Kč
Tato publikace neprošla redakční ani jazykovou úpravou v redakci nakladatelství