162
Kapitola 9. Párování
9.1.3 Příklad: Letecká bitva o Anglii. V letecké bitvě o Anglii v roce 1940 bojovala na straně Anglie řada pilotů různých národností. Královské letectvo mělo letadla, která vyžadovala dva piloty. Někteří piloti spolu ovšem nemohli letět pro jazykové potíže nebo pro rozdílnost výcviku. Kolik letadel (tj. dvojic pilotů) může za těchto omezení vzlétnout najednou?
Tento problém by bylo možno řešit nalezením maximálního párování v grafu, jehož vrcholy jsou piloti a jehož hrany spojují piloty, kteří mohou letět spolu.
9.1.4 Příklad zahrádkářský. Představme si ovocnou zahradu, ve které je 2n stromků a jedna hromada hnoje. Naším úkolem je přivézt půl kolečka hnoje ke každému stromku. Abychom šetřili časem, chceme vždy vézt k některému stromku plné kolečko, polovinu jeho obsahu složit a pokračovat s poloprázdným kolečkem k jinému stromku. Kromě času chceme šetřit i silami a chceme, aby např. součet drah vykonaných s plným kolečkem byl co nej menší.
Tuto úlohu lze převést na hledání nejlevnějšího perfektního párování v úplném grafu o 2n vrcholech. Každý vrchol odpovídá jednomu stromku. Cena hrany bude úměrná námaze spojené s jízdou plného kolečka k bližšímu z obou stromků, s následující jízdou poloprázdného kolečka ke druhému z nich a s návratem prázdného kolečka k hromadě hnoje. Je zřejmé, že každý stromek (vrchol) musí být zahrnut do přesně jedné jízdy, hrany odpovídající těmto jízdám musí tedy tvořit perfektní párování.
9.1.5 Cvičení. Jak byste řešili předchozí úlohu pro lichý počet stromků?
9.1.6 Příklad: Taneční. Předpokládejme, že v tanečních má každý hoch přesně k přítelkyň a každá dívka přesně k přátel. Je možno uspořádat tanec, při kterém každý hoch i dívka tančí s některým ze svých přátel? (Zde poněkud nerealisticky předpokládáme, že vztah přátelství je symetrický.)
Vztah přátelství můžeme znázornit bipartitním grafem, v němž každý vrchol má stupeň k. V tomto grafu hledáme perfektní párování. Ukážeme, že za uvedených podmínek lze existenci perfektního párování zaručit.
9.1.7 Přiřazovací úloha. Klasická formulace přiřazovací úlohy, totiž přiřazování pracovních úkolů pracovníkům, byla uvedena v 8.2.5, str. 135. Kromě řady dalších přímých aplikací se přiřazovací úloha vyskytuje i jako podúloha při řešení složitějších úloh, viz např. úloha čínského pošťáka 10.3, str. 182, a problém obchodního cestujícího 12.4.4, str. 206.
Řešením přiřazovací úlohy se budeme zabývat v 9.4, str. 171.
9.1.8 Cvičení. Úlohu o nejlevnějším maximálním párování lze převést na úlohu o nejdražším párování změnou cen hran. Navrhněte způsob, jak to udělat.
9.1.9 Poznámka. Úlohy o párování můžeme chápat jako hledání soustavy disjunktních dvojic vrcholů. Podobné úlohy týkající se disjunktních trojic jsou podstatně obtížnější (NP-těžké). Znamená to např., že kdybychom v zahrádkářské úloze
9.2. Párovaní v obecných grafech
163
9.1.4 snížili dávku hnoje na třetinu kolečka, byl by rozvoz hnoje snazší, ale najít optimální řešení by bylo složitější.
9.2   Párování v obecných grafech
9.2.1 Střídavé cesty a kružnice. Buď dán graf G a v něm párování P. Střídavá cesta (někdy též alternující cesta) vzhledem k párování P je taková neorientovaná cesta, že její hrany střídavě leží v F a neleží v F a je-li krajní vrchol cesty nasycen v párování P, pak hrana, která jej nasycuje, je částí cesty.
Příklad střídavé cesty je na obr. 9.1 vlevo vyznačen čárkovaně. Hrany, které náleží k párování, jsou nakresleny silně. Poznamenejme, že cesta spojující vrcholy 1, 6, 3 není střídavou cestou, ale její prodloužení 1, 6, 3, 2 již střídavou cestou je.
Obrázek 9.1: Střídavá cesta a změna párování.
Střídavá kružnice vzhledem k párování P je kružnice, jejíž hrany střídavě leží a neleží v párování P. Střídavá kružnice má vždy sudý počet hran.
Pomocí střídavých cest a kružnic lze párování snadno měnit tím, že u hran, které leží na cestě nebo kružnici, změníme příslušnost k párování. Přesněji, je-li H množina hran tvořících střídavou cestu nebo kružnici vzhledem k párování P, vytvoříme nové párování P' takto:
jestliže e € H, pak e 6 P' O e g P, jestliže   e £ H, pak e € P' & e € P.
Takovou změnu párování budeme nazývat změnou podél střídavé cesty nebo kružnice. Výsledek změny párování podél střídavé cesty je na obr. 9.1 vpravo.
9.2.2 Věta. Buď dán prostý graf G a v něm libovolné párování P\. Pak pro každé párování P2 v grafu G existuje soustava vrcholově disjunktních střídavých cest a střídavých kružnic taková, že změnami podél všech těchto cest a kružnic lze z párování Pi získat párování P2.
Poznámka: Poněvadž střídavé cesty a kružnice nemají žádný společný vrchol (jsou vrcholově disjunktní), lze změny provádět v libovolném pořadí.
Důkaz: Uvažujme faktor G' grafu G s množinou hran (PL\P2)U(p2\Pi). GrafG' tedy obsahuje právě ty hrany grafu G, které leží přesně v jednom z obou párování (tj. nikoli v obou).
164
Kapitola 9. Párovaní
Pro každý vrchol x e V (C) = V (G) nastane jedna ze čtyř možností:
1. Jestliže x není nasycen ani v P\, ani v P-2, je izolovaným vrcholem v G'.
2. Je-li vrchol x nasycen jen v jednom z párování Pi, P2, má v grafu G' stupeň 1.
3. Je-li x nasycen v P\ i P2 touž hranou, pak tato hrana neleží v G', a vrchol a; je tedy v G' izolovaným vrcholem.
4. Je-li x nasycen v P\ i P2 různými hranami e% G P% a e% £ P%j pak obě tyto hrany leží v G' a stupeň vrcholu x je roven 2.
Každý vrchol má tedy v grafu G' stupeň nejvýše 2. Z toho plyne, že graf G' má komponenty souvislosti tří typů:
1. izolovaný vrchol,
2. kružnice sudé délky, jejíž hrany střídavě leží v P\ a P2,
3. cesta, jejíž hrany střídavě leží v P\ a p2 a jejíž krajní vrcholy jsou různé, přičemž každý z nich je nasycen v jednom z obou párování Pi, P2.
Komponenty souvislosti grafu G' přímo určují střídavé cesty a kružnice. Provedením změn párování P\ podél všech těchto cest a kružnic dostaneme párování P2. □
9.2.3 Věta. Párování P v grafu G je maximální právě tehdy, když v grafu G vzhledem k párování P neexistuje střídavá cesta spojující dva volné vrcholy.
Důkaz: Je-li párování P maximální, pak vzhledem k němu nemůže existovat střídavá cesta spojující volné vrcholy. Kdyby totiž existovala, mohli bychom párování podél ní zvětšit.
Jestliže naopak párování P není maximální, vezměme nějaké maximální párování (nějaké určitě existuje) a označme je P\. Podle věty 9.2.2 existuje soustava střídavých cest a kružnic taková, že změnami podél nich získáme párování P\ z párování P. Poněvadž |Pi| > \P\, musí některá z těchto změn zvětšovat párování, musí tedy být změnou podél střídavé cesty s volnými krajními vrcholy (jiné změny nezvětšují počet hran v párování). □
9.2.4 Cena střídavé cesty a kružnice. Uvažujme graf G, jehož hrany jsou ohodnoceny cenami c : E(G) —> E. Dále mějme v grafu G párování P a vzhledem k němu střídavou cestu, popř. kružnici. Množinu hran této cesty, popř. kružnice, označme H.
Cenu střídavé cesty, popř. kružnice, definujeme jako
c= E <e)- E c(e)-
e€H\P eeHHP
Má-li střídavá cesta, popř. kružnice, cenu C a provedeme-li podél ní změnu, pak cena párování vzroste o hodnotu C.
9.2.5 Věta. Párování P v grafu G je nejdražší právě tehdy, když v grafu G vzhledem k párování P neexistuje ani střídavá cesta, ani střídavá kružnice s kladnou cenou.
Důkaz  je podobný důkazu věty 9.2.3 a je přenechán čtenáři jako cvičení. □
9.2. Párování v obecných grafech
165
9.2.6 Algoritmy pro párování v obecných grafech. Všeobecně lze k hledání maximálního i nejdražšího párování využít metody založené na větách 9.2.3 a 9.2.5. Základní schéma algoritmů je toto:
Zvolíme libovolné výchozí párování P a hledáme, zda vzhledem k němu existuje střídavá cesta, popř. kružnice, která by dovolila párování zlepšit. Jestliže neexistuje, pak podle věty 9.2.3, popř. 9.2.5, je párování P již optimální. Jestliže existuje, změníme (tj. zlepšíme) párování a znovu hledáme další střídavou cestu, popř. kružnici.
Bohužel, hledání potřebných střídavých cest a kružnic není tak jednoduché, jak se na první pohled zdá. Běžné metody prohledávání grafů popsané v kap. 3 a založené na značkování vrcholů lze jednoduše upravit pro hledání střídavých cest pouze v bipartitních grafech (viz 9.3).
V obecných grafech sice lze pro hledání střídavých cest použít backtracking (viz 11.2, str. 189), ten však je ve větších grafech neúnosně pomalý.
Rychlé (polynomiální) algoritmy pro párování v obecných grafech existují, pracují v čase 0(n3), ale jsou poměrně komplikované a v případě nejdražšího párování se navíc opírají o tzv. dualitu v lineárním programování. Z tohoto důvodu nastíníme pouze hlavní myšlenky rychlých algoritmů, a to pouze pro maximální párování (viz 9.2.8). Polynomiální algoritmy pro maximální i nejdražší párování jsou popsány např. v knihách [Plesník83], [Chr75] a [Lawler76].
9.2.7 Příklad. Na obr. 9.2 a 9.3 jsou příklady hledání maximálního a nejdražšího párování.
Obrázek 9.2: Výpočet maximálního párování.
Výchozí párování na obr. 9.2 vlevo bylo získáno náhodným přidáváním hran. Všimněte si, že k tomuto párování už nelze přidat žádnou další hranu, přesto má dost daleko k maximálnosti. Střídavé cesty mezi volnými vrcholy jsou vyznačeny čárkovaně. Všimněte si také, že výsledné maximální párování není perfektní.
166
Kapitola 9. Párovaní
Výchozí párování na obr. 9.3 vlevo bylo získáno „hladovým" postupem: postupně jsme přidávali vždy nejdražší přijatelnou hranu. Střídavé cesty i kružnice byly hledány ručně s využitím backtrackingu. Všimněte si, že nejdražší párování na obr. 9.3 vpravo jsme mohli získat také přímo z výchozího párování, kdybychom zvolili jinou střídavou kružnici.
20_, „_20_, „_20
cena párování = 36 cena párování = 37 cena párování = 38
Obrázek 9.3: Výpočet nejdražšího párování.
9.2.8 Rychlý algoritmus pro maximální párování. Naznačíme hlavní myšlenky rychlého algoritmu pro hledání střídavé cesty, jejíž krajní vrcholy jsou volné v párování P. Podrobnější popis nebo jiné postupy lze najít v [Kučera83], [Plesník83], [Chr75], [Lawler76], [SwTh81].
Začínáme v některém volném vrcholu r, který nazveme kořenem, a vytváříme tzv. střídavý strom, který má tu vlastnost, že každá cesta v tomto stromě, která začíná v r, je střídavou cestou. Strom vytváříme pomocí značkování vrcholů, přičemž používáme dva druhy značek: vrcholy stromu označujeme střídavě jako vnější a vnitřní, přičemž kořen r je vnější. V příkladě na obr. 9.4 jsou vnější vrcholy kresleny jako plné tečky.
Obrázek 9.4: Uříznutí květu a střídavá cesta procházející květem.
Jestliže najdeme hranu, která spojuje vnější vrchol s nějakým volným vrcholem různým od r, máme střídavou cestu s volnými krajními vrcholy a můžeme zvětšit párování.
9.3. Párování v bipartitních grafech
167
Jestliže najdeme hranu, která spojuje dva vnější vrcholy (a která tedy neleží v párování), našli jsme kružnici liché délky, která bývá nazývána květem. Květ kazí vlastnost střídavého stromu, totiž že cesta začínající v r je střídavou cestou. Proto všechny vrcholy květu nahradíme jediným vrcholem a hrany, které vedly z vnějšku do květu, vedeme do tohoto vrcholu. Tato operace bývá nazývána uříznutím květu. Lze dokázat, že střídavá cesta z r do některého volného vrcholu x v původním grafu existuje právě tehdy, když existuje i v upraveném grafu. Dále tedy pokračujeme s upraveným grafem (viz obr. 9.4) a dále se snažíme střídavý strom rozšířit.
Jestliže střídavý strom nelze dále rozšířit a nenastává žádný z předchozích případů, tj. když z vnějších vrcholů vedou hrany pouze do vnitřních vrcholů, odstraníme z grafu celý strom a všechny hrany s ním incidentní. Lze totiž dokázat, že část párování, která ležela ve stromě, je částí některého maximálního párování. To znamená, že vynechanou částí grafu se již není třeba dále zabývat. (Ověřte na příkladě!)
Tento postup opakujeme, dokud buď nezredukujeme graf na prázdný (pak stávající párování je již maximální), nebo dokud nenalezneme střídavou cestu s volnými krajními vrcholy. V tomto druhém případě lze stávající párování zvětšit. Jestliže však střídavá cesta prochází přes vrchol, který vznikl uříznutím květu, musíme nejprve květ obnovit a najít v něm chybějící část střídavé cesty. To se může i několikrát opakovat, neboť uříznutý květ mohl být součástí dalšího květu atd.
Praktické provedení tohoto algoritmu je relativně komplikované. Uřezávání květů se neprovádí změnami grafu, ale pomocí soustavy odkazů ve vhodné datové struktuře. Detaily i důkaz správnosti lze najít v [Plesník83], [Chr75], [Lawler76], poněkud odlišný algoritmus je uveden v [Kučera83]. Časové nároky těchto algoritmů jsou 0(n3), popř. až 0(n2^/n).
Poznamenejme, že v grafu, který neobsahuje kružnici liché délky (tj. který je bipartitní), se květ nemůže vyskytnout.
9.3   Párování v bipartitních grafech
Teorie i algoritmy pro párování v bipartitních grafech jsou podstatně jednodušší než v obecném případě, a to díky těsnému vztahu bipartitního párování k tokům v síti.
9.3.1 Převod bipartitního párování na tok v síti. Mějme bipartitní graf G se stranami X, Y. Orientaci hran tohoto grafu zvolme tak, aby všechny hrany vedly z I do ľ. K takto vzniklému orientovanému grafu přidejme dva vrcholy, umělý zdroj z a umělý spotřebič s (viz obrázek 9.5 na následující straně). Dále pro každý vrchol x G X přidejme hranu ze zdroje z do x a pro každý vrchol y € Y přidejme hranu z y do spotřebiče s. Kapacity těchto přidaných hran jsou jednotkové, kapacity původních hran jsou větší nebo rovny jedné. Dolní omezení toku jsou ve všech hranách nulová.
Párování v původním grafu vzájemně jednoznačně odpovídají celočíselným tokům od zdroje ke spotřebiči: párování je tvořeno těmi hranami původního grafu,
168
Kapitola 9. Párování
kterými teče nenulový (tj. jednotkový) tok. Maximální párování lze tedy hledat algoritmem pro maximální tok, nejdražší párování algoritmem pro nejlevnější tok (po obrácení znamének cen a po eventuálním přidání návratové hrany).
Obrázek 9.5: Převod úlohy o párování v bipartitním grafu na úlohu o toku v síti.
9.3.2   Speciální algoritmy pro maximální párování v bipartitním grafu
jsou ve své podstatě jen přeformulováním a zjednodušením algoritmů určených pro maximální tok. Zlepšující cestě, která se používá ke změnám toku v transportní síti, odpovídá v původním grafu střídavá cesta s volnými krajními vrcholy.
Přímým přeformulováním značkovací procedury 8.3.5 dostaneme tento návod:
1. [Inicializace.] Označkujeme všechny volné vrcholy z množiny X. Ostatní vrcholy jsou beze značek.
2. [Test nalezení cesty.} Je-li označkován některý volný vrchol z množiny Y, značkovací procedura končí. Je nalezena střídavá cesta s volnými krajními vrcholy a podél ní lze zvětšit počet hran v párování.
3. [Pokus o značkování vpřed.] Jestliže existuje hrana e 0 P vedoucí z označkovaného vrcholu x 6 X do neoznačkovaného vrcholu y € Y, pak označkujeme vrchol y a pokračujeme podle kroku 2. Neexistuje-li taková hrana, pokračujeme podle kroku 4.
4. [Pokus o značkování vzad.} Jestliže existuje hrana e G P z neoznačkovaného vrcholu x £ X do označkovaného vrcholu y £ Y, pak označkujeme vrchol x a pokračujeme podle kroku 3. Neexistuje-li taková hrana, značkovací procedura končí, stávající párování je maximální.
Tento postup lze ještě dále zjednodušit takto:
1. [Inicializace] Označkujeme všechny volné vrcholy z množiny X. Ostatní vrcholy jsou beze značek.
2. [Pokus o značkování vpřed.] Jestliže existuje hrana e £ P vedoucí z označkovaného vrcholu x G X do neoznačkovaného vrcholu y S Y, pak označkujeme vrchol y a pokračujeme podle kroku 3. Neexistuje-li taková hrana, značkování končí, střídavá cesta spojující volné vrcholy neexistuje.
9.3. Párování v bipartitních grafech
169
3. [Test nalezení cesty.] Je-li právě označkovaný vrchol y volný, značkovací procedura končí, je nalezena střídavá cesta s volnými krajními vrcholy. Je--li vrchol y párováním P nasycen, pokračujeme podle kroku 4.
4. [Značkování vzad.] Označkujeme vrchol z množiny X, který je spárován s vrcholem y, a pokračujeme podle kroku 2.
Jestliže takto upravená značkovací procedura skončí, aniž nalezla střídavou cestu s volnými krajními vrcholy, pak stávající párování již je maximální. Důkaz tohoto důležitého tvrzení vyplývá z věty 9.2.3 nebo také z analogie s toky v sítích (věta 8.3.7).
9.3.3 Konigova věta. Buď dán bipartitní graf G se stranami X a Y. Počet hran v maximálním párování v grafu G je roven
(9.1) mm(\X\A\ + \VG{A)\) .
Poznámka: Tato věta má pro párování v bipartitních grafech podobný význam jako Fordova-Fulkersonova věta 8.3.8 pro toky v sítích. Množinu A, pro kterou ve výraze (9.1) nastává minimum, lze sestrojit pomocí značkovací procedury.
důkaz:   Ke grafu G sestrojme transportní síť T podle 9.3.1.
Vezměme libovolnou množinu A C X a uvažujme řez W(Z) určený množinou vrcholů Z = {z} D AU VG{A). (Viz obr. 9.6.) Tento řez obsahuje \X \ A\ hran z množiny E+(z) a |Vg(-4)| hran z množiny E~(s). Tyto hrany mají jednotkové kapacity, ostatní hrany kapacitu řezu neovlivňují. Kapacita řezu W(Z) je tedy rovna |A"\^4|+ |Vg(^4)|. Proto žádné párování nemůže mít více než \X\A\ + \Va(A)\ hran.
Obrázek 9.6: K důkazu Konigovy věty.
Zbývá dokázat, že existuje množina A C X, pro kterou nastane rovnost. Podle Fordovy-Fulkersonovy věty 8.3.8 je velikost maximálního toku, tj. velikost párování, rovna kapacitě minimálního řezu. Dokážeme, že minimální řez má popsaný tvar W(Z), kde Z = {z} U A U VG(A) pro nějakou množinu A C X.
170
Kapitola 9. Párování
Uvažujme tedy některý maximální tok / a použijme na něj značkovací proceduru 8.3.5, str. 141. Výslednou množinu označkovaných vrcholů označme Z a dále označme A = X fl Z. (Viz obr. 9.6 na předchozí straně.)
Uvažujme libovolný vrchol x £ A. Jestliže vrcholem x neprotéká žádný tok, pak vrchol x byl označkován po hraně ze zdroje z a určitě jsou označkovaný všechny vrcholy množiny Vq{x). Jestliže vrcholem x tok protéká, pak vrchol x nemohl být označkován po hraně ze zdroje (neboť je nasycena tokem), musel tedy být označkován po (jediné) hraně, kterou tok z vrcholu x odtéká. Pak ovšem musel být koncový vrchol této hrany označkován dříve než x. Ostatními hranami z E+{x) tok neteče, proto jejich koncové vrcholy jsou jistě označkovaný (kdyby nebyly, bylo by možno dále značkovat). Tím je dokázáno, že Vg(A) C Y fl Z. Žádný vrchol z množiny Y \ Vg(A) nemůže být označkován, neboť do něj nevede žádná hrana z označkovaného vrcholu (tj. z množiny A). Platí tedy
VG(A)=Yr\Z   a   Z = {z} LI AU VG{A) ,
a pro množinu A tedy nastává rovnost. □
9.3.4 Hallova věta. Nechť G je bipartitní graf se stranami X a Y. V grafu G existuje párování, které nasycuje množinu X právě tehdy, když
(9.2) pro každou množinu A C X platí \A\ < \Vo(A)\ .
Důkaz: Pokud existuje párování nasycující množinu X, pak podmínka (9.2) triviálně platí. Zajímavá je pouze opačná implikace.
Z podmínky (9.2) plyne, že pro každou množinu A C X platí + |Vg(A)| =
— \X\-\A\ + \Vg(A)\ > \X\. Podle Konigovy věty je tedy počet hran v maximálním párování větší nebo roven \X\. Větší být ovšem nemůže, proto je roven \X\. □
9.3.5 Věta. Jestliže v bipartitním grafu G se stranami X, Y pro každé x € X ay E Y platí d(x) > d(y), pak v G existuje párování, které nasycuje všechny vrcholy množiny X.
DŮKAZ: Označme
dx = min d(x)      a     dy = max d(y) .
Platí tedy dx > dy- Vezměme nyní libovolnou množinu A C X. O počtu hran v řezu W(A) platí
\W(A)\ > \A\-dx
ci také
\W{A)\<\W{V{A))\<\V{A)\-dY .
Odtud \A\ ■ dx < \V{A)\ ■ dy, a poněvadž dx > dy, platí \A\ < \V{A)\. Toto platí pro libovolnou množinu A C X. Podle Hallovy věty tedy existuje párování, které nasycuje množinu X. □
9.4. Přiřazovací úloha
171
9.3.6 Cvičení. Dokažte, že z předpokladů předchozí věty plyne, že \X\ < \Y\. Charakterizujte grafy, pro které jsou splněny předpoklady věty a platí \X\ = \Y\.
9.3.7 Cvičení. Pomocí předchozí věty dokažte, že v příkladu 9.1.6 (taneční) existuje řešení, tj. perfektní párování.
9.3.8 Věta. V každém bipartitním grafu existuje párování, které nasycuje všechny vrcholy s maximálním stupněm.
důkaz: Označme k maximální stupeň vrcholu. Graf doplníme novými hranami a vrcholy tak, aby byl bipartitní a všechny vrcholy měly stupeň k. V takto vzniklém grafu mají obě strany stejný počet vrcholů a podle věty 9.3.5 v něm existuje perfektní párování. Nyní ze zvětšeného grafu vypustíme všechny přidané hrany a vrcholy. Tím získáme párování v původním grafu. Toto párování nasycuje všechny vrcholy stupně k, neboť k nim nebyla přidána žádná hrana. □
9.3.9 Věta. Nechť v bipartitním grafu G se stranami X, Y existují dvě párování P\, Pí. Nechť párování P\ nasycuje množinu vrcholů X\ C X a párování Pí nasycuje množinu Y2 C Y. Potom existuje párování P C Pj U P2, které nasycuje obě množiny Xi C X i Y2 C Y.
důkaz: Označme G' faktor grafu G s množinou hran P% u Pg. V grafu G' mají všechny vrcholy stupeň 0, 1 nebo 2, komponenty souvislosti grafu G' jsou tedy izolované vrcholy, cesty a kružnice.
Položme P = P\. Jestliže P nasycuje všechny vrcholy z Y2, pak P je hledané párování. Jestliže P nenasycuje některý vrchol y e ľj, pak vrchol y je krajním vrcholem cesty, která je komponentou souvislosti grafu G'. Tuto cestu můžeme pokládat za střídavou cestu vzhledem k párování P; proveďme změnu P podél této cesty. Nyní je vrchol y nasycen v P a všechny vnitřní vrcholy cesty také zůstávají nasyceny v P. Označme v druhý krajní vrchol cesty. Jestliže v € X, pak je nyní vrchol y nasycen v P. Jestliže »6ľ, pak sice není nasycen v P, ale není toho třeba, neboť v tomto případě byl vrchol v nasycen pouze v Pi, a tedy v $ Yi. Opakováním tohoto postupu budeme měnit párování P tak, že bude nasycovat stále větší počet prvků množiny Y% a zároveň celou množinu Xi. □
9.4   Přiřazovací úloha
Uvedeme tzv. maďarský algoritmus pro řešení přiřazovací úlohy, tj. pro hledání nejlevnějšího perfektního párování v úplném bipartitním grafu Kn<n, jehož hrany jsou ohodnoceny cenami. Algoritmus je založen na změnách cen, které nemají vliv na výsledné řešení.
9.4.1 Matice cen a její transformace. Buď G úplný bipartitní graf se stranami X, Y takový, že |X\ = \Y\ = n. Předpokládejme, že vrcholy obou stran X, Y jsou očíslovány čísly 1,2,... ,n. Hrany grafu G můžeme bez újmy na obecnosti
172
Kapitola 9. Párování
ztotožnit s uspořádanými dvojicemi vrcholů (x,y) € X x Y. Ceny hran pak můžeme přirozeným způsobem uspořádat do tvaru matice C, jejíž libovolný prvek c(i,j) je cenou hrany (i, j).
Vezměme libovolné ohodnocení vrcholů grafu G reálnými čísly p(v) pro v € € V (G) a na základě tohoto ohodnocení definujme matici transformovaných cen Cp předpisem
cP(i,j) = c(i,j) - p(i) - p(j) .
Transformací cen se optimální řešení přiřazovací úlohy nezmění, neboť cena každého perfektního párování se sníží o tutéž hodnotu
i€X j£Y vEV(G)
(Ověřte na příkladě!)
Ohodnocení vrcholů p nazveme přípustným ohodnocením, jsou-li všechny transformované ceny nezáporné, tj. cp(i,j) — c(i,j) — p(i) — p(j) > 0.
Je-li p přípustné ohodnocení vrcholů, pak grafem rovnosti Gp nazveme faktor grafu G, který obsahuje právě ty hrany grafu G, jejichž transformovaná cena je nulová, tj. c(i,j) = p(i) +p(j)- Poznamenejme, že všechny ostatní hrany grafu G mají transformované ceny kladné. Platí tedy tato věta:
9.4.2 Věta. Jestliže graf rovnosti Gp určený ohodnocením vrcholů p obsahuje perfektní párování P, pak párování P je optimálním řešením přiřazovací úlohy.
důkaz: Párování P má v transformovaných cenách Cp nulovou cenu. Žádné jiné párování nemůže být levnější, protože matice Cp neobsahuje záporné prvky. P je tedy nejlevnějším párováním vzhledem k transformovaným cenám Cp. Pak je ovšem nejlevnější i vzhledem k původním cenám C. □
Poznámka: Při notné dávce štěstí bychom mohli párování P a ohodnocení p uhodnout a pomocí této věty pak už jen ověřit, že jsme hádali správně.
9.4.3 Maďarský algoritmus pro přiřazovací úlohu. Hlavní myšlenka tzv. maďarského algoritmu spočívá v nalezení takového přípustného ohodnocení vrcholů, že v příslušném grafu rovnosti existuje perfektní párování.
Výchozí transformovanou matici cen a přípustné ohodnocení vrcholů získáme tím, že od každého řádku původní matice cen odečteme minimální cenu. Tím získáme v každém řádku alespoň jednu nulu. Tutéž operaci můžeme provést také se sloupci, pak i každý sloupec obsahuje alespoň jednu nulu. K takto získané transformované matici cen Cp sestrojíme graf rovnosti Gp a v něm najdeme maximální párování (viz 9.3.2, str. 168). Získáme-li takto perfektní párování, je úloha vyřešena.
Jestliže v grafu Gp perfektní párování neexistuje, pak v něm podle Hallovy věty existuje množina A C X taková, že \A\ > |Vgp(^)|- Tuto množinu najde značkovací procedura 9.3.2 při neúspěšném pokusu o nalezení střídavé cesty s volnými krajními vrcholy: A = Z H X, kde Z je množina všech označkovaných vrcholů.
9.4. Pňřazovací úloha
173
Abychom mohli v grafu rovnosti Gp zvětšit párování, potřebujeme označkovat další vrchol. K tomu je třeba přidat ke grafu Gv některou hranu, která vede z množiny A do neoznačkovaného vrcholu v množině Y. Potřebujeme tedy změnit ceny, ale chceme to udělat tak, abychom tuto změnu mohli pokládat za transformaci cen ve smyslu 9.4.1.
Zvýšíme tedy p(i) na množině A a zároveň snížíme p(j) na množině Vqv {A) o tutéž hodnotu d takovou, aby se vynulovala transformovaná cena na některé hraně vedoucí z A do Y \ Vgp(A) a přitom aby všechny transformované ceny zůstaly nezáporné. Prakticky to vypadá tak, že hodnota d bude rovna minimu (ze současných transformovaných) cen v průsečíku označkovaných řádků a neoznačkovaných sloupců.
Takto provedená změna ohodnocení zaručuje, že v grafu rovnosti zůstanou všechny hrany tvořící párování a také všechny hrany, které byly použity k označkovaní některého vrcholu. Navíc však ke grafu rovnosti přibude alespoň jedna hrana, po které bude možno označkovat alespoň jeden další vrchol. (Přitom ovšem může některá nepotřebná hrana z grafu rovnosti také zmizet.)
V takto upraveném grafu rovnosti opět hledáme maximální párování, tj. znovu použijeme značkovací proceduru a buď zvětšíme párování, nebo znovu měníme ohodnocení vrcholů, abychom mohli označkovat další vrchol. Po konečném počtu kroků nutně získáme perfektní párování, které je podle věty 9.4.2 optimálním řešením přiřazovací úlohy.
Maďarský algoritmus pro řešení přiřazovací úlohy lze shrnout takto:
1. [Počáteční přípustné ohodnocení vrcholů.] Pro každé i € X položíme p(i) := := minjey c(i, j). Pro každé j € Y dále položíme p(j) := mmiex(c(i,j)—p{i)).
2. [Graf rovnosti] Sestrojíme faktor Gp grafu G takový, že
E(GP) = E E (G) I c(i,j)-p(i)-p(j) = 0} .
3. [Maximální párování] Sestrojíme maximální párování P v grafu Gp. Je-li toto párování perfektní, výpočet končí, výsledné perfektní párování je nejlevnější.
4. [Změna přípustného ohodnocení vrcholů] Není-li párování P perfektní, nalezneme množinu A C X takovou, že \A\ > \Vb (A)\, vypočteme
d = min{c(í,j) - p(i) - p(j) \ieA,j# VGp(A)}
a změníme přípustné ohodnocení vrcholů takto:
p(i) := p(i) + d   pro všechna i G A, Pij) '■= PU) - d   Pr0 všechna j € VGp(A).
Pokračujeme podle kroku 2.
časové nároky: 0(n4).
174
Kapitola 9. Párování
9.
9.4.4   Příklad. Řešme přiřazovací úlohu, která je dana touto maticí cen:
5	3	7	4	5	4
10	11	10	7	8	3
18	7	6	6	6	2
6	12	2	1	9	8
oo	4	4	4	1	1
4	8	1	3	7	4
Odečtením řádkových minim od jednotlivých řádků získáme tuto transformovanou matici cen a ohodnocení p(i) vrcholů strany X:
						p(i)
2	0	4	1	2	1	3
7	8	7	4	5	0	3
16	5	4	4	4	0	2
5	11	1	0	8	7	1
7	3	3	3	0	0	1
3	7	0	2	6	3	1
Podobně odečteme od každého sloupce sloupcové minimum. Tím získáme výchozí ohodnocení p(j) vrcholů strany Y a transformovanou matici cen, která již obsahuje v každém řádku a v každém sloupci alespoň jednu nulu. Sestrojíme příslušný graf rovnosti a v něm zvolíme (v podstatě libovolným způsobem) výchozí párování.
							p(i)
	0	0	4	1	2	1	3
	5	8	7	4	5	0	3
	14	5	4	4	4	0	2
	3	11	1	0	8	7	1
	5	3	3	3	0	0	1
	1	7	0	2	6	3	1
pU)	2	0	0	0	0	0	
Značkováním jsme našli střídavou cestu s volnými krajními vrcholy a podél této cesty změníme (tj. zvětšíme) párování. Matice transformovaných cen ani samotný graf rovnosti se tím nemění. Poněvadž výsledné párování ještě není perfektní, pokračujeme dalším značkováním z volného vrcholu:
	i						p(i)
	0	0	4	1	2	1	3
-4	5	8	7	4	5	0	3
-y	14	5	4	4	4	0	2
	3	11	1	0	8	7	1
	5	3	3	3	0	0	1
	1	7	0	2	6	3	1
pij)	2	0	0	0	0	0	
■
9.4. Přiřazovací úloha
175
Označkované vrcholy a jim odpovídající řádky a sloupce jsou označeny šipkami. Velikost změny přípustného ohodnocení vrcholů d = 4 získáme jako minimum z transformovaných cen v průsečíku označených řádků a neoznačených sloupců, tj. zde druhého a třetího řádku a prvního až pátého sloupce. Po transformaci matice dostaneme:
			i	i	i	i	p(0
	0	0	4	i	2	5	3
->	1	4	3	0	1	0	7
->	10	1	0	0	0	0	6
-»	3	11	1	0	8	11	1
—>	5	3	3	3	0	4	1
->	1	7	0	2	6	7	1
p(i)	2	0	0	0	0	-4	
V transformované matici přibylo několik nul a v grafu rovnosti přibylo několik hran. Hrana (5,6) naopak z grafu rovnosti ubyla. Párování stále ještě nelze zvětšit, ale zvětšil se alespoň počet označkovaných vrcholů. Opět vybíráme minimum z průsečíku označkovaných řádků a neoznačkovaných sloupců, tentokrát d = 1:
							p(i)
	0	0	5	2	3	6	3
	0	3	3	0	1	0	7
	9	0	0	0	0	0	6
	2	10	1	0	8	11	1
	4	2	3	3	0	4	1
	0	6	0	2	6	7	1
pU)	2	0	-1	-1	-1	-4	
Nyní již v grafu rovnosti existuje střídavá cesta, podél níž lze párování zvětšit. Dokonce jsou zde tři takové cesty, nakreslena je pro přehlednost pouze jedna z nich. Tři výsledná perfektní párování jsou na obr. 9.7. Cena každého z nich je rovna součtu ohodnocení vrcholů, tj. 18.
Obrázek 9.7: Tři rovnocenná optimální řešení příkladu 9.4.4.
9.4.5 Cvičení. Řešte tutéž přiřazovací úlohu, ale volte jinak výchozí přípustné ohodnocení vrcholů a výchozí graf rovnosti. Výsledné optimální přiřazení musí mít samozřejmě stejnou cenu, ale postup výpočtu může být hodně odlišný.
176
Kapitola 9. Párování
9.4.6 Poznámka. Při výpočtu na počítači se obvykle graf rovnosti explicite nesestrojuje, maximální párování lze hledat pomocí nulových prvků matice Cp, značkují se přitom řádky a sloupce matice.
9.4.7 Jiné algoritmy pro přiřazovací úlohu. Přiřazovací úlohu lze pokládat za speciální případ klasické dopravní úlohy 8.2.4, str. 135, kde X je množina dodavatelů, Y je množina spotřebitelů a kapacity všech dodavatelů i spotřebitelů jsou jednotkové. Dopravní úlohu pak lze řešit buď speciálním algoritmem, nebo jako úlohu o nejlevnější cirkulaci.
Jinou možnost představuje převod přiřazovací úlohy na úlohu o nejdražším párování v temže úplném bipartitním grafu. Tento převod spočívá ve změně cen hran (viz cvičení 9.1.8). Výslednou úlohu o nejdražším párování v bipartitním grafu pak lze řešit tak, že vyjdeme z prázdného párování, které postupně zvětšujeme, a to vždy podél střídavé cesty, která spojuje dva nenasycené vrcholy a která má vzhledem ke stávajícímu párování nej větší cenu (viz 9.2.4). Lze dokázat, že takto dostaneme nejdražší párování, které je zároveň optimálním řešením přiřazovací úlohy.
177
Kapitola 10
Eulerovské tahy
10.1   Základní pojmy a aplikace
10.1.1 Eulerovský tah, pokrývání hran. Připomeňme, že tah je sled, který neobsahuje žádnou hranu dvakrát (viz 1.5.2, str. 20). Eulerovský tah je takový tah, který obsahuje všechny hrany grafu (tedy každou hranu přesně jedenkrát). Eulerovské tahy dělíme na orientované a neorientované a na uzavřené a neuzavřené.
Řekneme, že soustava tahů pokrývá hrany grafu, jestliže každá hrana grafu leží přesně v jednom z nich. Eulerovský tah je tedy takový tah, který sám pokrývá všechny hrany grafu.
V souvislosti s eulerovskými tahy lze formulovat a řešit tyto úlohy:
1. Rozhodnout, zda v grafu existuje eulerovský tah.
2. Sestrojit eulerovský tah.
3. Najít nejmenší počet tahů, které pokrývají hrany daného grafu.
4. V daném souvislém grafu, jehož hrany jsou ohodnoceny kladnými čísly, najít nejkratší uzavřený sled, který obsahuje všechny hrany grafu (každou hranu aspoň jedenkrát).
Pro řešení těchto úloh jsou známy rychlé (polynomiální nebo dokonce lineární) algoritmy.
Snadnost řešení těchto úloh je v pozoruhodném kontrastu s obtížností tzv. hamiltonovských úloh, které uvedeme v kapitole 12 (viz 12.1.4, str. 198).
10.1.2 Sedm mostů města Královce. Město Královec (Königsberg, dnešní Kaliningrad) leží na březích řeky Pregel a na dvou ostrovech. Břehy a ostrovy byly v 18. století spojeny sedmi mosty zhruba podle obr. 10.1 na následující straně. Obyvatelé města se tehdy bavili otázkou, zdaje možno vykonat procházku, která by vedla přes každý most přesně jedenkrát. Samozřejmě se při tom nesmělo plavat přes řeku. Dokonce se o tom uzavíraly a prohrávaly sázky, dokud Leonard Euler v roce 1736 nedokázal, že taková procházka není možná. Eulerův způsob řešení této hříčky bývá označován za počátek teorie grafů (historické podrobnosti viz [Šišma97]).
178
Kapitola 10. Eulerovské tahy
Úloha o sedmi mostech je ekvivalentní úloze najít v grafu, který je nakreslen na obr. 10.1 vpravo, eulerovský tah.
Obrázek 10.1: Sedm mostů města Královce a odpovídající graf.
10.1.3 Kreslení co nejmenším počtem tahů. Na hledání eulerovského tahu lze zřejmým způsobem převést známou úlohu, nakreslit nějaký daný obrázek (třeba „domeček") jedním tahem, aniž bychom kreslili některou čáru dvakrát a aniž bychom zvedli tužku z papíru. Od této úlohy je zřejmě odvozen termín tah. Každý asi ví, že na některé obrázky jeden tah nestačí.
Vzniká tedy přirozená otázka, jaký nejmenší počet tahů je k nakreslení nutný.
Nemusí přitom jít jen o zábavnou úlohu. Např. při kreslení pomocí počítače je účelné minimalizovat počet a délku přejezdů pisátka bez kreslení. Poněvadž každá čára by se měla kreslit přesně jedenkrát, je tato úloha příbuzná úloze 4. Pozor, nikoli totožná, a to ze dvou důvodů: obrázek nemusí být souvislý a navíc mohou být přejezdy pisátka přímočaré a nemusí probíhat podél kreslených čar. Je-li však kresba souvislá, lze k řešení použít postup podobný algoritmu 10.3.2.
10.1.4 Úloha čínského pošťáka. Pošťák musí při roznášce pošty projít všechny ulice svého rajónu. Jak má postupovat, aby ušel co nejméně kilometrů?
Tato úloha je pouze slovním vyjádřením úlohy 4, uvedené v 10.1.1. Jiným příkladem ze stejného soudku je optimalizace jízdy kropícího vozu, který má pokropit všechny ulice ve městě. Řešením se budeme zabývat v 10.3.
10.1.5 De Bruijnova posloupnost je příkladem důmyslné aplikace eulerov-ských tahů:
Máme dáno kladné číslo k. Úkolem je najít co nejdelší cyklickou posloupnost nul a jedniček takovou, že žádné dvě fc-tice po sobě jdoucích cifer nejsou stejné. Taková posloupnost se nazývá de Bruijnova posloupnost.
Tato úloha souvisí s kódováním zhruba takto: obvod otáčejícího se kotouče má být označen nulami a jedničkami tak, aby bylo možno určit přesnou pozici kotouče přečtením pouze k po sobě jdoucích číslic.
Řešení: Počet posloupností tvořených k nulami a jedničkami je 2k. Proto délka hledané de Bruijnovy posloupnosti nemůže být větší než 2k. Pomocí eulerovských tahů dokážeme, že posloupnost o délce 2k existuje, a získáme návod, jak ji sestrojit.
10.2. Existence a hledání eulerovských tahů
179
Vezměme graf, který má 2k~l vrcholů, viz příklad na obr. 10.2 pro k — 4. Vrcholy označíme všemi (k — l)-ticemi nul a jedniček. Graf bude mít 2k hran označených všemi Aľ-ticemi nul a jedniček, a to tak, že hrana označená (xi,X2, • ■ ■ ,Xk-i,Xk) povede z vrcholu («1,23,.. ■,fFfc-i) do vrcholu (x2, ■ ■ ■ ,Xk-i,Xk). To znamená, že z každého vrcholu vychází přesně dvě hrany; jejich označení se liší pouze na posledním k-tém místě, jedna hrana tam má jedničku a druhá nulu. Podobně do každého vrcholu vchází dvě hrany, jejichž označení se liší v první číslici.
110„ c =1100 „100
= oooo
Obrázek 10.2: Graf pro konstrukci de Bruijnovy posloupnosti pro A: = 4. Například eulerovskému tahu abcdef ghijklmnpq odpovídá de Bruijnova posloupnost
1111000011010010.
Libovolný sled v takovémto grafu můžeme snadno zakódovat pomocí posloupnosti nul a jedniček: každá číslice vyjadřuje jednu ze dvou možností jak pokračovat z daného vrcholu, který je označen předcházející (k — l)-ticí.
Původní úloha o de Bruijnově posloupnosti je tedy převedena na hledání uzavřeného orientovaného eulerovského tahu v popsaném grafu. Tento graf je souvislý a pro každý jeho vrchol x platí d+(x) = d~(x), proto podle věty 10.2.2 požadovaný eulerovský tah existuje. Dokonce je zřejmé, že eulerovských tahů (a tedy i de Bru-ijnových posloupností) může existovat několik.
Ve výše uvedené úloze jsme použili abecedu o dvou symbolech, totiž {0,1}. Výše popsanou konstrukci lze snadno zobecnit i pro libovolnou větší abecedu. Má-li abeceda n prvků, bude mít de Bruijnova posloupnost délku nk.
10.1.6 Cvičení. Najděte de Bruijnovu posloupnost pro k = 3 a n = 2. Kolik takových posloupností je? Řešte tutéž úlohu pro k = 2 a n = 3.
10.2   Existence a hledání eulerovských tahů
10.2.1 Věta. (Euler 1736.) Nechť graf G je souvislý. Pak v grafu G existuje neorientovaný uzavřený eulerovský tah právě tehdy, když každý vrchol grafu G má sudý stupeň.
Důkaz je téměř shodný s důkazem následující věty 10.2.2. Proto obě věty dokážeme společně. □
180
Kapitola 10. Eulerovské tahy
10.2.2 Věta. Nechť graf G je souvislý. Pak v grafu G existuje orientovaný uzavřený eulerovský tah právě tehdy, když pro každý vrchol v platí d+ (v) = d~ (v).
Důkaz: Důkaz jedné z implikací je velmi snadný: Předpokládejme, že v grafu existuje uzavřený eulerovský tah (orientovaný nebo neorientovaný). Představme si cestovatele, který prochází grafem podél tohoto tahu. Zřejmě platí, že kolikrát přišel do nějakého vrcholu v, tolikrát z něj musel i odejít. Poněvadž při tom projde každou hranou přesně jedenkrát, plynou odtud okamžitě tvrzení o stupních vrcholů: d(v) je sudý pro neorientovaný tah a d+(v) = d~(v) pro tah orientovaný.
Opačná implikace je těžší, dokážeme ji tím, že popíšeme (a dokážeme) postup, jak eulerovský tah sestrojit, jsou-li splněny předpoklady jeho existence, tj. souvislost a vlastnosti stupňů.
Začněme z libovolného vrcholu xq a procházejme hranami grafu libovolně, ale tak, abychom žádnou hranou nešli dvakrát. Takto pokračujeme, dokud je to možné, tj. dokud z vrcholu, kam jsme právě přišli, vychází ještě nějaká dosud nepoužitá hrana. Tato procházka zcela jistě skončí v xo, protože díky vlastnostem stupňů nemůže skončit nikde jinde a díky konečnosti grafu někde skončit musí. Nalezli jsme tedy nějaký uzavřený tah.
Nyní jsou dvě možnosti. Je-li tento tah eulerovský, jsme hotovi. Není-li tah eulerovský, pak někde v grafu existuje hrana, která v tahu neleží. Mezi xo a touto hranou existuje cesta (neboť graf je souvislý) a někde na této cestě musí existovat vrchol xi, kterým prochází tah a z něhož ještě vychází nějaká nepoužitá hrana. Ve vrcholu x\ tah přerušíme (rozpojíme) a začneme opět procházet nepoužitými hranami a tím tah (který je nyní otevřený) prodlužovat. Díky vlastnostem stupňů toto prodlužování skončí ve vrcholu x\. V tomto vrcholu navážeme novou část tahu na původní, čímž získáme uzavřený tah, který má více hran.
Tento postup (přerušování a prodlužování tahu) opakujeme, dokud existuje hrana, která v tahu neleží. Díky konečnému počtu hran v grafu G nakonec jistě dostaneme tah, který je eulerovský. □
10.2.3 Poznámka. Předpoklad souvislosti v předchozích dvou větách je zbytečně silný: izolované vrcholy by nevadily.
10.2.4 Cvičení. Dokažte, že (slabě) souvislý orientovaný graf, jehož každý vrchol v splňuje d+(y) = d~(v), je také silně souvislý.
10.2.5 Algoritmus pro hledání uzavřeného eulerovského tahu. Postup byl již vysvětlen v důkaze věty 10.2.2. Zaměříme se na jeho efektivní provedení. V algoritmu se střídavě provádějí dvě fáze:
1. Existující tah prodlužujeme, dokud se nestane uzavřeným.
2. Uzavřený tah kontrolujeme, zda je eulerovský.
Při kontrole procházíme podél tahu a v každém vrcholu x testujeme, zda v množině E(x), popř. E+(x) existuje hrana h, která dosud není obsažena v tahu. Pokud takovou hranu h najdeme, přerušíme kontrolu, tah ve vrcholu x rozpojíme a začneme
10.2. Existence a hledání eulerovských tahů
181
jej prodlužovat počínaje hranou h. Prodlužování skončí ve vrcholu x. Po propojení staré a nové části tahu pokračujeme v kontrole počínaje vrcholem x (předcházející část tahu je již zkontrolována) a postupujeme podél nové části tahu (ta doud není zkontrolována). Tím je zajištěno, že nejen při prodlužování, ale i při kontrole postupujeme podél každé hrany pouze jedenkrát. Celý postup tedy vyžaduje čas 0(n+m).
10.2.6 Příklad. Sestrojme uzavřený orientovaný eulerovský tah v grafu, který je nakreslen na obr. 10.3. Použijeme postup 10.2.5. Abychom se vyhnuli nejednoznačnosti, budeme k prodlužování tahu volit vždy hranu s nejnižším číslem a začneme ve vrcholu v\.
Obrázek 10.3: Graf k příkladu 10.2.6.
V prvé fázi získáme tah tvořený hranami 1, 2, 4, 6. Při kontrole zjistíme, že ve vrcholu v\ jsou všechny hrany obsaženy v tahu, ale z vrcholu i>2 vychází dosud nepoužitá hrana 5. Tah tedy rozpojíme mezi hranami 2 a 4, prodloužíme jej o hrany 5, 3, 8 a znovu spojíme. Tím získáme uzavřený tah 1, 2, 5, 3, 8, 4, 6. Pokračujeme v kontrole tam, kde jsme ji přerušili, tj. ve vrcholu v-2 (ten je již v pořádku) a dále ve t>3, kde zjistíme, že z V3 vychází nepoužitá hrana 7. Tah proto rozpojíme mezi hranami 5 a 3 a prodloužením získáme tah 1, 2, 5, 7, 3, 8, 4, 6. Další kontrola ve vrcholech v$, v^, Vi,V2,V4 již ukáže, že tento tah je eulerovský.
10.2.7 Věta. Nechť graf G je souvislý a obsahuje k vrcholů lichého stupně. Pak nejmenší počet neorientovaných tahů pokrývajících hrany grafu G je roven k/2.
Důkaz: Nejprve si uvědomme, že číslo k je sudé: Součet všech stupňů je roven 2\E(G)\, a je tedy sudý. Kdyby k bylo liché, musel by součet všech stupňů být lichý, což by byl spor (součet lichého počtu lichých čísel je vždy lichý).
Přidejme nyní ke grafu G celkem k/2 hran, které budou spojovat vždy dva vrcholy lichého stupně. Tím dostaneme souvislý graf G', v němž všechny vrcholy budou mít stupně sudé. Podle věty 10.2.1 tedy v grafu G' existuje uzavřený neorientovaný eulerovský tah.
Nyní odstraňme z grafu G' přidané hrany. Tím jednak dostaneme původní graf G, jednak se nám uzavřený eulerovský tah v G' rozpadne na celkem k/2 neuzavřených tahů, které dohromady pokrývají všechny hrany grafu G. □
10.2.8 Cvičení. Kolik tahů je nutných k pokrytí všech hran neorientovaného grafu, o kterém víme, že má 3 komponenty souvislosti, 2 vrcholy lichého stupně a žádný izolovaný vrchol? Bylo by možno určit potřebný počet tahů, kdyby počet vrcholů lichého stupně nebyl 2, ale 4?.
182
Kapitola 10. Eulerovské tahy
10.2.9 Věta. V orientovaném grafu G bez izolovaných vrcholu existuje orientovaný neuzavřený eulerovský tah právě tehdy, když graf G je souvislý a existují v něm dva vrcholy x,y takové, že d+(x) = d~(x) + 1 a d+(y) = d~(y) — 1 a pro všechny ostatní vrcholy v platí d+(v) = d~(v).
důkaz   je podobný důkazu věty 10.2.7. □
10.2.10 Cvičení. Najděte způsob, jak pro (slabě) souvislý orientovaný graf zjistit na základě stupňů vrcholů nejmenší počet orientovaných tahů, které pokrývají jeho hrany. Návod: pro každý vrchol vypočtěte číslo R(v) — d+(v) — d~{v).
10.3   Úloha čínského pošťáka
10.3.1 Úloha čínského pošťáka. Pošťák má projít všechny ulice města a vrátit se do výchozího místa, a to tak, aby ušel co nejméně kilometrů. Přeloženo do řeči grafů, jde o tuto úlohu:
Je dán neorientovaný souvislý graf, jehož hrany jsou ohodnoceny kladnými čísly. Úkolem je najít nejkratší uzavřený sled, který obsahuje všechny hrany grafu.
10.3.2 Řešení úlohy čínského pošťáka. Je zřejmé, že existuje-li v grafu eulerovský tah, je tento tah hledaným optimálním řešením.
Pokud v grafu eulerovský tah neexistuje, pak sled, který obsahuje všechny hrany, musí některými hranami procházet dvakrát nebo i vícekrát. Lze však dokázat (viz cvičení 10.3.4), že nejkratší sled prochází každou hranou pouze jedenkrát nebo dvakrát. Hledáme tedy sled, v němž je nejmenší součet délek hran, které jsou procházeny opakovaně (tj. dvakrát).
V nejkratším sledu, který obsahuje všechny hrany grafu, tvoří opakovaně procházené hrany soustavu cest, které spojují vždy dva vrcholy lichého stupně. Lze dokázat, že tyto cesty jsou navzájem hranově disjunktní, tj. že žádná hrana grafu neleží ve dvou různých takových cestách (viz cvičení 10.3.5).
Klíčem k řešení úlohy tedy je rozdělit vrcholy s lichým stupněm do dvojic, a to tak, aby součet délek nejkratších cest mezi vrcholy ve dvojicích byl nejmenší. Toto je vlastně úloha o párování, v níž je však třeba spárovat pouze vrcholy lichého stupně. Můžeme se na to dívat také tak, že hledáme nej levnější perfektní párování v pomocném úplném grafu K, jehož vrcholy jsou všechny vrcholy lichého stupně původního grafu G a délky hran grafu K jsou délky nejkratších cest v grafu G.
Celý postup řešení lze shrnout takto:
1. V daném grafu G najdeme množinu L vrcholů s lichým stupněm.
2. Pro všechny dvojice (x, y) vrcholů množiny L vypočteme délku u(x, y) nejkratší (neorientované) cesty z x do y.
3. Na množině vrcholů L definujeme úplný graf K, jehož hrany jsou ohodnoceny délkami nejkratších cest u(x,y).
4. V grafu K najdeme nejlevnější perfektní párování P (viz kapitola 9).
10.3. Úloha čínského pošťáka
183
5. Pro každou hranu (x,y) grafu K, která leží v párování P, vezmeme všechny hrany původního grafu G, které tvoří nejkratší cestu z x do y, a ke grafu G přidáme kopie všech těchto hran. V grafu G', který takto získáme, budou mít všechny vrcholy sudý stupeň.
6. V grafu G' sestrojíme eulerovský tah. Tento tah prochází všemi přidanými hranami, což odpovídá opakovaným průchodům hranami původního grafu.
7. V eulerovském tahu nahradíme všechny přidané hrany jim odpovídajícími hranami grafu původního. Tím získáme hledaný nejkratší sled, který prochází všemi hranami grafu G.
Důkaz správnosti tohoto algoritmu se opírá o fakt, že součet délek opakovaně procházených hran je roven ceně nejlevnějšího perfektního párování. Výpočet lze provést v čase 0(m + n3).
10.3.3   Příklad. Řešme úlohu čínského pošťáka pro graf z obrázku 10.4.
„     4 _o     5     b 2
5     e     8 2 Obrázek 10.4: Graf k úloze čínského pošťáka 10.3.3.
V grafu je šest vrcholů lichého stupně, L = {a,b, c,d,e, /}. Úplný graf K na množině vrcholů L je na obr. 10.5 vlevo. Hrany tvořící nejlevnější perfektní párování jsou v něm nakresleny silně. Na temže obrázku vpravo je nakreslen původní graf s přidanými hranami. Stupně všech vrcholů jsou v něm již sudé, není tedy problém najít v něm eulerovský tah.
Obrázek 10.5: Řešení úlohy čínského pošťáka 10.3.3.
184
Kapitola 10. Eulerovské tahy
10.3.4 Cvičení. Dokážte, že sled, který je řešením úlohy čínskeho pošťáka, nemůže procházet žádnou hranou více než dvakrát.
10.3.5 Cvičení. Dokažte, že žádné dvě cesty, které ke grafu přidáváme v kroku 5 algoritmu 10.3.2, nemají společnou hranu. Jinými slovy, dokažte, že v grafu G' bude ke každé hraně grafu G přidána nejvýše jedna kopie. Návod: využijte faktu, že párování P je nejlevnější.
10.3.6 Poznámka. Úlohu čínského pošťáka jsme pro jednoduchost formulovali a řešili pouze pro kladné délky hran. Algoritmus 10.3.2 lze použít i na graf, který obsahuje hrany o nulové délce. Důkaz správnosti je v tomto obecnějším případě složitější, neboť je třeba počítat s tím, že hrana o nulové délce se může ve výsledném sledu vyskytovat i více než dvakrát. To však nevadí, na délku sledu to nemá vliv.
10.3.7 Cvičení. Lze algoritmus 10.3.2 použít i na graf, který obsahuje hrany o záporné délce?
185
Kapitola 11 NP-těžké úlohy
V předchozích kapitolách jsme se (až na několik výjimek) zabývali úlohami, pro které jsou známy uspokojivě rychlé algoritmy. Následující dvě kapitoly se naopak věnují úlohám, které jsou (až na výjimky) „těžké". Co to však jsou „těžké" úlohy?
Prvý oddíl teto kapitoly obsahuje velmi stručné shrnutí základních pojmů a poznatků teorie složitosti (míněno: složitosti výpočtů), zejména teorie tzv. NP--úplnosti. Uvádíme je jednak proto, aby naše výroky o obtížnosti úloh měly alespoň trochu solidní základ, jednak proto, že se v literatuře lze poměrně často setkat s výroky o NP-úplnosti některých úloh.
Výklad v tomto prvém oddíle je poněkud abstraktnější a vybočuje mimo rámec teorie grafů. Studium tohoto oddílu můžete přeskočit, smíříte-li se s vágním vyjádřením, že „NP-těžké úlohy jsou obtížně řešitelné".
V oddílech 11.2 a 11.3 uvedeme dvě metody, které lze použít k řešení poměrně různorodých úloh (i negrafových). Obě metody se používají (zejména) k řešení NP-těžkých úloh, obě lze pokládat za „inteligentní průzkum všech myslitelných možností" a v obou se prohledává tzv. strom řešení. Srovnání obou metod je uvedeno v 11.3.8. Obě metody využijeme v kapitolách 12 a 13.
11.1   Časová složitost
Teorie složitosti je část informatiky, která se (zjednodušeně řečeno a mimo jiné) zabývá závislostí doby řešení úlohy na velikosti instance úlohy.
11.1.1 Typ úlohy a instance úlohy. Slovo „úloha" se používá ve dvou různých významech, mezi nimiž zde musíme pečlivě rozlišovat:
Typ úlohy určuje, jakým způsobem je úloha zadána, tj. jaká data a v jakém uspořádání budou tvořit zadání úlohy, co má být výsledkem a jaký má být vztah mezi výsledkem a zadáním. Instance úlohy je konkrétní případ úlohy daného typu.
Známe-li pouze typ úlohy, nemáme ještě co počítat, můžeme však přemýšlet o algoritmu, kterým bychom řešili instance tohoto typu úlohy, kdybychom nějaké
186
Kapitola 11. NP-těžké úlohy
měli. Počítat má smysl, teprve když máme konkrétní zadání, tj. instanci úlohy. Viz též 1.11.3, str. 32, kde jsme tyto pojmy zavedli pro optimalizační úlohy.
11.1.2 Velikost instance úlohy. Data, která popisují instanci daného typu úlohy, tvoří vstup do algoritmu, který úlohy daného typu řeší, proto o těchto datech mluvíme jako o vstupních datech. Velikost instance pak měříme jako objem těchto vstupních dat. Obecně se používá počet bitů, ale v grafových úlohách, kde zadáním úlohy je obvykle graf (a možná nějaké jeho ohodnocení), je zvykem vyjadřovat velikost vstupních dat počtem vrcholů nebo počtem vrcholů a počtem hran (tj. dvěma čísly).
11.1.3 Doba práce algoritmu. To je tak trochu potíž. Doba výpočtu na konkrétním typu počítače se pro teoretické úvahy nehodí, protože počítače mívají různě rychlé procesory a jakékoli tvrzení by mělo velice omezenou platnost. Počet instrukcí, které je třeba při výpočtu vykonat, je trochu lepší, ale i on závisí na typu procesoru (procesory mívají různé soubory instrukcí).
Proto se v teoretických úvahách často používá tzv. asymptotické vyjádření doby práce algoritmu pomocí symbolu O (velké písmeno O). Připomeňme (viz 1.10.6, str. 30) jeho definici:
Nechť /, g jsou dvě nezáporné funkce reálné proměnné. Existují-li reálné konstanty k, m takové, že pro všechna x > m platí g(x) < kf(x), pak píšeme g = O(f).
Zápis g = O(f) se vyslovuje jako „g je o /". Vztah g = O(f) je vlastně odhadem funkce g shora. Nezávisí na chování obou funkcí g a, f pro „malé" hodnoty argumentů (přesněji, pro x < m) a nezávisí také na násobení jedné z funkcí nějakou konstantou.
Řekneme-li, že nějaký algoritmus pracuje v čase 0(/(n)), kde n je velikost instance úlohy, znamená to, že doba jeho práce na instancích od určité velikosti výše nepřesahuje nějaký násobek funkce /. Přitom je však možné, že pro mnoho konkrétních případů vstupních dat (třeba i pro všechny) bude tentýž algoritmus pracovat rychleji. Dokonce i kdyby platil lepší odhad, např. 0(n2), byl by odhad 0(n3) také pravdivý.
Vyjádření doby práce algoritmu symbolem O se nezískává měřením doby skutečných výpočtů na počítači, ale teoretickým rozborem činnosti algoritmu.
Dodejme, že je třeba rozlišovat, zda máme na mysli dobu práce v nejhorším případě nebo dobu práce průměrnou. Není výjimkou, když nějaký algoritmus má odhad průměrné dobypráce řádově lepší než odhad pro nejhorší případ. Odhady pro nejhorší případ jsou jednodušší (snáze odvoditelné). V této knize se téměř výhradně zabýváme jen odhady pro nejhorší případ.
Asymptotické vyjádření doby práce pomocí symbolu O má své výhody i nevýhody. Výhodou je to, že se zaměřuje na chování algoritmu na velikých instancích úloh. S instancemi malého rozsahu totiž zpravidla nejsou problémy. Další výhodou je nezávislost na typu a rychlosti počítače, na programovacím jazyce, překladači, schopnostech programátora apod.
Nevýhoda je v tom, že z asymptotického odhadu není jasné, která instance úlohy je velká. Může se snadno stát, že algoritmus s horším asymptotickým odhadem
11.1. Časová složitost
187
bude na grafu o řekněme 5000 vrcholech rychlejší než jiný algoritmus, který je sice asymptoticky lepší, ale jeho rychlost se projeví až na grafech mnohem větších.
11.1.4 Rozhodovací úlohy jsou takové úlohy, jejichž výsledek je buď „ano", nebo „ne".
Mnohé (ovšem zdaleka ne všechny) rozhodovací úlohy jsou odvozeny z optimalizačních úloh jako jejich rozhodovací verze: k zadání úlohy se přidá konstanta K a ptáme se, zda existuje přípustné řešení s hodnotou účelové funkce, která je lepší nebo rovna K. Zvláštním případem rozhodovací verze pak je dotaz, zda existuje vůbec nějaké přípustné řešení dané úlohy (stačí vhodně zvolit konstantu K). Rozhodovací verze úlohy určitě není těžší než sama optimalizační úloha.
11.1.5 Polynomiálně řešitelné úlohy jsou úlohy, pro něž existuje algoritmus, který danou úlohu řeší, přičemž doba práce je pro nejhorší případ shora omezena asymptoticky nějakým polynomem, tj. doba práce je 0(p{n)), kde n je velikost vstupních dat a p je nějaký polynom. Říkáme, že takový algoritmus úlohu řeší v polynomiálním čase nebo že je polynomiální.
Třída úloh P je tvořena polynomiálně řešitelnými rozhodovacími úlohami.
Polynomiálně řešitelné úlohy jsou obvykle pokládány za „snadno řešitelné". Pro mnoho úloh však polynomiální algoritmus není znám, a to navzdory dlouhému úsilí nejlepších odborníků.
11.1.6 Třída úloh NP. Rozhodovací úloha patří do třídy NP, když pro ni existuje tzv. ověřovací algoritmus V, který má tyto vlastnosti:
• jeho vstupem jsou data d popisující instanci úlohy a tzv. certifikát, což je jakýsi blíže neurčený kus dat, jehož velikost je shora omezena nějakým pevně daným polynomem vzhledem k délce vstupních dat d,
• pracuje v polynomiálním čase vzhledem k velikosti vstupních dat d a dává vždy odpověď „ano" nebo „nevím",
• pro instanci dané úlohy d, pro kterou je správná odpověď „ano", existuje certifikát c takový, že ověřovací algoritmus V(d, c) dá odpověď „ano",
• pro instanci úlohy d, pro kterou je správná odpověď „ne", dává ověřovací algoritmus vždy (pro všechny možné certifikáty) odpověď „nevím".
Lidově řečeno, rozhodovací úloha patří do třídy NP, když kladnou odpověď lze potvrdit tím, že uhodneme vhodný certifikát a pak v polynomiálním čase ověříme, že jsme hádali správně. Záporná odpověď se nepotvrzuje, pouze se požaduje, aby v tomto případě neexistoval žádný falešný certifikát, který by potvrzoval nesprávnou odpověď.
V typických NP-úlohách se ptáme, zda existuje něco, co se možná i těžko hledá, ale snadno se ověřuje, že jsme to našli.
Konkrétním příkladem je úloha, zda v daném grafu existuje kružnice, která prochází všemi vrcholy grafu (tzv. hamiltonovská kružnice, viz kapitola 12). Certifikátem zde je ona kružnice. Ověřovací algoritmus ověřuje, že to je opravdu kružnice a že opravdu prochází přes všechny vrcholy grafu.
188
Kapitola 11. NP-těžké úlohy
Poznamenejme, že u NP-úloh je velmi důležité, jak je položena otázka, která se v úloze řeší. Je to proto, že certifikát a potvrzení požadujeme pouze pro kladnou odpověď. Obrácením otázky u nějaké NP-úlohy tedy dostaneme úlohu zcela jinou, která již do třídy NP nemusí patřit (může být těžší).
Každá úloha ze třídy P je zároveň ve třídě NP, neboť polynomiální algoritmus, který úlohu řeší, lze pokládat za algoritmus ověřovací, u něhož na certifikátu nezáleží. Platí tedy P C NP. V současné době není známo (nikdo neumí matematicky dokázat), zda platí rovnost, ale všeobecně se věří, že P ^ NP.
Ve třídě NP jsou úlohy různé obtížnosti. Než si řekneme, které jsou nejtěžší, musíme umět porovnávat obtížnost úloh.
11.1.7 Porovnávání obtížnosti, P-redukce. Úloha A je P-redukovatelná (též polynomiálně redukovatelná) na úlohu B, existuje-li polynomiální algoritmus, který ze vstupních dat úlohy A vyrobí vstupní data pro úlohu B, a to tak, že odpovědi na obě instance jsou stejné. Doba řešení úlohy B při tom nehraje žádnou roli.
Existuje-li P-redukce úlohy A na úlohu B, chápeme to jako doklad, že úloha A je lehčí nebo stejně obtížná jako úloha B. Pokud existují P-redukce v obou směrech (.4 na B a také B na A), pokládáme obě úlohy za stejně obtížné. Díky P-redukcím existují ve třídě NP skupiny stejně obtížných úloh. Třída P je jednou z nich.
Jestliže úloha A je P-redukovatelná na úlohu B a B G P, pak také A e P.
Několik příkladů P-redukcí je uvedeno v 12.2, str. 199.
11.1.8 NP-úplná úloha (anglicky NP-complete) je taková úloha, která patří do NP a je ve třídě NP nejtěžší v tom smyslu, že jakákoli jiná NP-úloha je na ni P-redukovatelná. Třídu všech NP-úplných úloh značíme NP-C.
NP-úplných úloh je známo mnoho (kniha [GJ79] jich uvádí přes 300), řada z nich jsou grafové úlohy. V naší knize se s NP-úplnými úlohami setkáme zejména v kapitolách 12 a 13.
Všechny NP-úplné úlohy jsou z hlediska P-redukce stejně těžké. Kdyby se podařilo najít polynomiální algoritmus pro kteroukoli z nich, měli bychom ihned polynomiální algoritmy pro všechny NP-úlohy a platilo by P = NP. V podstatě nikdo nevěří, že se takový algoritmus najde, ale dokázat to prozatím nikdo nedovede.
11.1.9 NP-těžká úloha (anglicky NP-hard) je taková úloha B, na kterou lze P-redukovat nějakou NP-úplnou úlohu A.
Na rozdíl od NP úplnosti zde nepožadujeme příslušnost úlohy B ke třídě NP. Díky tomu do třídy NP-těžkých úloh patří i optimalizační úlohy, jejichž rozhodovací verze jsou NP-úplné. Mezi NP-těžké však patří i mnohé další, daleko obtížnější úlohy.
11.1.10 Pozor na speciální případy. Je běžné, že nějaká úloha je NP-těžká, ale některé její speciální případy jsou snadno (polynomiálně) řešitelné.
Například úloha najít v daném grafu kružnici, která prochází všemi vrcholy grafu (tzv. hamiltonovská kružnice, viz kapitola 12), je notoricky známa jako NP-těžká,
11.2. Backtracking
189
ale kdybychom se omezili pouze na grafy, které mají stejný počet vrcholů i hran, dostali bychom úlohu (typ úlohy), která je triviálně řešitelná v lineárním čase.
Na tuto záludnost byste měli dát pozor, až se budete vymlouvat, že nějakou úlohu neumíte řešit, protože je NP-těžká.
11.1.11 Praktický význam teorie NP-úplnosti. Celá teorie NP-úplnosti působí dost pesimistickým dojmem: pokud věříme, že P ^ NP, pak není naděje, že by existovaly polynomiální (a tedy rychlé) algoritmy pro celou řadu velmi praktických úloh.
Reálné využití této teorie je tedy v podstatě alibistické: pokud o nějaké úloze umíme dokázat, že je NP-těžká, a věříme-li, že P ^ NP, pak to, že pro naši úlohu nedovedeme najít polynomiální algoritmus, není žádná ostuda, protože to neumí nikdo na světě včetně těch nej chytřejších odborníků.
To ovšem vůbec neznamená, že NP-úplné a NP-těžké úlohy nelze řešit. Musíme však buď slevit z požadavků na rychlost (algoritmus nebude polynomiální, ale stále ještě může být prakticky použitelný), nebo použijeme nějaký heuristický algoritmus, který sice bývá rychlý, ale musíme se smířit s rizikem, že nedosáhneme vždy požadovaného výsledku (např. najdeme řešení, které není optimální, nebo nenajdeme přípustné řešení, i když ve skutečnosti existuje).
Úlohy (instance) malého rozsahu lze téměř vždy řešit tzv. metodou hrubé síly, což je vznešený název pro jednoduché vyzkoušení všech možností, které přicházejí v úvahu.
Pro mnoho úloh lze použít backtracking 11.2 nebo metodu větví a mezí 11.3. Tyto metody lze pokládat za inteligentní vyzkoušení všech možností, kdy se dosahuje někdy i značného zrychlení tím, že se nezkoumají možnosti, které nemohou přispět k řešení.
11.2 Backtracking
11.2.1 Posloupnosti a strom řešení. Backtracking lze použít v těch situacích, kdy každé řešení úlohy (tj. každý prvek prostoru řešení) můžeme považovat za konečnou posloupnost, přičemž každý prvek posloupnosti musí být vybrán z nějaké předem dané konečné množiny. Při troše fantazie se na většinu kombinatorických úloh můžeme dívat tímto způsobem.
Kromě posloupností, které představují (úplné) řešení úlohy budeme uvažovat také všechny jejich počáteční úseky. Tyto počáteční úseky odpovídají částečným (neúplně určeným) řešením. Všechny takovéto posloupnosti můžeme pokládat za vrcholy orientovaného grafu, v němž každá částečná posloupnost má jako své následníky všechna svá prodloužení o jeden prvek. Tento graf je kořenovým stromem (kořenem je prázdná posloupnost) a nazýváme jej stromem řešení.
11.2.2 Backtracking. Nejjednodušší verze backtrackingu spočívá v prohledávání stromu řešení do hloubky. Vždy, když se při prohledávání dostaneme k posloup-
190
Kapitola 11. NP-těžké úlohy
nosti, která odpovídá úplnému řešení, provedeme test, zda toto řešení je přípustné. U optimalizační úlohy navíc evidujeme nejlepší dosud nalezené přípustné řešení.
Takto jednoduchý backtracking bez použití dalších triků ovšem není v podstatě ničím jiným než systematicky provedenou metodou hrubé síly. Triky, kterými lze výpočet mnohdy i značně urychlit, spočívají v tom, že vynecháme prohledávání některých podstromů.
Má smysl prodlužovat jen ty posloupnosti, u nichž je naděje, že mohou být prodlouženy na přípustné řešení. Pokud jsme tedy schopni s jistotou poznat, že žádné prodloužení už nemůže být přípustné, můžeme ušetřit čas tím, že prohledávání příslušného podstromu přeskočíme (provedením návratu).
Řešíme-li optimalizační úlohu, můžeme dosáhnout další úspory času, budeme--li schopni pro každou posloupnost x\,... ,Xi určit číslo D, které nazveme dolním, popř. horním odhadem (pro minimalizační, popř. maximalizační úlohu) a které má tu vlastnost, že prodlužováním posloupnosti x\,..., Xi nelze dosáhnout přípustného řešení lepšího než D. Bude-li tedy pro posloupnost xi,...,Xí tento odhad horší než nějaké přípustné řešení, které už v té chvíli známe, nemá další prodlužování posloupnosti xi,...,Xí smysl a prohledávání příslušného podstromu můžeme opět přeskočit.
I přes uvedené možnosti úspor bývá backtracking časově hodně náročný.
Příkladem jednoduchého backtrackingu je algoritmus 3.3.10, str. 56, další příklady uvedeme v kapitolách 12 a 13. Backtracking se však běžně používá i k řešení negrafových úloh.
11.2.3 Příklad. Metodou backtrackingu řešme tuto úlohu: Najděte maximum funkce 4xi + Sx2 + 2x% + X4 za podmínek 2x\ + Zx2 + x3 + 3x4 < 6, xi,x2 € {0,1,2},
13,2:4 e {o, 1}.
Tuto úlohu lze samozřejmě řešit i mnoha jinými (a lepšími) postupy. Zde nám však jde o ukázku postupu, který je „ve stylu backtrackingu".
Řešení úlohy, tj. vektor (xi,x2,x$,x4) pokládejme za posloupnost celých čísel. Dílčí posloupnosti budeme prodlužovat zleva doprava a k prodlužování budeme používat přednostně nejvyšší povolené hodnoty.
Poněvadž všechny proměnné mohou nabývat jen nezáporných hodnot, můžeme při prohledávání stromu řešení do hloubky provést návrat, jakmile součet hodnot na levé straně nerovnosti přesáhne číslo 6. Takovou posloupnost totiž nelze doplnit na přípustné řešení.
Horní odhad budeme pro každé částečné řešení počítat tak, že částečné řešení doplníme nejvyššími možnými hodnotami na délku úplného řešení a tuto posloupnost dosadíme do účelové funkce (bez ohledu na omezující podmínku). Např. posloupnost (1,2) doplníme na (1,2,1,1), odhad tedy je 13. Je zřejmé, že vyšší hodnoty prodlužováním posloupnosti (1,2) nelze dosáhnout, ve skutečnosti nedosáhneme ani oněch 13.
Pro stručnost uvedeme jen ty posloupnosti, ze kterých provádíme návrat:
(2,2) (2,D
nepřípustné, nepřípustné,
11.3. Metoda větví a mezí
191
(2,0,1,1) nepřípustné,
(2,0,1,0) úplné přípustné řešení s hodnotou 10,
(2,0,0) odhad 9 < 10,
(1,2) nepřípustné,
(1,1,1,1) nepřípustné,
(1,1,1,0) odhad 9 < 10,
(1,1,0) odhad 8 < 10,
(1,0) odhad 7 < 10,
(0) odhad 9 < 10.
Optimálním řešením je posloupnost (2,0,1,0) s hodnotou účelové funkce 10. Všimnete si, že toto řešení jsme našli poměrně brzy. Zbytek výpočtu však byl nutný pro ověření, že neexistuje lepší řešení.
11.3   Metoda větví a mezí
Metoda větví a mezí se používá pouze k řešení optimalizačních úloh. Podobně jako u backtrackingu se zde prohledává strom řešení, ten však bývá definován jiným, složitějším způsobem.
V tomto oddíle podáme obecný výklad metody větví a mezí a uvedeme příklad použití na negrafové úloze. Příklady použití na úlohy teorie grafů jsou uvedeny v 12.4, str. 203.
11.3.1 Větvení množiny přípustných řešení. Množinu přípustných řešení úlohy U označme symbolem Př([7).
Mějme optimalizační úlohu U s účelovou funkcí /. Úlohu U můžeme řešit (mimo jiné) tak, že vytvoříme úlohy Ui,..., Un se stejnou účelovou funkcí (tzv. podúlohy úlohy U) takové, že
Př(c/) = Př(ř7i)U...UPř([/„) .
Optimální řešení úlohy U pak lze získat tak, že vybereme nejlepší ze všech optimálních řešení podúloh Ui,...,Un. Samozřejmě se při tom snažíme (v tom je smysl větvení), aby podúlohy Ui,..., Un byly v nějakém smyslu snazší než původní úloha U, tj. aby např. byly menší. Dodejme, že při tom je výhodné, když množiny Př(Li),... ,Př([/n) jsou navzájem disjunktní, ale není to nutné.
Nalezení optimálního řešení úlohy U je snadné, pokud pro každou podúlohu U c
1. buď najdeme optimální řešení úlohy Ui,
2. nebo prokážeme, že úloha Ui nemá žádné přípustné řešení,
3. nebo prokážeme, že žádné přípustné řešení úlohy Ui není lepší než nějaké v té době již známé přípustné řešení úlohy U.
Často se ovšem stává, že pro některou podúlohu (a často ne jen jednu) nejsme schopni přímo zjistit ani jednu z výše uvedených tří možností. V tom případě pro každou takovou podúlohu, označme ji Ui, použijeme stejný postup jako pro
192
Kapitola 11. NP-těžké úlohy
úlohu U, tj. rozvětvíme ji na podúlohy t/j,,..., Uim a pro takto získané podúlohy se opět snažíme zjistit některou z výše uvedených možností. Některé z takto získaných podúloh může být nutno dále větvit.
11.3.2 Strom řešení. Jednotlivé podúlohy můžeme pokládat za vrcholy kořenového stromu, který nazýváme stromem řešení. Kořenem je výchozí úloha U a z každé úlohy, která byla větvena na podúlohy, vedou hrany ke všem jejím podúlohám. Během výpočtu se strom řešení mění (zvětšuje).
Pro výpočet jsou zajímavé pouze listy stromu řešení. Listy dělíme na tzv. živé a mrtvé. Za mrtvé pokládáme ty listy (podúlohy), u nichž se již podařilo prokázat některou ze tří možností uvedených v 11.3.1. Těmito podúlohami se již není třeba dále zabývat. Ostatní listy (podúlohy) jsou živé.
Živou podúlohu je třeba buď umrtvit (zjištěním některé ze tří možností z 11.3.1), anebo rozvětvit. Rozvětvením podúloha přestává být listem, ve stromě řešení se však místo ní objeví několik nových listů. Výpočet končí v okamžiku, kdy všechny listy stromu řešení jsou mrtvé.
11.3.3 Odhady a meze. Pokud pro některou podúlohu Ui zjistíme, že platí možnost 3, tj. pokud prokážeme, že žádné přípustné řešení úlohy L\ není lepší než nějaké v té době již známé řešení úlohy U, je to při řešení dobrá zpráva, protože tuto podúlohu není třeba větvit. Nejlepší dosud známé řešení úlohy U se však během výpočtu obvykle mění (zlepšuje), a tak se snadno stane, že možnost 3 se o nějaké podúloze podaří prokázat, teprve až najdeme dostatečně dobré řešení celé úloh}' U.
Proto bývá výpočet uspořádán tak, že jednak evidujeme nejlepší dosud známé řešení a hodnotu jeho účelové funkce, jednak pro každou podúlohu Ui vypočteme číslo Odh(ř/i) takové, že žádné přípustné řešení úlohy U% není lepší než Odh(ř/j).
Číslo Odh(ř7i) bývá v literatuře nazýváno u minimalizačních úloh dolním odhadem a u maximalizačních úloh horním odhadem. Cím je odhad blíže skutečné hodnotě optimálního řešení podúlohy, tím je tento odhad užitečnější, neboť tím snáze jeho pomocí prokážeme, že pro podúlohu platí možnost 3. Odhad je tedy tím lepší, čím je méně optimistický. Někdy lze volit mezi několika metodami výpočtu odhadu, které dávají různě kvalitní výsledky.
Způsob výpočtu odhadu samozřejmě velice závisí na řešené úloze a na způsobu vytváření podúloh. Jako odhad pro podúlohu Ui se často používá hodnota optimálního řešení tzv. relaxované podúlohy:
11.3.4 Relaxace nepříjemných omezujících podmínek. Poněvadž množina přípustných řešení úlohy je vždy popsána (zadána) pomocí omezujících podmínek, provádí se i větvení úlohy na její podúlohy pomocí dodatečných omezujících podmínek, které se k větvené úloze přidávají.
Obvyklá situace je tato: Omezující podmínky výchozí úlohy U lze rozložit na dvě skupiny, nazvěme je příjemné a nepříjemné. Vynecháme-li (takzvaně relaxujeme) nepříjemné omezující podmínky, dostaneme tzv. relaxovanou úlohu, která má již jenom příjemné omezující podmínky a kterou dovedeme (pokud možno rychle) řešit.
11.3. Metoda větví a mezí
193
Najdeme-li optimální řešení r úlohy, která vznikla relaxací z U, jsou dvě možnosti: buď řešení r splňuje, nebo nesplňuje nepříjemné omezující podmínky. Pokud splňuje, pak máme štěstí, protože řešení r je zároveň optimálním řešením i samotné úlohy U, a úlohu U tedy není třeba větvit. Obvykle však štěstí nemáme a řešení r nepříjemné omezující podmínky nesplňuje. V takové situaci uděláme dvě věci: za prvé, hodnotu optimálního řešení relaxované úlohy můžeme použít jako odhad, a za druhé, platnost oněch nepříjemných podmínek si snažíme vynutit přidáváním podmínek příjemných, a to i za cenu toho, že se nám úloha rozpadne (rozvětví) na několik podúloh.
Podstatné je, že při větvení úlohy přidáváme vždy jen příjemné omezující podmínky. Tím jc totiž zaručeno, že takto vzniklé podúlohy jsou stejného typu jako větvená úloha, a můžeme tedy opět použít onen trik s relaxací a řešením relaxované podúlohy.
Které omezující podmínky můžeme pokládat za příjemné, je dáno naší schopností rozumně rychle řešit příslušné relaxované podúlohy. Zpravidla pro danou úlohu existuje několik možností, jak zvolit prostor řešení a jak přeformulovat omezující podmínky, přitom obojí má značný vliv na pracnost řešení metodou větví a mezí. Příklady uvedeme v 12.4.
11.3.5 Volba podúlohy k větvení by mohla být založena na prohledávání stromu řešení např. do šířky nebo do hloubky. Častěji se však pro každou pod-úlohu vypočte hodnota, nazvěme ji prioritou, a mezi živými podúlohami vybíráme k větvení tu, která má prioritu nejlepší. Běžně se v roli priority používá (dolní nebo horní) odhad. Vybíráme pak podúlohu, která má odhad nejlepší (nejnadějnější), neboť u této podúlohy lze očekávat, že zlepšíme nejlepší dosud nalezené řešení a pomocí odhadů pak umrtvíme některé dosud živé podúlohy.
11.3.6 Shrnutí metody větví a mezí. Při výpočtu udržujeme nejlepší dosud nalezené přípustné řešení ŕ dané úlohy U a jeho hodnotu účelové funkce L. Na začátku ř není definováno a jako hodnotu L použijeme nejhorší možnou hodnotu (+oc nebo —oo).
Doporučuje se však ještě před zahájením výpočtu metodou větví a mezí získat nějakým heuristickým postupem (viz 11.4) co nejlepší přípustné řešení ř a jeho hodnotu L, neboť to může následující výpočet urychlit.
Dále při výpočtu udržujeme seznam živých podúloh.
Obvykle ještě před zařazením do seznamu pro každou podúlohu vypočteme odhad, nejčastěji řešením relaxované verze příslušné podúlohy. Pokud přitom dostaneme přípustné řešení, porovnáme je s řešením ř a dále uchováváme lepší z nich. Pokud bylo řešení ř nahrazeno lepším, tj. pokud se zlepšila hodnota L, projdeme seznam živých podúloh a vyřadíme ty, které jsou díky nové hodnotě L umrtveny.
Pokud podúloha nemá žádné přípustné řešení nebo pokud pro ni dostaneme odhad, který je horší než L, pak tuto podúlohu okamžitě umrtvíme a do seznamu živých podúloh ji vůbec nezapisujeme.
Ze seznamu živých podúloh vybíráme zpravidla tu, která má nejlepší odhad. Tuto podúlohu ze seznamu odstraníme, rozvětvíme ji na podúlohy, pro každou z nich
194
Kapitola 11. NP-těžké úlohy
ihned vypočteme odhad a případněji zařadíme do seznamu živých podúloh, jak bylo popsáno výše.
Tento postup opakujeme, dokud je v seznamu nějaká živá podúloha. Výsledné řešení ŕ pak je optimálním řešením úlohy.
11.3.7 Příklad. Postup výpočtu metodou větví a mezí předvedeme na problému batohu (viz 2.4.2, str. 44), tj. na negrafové úloze, aby vynikla obecná použitelnost metody. Další příklady viz 12.4, str. 203.
Mějme batoh o kapacitě 40 a pět předmětů s těmito vahami a cenami:
předmět i:	A	B	C	D	E
cena co	50	107	31	31	69
váha ví :	14	30	9	10	27
Jako prostor řešení vezmeme r5, jeho prvky jsou uspořádané pětice čísel X\,...,X5, která určují, kolikrát zabalíme do batohu jednotlivé předměty. Omezující podmínky určují, že 0 < Xi < 1 a £3i=1 v*xi — 40. Nepříjemnou omezující podmínkou zde je, že všechna Xi musí být navíc celočíselná.
Pro účely snadného řešení relaxované úlohy si předměty seřadíme sestupně podle jejich „měrné ceny", tj. podle podílu cena/váha. Ve výše uvedeném zadání je toto seřazení již provedeno.
Optimální řešení relaxované úlohy pak získáme velmi jednoduše tak, že do batohu budeme ukládat celé předměty v pořadí klesající měrné ceny, přičemž poslední z takto zařazených předmětů možná nebude zařazen celý. Pro naši úlohu tak dostaneme řešení o hodnotě 142,73 tvořené celým předmětem A a částí 26/30 předmětu B. Jako horní odhad použijeme celou část této hodnoty, tj. zde 142, neboť všechna přípustná řešení původní (nerelaxované) úlohy U mají hodnotu účelové funkce celočíselnou, a ta tedy nemůže přesáhnout 142.
Větvení budeme provádět vždy na dvě podúlohy, a to tak, že si vybereme některý předmět, o němž v dané podúloze není ještě rozhodnuto, a v jedné z podúloh jej pevně zařadíme, zatímco ve druhé jej zakážeme. V obou podúlohách se tedy rozhoduje o menším počtu předmětů. Přidané omezující podmínky, tj. příkazy a zákazy, budeme zkráceně označovat symboly + a - tak, že např. -+-.. bude znamenat, že 1. a 3. předmět jsou zakázány, 2. předmět je přikázán a o ostatních předmětech není v podúloze rozhodnuto.
Průběh řešení je zaznamenán v následující tabulce. Podúlohy jsou očíslovány pořadovými čísly v pořadí, jak byly vytvořeny větvením. K větvení byla vybírána vždy podúloha s nejlepším odhadem, a to v pořadí 1, 2, 3, 6, 8, 11.
číslo    přidaná     horní komentář podúlohy   omezení odhad
1 ..... 142   větveno podle A na podúlohy 2 a 3
2 +. ...       142   větveno podle B na podúlohy 4 a 5
3 141   větveno podle B na podúlohy 6 a 7
11.3. Metoda větví a mezí
195
4	++...	-	přetíženo
5	+-.. .	129	umrtveno po zpracování podúlohy 9
6	-+...	141	větveno podle C na podúlohy 8 a 9
7		115	umrtveno po zpracování podúlohy 9
8	-++..	141	větveno podle D na podúlohy 10 a 11
9	-+-..	138	(optimum) viz komentář v textu
10	-+++.	-	přetíženo
11	-++-.	140	větveno podle E na podúlohy 12 a 13
12	-++-+	-	přetíženo
13	-++—	138	další optimum
Strom řešení je na obrázku 11.1.
1: 142
4: přetíženo        5: 129 6: 141 7: 115
/ X
8: 141 9: 138 opt
10: přetíženo       11: 140
12: přetíženo       13: 138 (opt)
Obrázek 11.1: Strom řešení k příkladu 11.3.7. U vrcholů jsou napsána čísla podúloh
a hodnoty horních odhadů.
Podúloha 9 vyžaduje podrobnější komentář: Řešením relaxované verze podúlohy 9 jsme zde (náhodou) dostali celočíselné řešení. Získali jsme tedy přípustné řešení celé úlohy, aniž by bylo nutno podúlohu větvit. V té době to bylo první přípustné řešení, které jsme nalezli. Použili jsme je ihned k umrtvení podúloh 5 a 7, které v té době byly ještě živé, ale měly ve srovnání s podúlohou 9 horší odhad.
Stojí za zmínku, že v této chvíli jsme již měli řešení, o kterém se později ukázalo, že je optimální, ale v té době jsme to ještě nevěděli, protože stále ještě zbývala živá podúloha 8 s odhadem, který dával naději na zlepšení. Bylo tedy nutno ve výpočtu pokračovat a teprve po rozvětvení podúloh 8 a 11 se ukázalo, že lepší řešení neexistuje.
11.3.8 Backtracking versus větve a meze. Obě metody mají některé rysy společné a u některých algoritmů je těžké říci, o kterou z obou metod jde.
Backtracking použitý k řešení optimalizační úlohy lze pokládat za speciální případ metody větví a mezí. Na posloupnost, která v backtrackingu tvoří částečné
196
Kapitola 11. NP-těžké úlohy
řešení, se totiž můžeme dívat jako na podúlohu, v níž několik prvých členů posloupnosti je pomocí přidaných omezujících podmínek pevně určeno. Prodloužení posloupnosti pak znamená přidání nové omezující podmínky.
Při backtrackingu však prohledáváme strom řešení vždy do hloubky (jinak by to nebyl backtracking), zatímco v metodě větví a mezí lze další postup řešení volit svobodněji, a tedy zpravidla výhodněji (např. pomocí priorit, viz 11.3.5).
V backtrackingu lze k zamezení zbytečného větvení použít i jiné triky než dolní, popř. horní odhady. A konečně, backtracking lze použít také k řešení úloh, které nemají optimalizační charakter (viz např. 13.3.1).
11.4   Heuristické algoritmy
V praxi mnohdy vystačíme s řešením, které je „dostatečně dobré", které však získáme rychle. Algoritmy, které poskytují takováto řešení, nazýváme heuristické. Tyto algoritmy bývají založeny na nejrůznějších principech.
Mnohé heuristické algoritmy pracují tzv. hladovým způsobem: řešení vytváří (konstruují) postupně a v každém kroku se snaží o co největší zlepšení účelové funkce, popř. o co největší úsporu. Samozřejmě se může stát, že se „chamtivost nevyplatí" a výsledkem je řešení, které není optimální. Úlohy, v nichž hladový postup zaručeně vede k optimálnímu řešení, jsou spíše výjimečné, viz poznámka u algoritmu 4.3.7, str. 62, pro minimální kostru.
Některé heuristické algoritmy řešení mnohokrát opakují s využitím náhody a z takto získaných řešení vybírají nejlepší.
Další heuristické algoritmy využívají tzv. lokální průzkum: vezmou nějaké stávající řešení (zpravidla získané nějakou jinou heuristikou) a systematicky je pozměňují, tj. v jistém smyslu prozkoumávají okolí stávajícího řešení. Pokud některé z pozměněných řešení je lepší než řešení stávající, prohlásí toto lepší řešení za stávající a pokračují průzkumem okolí tohoto nového řešení. Toto se opakuje, dokud se daří řešení zlepšovat. Samozřejmě můžeme skončit i dříve, pokud najdeme řešení, jehož kvalita nám postačuje nebo pokud už nemáme čas na další zlepšování.
Metodu lokálního průzkumu lze dále zdokonalit s využitím náhody. Jednak můžeme s nějakou pravděpodobností akceptovat i zhoršení účelové funkce v naději, že takto později objevíme celkově lepší řešení, jednak můžeme celý postup mnohokrát opakovat z jiného, náhodně zvoleného výchozího řešení.
Další, složitější heuristické algoritmy jsou „ošizené" varianty backtrackingu nebo metody větví a mezí, v nichž používáme nepřesné (ne zcela spolehlivé) odhady. Prohledáváme pak menší strom řešení a výpočet se může podstatně urychlit, ale může se stát, že díky nepřesnému odhadu přeskočíme prohledávání podstromu, který obsahuje optimální řešení.
Obecně platí, že heuristické algoritmy bývají „šity na míru" pro určitý typ úlohy, jejich úspěšnost závisí na tom, jak se podaří využít specifických rysů daného typu úlohy i specifických rysů instancí, které chceme řešit. Při jejich návrhu hodně záleží i na zkušenosti a citu pro řešený problém.
197
Kapitola 12
Hamiltonovské cesty a kružnice
12.1   Základní pojmy, aplikace a vzájemné převody
12.1.1 Definice. Hamiltonovská cesta v grafu G je taková cesta, která obsahuje všechny vrcholy grafu G.
Podobně definujeme hamiltonovskou kružnici a hamiltonovský cyklus jako kružnici nebo cyklus procházející přes všechny vrcholy grafu.
12.1.2 Hamiltonova hádanka. Výše uvedené pojmy jsou nazvány podle irského matematika W. R. Hamiltona, který v polovině 19. století zveřejnil v zeměpisném časopise hádanku, v níž šlo o nalezení uzavřené trasy vedoucí přes dvacet měst, která byla rozmístěna ve vrcholech pravidelného dvanáctistěnu, přičemž se přes žádné město nesmělo cestovat dvakrát. Příslušný graf je na obr. 12.1.
Obrázek 12.1: Dvě nakreslení grafu pravidelného dvanáctistěnu s vyznačenou hamiltonovskou kružnicí. Obrázek vpravo lze chápat jako „širokoúhlý" pohled dovnitř skrz přední stěnu dvanáctistěnu.
12.1.3 Typy hamiltonovských úloh. Úlohy, ve kterých jde o hamiltonovské pojmy, mají mnoho variant a lze je třídit z několika různých hledisek.
198
Kapitola 12. Hamiltonovské cesty a kružnice
Především je třeba odlišit úlohy existenční a optimalizační. V existenčních úlohách jde o zjištění existence nebo dokonce o nalezení hamiltonovské cesty, kružnice nebo cyklu v daném grafu.
V optimalizačních úlohách jsou hrany grafu ohodnoceny délkami a požaduje se nalezení hamiltonovské cesty, kružnice nebo cyklu o nej menší délce. Optimální řešení se přitom často hledá v úplném grafu, protože obecnější úlohy lze na tento speciální případ velmi snadno převést (viz 12.2.2).
Dále úlohy dělíme na orientované a neorientované podle toho, zda hledáme orientovanou nebo neorientovanou hamiltonovskou cestu, případně zda hledáme hamiltonovský cyklus nebo kružnici.
V případě hamiltonovských cest musíme navíc rozlišit tři až čtyři varianty podle toho, zda je v zadání úlohy předepsán vrchol, ve kterém musí hamiltonovská cesta začínat, a vrchol, kde musí končit.
Ve všech těchto úlohách se můžeme omezit na prosté grafy bez smyček.
12.1.4 Obtížnost hamiltonovských úloh. Všechny výše uvedené typy hamiltonovských úloh jsou pro obecné grafy NP-těžké.
Stojí za zmínku, že kdybychom tyto úlohy „maličko" pozměnili a namísto sledu, který obsahuje přesně jedenkrát každý vrchol, požadovali sled, který obsahuje přesně jedenkrát každou hranu, dostali bychom snadno řešitelné úlohy, kterými jsme se zabývali v kapitole 10 o eulerovských tazích.
12.1.5 Problém obchodního cestujícího. Jde o nalezení nejkratší hamiltonovské kružnice v úplném neorientovaném grafu, jehož hrany jsou ohodnoceny délkami.
Název (a popularita) této úlohy je založen na následující představě: obchodní cestující má za úkol navštívit v libovolném pořadí n měst a vrátit se zpět tak, aby jeho trasa byla co nejkratší. Přitom se předpokládá, že vzdálenosti mezi všemi dvojicemi měst jsou předem známé a symetrické (v obou směrech je vzdálenost stejná).
Často se mluví také o orientované variantě problému obchodního cestujícího -hledá se nejkratší hamiltonovský cyklus v úplném orientovaném grafu.
12.1.6 Příklad: Dopravní úlohy. Problém obchodního cestujícího má četné aplikace, v nichž jde o optimalizaci pohybu dopravního prostředku, např. při rozvozu zboží, vybírání poštovních schránek apod. Stejný problém se však vyskytuje např. při vrtání velkého počtu děr do desky s plošnými spoji pomocí číslicově řízené vrtačky (minimalizace přesunů).
V některých případech jde o nalezení (neuzavřené) hamiltonovské cesty. Např. při rozvozu pracovníků na roztroušená pracoviště můžeme požadovat, aby se dopravní prostředek nevracel prázdný, ale aby po skončení prací opět naložil v obráceném pořadí všechny pracovníky. Výchozí vrchol je přitom pevně určen, zatímco koncový obvykle nikoli.
Mnohé praktické úlohy jsou obecnější a zahrnují problém obchodního cestujícího jako částečný případ: jestliže se při rozvozu zboží nevejde všechno do jednoho auta,
12.2.  Vzájemné převody úloh
199
je třeba vykonat několik jízd (lhostejno, zda postupně nebo několika auty najednou). Optimální rozvoz by pak měl mít tu vlastnost, že každá jízda je optimálním řešením problému obchodního cestujícího pro podmnožinu těch míst, která jsou touto jízdou zásobována.
12.1.7 Příklad: Plánování procesů. Mějme nějaké výrobní zařízení (třeba chemický reaktor), kterým máme periodicky vyrábět n produktů pi,p2, ■ ■ ■ ,pn-Má-li po výrobě produktu Pí bezprostředně následovat výroba produktu pj, pak v závislosti na těchto dvou produktech buď je, anebo není třeba zařízení vyčistit, nastavit nebo seřídit, což stojí nějaký čas nebo peníze. Úkolem je najít cyklický plán výroby všech produktů (tj. cyklické pořadí produktů) bez ztrátových časů.
Tuto úlohu lze snadno převést na hledání hamiltonovského cyklu v grafu, jehož n vrcholů odpovídá produktům pi,p2, ■ ■ ■ ,pn a jehož hrany vyjadřují možnost změn vyráběných produktů bez časových nebo peněžních ztrát.
Jestliže v této úloze hamiltonovský cyklus neexistuje, cyklická výroba bez ztrátových časů není možná. V takovém případě se můžeme snažit alespoň o minimalizaci ztrát, což vede na orientovanou variantu problému obchodního cestujícího.
Má-li být výroba jednorázová (každý produkt se má vyrábět jen jedenkrát), pak odpadnou náklady na uvedení výrobního zařízení do výchozího stavu, což vede k hledání nejkratší orientované hamiltonovské cesty.
12.2   Vzájemné převody úloh
Situace, kdy máme řešit nějakou úlohu, ale nemáme k dispozici vhodnou metodu řešení (nebo počítačový program), je bohužel častá. Mnohdy si však lze pomoci tím, že danou úlohu převedeme (transformujeme) na úlohu jinou, kterou řešit dovedeme, a z nalezeného řešení této druhé úlohy pak odvodíme řešení úlohy původní. Dovednost převádět jednu úlohu na druhou je obecně velice užitečná. V případě hamilto-novských úloh, které mají značný počet variant, je toto „umění" tím užitečnější.
Souhrnně lze konstatovat, že všechny existenční hamiltonovské úlohy lze vzájemně převádět, (každou na každou) a totéž platí i o úlohách optimalizačních. Navíc lze každou existenční úlohu převést na analogickou úlohu optimalizační. Všechny tyto převody jsou P-redukcemi, viz 11.1.7, str. 188.
Uvedeme zde jen některé převody, ostatní přenecháme čtenáři jako cvičení.
12.2.1 Převod existenční úlohy na optimalizační je snadný: Daný graf (prostý a bez smyček) doplníme na úplný graf. Délky původních hran zvolíme nulové, přidané hrany budou mít délku 1. Nyní platí, že v původním grafu existuje hamiltonovská cesta (kružnice, cyklus) právě tehdy, když v odpovídajícím úplném grafu existuje hamiltonovská cesta (kružnice, cyklus) o nulové délce. Žádná cesta (kružnice, cyklus) nemůže mít délku zápornou, proto nejkratší cesta, má-li nulovou délku, je řešením původní existenční úlohy. Pokud nejkratší cesta v úplném grafu má délku kladnou, pak v původním grafu cesta s požadovanými vlastnostmi neexistuje: kdyby existovala, musela by mít nulovou délku.
200
Kapitola 12. Hamiltonovské cesty a kružnice
12.2.2 Převod optimalizační úlohy na úplný graf. Podobný trik se používá k převodu optimalizační úlohy v obecném grafu na analogickou optimalizační úlohu v grafu úplném. Původní graf doplníme na úplný, přičemž jako délku nově přidaných hran zvolíme nějaké dost velké kladné číslo M. Jako M lze použít např. součet absolutních hodnot délek všech hran. Potom najdeme optimální řešení v úplném grafu. Pokud toto řešení neobsahuje žádnou z přidaných hran, je toto řešení i optimálním řešením úlohy pro původní graf. Pokud naopak nějakou přidanou hranu obsahuje, pak v původním grafů přípustné řešení neexistuje.
12.2.3 Fixovaný počáteční vrchol. Hledáme-li hamiltonovskou cestu, jejíž počáteční vrchol x v grafu G je pevně dán, můžeme takovou úlohu převést na obdobnou úlohu ve větším grafu G', kde již počáteční vrchol není předepsán. Trik spočívá v tom, že ke grafu G přidáme kopii x' vrcholu x a hranu z vrcholu x' do x (viz obr. 12.2a). Poněvadž z vrcholu x' vychází v G' jen jediná hrana, nemůže žádná hamil-tonovská cesta v grafu G' začínat jinde než v tomto přidaném vrcholu a odtud musí pokračovat přidanou hranou do vrcholu x. Všechny hamiltonovské cesty v G začínající via všechny hamiltonovské cesty v G' si vzájemně jednoznačně odpovídají, liší se pouze v hraně (x, x'). Postupujeme tedy tak, že v G' najdeme hamiltonovskou cestu (např. nejkratší), pak vynecháním přidané hrany dostaneme (stejně dlouhou) hamiltonovskou cestu v G, která začíná tam, kde to bylo předepsáno, tj. v x.
Stejný trik lze použít, je-li předepsán koncový vrchol hamiltonovské cesty.
Pro optimalizační úlohu by bylo možno postupovat stejně (délka přidané hrany by byla nulová), existuje však lepší možnost. Popíšeme ji pro orientovanou verzi úlohy: graf ponecháme beze změny, ale všem hranám z množiny E+{x) zvětšíme jejich délku o dostatečně velké číslo M a hranám z množiny E~(x) zvětšíme jejich délku o hodnotu 2M. Tím všechny orientované hamiltonovské cesty, které začínají ve vrcholu x, prodloužíme o hodnotu M, zatímco všechny ostatní hamiltonovské cesty prodloužíme o 3M nebo 2M podle toho, zda vrcholem x prochází nebo v něm končí. Cesty, které nezačínají v x, jsou tím natolik znevýhodněny, že nejkratší hamiltonovská cesta při změněných délkách bude začínat v x (pokud taková existuje).
12.2.4 Převod neorientované cesty na kružnici. Úlohu najít neorientovanou hamiltonovskou cestu s libovolnými krajními vrcholy v grafu G lze převést na úlohu najít hamiltonovskou kružnici ve větším grafu G', který získáme tak, že ke grafu
x
o'
Obrázek 12.2: Ilustrace převodů hamiltonovských úloh.
12.2. Vzájemné převody úloh
201
G přidáme jeden nový vrchol v a spojíme jej hranami se všemi vrcholy grafu G. V optimalizační úloze zvolíme délky nových hran nulové. V grafu G' existuje hamiltonovská kružnice právě tehdy, když v G existuje hamiltonovská cesta. Viz obr. 12.2b.
12.2.5 Převod hamiltonovské kružnice na neorientovanou cestu. Úlohu najít hamiltonovskou kružnici v grafu G lze naopak převést na hledání hamiltonovské cesty s libovolnými krajními vrcholy ve větším grafu G', který získáme takto: Ke grafu G přidáme tři nové vrcholy x,y,z a v grafu G zvolíme libovolně vrchol v. Ke každé hraně mezi vrcholem v a jeho sousedem a v grafu G přidáme v grafu G' stejně dlouhou hranu mezi a a y. Navíc spojíme vrcholy y a z a vrcholy v a x hranami o nulové délce. V takto sestrojeném grafu G' existuje hamiltonovská cesta (z x do z) právě tehdy, když v G existuje (stejně dlouhá) hamiltonovská kružnice. Viz obr. 12.2c.
12.2.6 Převod orientované verze na neorientovanou. Jako poslední ukážeme převod orientovaných verzí hamiltonovských úloh na verze neorientované. Každému vrcholu Xi původního orientovaného grafu přiřadíme trojici vrcholů x[, x", x'-'1. Každý vrchol x'- spojíme neorientovanými hranami o nulové délce s vrcholy x[ a x"'. Každé orientované hraně z Xi do x j v grafu G přiřadíme v grafu G' stejně dlouhou neorientovanou hranu spojující vrcholy x"' a x'j. Viz obr. 12.3.
Vtip této konstrukce je v tom, že všechny dvoučárkované vrcholy musí hamiltonovská cesta procházet stejným směrem, tj. buď všechny od jednočárkované ke tříčárkované, nebo všechny naopak. Orientované hamiltonovské cesty a cykly v původním grafu G tedy vzájemně jednoznačně odpovídají stejně dlouhým neorientovaným hamiltonovským cestám a kružnicím v grafu G'.
Obrázek 12.3: Převod orientované verze hamiltonovských úloh na neorientovanou.
12.2.7 Cvičení. Promyslete detaily převodu úlohy najít nejkratší neorientovanou cestu s fixovaným počátečním i koncovým vrcholem na úlohu bez fixovaných vrcholů. Použijte analogii k 12.2.3.
12.2.8 Cvičení. Jak velké musí být číslo M, které je použito v převodech 12.2.2 a 12.2.3?
202
Kapitola 12. Hamiltonovské cesty a kružnice
12.2.9 Cvičení. Najděte příklad ohodnoceného grafu, v němž nejkratší neorientovaná hamiltonovská cesta není částí nejkratší hamiltonovské kružnice.
Jinak řečeno, najděte příklad, který ukazuje, že nejkratší hamiltonovskou cestu nelze hledat tak, že vezmeme řešení problému obchodního cestujícího a vynecháme z něj nej delší hranu.
12.2.10 Správnost převodu je třeba dokázat. Předchozí cvičení ukazuje, že ne každý nadějně vypadající „převod" jedné úlohy na druhou je korektní a skutečně použitelný. Chcete-li nějaký převod použít bez rizika chyby, měli byste o tomto převodu dokázat dvě věci:
• pokud původní úloha má řešení, pak pomocí převodu takové řešení najdeme,
• pokud původní úloha řešení nemá, pak to pomocí převodu spolehlivě zjistíme.
12.3   Existenční hamiltonovské úlohy
Existenční hamiltonovské úlohy obecně patří k NP-těžkým úlohám. V některých speciálních případech však přesto lze rychle prokázat, že řešení existuje nebo naopak neexistuje.
12.3.1 Cvičení. Graf, který obsahuje most (viz 4.4.1, str. 65), nemůže obsahovat hamiltonovskou kružnici. Najděte graf, který žádný most neobsahuje a přesto v něm hamiltonovská kružnice také neexistuje.
12.3.2 Věta. (Chvátal 1972.) Nechť G je prostý graf bez smyček s n > 3 vrcholy. Jestliže cři < tfe < ... < dn je soubor stupňů jeho vrcholů a jestliže
(12.1) dk < k =>■ dn-k >n — k      pro   1 < k < n/2 ,
pak graf G obsahuje hamiltonovskou kružnici.
Jestliže naopak posloupnost čísel d\ < di < ... < dn nesplňuje podmínku 12.1, pak existuje graf o n vrcholech, který neobsahuje hamiltonovskou kružnici a pro jehož všechny vrcholy ví platí d(vi) > d{.
Poznámka: Prvá část věty zaručuje existenci hamiltonovské kružnice, jsou-li stupně vrcholů „dost velké". Druhá část vlastně říká, že lepší podmínka založená pouze na stupních vrcholů již neexistuje. Dodejme, že pokud není splněna podmínka 12.1 (a takových grafů je spousta), hamiltonovská kružnice může a nemusí existovat, věta o tom nic neříká.
Důkaz této věty není jednoduchý, lze jej najít např. v knize [Nešetřil79]. Poznamenejme pouze, že důkaz je proveden sporem a nedává žádný návod k hledání hamiltonovské kružnice, a to ani v případě, když věta její existenci zaručuje.
12.3.3 Věta. (Ghouilla-Houri 1960.) Nechť G je silně souvislý prostý orientovaný graf s n vrcholy a nechť pro každý vrchol x platí d+(x) + d~{x) > n. Potom graf G obsahuje hamiltonovský cyklus.
12.4. Optimalizační hamiltonovské úlohy
203
Poznámka: Také tato věta nedáva návod, jak hamiltonovský cyklus hledat, a to ani v případě, kdy jeho existenci zaručuje.
12.3.4 Cvičení. Zjistěte, zda existuje hamiltonovská kružnice v úplném bipar-titním grafu Äe.s?
12.3.5 Hledání hamiltonovských cest, cyklů a kružnic. Můžeme použít backtracking (viz 11.2, str. 189), který v tomto případě bude modifikací algoritmu 3.3.10 k prozkoumání všech cest, které začínají ve zvoleném vrcholu. Algoritmus 3.3.10 lze snadno doplnit o test, zda právě nalezená cesta je hamiltonovskou cestou, kružnicí, popř. cyklem. Takto můžeme získat dokonce úplný seznam všech hamiltonovských cest, kružnic či cyklů v daném grafu, je to však časově velice náročné i pro nepříliš velké grafy.
Celý postup lze poněkud zrychlit tím, že se v každém kroku snažíme rozpoznat hrany, které musíme nebo naopak nesmíme přidávat ke stávající cestě, aby ji bylo možno doplnit na hamiltonovskou. Dosažitelné zrychlení však je řádově jen asi dvojnásobné. Detaily lze najít v [Chr75].
Další možností je převod na optimalizační úlohu, viz 12.2.1.
12.3.6 Heuristické postupy. Pro řešení hamiltonovských úloh byla vypracována také řada poměrně rychlých algoritmů, u nichž však není zaručeno, že řešení najdou vždy, když existuje. V jednom z nich např. prodlužujeme stávající cestu, dokud je to možné. Nelze-li již cestu prodloužit, pokoušíme se závěrečnou část cesty odpojit a připojit obráceně (viz obr. 12.4) a pokračovat v prodlužování z jiného vrcholu.
Pro zvýšení naděje na úspěch se doporučuje tyto algoritmy použít opakovaně na týž graf s náhodně přečíslovanými vrcholy. Podrobnosti lze najít v [Chr75] a [Kučera83].
12.4   Optimalizační hamiltonovské úlohy
Optimalizační hamiltonovské úlohy jsou přinejmenším stejně obtížné jako úlohy existenční, neboť každou existenční úlohu lze velmi jednoduše převést na řešení úlohy optimalizační (viz 12.2.1). Všechny tyto úlohy jsou pro obecné grafy NP--těžké.
Problém obchodního cestujícího lze asi nejjednodušeji řešit takzvanou metodou hrubé síly, tedy jednoduchým, ale pracným vyzkoušením všech přípustných řešení, tj. všech permutací (pořadí) vrcholů: pro každou permutaci vypoč-
Obrázek 12.4: Přepojování cest.
204
Kapitola 12. Hamiltonovské cesty a kružnice
teme délku odpovídající hamiltonovské kružnice a vybereme z nich nejkratší. Počet všech přípustných řešení však roste jako faktoriál počtu vrcholů, proto přidání i jen jediného vrcholu prodlouží výpočet mnohonásobně. Tento primitivní způsob řešení je prakticky použitelný jen na grafy s nejvýše asi tak tuctem vrcholů.
Pro obecnější hamiltonovské optimalizační úlohy lze podobně použít jednoduchý backtracking (např. podle 3.3.10, str. 56) k nalezení všech hamiltonovských cest, kružnic nebo cyklů a z nich pak opět vybrat nejkratší. Pokud však při tom nepoužijeme nějaké triky pro urychlení výpočtu, je to jen jiná forma metody hrubé síly. V grafech, které mají hodně hran (zejména pak v úplných grafech), to není o mnoho rychlejší než výše zmíněné vyzkoušení všech permutací.
Dále uvedeme několik algoritmů, které lze použít na úlohy o něco rozsáhlejší (několik desítek vrcholů).
12.4.1 Hledání nejkratší neorientované hamiltonovské cesty. Popíšeme algoritmus, který je jednoduchým použitím metody větví a mezí (viz 11.3, str. 191). Úlohu přeformulujeme takto:
Hledáme nejlevnější podgraf H daného grafu G takový, že:
1. podgraf H je kostrou grafu G,
2. všechny vrcholy podgrafu H mají stupeň dn(x) < 2.
Prvá z uvedených omezujících podmínek je příjemná ve smyslu 11.3.4, relaxováním (uvolněním) druhé (nepříjemné) podmínky totiž dostaneme známou úlohu o minimální kostře, kterou lze snadno řešit, viz 4.3, str. 61.
Pokud v nejlevnější kostře, kterou dostaneme řešením relaxované úlohy, mají všechny vrcholy stupeň nejvýše 2, pak tato kostra je nejlevnější nejen mezi kostrami, ale i mezi všemi hamiltonovskými cestami, máme tedy optimální řešení.
Pokud má některý vrchol x v kostře H stupeň dn(x) > 2, pak úlohu rozvětvíme na podúlohy. Nejjednodušší verze větvení je založena na faktu, že hrany z množiny Eh{x) nemohou být všechny obsaženy v téže hamiltonovské cestě. Proto pro každou hranu e 6 Eh (x) vytvoříme podúlohu, v níž je hrana e zakázána. Tím dostaneme <Ih{x) podúloh, které pak řešíme stejným postupem jako původní úlohu: hledáme nejlevnější kostru a testujeme stupně vrcholů v této kostře. Je-li třeba, podúlohu dále větvíme zakazováním dalších hran.
Dodejme, že po zákazu hrany není nutno opakovat celý výpočet nejlevnější kostry. Zákazem hrany se dosavadní minimální kostra rozpadla na dvě komponenty a tyto komponenty stačí spojit nejlevnější dosud nezakázanou hranou. Vyplývá to z věty 4.3.14, str. 64.
Právě popsaný postup řešení je předveden v příkladě 12.4.2.
Dodejme dále, že výše uvedený způsob větvení na podúlohy je sice jednoduchý, ale neefektivní, poněvadž vytvořené podúlohy nemají disjunktní množiny přípustných řešení. Snadno se pak stane, že totéž řešení se zbytečně vyskytuje v několika větvích stromu řešení, strom se příliš rozrůstá a výpočet je zbytečně pomalý. Platí to zejména v případě, kdy stupeň vrcholu v kostře je větší než tři.
12.4. Optimalizační hamiltonovské úlohy
205
Efektivnější způsob větvení využívá nejen zákazy, ale i vynucenou přítomnost hrany v kostře:
- zakážeme hranu e\ € Ejj{x),
- vynutíme hranu e\ a zakážeme e2 € Eh{x),
- vynutíme hrany e\,e2 a zakážeme všechny ostatní hrany z množiny Eq{x) (pozor, nikoli pouze z Eh{x)).
Všimněte si, že u třetí z těchto podúloh využíváme fakt, že nejvýše dvě hrany z množiny Eg(x) mohou být obsaženy v hamiltonovské cestě. Dále si všimněte, že tímto způsobem dostaneme vždy jen tři podúlohy nezávisle na stupni vrcholu x v kostře.
12.4.2 Příklad. Hledejme nejkratší hamiltonovskou cestu v úplném grafu, ve kterém jsou délky hran dány maticí
(	oc	7	2	3	11	17 \
	7	oo	10	13	8	10
	2	10	oo	10	19	15
	3	13	10	co	16	15
	11	8	19	16	00	13
\	17	10	15	15	13	oo /
K řešení použijeme právě popsaný algoritmus 12.4.1. K větvení budeme vybírat vždy živou podúlohu s nejnadějnějším (tj. zde nejmenším) odhadem, větvení budeme dělat prvým a jednodušším z obou popsaných způsobů (tj. pouze zakazujeme jednotlivé hrany). Průběh výpočtu je patrný z následující tabulky a z obr. 12.5 na následující straně.
podúloha   zakázané hrany        odhad komentář
1	—		30	větveno na podúlohy 2, 3, 4	
2	(1,3)		38	umrtveno díky odhadu	
3	(1,2)		33	větveno na podúlohy 5,	6, 7
4	(1,4)		37	umrtveno díky odhadu	
5	(1, 2), (2, 5)		36	umrtveno díky odhadu	
6	(1, 2), (2, 3)		34	větveno na podúlohy 8,	9, 10
7	(1, 2), (2, 6)		36	optimální řešení	
8	(1, 2), (2, 3), (1,3)		42	umrtveno díky odhadu	
9	(1, 2), (2, 3),	(1,4)	41	umrtveno díky odhadu	
10	(1, 2), (2, 3),	(1, 5)	36	umrtveno diky odhadu	
12.4.3 Cvičení. Řešte znovu příklad 12.4.2, ale použijte efektivnější způsob větvení, popsaný v 12.4.1. Výsledek bude týž, ale dosáhnete jej s menším stromem řešení. (Obecně by výsledkem nemusela být stejná hamiltonovská cesta, ale délka výsledné cesty samozřejmě stejná být musí.)
206
Kapitola 12. Hamiltonovské cesty a kružnice
5 4 Odhad = 30
5" 4
Odhad = 38 umrtveno díky odhadu
5 4 Odhad = 33
5 4
Odhad = 36 umrtveno díky odhadu
5 4 Odhad = 34
5 4
Odhad = 42 hamilt. cesta
5 4
Odhad = 41 hamilt. cesta
5 4
Odhad = 37 umrtveno díky odhadu
5 4
Odhad = 36 optimální řešení
5 4
Odhad = 36 umrtveno díky odhadu
Obrázek 12.5: Strom řešení k příkladu 12.4.2.
12.4.4 Nejkratší hamiltonovský cyklus lze hledat rovněž metodou větví a mezí. Úlohu přeformulujeme takto:
Hledáme nejlevnější podgraf H daného grafu G takový, že:
1. hrany podgrafu H tvoří soustavu vrcholově disjunktních cyklů, které procházejí všemi vrcholy grafu G,
2. podgraf H je souvislý.
Prvou z podmínek opět pokládáme ve smyslu 11.3.4 za příjemnou, druhou za nepříjemnou. Relaxovanou úlohu, v níž je uvolněna (relaxována) podmínka 2, lze řešit převodem na přiřazovací úlohu 9.4, str. 171:
kružnice
12.4. Optimalizační hamiltonovské úlohy
207
dou vetví
Každému vrcholu původního grafu je třeba přiřadit vrchol, který po něm v cyklu následuje, každý vrchol zároveň musí být přiřazen jako následník přesně jednomu vrcholu, totiž svému předchůdci. Toto přiřazení můžeme chápat jako perfektní párování v bipartitním grafu, který dostaneme tak, že každý vrchol původního grafu zdvojíme.
Jinou možností, jak hledat zmíněnou soustavu cyklů, je pomocí toků v síti. Hledáme nejlevnější cirkulaci takovou, že tok každým vrcholem má jednotkovou velikost. Tuto úlohu nejprve trikem podle 8.1.13, str. 132, převedeme na standardní úlohu hledání nejlevnější přípustné cirkulace a tu pak řešíme algoritmem 8.7.
Pokud nejkratší soustava cyklů nesplňuje podmínku 2, tj. pokud jde o soustavu více než jednoho cyklu, je zřejmé, že hrany některého (libovolného) z těchto cyklů nemohou být všechny obsaženy v cyklu hamiltonovském. Proto můžeme úlohu rozvětvit na podúlohy nejjednodušeji tak, že vybereme jeden z cyklů (doporučuje se, aby měl co nejméně hran) a pro každou jeho hranu vytvoříme podúlohu í/;, v níž je hrana ěj zakázána.
V přiřazovací úloze lze zákaz hrany docílit zvýšením její ceny na dostatečně vysokou hodnotu (tzv. prohibitivní cena). Přitom není nutno opakovat celý výpočet přiřazovací úlohy, stačí změnit cenu zakazované hrany a pokračovat od poslední fáze výpočtu. Při použití toku v síti docílíme zákazu změnou kapacity hrany e\. Viz též poznámku 8.7.9 k algoritmu Out of Kilter.
Výše popsaný jednoduchý způsob větvení na podúlohy je neefektivní, neboť podúlohy nemají disjunktní množiny přípustných řešení. Disjunktnosti lze dosáhnout vynucováním hran podobně jako v 12.4.1.
Lepší výsledky (menší strom řešení) však dává následující způsob větvení: Zvolme některý cyklus a označme M množinu všech jeho vrcholů. Ve výsledném hamiltonovském cyklu musí zcela jistě být zahrnuta alespoň jedna hrana z množiny W+(M), jinými slovy, je třeba „donutit cyklus, aby opustil množinu M". Toho lze docílit tím, že vytvoříme podúlohu pro každý vrchol Vi e M, a to tak, že zakážeme všechny hrany, které z vrcholu v i vedou do množiny M.
Uvedeným postupem lze řešit orientovanou verzi problému obchodního cestujícího. Lze jej samozřejmě použít i pro řešení verze neorientované (kde matice délek hran je symetrická).
12.4.5 Příklad. Použijeme právě popsanou metodu k nalezení nejkratšího ha-miltonovského cyklu v úplném grafu s maticí délek hran z příkladu 12.4.2.
Průběh řešení je patrný z následující tabulky a obrázku 12.6 na následující straně. K větvení byla použita poslední z uvedených metod.
ré prochá-
druhou za nka 2, lze
podúloha	zakázané hrany	odhad	komentář
1		46	větveno na podúlohy 2, 3, 4
2	(1, 3), (1, 4)	55	hamilt. cyklus
3	(3, 1), (3, 4)	51	optimální řešení
4	(4, 1), (4, 3)	50	větveno na podúlohy 5, 6
5	(4, 1), (4, 3), (1, 3)	51	umrtveno díky odhadu
6	(4, 1), (4, 3), (3, 1)	55	hamilt. cyklus
208
Kapitola 12. Hamiltonovské cesty a kružnice
Odhad = 55 Odhad = 51 Odhad = 50
hamilt. cyklus optimální řešení
Odhad = 51 Odhad = 55
umrtveno díky odhadu      hamilt. cyklus
Obrázek 12.6: Strom řešení k příkladu 12.4.5.
12.4.6 1-strom a metoda penalizace. Jde o docela poučný trik, který lze použít k hledání nejkratší hamiltonovské kružnice, a tedy i k řešení problému obchodního cestujícího. Mějme graf s množinou vrcholů V(G) = {1,..., n}.
1-strom je faktor H daného grafu G, který má stejný počet vrcholů a hran a vrchol 1 v něm má stupeň dn(l) — 2. Jinak řečeno, libovolný 1-strom daného grafu o n vrcholech dostaneme tak, že vezmeme podgraf indukovaný množinou {2,..., n}, najdeme nějakou kostru tohoto podgrafu a přidáme k ní vrchol 1 spolu s nějakými dvěma hranami z tohoto vrcholu. Každý 1-strom tedy obsahuje přesně jednu kružnici a tato kružnice prochází vrcholem 1.
Nyní můžeme úlohu najít nejkratší hamiltonovskou kružnici přeformulovat takto: hledáme podgraf H daného grafu G takový, že
1. podgraf H je 1-stromem,
2. každý vrchol x podgrafu H má stupeň dfi(x) = 2.
Opět platí, že prvá z obou podmínek je příjemná, protože nejlevnější 1-strom lze snadno najít pomocí algoritmu pro nejlevnější kostru (viz 4.3): najdeme nejlevnější kostru na množině {2,... ,n} a přidáme dvě nejlevnější hrany z množiny £g(1).
Pokud nejlevnější l-strom náhodou splňuje i druhou podmínku, pak tento 1-strom je zároveň hledanou nejkratší hamiltonovskou kružnicí.
12.4. Optimalizační hamiltonovské úlohy
209
Druhá z podmínek je však nepříjemná a činí úlohu obtížnou. Platnost této podmínky samozřejmě lze vynucovat metodou větví a mezí podobně jako při hledání nejkratší hamiltonovské cesty v 12.4.1. Na tuto metodu zpravidla stejně dojde, ale napřed je vhodné na podúlohu zkusit trik, kterému se říká penalizace vrcholů.
Každému vrcholu x grafu G přiřadíme číslo p(x), tzv. penále. Každé hraně grafu, která spojuje vrcholy i a j, nyní změníme délku z hodnoty a(i,j) na hodnotu a(i,j) + + p(i) + p(j) a v takto ohodnoceném grafu znovu vyhledáme nejlevnější 1-strom.
Vtip penalizace spočívá v tom, že délky všech hamiltonovských kružnic se vlivem penále zvětšily o stejnou hodnotu, totiž o dvojnásobek sumy všech penále, tj. o hodnotu 2^™=1p(«). Délky ostatních 1-stromů se přitom mohly změnit jinými způsoby, některé mohly stoupnout, jiné klesnout. Proto, podaří-li se vhodně zvoleným penále docílit toho, že nejlevnější 1-strom bude zároveň hamiltonovskou kružnicí, budeme mít jistotu, že tento 1-strom (tj. kružnice) je také nejkratší ze všech hamiltonovských kružnic.
Penále, popř. jeho změna, se zpravidla odvozuje ze stupňů vrcholů v 1-stromu. Má-li vrchol vysoký stupeň, dostane kladné penále, tím se prodraží hrany z jeho okolí a je naděje, že se stupeň sníží. Má-li naopak vrchol stupeň 1, dostane záporné penále, ceny hran v jeho okolí klesnou a stupeň vrcholu se může zvětšit. Nejjedno-dušší pravidlo radí zvětšovat dosavadní penále vrcholu v o hodnotu k(d(v) — 2), kde konstanta k nemá být příliš velká, může být i rovna jedné. Různé způsoby volby penále a výpočetní zkušenosti jsou podrobně popsány v knize [Chr75].
Výpočet obvykle začíná s nulovým penále, tj. s původními délkami hran tím, že vypočteme nejlevnější 1-strom. Pokud není nalezena hamiltonovská kružnice, tj. pokud některý vrchol má jiný stupeň než 2, vypočteme změny (přírůstky) penále pro jednotlivé vrcholy, změníme délky hran a znovu hledáme nejlevnější 1-strom.
Metoda penalizace bohužel nevede vždy k cíli. Existují grafy, kde sebedůmysl-nější volba penále nevynutí vznik hamiltonovské kružnice. Výše popsaný výpočet by pak nikdy neskončil. Proto je nutno neúspěšný výpočet ukončit buď když zjistíme, že se opakuje stejná situace, nebo prostě po přiměřeném počtu neúspěšných penalizací.
Ovšem i neúspěšná penalizace není zbytečná, lze ji použít v metodě větví a mezí k získání lepšího dolního odhadu. Jestliže jsme při použití penále p dostali 1-strom o ceně C, pak číslo C — 2 J2i=i PÍO 'ze použít jako dolní odhad: délka žádné hamiltonovská kružnice (měřená v původních, tj. nepenalizovaných cenách) nemůže být kratší než toto číslo. V průběhu neúspěšné penalizace takovýchto odhadů získáme několik a jako odhad pro celou podúlohu použijeme nejlepší (tj. zde největší) z nich.
12.4.7 Cvičení. Metodu penalizace lze snadno upravit pro hledání nejkratší neorientované hamiltonovské cesty z daného počátečního vrcholu x do daného koncového vrcholu y. V takovém případě namísto nejlevnějšího 1-stromu hledáme minimální kostru takovou, že vrcholy x a y v ní mají stupeň 1. Takovou minimální kostru lze snadno najít buď tak, že najdeme minimální kostru na množině vrcholů V(G) \ {x,y} a přidáme nejlevnější hrany z vrcholů x a y, nebo (jednodušeji) vrcholům x a y dáme velmi vysoké počáteční penále.
210
Kapitola 12. Hamiltonovské cesty a kružnice
Jak se změní délky všech hamiltonovských cest z a; do y při použití penále p? Jakou hodnotu lze použít jako dolní odhad v metodě větví a mezí?
12.4.8 Heuristicke algoritmy pro problém obchodního cestujícího. Poměrně dobré výsledky dává metoda nejvzdálenějšího vkládání:
Začneme s triviální kružnicí v nějakém vrcholu a do této kružnice postupně zařazujeme další vrcholy, dokud nedostaneme kružnici hamiltonovskou. K zařazení do kružnice vybíráme vrchol, který je od kružnice nejvíce vzdálen (odtud název metody). Přesněji, máme-li kružnici K, která prochází vrcholy vi,...,Vk, pak vybereme vrchol v, pro který je výraz min{a(v,Vi) \ i = 1,...,k} největší. Vrchol v pak zařadíme do kružnice mezi takové dva sousední vrcholy, aby se tím kružnice prodloužila co nejméně.
Stojí za zmínku, že o něco „hladovější" postup, při němž se vkládá vrchol, který je ke kružnici nejblíže, dává v průměru o něco horší výsledky. Je vidět, že chamtivost se vždycky nevyplácí.
Dobré výsledky dává také lokální průzkum (viz 11.4, str. 196), v němž se stávající řešení snažíme vylepšovat prováděním „drobných změn". Osvědčilo se kombinovat dva typy změn. Jedna spočívá v tom, že ze stávající hamiltonovské kružnice odstraníme dvě hrany a zbývající části kružnice propojíme „do kříže" tak, aby znovu vznikla hamiltonovská kružnice. Druhý typ spočívá v odstranění vrcholu a jeho zařazení na jiné místo kružnice.
211
Kapitola 13
Barevnost, nezávislost, kliky
Pojmy uvedené v nadpise bývají někdy označovány jako kombinatorické. Třebaže mají důležité aplikace, jsou úlohy s nimi spojené většinou NP-těžké. Algoritmy pro barvení grafu a pro hledání nejpočetnějších nezávislých množin, které zde uvedeme, jsou založeny na backtrackingu.
Všechny pojmy studované v této kapitole jsou nezávislé na orientaci a na násobnosti hran. Můžeme se tedy omezit na prosté neorientované grafy. Navíc se omezíme na grafy bez smyček.
13.1   Definice a základní fakta
13.1.1 Obarvení grafu G (nebo též obarvení vrcholů grafu) je ohodnocení vrcholů hodnotami z množiny B (takzvanými barvami), a to takové, že žádné dva sousední vrcholy nejsou ohodnoceny (obarveny) stejnou barvou. V roli barev můžeme brát libovolné prvky z libovolné množiny, často používáme např. čísla.
Graf nazýváme r-barevným, jestliže existuje jeho obarvení r barvami. Barevnost grafu (někdy též chromatické číslo grafu nebo vrcholová barevnost) je nejmenší počet barev, který je potřebný k obarvení grafu. Barevnost grafu G značíme x(G)-
13.1.2 Cvičení. Najděte obarvení grafu z obrázku 13.1 třemi barvami. Ověřte, že toto obarvení je až na záměnu barev jediné. Lze obarvit graf, který má smyčky?
1 3 5 7 A B A B
2 4 6 & C D C D
Obrázek 13.1: Graf a jeho obarvení čtyřmi barvami A, B, C, D.
212
Kapitola. 13. Barevnost, nezávislost, kliky
13.1.3 Nezávislá množina vrcholů v grafu G je taková množina, jejíž žádné dva vrcholy nejsou spojeny hranou. Podgraf indukovaný touto množinou je tedy diskrétní. Maximální nezávislá množina je nezávislá množina, která je maximální vzhledem k inkluzi, tj. nezávislá množina, ke které již nelze přidat žádný vrchol, aniž by přestala být nezávislou.
Nejpočetnější nezávislá množina je nezávislá množina, která má největší počet prvků (mezi všemi nezávislými množinami v grafu G). Každá nejpočetnější nezávislá množina je samozřejmě i maximální nezávislou množinou, ale naopak to neplatí. Jak nejpočetnějších, tak i maximálních nezávislých množin může být v temže grafu několik. Počet vrcholů v nejpočetnější nezávislé množině grafu G nazýváme nezávislostí grafu G. Nezávislost grafu G značíme a(G). V aplikacích se setkáváme také s úlohou najít nejdražší nezávislou množinu ve smyslu součtu ohodnocení vrcholů cenami.
Graf na obr. 13.1 vlevo má tyto maximální nezávislé množiny: {1,4,5,8}, {1,4,7}, {1,6}, {2,5,8}, {2,6}, {2,7}, {3,7} a {3,8}. Nejpočetnější nezávislá množina byla uvedena jako první, nezávislost tohoto grafu je rovna 4. Množina {1,4,5} je příkladem množiny, která je nezávislá, ale není maximální nezávislá.
Všimněte si, že množina vrcholů, které mohou být obarveny stejnou barvou, je vždy nezávislá.
13.1.4 Klika v grafu G je maximální podgraf grafu G, který je úplným (neorientovaným) grafem. Počet vrcholů v největší klice nazýváme klikovostí grafu. Klikovost grafu budeme značit u>(G).
V grafu na obr. 13.1 je každá klika trojúhelníkem, klikovost tohoto grafu je tedy rovna 3, v grafu je celkem šest klik.
Kliky a maximální nezávislé množiny spolu velmi úzce souvisí. Abychom to ukázali, sestrojme k danému grafu G tzv. doplňkový graf —G takto: Oba grafy budou mít stejné vrcholy. V doplňkovém grafu — G budou dva vrcholy spojeny hranou právě tehdy, když nejsou spojeny hranou v původním grafu G. Je zřejmé, že doplňkový graf —(—G) k doplňkovému grafu — G je shodný s původním grafem G. Stejně tak je zřejmé, že kliky v grafu G odpovídají vzájemně jednoznačně maximálním nezávislým množinám v doplňkovém grafu — G. Platí tedy a{G) = w(—G) a to(G) = = a(-G).
13.1.5 Příklad: Skladování nebezpečných látek. Mějme n nebezpečných látek. Bezpečnostní předpisy zakazují skladovat některé dvojice látek ve stejné místnosti (skříni, polici). Kolik nejméně místností (skříní, polic) je nezbytně třeba k uskladnění všech n látek?
Řešení lze nalézt pomocí barevnosti: Sestrojme graf G, jehož vrcholy odpovídají zmíněným látkám a v němž jsou dva vrcholy spojeny hranou, jestliže odpovídající látky nesmí být skladovány společně. Přípustné umístění látek do místností pak odpovídá obarvení grafu G. Roli barev zde hrají místnosti. Potřebujeme tedy nejméně x(C) místností.
Podívejme se nyní na jinou úlohu: Máme za úkol přepravit najednou, např. v jednom autě, co největší počet vzorků těchto látek. Přepravované vzorky musí
13.1. Dennice a základní fakta
213
tvořit nezávislou množinu v grafu G, můžeme tedy najednou přepravit nejvýše a(G) vzorků.
Pokud by každý ze vzorků měl danou cenu, mohli bychom požadovat přepravu množiny vzorků, která bude mít co nej větší cenu. To by odpovídalo nej dražší nezávislé množině v grafu G. Srovnejte tuto poslední variantu s problémem batohu 2.4.2, str. 44.
13.1.6 Příklad: Plánování procesů. Máme za úkol uskutečnit n procesů pi, p2, ■ • ■, pn, přičemž některé dvojice procesů nesmějí (nebo nemohou) probíhat současně např. proto, že vyžadují použití stejných strojů. Kolik časových jednotek je třeba k uskutečnění všech procesů, trvá-li každý proces stejně dlouho (např. jednotku času)? Jaký největší počet procesů může probíhat najednou?
Sestrojme graf G, jehož vrcholy odpovídají procesům. Dva vrcholy spojíme hranou právě tehdy, když odpovídající procesy nesmějí probíhat současně. Každé obarvení vrcholů grafu G rozděluje procesy na skupiny, které mohou probíhat najednou (odpovídající vrcholy jsou obarveny stejnou barvou). Nejkratší možné provedení všech procesů tedy trvá x(G)- Procesy, které mohou probíhat najednou, vždy tvoří nezávislou množinu. Maximální možný počet současně probíhajících procesů tedy je roven a(G).
13.1.7 Cvičení. Na škole se vyučují předměty pi,p2,... ,pn ve studijních skupinách Sj, s2, ■ ■ ■, sr. Na škole učí učitelé u\,u2,... ,um. Předpokládejme, že pro každou studijní skupinu a předmět je předem pevně určen učitel. Učební plán je tedy dán jako seznam trojic (sí,Pj,Uk), které vyjadřují, že ve studijní skupině Sj bude předmět pj učit učitel Uk- Kolik nejméně vyučovacích hodin bude nezbytných pro splnění učebního plánu?
NÁVOD: Vyučovací hodinu vyjádřenou trojicí {si,Pj,Uk) pokládejte za proces (viz 13.1.6). Dva procesy nemohou probíhat současně, vyžadují-li stejného učitele nebo stejnou studijní skupinu.
13.1.8 Věta. V prostém grafu G bez smyček platí:
X[G) < max{d(x)\x € V(G)} + 1 .
Důkaz: Uvedeme jednoduchý algoritmus, který vrcholy grafu G obarví h + 1 barvami, kde h = max{<i(x)|a: 6 V(G)}. V roli barev použijeme čísla 1,2,.,, ,h+ 1.
Seřaďme vrcholy do posloupnosti Xi,x2,... ,xn. Vrchol xi obarvíme barvou 1. Pak postupně vrcholům x2,xs,... ,xn přiřadíme barvy podle tohoto pravidla: vrchol Xi obarvíme nejnižší barvou, která se nevyskytuje mezi dosud obarvenými sousedy vrcholu Xj.
Poněvadž každý vrchol x má nejvýše h sousedů, musí mezi h + 1 barvami vždy existovat alespoň jedna barva b, kterou není obarven žádný soused vrcholu x. Vrchol x tedy lze obarvit barvou b. Takto lze postupně obarvit všechny vrcholy grafu s použitím nejvýše h + 1 barev. □
214
Kapitola 13. Barevnost, nezávislost, kliky
Poznámka: Právě uvedený algoritmus je rychlý a je vhodný pro první odhad barevnosti. Algoritmus 13.2.1 pro obarvení grafu nejmenším počtem barev vychází z obarvení získaného touto metodou. Viz také 13.2.7.
13.1.9 Věta. Pro graf G bez smyček o n vrcholech platí:
1. X(G) < n.
2. X(G) > u(G).
3. X(G)a(G)>n.
4. X(G)+a(G) <n + l.
důkaz: První tvrzení je zřejmé. Druhé tvrzení vyplývá z faktu, že všechny vrcholy kliky je nutno obarvit různými barvami. K důkazu třetího tvrzení si stačí uvědomit, že vrcholy obarvené stejnou barvou tvoří nezávislou množinu. Obarvíme-li tedy graf x(G) barvami, získáme x(G) nezávislých množin, z nichž každá obsahuje nejvýše q(G) vrcholů. Odtud pak plyne nerovnost x{G)ct(G) > n.
K důkazu čtvrtého tvrzení obarvěme nejpočetnější nezávislou množinu první barvou. K obarvení zbývajících n — a(G) vrcholů zcela jistě stačí n — a(G) barev. Platí tedy n — a(G) + 1 > x(G), coz Je Jen jiný zápis dokazované nerovnosti. □
13.1.10 Věta. Nechť G je prostý graf bez smyček. Označme n počet vrcholů, m počet hran a h maximální stupeň vrcholu v grafu G. Dále označme [x\ a \x~\ dolní a horní celou část čísla x, tj. nejbližší celé číslo takové, že [x\ < x a \x~\ > x. Potom o nezávislosti a(G) a barevnosti x(G) platí:
1. a{G) > (2n — m)/3, přičemž rovnost platí pouze pro úplný graf K%.
2. ct(G) > n2/(2m + n), přičemž rovnost platí pouze tehdy, když souvislé komponenty grafu G jsou úplné grafy téže velikosti.
3. a(G) > \n/(h+í)].
4. X(G)+X(-G)<n + 1.
5- x(G) > n2/(n2 — 2m), přičemž rovnost nastává právě tehdy, je-li G úplným
x(G)-partitním grafem se stejně velkými stranami. 6. Vrcholy grafu G lze rozložit na h+ 1 disjunktních nezávislých množin, z nichž
každá má buď [n/(h + 1)J, nebo \n/(h + 1)] vrcholů.
Důkaz   lze najít v knize [Berge73]. □
13.1.11 Věta. Pro libovolný graf G bez smyček platí:
1. x(G) = 1 právě tehdy, když graf G je diskrétní.
2. x{G) = 2 právě tehdy, když graf G neobsahuje kružnici liché délky.
3. x(G) = 2 právě tehdy, když graf G je bipartitní.
Důkaz: První tvrzení je zřejmé. Dokážeme druhé tvrzení. K obarvení kružnice liché délky potřebujeme nejméně 3 barvy. Je-li tedy x(G) = 2, nemůže graf G takovou kružnici obsahovat. Naopak, nechť graf G neobsahuje kružnici liché délky.
13.1. Dennice a základní fakta
215
Popíšeme, jak lze graf obarvit dvěma barvami. (Je-li graf nesouvislý, obarvíme takto každou komponentu zvlášť.)
Zvolme pevně vrchol x. Vrcholy, které mají od vrcholu x lichou vzdálenost (ve smyslu počtu hran v nejkratší cestě), obarvíme barvou 1, vrcholy, které mají sudou vzdálenost (včetně vrcholu x) obarvíme barvou 2. Musíme dokázat, že takto získáme skutečně obarvení, tj. že žádné dva stejně obarvené vrcholy nejsou spojeny hranou.
Vezměme tedy dva libovolné vrcholy u,v, které mají oba lichou (oba sudou) vzdálenost od x. Mezi vrcholy u, v vede cesta sudé délky, která je tvořena částmi nejkratších cest z vrcholu u do a; a z vrcholu x do v. Kdyby byly vrcholy u, v spojeny hranou, tvořila by tato hrana spolu s cestou ziidou kružnici liché délky. Sestrojili jsme tedy skutečně obarvení dvěma barvami.
Třetí tvrzení je snadné. Každé obarvení dvěma barvami určuje rozklad množiny V{G) na množiny A, B takové, že W(A) = W(B) = E(G), graf je tedy bipartitní. Naopak, je-li graf bipartitní, stačí obarvit každou z jeho stran jednou barvou. □
13.1.12 Cvičení. Jakou barevnost má strom?
13.1.13 Věta. Rovinný graf bez smyček lze obarvit čtyřmi barvami.
Poznámka: Tato věta je řešením kdysi slavného tzv. problému čtyř barev: Stačí čtyři barvy k obarvení libovolné politické mapy tak, aby žádné dva sousední státy nebyly vybarveny stejnou barvou?
O řešení tohoto problému se marně pokoušely řady matematiků i laiků přes 100 let. Od roku 1890 byl znám důkaz, že stačí pět barev. Důkaz pro čtyři barvy však byl nesmírně komplikovaný (pomocí počítače bylo nalezeno a vyšetřeno asi 1900 dílčích případů) a byl nalezen až v roce 1976.
Důsledek:   Rovinný graf G bez smyček o n vrcholech má nezávislost a(G) > n/4.
13.1.14 Věta. Pro každá dvě celá kladná čísla kar existuje graf G, který má barevnost x(G) = k a neobsahuje kružnici délky menší nebo rovné r.
Poznámka: Tato věta vlastně říká, že existují grafy s vysokou barevností, které jsou „lokálně řídké". Speciálním případem této věty je tvrzení, že grafy, které neobsahují trojúhelníky, mohou mít libovolně vysokou barevnost. Důkaz tohoto speciálního případu lze najít v knize [Nešetřil79].
13.1.15 Hranová barevnost. V některých aplikacích je vhodnější nebarvit vrcholy, ale hrany. U obarvení hran pak požadujeme, aby každé dvě hrany, které mají společný vrchol, byly obarveny různými barvami. Hranová barevnost (též chromatický index) je nejmenší počet barev, které stačí k obarvení hran. Hranovou barevnost budeme značit x'{G).
Vyšetřování hranové barevnosti grafu G lze převést na vyšetřování (vrcholové) barevnosti v tzv. hranovém grafu: Hranový graf dG získáme takto: Za vrcholy grafu dG prohlásíme hrany původního grafu G. Dva vrcholy v hranovém grafu dG jsou spojeny hranou, jestliže jim odpovídající hrany původního grafu G měly společný vrchol.
216
Kapitola 13. Barevnost, nezávislost, kliky
13.2.
Obarvení hran grafu G a obarvení vrcholů hranového grafu dG si vzájemně x < j
jednoznačně odpovídají, platí tedy x'{G) = x(9G). Navíc však platí: návrc
N
13.1.16   Věta. (Vizing 1964.) Nechť G je prostý neorientovaný graf bez smyček další,
a označme d maximální stupeň vrcholu. Pak hranová barevnost je rovna buď d, B
nebo d + 1. Z poc
poznámka:   Navzdory této větě je přesné určení hranové barevnosti (přesněji, ^
rozhodnutí, zda hranová barevnost je rovna d) v obecném případě NP-úplnou 0 an
úlohou. Algc
1.
13.2   Zjišťování barevnosti 2
Věta 13.1.11 (a její důkaz) spolu s 3.2.7, str. 52, dává dobrý návod ke snadnému ověření, zda daný graf je jedno- či dvoubarevný. Pro tři a více barev již žádný tak efektivní postup není znám. Naopak, rozhodnutí, zda graf je vrcholově r-barevný
pro r > 3, je NP-úplnou úlohou. 2
Dále uvedený algoritmus pro barvení grafu nejmenším možným počtem barev je klasickým příkladem backtrackingu (viz 11.2, str. 189).
13.2.1   Algoritmus pro zjišťování barevnosti.
4.
vstup:   graf G, jehož vrcholy jsou očíslovány čísly 1, 2,.... n. Pro každý vrchol x je dána množina P{x) = V(x) fl {1,2,... ,x — 1}.
Pomocné proměnné:   Právě zkoumané částečné obarvení budeme uchovávat 5,
v hodnotách B(x). Hodnoty Barva(x) budou obsahovat nejlepší dosud nalezené
obarvení. Proměnná omez bude obsahovat číslo barvy, kterou již nechceme použít
ve snaze získat obarvení méně než omez barvami. S výjimkou počáteční fáze bude
proměnná omez rovna počtu barev v nejlepším dosud nalezeném obarvení Barva.
výstup:   výše popsané proměnné Barva a omez.
Metoda:   Vzhledem k pevnému očíslování vrcholů můžeme každé obarvení pokládat za posloupnost barev. Tyto posloupnosti budeme systematicky prodlužovat 13.2. a zkracovat v duchu backtrackingu. Postu:
Při postupu vpřed, tj. při prodlužování částečné posloupnosti barev, dáme B po
následujícímu vrcholu x jako výchozí vždy nejnižší barvu, která (momentálně) není použita u vrcholů z množiny P(x). Nižší barvu nelze použít (při stávajících barvách předchozích vrcholů), vyšší barvy budou zkoušeny v dalším průběhu backtrackingu (po provedení návratu).
Prvé úplné obarvení tedy bude stejné jako v důkaze věty 13.1.8.
Návraty v backtrackingu budeme provádět jednak při dosažení úplného obarvení, jednak v situaci, kdy některý vrchol y dostal barvu omez nebo vyšší. Přidělením této barvy jsme totiž dostali částečné obarvení, jehož prodlužování již nemá smysl, neboť nemůže vylepšit nejlepší dosud známé obarvení Barva.
Cílem návratu je snížit barvu ve vrcholu y. Poněvadž však nižší barvy v y již jsou vyzkoušeny, je třeba změnit (a tedy zvýšit) barvu v některém předchozím vrcholu
13.2. Zjišťování barevnosti
217
x < y. Aby to však mělo vliv na vrchol y, musí být x € P(y), proto provedeme prvý návrat až do vrcholu x = max(P(y)) a v tomto vrcholu se pokusíme zvýšit barvu.
Nelze-li barvu ve vrcholu x zvýšit (byla by použita barva omez), provedeme další, tentokrát již prostý návrat do vrcholu x — 1, x — 2 atd.
Barvu vrcholu 1 nezvyšujeme, nemá to smysl. (Proč? Zvažte záměnu barev.) Z podobného důvodu nemá smysl barvit vrchol x barvou b > x.
Na počátku volíme omez := n +1, aby hodnota omez nebránila nalezení prvého obarvení.
Algoritmus:
1. [Inicializace.] x := 1; B(x) := 1; omez := n + 1.
2. [Postup vpřed - obarvení dalšího vrcholu.] Položíme x := x + 1. Jestliže x > n, pokračujeme podle kroku 3. V opačném případě položíme B{x) := minimum ze všech barev nevyskytujících se v množině P(x). Jestliže B(x) > omez, položíme y := x a pokračujeme podle kroku 4, jinak zopakujeme krok 2.
3. [Všechny vrcholy obarveny, počet barev je menší než omez.] Pro všechny vrcholy x grafu G provedeme Barva(:t) := B{x) a dále položíme omez := := maximum z hodnot barva. Označme y první vrchol, který má barvu omez, a pokračujme krokem 4.
4. [Návrat - pokus o snížení barvy ve vrcholu y.] Označme x poslední vrchol z množiny P(y) a pokračujme krokem 5.
5. [Pokračování návratu - pokus o zvýšení barvy ve vrcholu x] Jestliže x = 1, výpočet končí. V opačném případě položíme b := minimum ze všech barev, které jsou větší než B(x) a nevyskytují se v množině P(x). Pokud b < omez a zároveň b < x, položíme B{x) := b a pokračujeme podle kroku 2, v opačném případě položíme x := x — 1 a zopakujeme krok 5.
13.2.2 Příklad. Činnost algoritmu 13.2.1 předvedeme na grafu z obrázku 13.2. Postup výpočtu je patrný z následující tabulky, kde každý řádek zachycuje hodnoty B po vykonání kroku 4.
4 7 3
Obrázek 13.2: Graf k příkladu 13.2.2.
218
Kapitola 13. Barevnost, nezávislost, kliky
13.3.
1
7 8
9   10 11 12
1 1 1 1 1 1
1 1 1 1 1
Cffi
i i i
ď
2 2 2 dT
df2 j] df
3 3
[4] 4
(= obarvení 4 barvami)
JI
2   3 3
(= obarvení 3 barvami)
2 m
3
i i i i i i i
ď
Čtverečkem je zde vždy vyznačen vrchol y, v němž chceme snížit barvu. Návraty v backtrackingu jsou vyznačeny šipkami a prvý vrchol, v němž se po návratu zvýšila barva, je v kroužku.
Dodejme, že v tomto příkladě jsme zvolili očíslování vrcholů úmyslně trochu nešikovně, abychom na delším výpočtu mohli demonstrovat jeho postup. Kdybychom očíslovali vrcholy podle obrázku 13.3, proběhl by výpočet velmi rychle. Ověřte!
1
10 11 12
Obrázek 13.3: Jiné očíslování vrcholů k příkladu 13.2.2.
13.2.3 Poznámka. Rychlost algoritmu 13.2.1 velice záleží na očíslování vrcholů. Doporučuje se nejnižšími čísly očíslovat co největší kliku a vrcholy s velkým stupněm číslovat nižšími čísly. Také je vhodné, aby sousední vrcholy byly číslovány pokud možno sousedními čísly.
13.2.4 Cvičení. Vezměte kořenový strom, který má jeden list v hloubce 2 a ostatní listy v hloubce 1. Určitě víte, že barevnost každého stromu je rovna 2. Přesto tento strom obarvěte algoritmem 13.2.1. Při kterém uspořádání (očíslování) vrcholů proběhne výpočet nejrychleji a při kterém nejpomaleji?
13.2.5 Test fc-barevnosti. Potřebujeme-li pouze pro dané k zjistit, zda daný graf lze obarvit k barvami, lze algoritmus 13.2.1 zrychlit: při inicializaci položíme omez :=Hlav kroku 3, kde je nalezeno obarvení A; barvami, můžeme výpočet ukončit. Pokud výpočet skončí v kroku 5, pak obarvení k barvami neexistuje.
3.
13.3. Hledání maximálních nezávislých množin
219
13.2.6 Cvičení. Snažíme-li se jednoduchý backtracking urychlit podobně jako v algoritmu 13.2.1, je třeba pečlivě ověřit (dokázat), že urychlením nevynecháme optimální řešení.
Zjistěte, co je špatně na následujícím „vylepšení" algoritmu 13.2.1, a najděte příklad grafu, kde takto „vylepšený" postup selže:
Snažíme-li se snížit barvu vrcholu y a nelze-li barvu zvýšit u vrcholu x = max(P(y)), pak neprovedeme další návrat do vrcholu x — 1, ale rovnou až do druhého nej vyššího vrcholu z množiny P(y), neboť pouze vrcholy z množiny P(y) ovlivňují barvu vrcholu y.
13.2.7 Heuristické postupy. Algoritmus uvedený v důkaze věty 13.1.8 lze použít pro hrubý odhad barevnosti. Jeho výhodu je fakt, že při vhodném uspořádání vrcholů máme šanci získat přímo optimální obarvení. Doporučuje se volit pořadí vrcholů tak, aby vrcholy s velkým stupněm byly použity dříve. Další možností je opakovat výpočet s náhodně změněným pořadím vrcholů. Při dostatečném počtu opakování pak poměrně rychle roste i pravděpodobnost, že se strefíme do optimálního obarvení.
13.3   Hledání maximálních nezávislých množin
Uvedeme relativně rychlý algoritmus pro vyhledání všech maximálních nezávislých množin založený na backtrackingu. Po jednoduchých úpravách jej lze použít k hledání nejpočetnější nebo nejdražší nezávislé množiny.
13.3.1   Algoritmus pro hledání maximálních nezávislých množin.
Vstup:   Graf G zadaný pomocí seznamu vrcholů a seznamů sousedů V(x). výstup:   Posloupnost seznamů maximálních nezávislých množin. Pomocné proměnné:   v proměnné R budeme udržovat posloupnost vrcholů ri,r2,. ■ ■ ,rk, přičemž její prvky budou tvořit fc-prvkovou nezávislou množinu. Pro i < k označme Ri = {ri,r2, ■ ■. ,tí).
Dále budeme udržovat dva systémy množin vrcholů Ni a Si pro všechna i = = 0,1,..., k, přičemž bude platit:
1. Množiny Si, Ni a Ri jsou po dvou disjunktní.
2. (SíLíNí) = množina všech vrcholů v takových, že Ril){v} je nezávislá množina, tj. vrchol v by bylo možno přidat k Rt.
3. Ni = množina všech vrcholů, které dosud k množině Ri nebyly přidány, tj. žádná nezávislá množina obsahující Ri U {v} dosud nebyla zkoumána.
4. Si = množina všech vrcholů v, jejichž přidání k množině Ri již bylo vyzkoušeno, tj. všechny maximální nezávislé množiny obsahující Ri U {v} již byly prozkoumány.
220
Kapitola 13. Barevnost, nezávislost, kliky
METODA: Backtracking spočívá v systematickém prodlužování a zkracování posloupnosti i? a v odpovídající údržbě množin Si, Ni,
Máme-li posloupnost R o délce k, pak k jejímu prodloužení vybereme nějaký vrchol x € Nft- Množiny Nk a Sk uschováme, budeme je potřebovat později, až se posloupnost R opět zkrátí na délku k. Nyní však posloupnost R prodloužíme o vrchol x tím, že položíme r^+i := x, vytvoříme množiny N/.+1 a S^+i tak, aby splňovaly výše uvedené podmínky, a položíme k := k + 1.
Z podmínek 1-4 vyplývá, že posloupnost R obsahuje maximální nezávislou množinu právě tehdy, když N k = Sk — 0.
Nelze-li posloupnost R prodloužit, tj. je-li Nk = 0, provedeme v backtrackingu návrat, tj. posloupnost zkrátíme o její poslední prvek r*, položíme fc := k — 1 a upravíme množiny Nk a Sk-
Návrat provedeme také tehdy, existuje-li vrchol y £ Sk takový, že V(y)(~\Nk = 0. V této situaci je totiž jakékoli další prodlužování posloupnosti R zbytečné, protože každé nezávislé množině, která by R obsahovala, by k maximálnosti scházel vrchol y.
Algoritmus:
1. [Inicializace.] Položíme k := 0, Sq := 0 a No := V. Pokračujeme krokem 2.
2. [Rozšíření nezávislé množiny.] Vybereme libovolný vrchol x £ Nk a položíme rk+i := x, Sk+i := Sk \ V(x), Nk+l := Nk \ (V(x) U {x}) a k := k + 1. Pokračujeme krokem 3.
3. [Test maximálnosti množiny Rk] Jestliže Nk = Sk = 0, vytiskneme posloupnost R = {r\,T2,■.• ,Tk) a pokračujeme podle kroku 6, jinak pokračujeme krokem 4.
4. [Test možnosti zvětšování] Jestliže Nk — 0, pokračujeme podle kroku 6, jinak pokračujeme krokem 5.
5. [Test, lze-li Rk doplnit na maximální nezávislou množinu] Jestliže existuje vrchol y & Sk takový, že V{y) n = 0, pokračujeme podle kroku 6, jinak pokračujeme krokem 2.
6. [Návrat, zkrácení posloupnosti R] Jestliže k = 0, výpočet končí. V ostatních případech položíme x := r*, k := k — 1, Nk '■= Nk \ {x} a Sk := Sk U {x}. Pokračujeme krokem 4.
13.3.2 Poznámky. Při výpočtu na počítači lze systém množin Si, N a Ri uchovávat v jediné matici o n sloupcích, kde n je počet vrcholu. Pro i > 0 mohou být v i-tém řádku zakódovány všechny tři zmíněné množiny, neboť jsou disjunktní. Posloupnost R je vhodné udržovat zvlášť. Víme-li, že nezávislost grafu a(G) < K, pak stačí, aby matice měla pouze K řádků.
Jinou možností je reprezentovat množiny Si, Ni jako pole bitů a využít toho při provádění množinových operací.
Rychlost práce tohoto algoritmu lze podstatně ovlivnit strategií pro volbu vrcholu x v kroku 2.
13.3. Hledání maximálních nezávislých množin
221
13.3.3 Příklad. Pomocí algoritmu 13.3.1 vyhledejme všechny maximální nezávislé množiny v grafu z obr. 13.4.
6 5 4
o-—o-o
ó-o-ó
12 3
Obrázek 13.4: Graf k příkladu 13.3.3.
Průběh práce algoritmu je patrný z následující tabulky. Obsah množin Nk, Sk a .R* je vyznačen písmeny N, S a R. Znak — znamená, že příslušný vrchol nepatří do žádné z těchto množin. Situace, kdy Rk byla maximální nezávislá množina, jsou označeny hvězdičkou (*). Znak ^/ upozorňuje, že byl proveden návrat vyvolaný testem v kroku 5.
k	Rk	Nq, So, Ro		N2, S2,R2	N3,S3,	R3
		1 2 3 4 5 6	1 2 3 4 5 6	1 2 3 4 5 6	12 3 4	5 6
0	0	N N N N N N				
1	1		R - N N N -	1_		
2	13			R-R-N-		
3	135*				R — R —	R- 1*
2	13			R-R-S -		
1	1		R-SNN-	i		
2	14*			R--R--	*	
1	1		R-S S N-	!/		
0	0	S N N N N N				
1	2		— R - N N N	1		
2	24			-R-R-N		
3	246*				- R-R	-R 1*
2	24			-R-R-S		
1	2		- R - S N N	1_		
2	25*			-R--R-	*	
1	2		-R-S S N	w		
0	0	S S N N N N				
1	3		S - R - N N	j		
2	35			S - R - R -		
1	3		S - R - S N			
2	36*			--R--R	1 *	
1	3		S-R-S S	1		
0	0	S S S N N N				
13.3.4 Heuristicke postupy. Pro hledání nejpočetnějších nebo nejdražších nezávislých množin se používají také heuristické algoritmy, které bývají rychlejší, ale „bez záruky". Nejjednodušší je zvolit některý vrchol a k němu přidávat další tak dlouho, dokud nedostaneme maximální nezávislou množinu. Pravidlo pro volbu přidávaného vrcholu má zásadní vliv na kvalitu výsledného řešení. Volba může být i náhodná, ale doporučuje se preferovat vrcholy s malým stupněm nebo s velkou ce-
222
Kapitola 13. Barevnost, nezávislost, kliky
nou. Výpočet je vhodné několikrát opakovat s využitím náhody a nakonec si vybrat nej lepší z dosažených řešení.
Také lze použít metodu lokálního průzkumu (viz 11.4, str. 196) k postupnému vylepšování dosaženého řešení např. tak, že jeden vrchol z nezávislé množiny odstraníme a pokoušíme se místo něj zařadit jeden nebo i několik vrcholů jiných.
, kliky
223
si vybrat
ostupnému '.é množiny lů jiných.
Kapitola 14
Rovinné grafy
Rovinné grafy, tj. grafy, které lze nakreslit v rovině bez křížení hran, jsou důležité zejména v počítačové grafice, kde se využívá faktu, že struktura vrcholů a hran třírozměrných hranatých těles odpovídá rovinným grafům, a také v elektrotechnice při návrhu integrovaných obvodů a tištěných spojů. Další význam rovinných grafů vyplývá z jejich speciálních vlastností. Pro rovinné grafy lze například zjednodušit některé algoritmy (maximální tok v síti, prohledávání bludiště).
14.1   Nakreslení grafu a topologický rovinný graf
14.1.1 Nakreslení grafu. Formální definice říká, že nakreslení grafu G v rovině p je dvojice prostých zobrazení 4>, ip takových, že <j> přiřazuje vrcholům grafu různé body roviny p a zobrazení v1) přiřazuje každé hraně spojující např. vrcholy {x,y} jednoduchou křivku v rovině p s krajními body (j>{x) a <f>(y). Přitom požadujeme, aby žádná křivka, která je obrazem hrany, neobsahovala obraz žádného vrcholu jako svůj vnitřní bod.
Jednoduché křivky mohou mít rozličný tvar a mohou se vzájemně protínat, přičemž je nutno rozlišovat obrazy vrcholů od průsečíků křivek. Proto při praktickém kreslení znázorňujeme vrcholy pomocí kroužků, puntíků a podobně, abychom je odlišili od průsečíků.
Rovinné nakreslení je takové nakreslení, v němž libovolné dvě křivky, přiřazené různým hranám, mají společné nejvýše dva - a to své krajní - body. Graf, ke kterému existuje rovinné nakreslení, nazýváme rovinným grafem nebo také grafem planárním.
14.1.2 Topologický rovinný graf je rovinný graf chápaný společně se svým nakreslením. Formálně tedy topologický rovinný graf je šestice (V, E, e, p, <j),ij}),v níž (V, E, e) je graf a (<j>, ip) je jeho nakreslení v rovině p. Rovinný graf (bez přívlastku topologický) je formálně pouze graf (tj. trojice (V,E,e)), pro který existuje nějaké rovinné nakreslení.
224
Kapitola 14. Rovinné grafy
Vlastnosti rovinného grafu se netýkají konkrétního nakreslení, ale pouze jeho existence nebo dokonce jen možnosti nějaké rovinné nakreslení vytvořit. Vlastnosti topologického rovinného grafu zahrnují navíc všechny vlastnosti jeho konkrétního nakreslení.
Stěna topologického rovinného grafu je část roviny ohraničená křivkami, které jsou obrazy hran. Jedna ze stěn je vždy neomezená, ostatní jsou omezené. Dvě stěny nazýváme sousedními, jestliže společná část jejich hranice je tvořena jednou nebo několika křivkami, které jsou obrazy hran.
Řekneme, že stenaje incidentní s hranou, jestliže křivka, která je obrazem hrany, tvoří část hranice (nebo celou hranici) stěny. Stupeň stěny definujeme jako počet hran, s nimiž je stěna incidentní, přičemž každou hranu, která je mostem, počítáme dvakrát. Například v grafu na obr. 14.1 má stěna B stupeň 6 a stěna C stupeň 8. Dvě stěny jsou sousední, jsou-li obě incidentní s touž hranou.
Obrázek 14.1: Stěny topologického rovinného grafu.
14.1.3 Kreslení grafu na kouli, stereografická projekce. Definice nakreslení grafu uvedená v 14.1.1 může být snadno zobecněna i na jiné plochy než roviny. Kreslení grafu na povrch koule má těsný vztah ke kreslení v rovině: graf lze nakreslit bez křížení hran na povrch koule právě tehdy, když je rovinný.
Obrázek 14.2: Stereografická projekce.
Nakreslení na kouli a nakreslení v rovině lze vzájemně převádět mnoha způsoby, jedním z nich je tzv. stereografická projekce: Na povrchu koule zvolíme dva souměrně sdružené body S a J („severní a jižní pól") a zvolíme rovinu p, která se dotýká koule v bodě J (viz obr. 14.2). Nyní každému bodu x jí S z povrchu koule přiřadíme bod x' v rovině takto: body S a x vedeme přímku a ta protne rovinu p v bodě x'. Toto zobrazení je prosté a zobrazuje celý povrch koule kromě bodu 5 na celou rovinu, existuje tedy inverzní zobrazení. Obě tato zobrazení jsou spojitá, obrazem křivky je tedy opět křivka.
14.1. Nakreslení grafu a topologický rovinný graf
225
Převádíme-li nakreslení z koule na rovinu, musíme samozřejmě zvolit „severní pól" S tak, aby neležel v obraze žádné hrany nebo vrcholu.
Je-li graf nakreslen na povrchu koule tak, že se jeho hrany (přesněji křivky odpovídající hranám) nekříží, můžeme i zde definovat pojmy stěna, incidence stěny s hranou, stupeň stěny a sousední stěna. Na povrchu koule jsou všechny stěny omezené, stěně obsahující „severní pól" S odpovídá v rovinném nakreslení neomezená stěna.
Poznámka: Každý graf lze nakreslit na povrch nějakého tělesa tak, aby se obrazy hran nekřížily. Mnohdy k tomu však potřebujeme složité těleso s mnoha „dírami" nebo „uchy". Rovinné grafy jsou ty, které lze nakreslit bez křížení na tělesa bez „děr" a bez „uch", tj. na tělesa, která lze získat spojitou deformací z koule.
14.1.4 Silně ekvivalentní nakreslení. Je-li dáno rovinné nakreslení grafu G, pak je tím pro každý jeho vrchol v definováno cyklické uspořádání hran z množiny E(v), a to tak, že budeme kolem vrcholu v obíhat ve směru hodinových ručiček. Dvě rovinná nakreslení nazýváme silně ekvivalentní, určují-li obě stejná cyklická uspořádání hran.
Cyklická uspořádání hran i silnou ekvivalenci lze definovat také pro grafy nakreslené na povrch koule. Lze dokázat, že jsou-li dána dvě silně ekvivalentní nakreslení, lze jedno z druhého získat spojitou transformací.
Pomocí cyklických uspořádání hran lze snadno a úsporně reprezentovat v počítači to, co je na rovinném nakreslení z grafového hlediska podstatné.
14.1.5 Věta. Nechť A je libovolná stěna topologického rovinného grafu G. Pak existuje silně ekvivalentní nakreslení grafu G takové, že stěna odpovídající A je neomezená.
Důkaz: Graf G přeneseme stereografickou projekcí na povrch koule, pootočíme jej tak, aby „severní pól" S byl uvnitř požadované stěny a toto nakreslení promítneme zpět do roviny. □
Důkazy tří následujících vět lze najít v knize [Plesník83].
14.1.6 Věta. Ke každému rovinnému nakreslení prostého grafu bez smyček existuje silně ekvivalentní nakreslení takové, že každá hrana je reprezentována úsečkou.
14.1.7 Věta. Buď dán prostý topologický rovinný graf bez smyček s vrcholy Vi,...,vn. Dále nechť je v téže rovině dáno n různých bodů p\,..., pn. Pak existuje silně ekvivalentní rovinné nakreslení takové, v němž každý vrchol ví je nakreslen jako bod p;.
14.1.8 Věta. Každá dvě rovinná nakreslení vrcholově 3-souvislého grafu buďjsou silně ekvivalentní, nebo se takovými stanou zrcadlovým převrácením jednoho z nich.
226
Kapitola 14. Rovinné grafy
14.1.9 Mnohostěny. Vypuklé mnohostěny, tj. vypuklá1 tělesa, jejichž stěny jsou mnohoúhelníky, přirozeným způsobem určují graf: vrcholy mnohostěnu pokládáme za vrcholy grafu a hrany mnohostěnu pokládáme za hrany grafu. Ostatně, odtud pochází naše grafová terminologie.
Je zřejmé, že je-li mnohostěn vypuklý, je jeho graf rovinný.
Lze dokázat, že graf je grafem nějakého vypuklého mnohostěnu právě tehdy, když je rovinný a vrcholově 3-souvislý.
Pravidelný mnohostěn je takový mnohostěn, jehož všechny stěny jsou shodné mnohoúhelníky a všechny vrcholy mají stejný stupeň. Graf pravidelného mnohostěnu je regulární (vrcholy mají stejný stupeň) a navíc také všechny jeho stěny mají stejný stupeň. Pomocí tzv. Eulerovy formule (viz 14.3.1) lze dokázat, že existuje (až na izomorfismus) pouze pět grafů s těmito vlastnostmi, existuje tedy pouze pět pravidelných mnohostěnů. Tyto mnohostěny znali již staří Rekové, říká se jim také Platonova tělesa. Grafově teoretický důkaz, že je pouze pět Platonových těles, lze najít v knize [MN96], zde uvedeme pouze číselné charakteristiky Platonových těles:
počet			stupeň	
stěn	vrcholů	hran	vrcholu	stěny
4	4	6	3	3
6	8	12	3	4
8	6	12	4	3
12	20	30	3	5
20	12	30	5	3
Pravidelný dvanáctistěn je nakreslen na obr. 12.1, str. 197. Pravidelný šestistěn asi znáte pod názvem krychle.
14.2   Duální grafy
14.2.1 Dualita neorientovaných rovinných grafů. Mějme souvislý neorientovaný topologický rovinný graf G. Duální graf GD sestrojíme takto: Do každé stěny s grafu G umístíme jeden vrchol sD grafu GD. Pro každou hranu e grafu G sestrojíme hranu eD, která bude spojovat ty vrcholy grafu GD, které odpovídají stěnám grafu G incidentním s hranou e. Viz příklad na obr. 14.3. Platí:
1. Duální graf je také souvislý a rovinný.
2. Duální graf k duálnímu grafu je původní graf, tj. (GD)D = G.
3. Dualita převádí vrcholy grafu G na stěny grafu GD.
4. Smyčce v grafu G odpovídá most v grafu GD a naopak.
5. Kružnici v grafu G odpovídá v duálním grafu řez Wqd(A) určený množinou vrcholů A duálního grafu, přičemž vrcholy množiny A odpovídají stěnám grafu G ležícím uvnitř kružnice.
Ověřte si to alespoň nakreslením obrázku, lépe však úvahou.
'Těleso je vypuklé (též konvexní), jestliže s každými dvěma body obsahuje i celou úsečku, která tyto dva body spojuje.
24.2. Duální grafy
227
Obrázek 14.3: Duální graf ke grafu z obr. 14.1.
14.2.2 Cvičení. Nakreslete si rovinné grafy všech Platonových těles (viz 14.1.9) a sestrojte k nim grafy duální. Získáte tím opět grafy mnohostěnů - kterých?
14.2.3 Dualita orientovaných grafů. Duální graf k orientovanému souvislému topologickému grafu je definován stejně jako pro graf neorientovaný, navíc je však třeba určit orientaci hran. Orientaci hrany eD volíme tak, aby protínala hranu e zleva doprava. Jinými slovy, orientaci hrany eD získáme pootočením hrany e ve směru hodinových ručiček. Viz příklad na obr. 14.4.
Obrázek 14.4: Duální graf k orientovanému grafu.
Tvrzení uvedená v 14.2.1 platí analogicky pro orientované grafy s výjimkou tvrzení 2: Duální graf k duálnímu grafu GD není původní graf G, ale graf, který z něj dostaneme obrácením orientace všech hran.
Další vztahy mezi topologickým rovinným grafem a jeho duálním grafem jsou uvedeny v 15.3.7, str. 240.
228
Kapitola 14. Rovinné grafy
14
14.2.4 Minimální řez a nejkratší cesta. Uvažujme orientovaný topologický rovinný graf G, jehož hrany jsou ohodnoceny kapacitami a jehož dva vrcholy, zdroj z a spotřebič ,s, leží na obvodě neomezené stěny. Hledáním maximálního toku v takovéto transportní síti jsme se zabývali v 8.3.15, str. 145.
Vytvořme topologický rovinný graf G' přidáním návratové hrany e ze spotřebiče do zdroje a její kapacitu zvolme tak, aby nemohla omezit tok. Ke grafu G' vytvořme duální graf. Označme zD počáteční a sD koncový vrchol hrany eD v duálním grafu GD (viz obr. 14.5). Hrany duálního grafu ohodnoťme délkami, které jsou číselně rovny kapacitám hran grafu G'.
Obrázek 14.5: Duální graf ke grafu z příkladu 8.3.16, str. 145. Nejkratší cesta odpovídá řezu s minimální kapacitou.
Každé neorientované cestě v duálním grafu z vrcholu zD do vrcholu sD odpovídá v grafu G řez, který odděluje zdroj z a spotřebič s. Kapacita řezu je přitom rovna délce cesty, ve které počítáme jenom hrany vpřed. Hrany, kterými cesta prochází proti jejich orientaci, totiž odpovídají hranám, které se v původním grafu díky své orientaci do kapacity řezu nepočítají.
V neorientované rovinné transportní síti je situace jednodušší. Maximální tok nasycuje vždy všechny hrany minimálního řezu, a proto je minimální kapacita řezu rovna délce nejkratší cesty v duálním grafu.
Je třeba upozornit, že v obou případech (orientovaném i neorientovaném) v grafu mohou existovat i řezy, které neodpovídají žádné cestě z vrcholu zD do vrcholu sD. Jsou to řezy W(A) určené množinou vrcholů A takovou, že podgraf indukovaný touto množinou není souvislý. Snadno však lze nahlédnout, že žádný takový řez není minimální, neboť komponenta obsahující zdroj z určuje řez s menší kapacitou. Je-li řez určen množinou A takovou, že z G A a podgraf indukovaný množinou A je souvislý, pak hrany řezu W(^4) tvoří v duálním grafu cestu z vrcholu zD do vrcholu sD. Tato cesta vede po hranici souvislé oblasti tvořené těmi stěnami duálního grafu, které odpovídají množině A.
14.3. Vlastnosti rovinných grafů
229
14.3   Vlastnosti rovinných grafů
14.3.1 Věta (Eulerova formule). Pro každý souvislý topologický rovinný graf, který má n vrcholu, m hran a s stěn, platí n + s = m + 2.
důkaz: Graf G můžeme získat z jeho kostry postupným přidáváním hran, které v kostře neleží. Kostra topologického rovinného grafu má jedinou stěnu a počet hran je m = n — 1, proto pro kostru Eulerova formule platí. Přidáním hrany k topologickému rovinnému grafu rozdělíme vždy některou jeho stěnu na dvě. Levá i pravá strana Eulerovy formule se tedy přidáním hrany zvětší o jedničku. Po přidání všech hran tedy dostaneme Eulerovu formuli pro původní daný graf. □
14.3.2 Cvičení. Dokažte zobecnění Eulerovy formule pro nesouvislé grafy: Pro topologický rovinný graf s n vrcholy, m hranami, s stěnami a k komponentami souvislosti platí n + s = m + k+l.
Následující tři věty zaručují, že prosté rovinné grafy bez smyček nemají „příliš mnoho" hran, jsou tedy řídké.
14.3.3 Věta. Pro prostý souvislý rovinný neorientovaný graf bez smyček, který má n > 3 vrcholů a rn hran, platí rn < 3n — 6.
Důkaz: Poněvadž graf je prostý a bez smyček, má každá stěna (včetně stěny neomezené) stupeň alespoň 3. Součet stupňů všech stěn je roven 2m, neboť v něm každou hranu počítáme dvakrát. Počet stěn s tedy splňuje s < 2m/3. Dosadíme-li to do Eulerovy formule, dostaneme n + 2m/3 > m + 2, a tedy m < 3n — 6. □
14.3.4 Věta. Pro prostý souvislý rovinný neorientovaný graf bez smyček a bez trojúhelníků, který má n > 3 vrcholů a m hran, platí m < 2n — 4.
důkaz: Stupeň každé stěny grafu je větší nebo roven 4. Součet stupňů všech stěn je roven 2m, počet stěn s tedy splňuje s < 2m/4 = m/2. Dosadíme-li to do Eulerovy formule, dostaneme n + m/2 > m + 2, a tedy m < 2n — 4. □
14.3.5 Věta. V každém prostém rovinném neorientovaném grafu bez smyček existuje vrchol, jehož stupeň je menší nebo roven 5.
důkaz: Kdyby každý vrchol měl stupeň 6 nebo více, měl by celý graf alespoň 3n hran (je-li n počet vrcholů), což by bylo v rozporu s větou 14.3.3. □
14.3.6 Cvičení. Pomocí vět 14.3.3 a 14.3.4 dokažte, že grafy Ks a #3,3 nejsou rovinné.
14.3.7 Věta o čtyřech barvách. Rovinný graf bez smyček lze obarvit čtyřmi barvami.
Poznámka:   Viz komentář k větě 13.1.13, str. 215.
230
Kapitola 14. Rovinné grafy
14.4   Charakterizace rovinných grafů
14.4.1 Homeomorfní grafy. Dva grafy Gi,(t2 nazýváme vzájemně homeo-morfními, jestliže lze jeden získat z druhého těmito operacemi:
Dělení hrany. Mějme hranu e s krajními vrcholy x, y. Hranu e odstraníme a místo ní přidáme nový vrchol v a dvě nové hrany spojující nový vrchol v s vrcholy x a, y.
Odstranění vrcholu stupně 2 je opačná operace: vrchol stupně 2 odstraníme spolu s oběma hranami a nahradíme hranou, která spojí bývalé sousedy odstraněného vrcholu.
Obě operace „zachovávají rovinnost" v tom smyslu, že byl-li graf rovinný před operací, bude rovinný i po ní a naopak. Jsou-li tedy dva grafy homeomorfní, pak jsou buď oba rovinné, anebo oba nerovinné.
Obrázek 14.6: Grafy homeomorfní s grafy Ks a ^3,3.
14.4.2 Kuratowského věta. Graf je rovinný právě tehdy, když neobsahuje podgraf homeomorfní s grafem K5 nebo #3,3.
důkaz   není jednoduchý, lze jej najít např. v [Berge58], □
Poznámka: Pomocí Kuratowského věty lze např. o daném grafu dokázat, že není rovinný. Pro praktické zjišťování, zda daný graf je rovinný, to však není vhodný způsob, protože vyhledávání podgrafů je dost obtížné. Hlavní význam Kuratowského věty spočívá v tom, že rovinné grafy charakterizuje pomocí čistě grafových pojmů. Uvědomte si, že pojem rovinného nakreslení není čistě grafovým pojmem, potřebujeme k němu pojem roviny, spojitého zobrazení, křivky apod.
14.4.3 Cvičení. Pomocí Kuratowského věty dokažte, že tzv. Petersenův graf nakreslený vlevo na obr. 1.2, str. 18, není rovinným grafem.
14.4.4 Algoritmy pro testování rovinnosti. Kuratowského věta nedává dobrý návod k testování rovinnosti. Existují však rychlé algoritmy, které v čase 0(n) nejen rozhodnou, zda graf je rovinný, ale rovinné nakreslení zakódované pomocí cyklických uspořádání hran (viz 14.1.4) dokonce sestrojí. Vzhledem ke značné komplikovanosti se jimi nebudeme zabývat, jejich stručný popis lze najít např. v [Kučera83, Plesník83]. Poznamenejme pouze, že tyto algoritmy postupně přidávají kusy grafu ke vhodně zvolené kružnici a rozhodují, zda příslušná část grafu bude nakreslena uvnitř nebo vně kružnice.
231
Kapitola 15
Cirkulace a potenciály
Tato kapitola je věnována algebraickým vlastnostem cirkulací, potenciálových rozdílů, kružnic a řezů. Tyto vlastnosti jsou důležité zejména v elektrotechnice při analýze elektrických obvodů.
Ke studiu této kapitoly je potřebná alespoň základní znalost lineární algebry, zejména vektorových prostorů.
Poznamenejme, že následující výklad je možno dále zobecnit na vektorové prostory nad obecnými tělesy včetně těles konečných, takže pak lze mluvit např. o vektorovém prostoru kružnic v grafu apod. My se však omezíme na vektorové prostory nad tělesem reálných čísel.
V celé kapitole budeme předpokládat, že hrany grafu jsou pevně očíslovány čísly l,2,...,m.
15.1   Vektorový prostor cirkulací
Pojem cirkulace jsme definovali v 8.1.1, str. 129, některé vlastnosti cirkulací jsou uvedeny v 8.5, str. 149. Zde nahlédneme o něco hlouběji do algebraického zákulisí toků v síti. Na rozdíl od kapitoly 8 se zde nebudeme zabývat omezeními toku (kapacitami) a nebudeme rozlišovat toky přípustné a nepřípustné.
Díky pevnému očíslování hran čísly 1,2,... ,m můžeme každou cirkulaci pokládat za m-členný aritmetický vektor.
15.1.1 Věta. Množina všech cirkulací v grafu G tvoří vektorový prostor, který je podprostorem prostoru Rm, kde m = \E(G)\.
důkaz vyplývá z faktu, že součet cirkulací i násobek cirkulace číslem je opět cirkulace (splňuje Kirchhoffův zákon). □
15.1.2 Kružnice a cirkulace. Připomeňme, že v 8.3.3, str. 140, jsme hrany libovolné kružnice rozdělili na hrany vpřed a hrany vzad, a to podle vztahu orientace hrany ke směru průchodu kružnicí.
232
Kapitola 15. Cirkulace a potenciály
Každé kružnici můžeme přiřadit tzv. elementární cirkulaci f předpisem:
{O,   jestliže e neleží na kružnici, 1,   je-li e hranou vpřed, — 1,   je-li e hranou vzad.
15.1.3 Fundamentální soustava kružnic. Uvažujme graf G a nějaký jeho napnutý les K (viz 4.2.4, str. 58).
Ke každé hraně e £ E(G) \ E{K) existuje podle věty 4.2.9 přesně jedna kružnice ke tvořená hranou e a (některými) hranami lesa K. Tuto kružnici budeme orientovat tak, aby hrana e byla hranou vpřed. Každou takovou kružnici nazveme fundamentální kružnicí a množinu všech fundamentálních kružnic nazveme fundamentální soustavou kružnic vůči napnutému lesu K.
Každá fundamentální kružnice ke určuje elementární cirkulaci fe, která má v hraně e jednotkovou velikost. Takovou elementární cirkulaci nazýváme fundamentální cirkulací.
Fundamentální matice kružnic je matice, jejíž řádky jsou tvořeny všemi fundamentálními cirkulacemi chápanými jako řádkové vektory.
5 8 11
Obrázek 15.1: Fundamentální soustava kružnic.
15.1.4 Příklad. Graf na obr. 15.1 má dvě komponenty souvislosti. Napnutý les K je vyznačen silnými čarami. Tento les určuje (jednoznačně) fundamentální soustavu kružnic a fundamentální matici kružnic:
		ei	e-í	Ě3	£■1	C5	ee	C-7	es	eg	eio	en	ei2	1-13	ei4	
h	í	1	1	1	0	0	0	0	0	0	0	0	0	0	0	\
		0	0	0	1	-1	1	-1	0	0	0	0	0	0	0	
kg		0	0	0	0	0	0	1	1	1	-1	0	0	0	0	
ku		0	0	0	0	0	0	0	0	0	-1	1	-1	1	0	
ku	V	0	0	0	-1	1	0	0	-1	0	1	0	1	0	1	/
Řádky této matice tvoří bázi vektorového prostoru cirkulací, což vyplývá z následující věty.
15.1. Vektorový prostor cirkulací
233
15.1.5 Věta. V grafu G zvolme libovolný napnutý les K. Potom množina všech fundamentálních cirkulací vzhledem k lesu K tvoří bázi vektorového prostoru cirkulací.
důkaz: Je třeba dokázat, že fundamentální cirkulace jsou lineárně nezávislé a že generují celý vektorový prostor cirkulací.
Nezávislost vyplývá z faktu, že každá hrana e 6 E{G) \ E{K) je obsažena pouze v jediné fundamentální kružnici, totiž v ke, a proto pouze jediná fundamentální cirkulace, totiž fe, je na této hraně nenulová. Má-li tedy být nulová cirkulace (tj. nulový vektor) lineární kombinací fundamentálních cirkulací, musí být všechny koeficienty této lineární kombinace rovny nule. Tím je dokázána nezávislost.
Uvažujme nyní libovolnou cirkulaci / v grafu G. Ukážeme, že / je lineární kombinací fundamentálních cirkulací. Vezměme postupně všechny hrany e £ E(G)\ \ E(K) a od cirkulace / odečtěme vždy /(e)-násobek fundamentální cirkulace fe. Je zřejmé, že tím vynulujeme cirkulaci na všech hranách z množiny E(G) \ E(k). Protože však zbývající hrany neobsahují žádnou kružnici (jde o hrany lesa K), musí být výsledná cirkulace nulová i na nich. Z této úvahy plyne, že pro libovolně zvolenou cirkulaci / platí
e.EE(G)\B(K)
a tedy / je lineární kombinací fundamentálních cirkulací. □
15.1.6 Věta. V grafu o n vrcholech, m hranách a k komponentách souvislosti je dimenze vektorového prostoru cirkulací rovna m — n + k.
důkaz: Dimenze je rovna počtu prvků báze, tedy podle předchozí věty počtu fundamentálních cirkulací, tj. počtu všech hran mimo napnutý les. Podle věty 4.2.8 má každý napnutý les n — k hran. Počet hran mimo napnutý les (a tedy i dimenze vektorového prostoru cirkulací) je tedy m — n + k. □
15.1.7 Cyklomatické číslo. Dimenzi vektorového prostoru cirkulací nazýváme cyklomatickým číslem grafu.
15.1.8 Poznámka. Vektorový prostor cirkulací má i jiné báze než fundamentální cirkulace určené nějakým napnutým lesem. V topologických rovinných grafech lze například získat bázi prostoru cirkulací ze soustavy kružnic určených omezenými stěnami. Ověřte na příkladě. Viz též následující cvičení.
15.1.9 Cvičení. Vezměte topologický rovinný graf z obrázku 1.1, str. 18 uprostřed, a zvolte jeho libovolnou orientaci. Ověřte, že čtyři elementární cirkulace určené kružnicemi kolem omezených stěn tvoří bázi prostoru cirkulací. Ověřte také, že tato báze není fundamentální bází vzhledem k žádnému napnutému lesu (tj. kostře) daného grafu.
234
Kapitola 15. Cirkulace a potenciály
15.2   Potenciály a potenciálové rozdíly
15.2.1 Potenciál a potenciálový rozdíl. Buď dán orientovaný graf G. Potenciálem nazveme jakékoli ohodnocení vrcholů p : V{G) —> R grafu G reálnými čísly.
Ohodnocení hran ir : E(G) -4 K reálnými čísly nazýváme potenciálovým rozdílem, jestliže existuje potenciál p takový, že pro každou hranu e grafu platí:
(15.1) 7r(e)=p(Kv(e))-p(Pv(e)).
Všimněte si, že potenciálový rozdíl n se nezmění, zvýšíme-li potenciál p o stejnou konstantu ve všech vrcholech některé souvislé komponenty.
Zdaleka ne každé ohodnocení hran je potenciálovým rozdílem. Najděte příklad! Návod, jak ověřit, zda dané ohodnocení je potenciálovým rozdílem, podáme v následující větě 15.2.2, úspornější verzi pak ve větě 15.3.4.
Dále poznamenejme, že máme-li pevně zvoleno očíslování hran čísly 1,2,..., m, pak každý potenciálový rozdíl můžeme pokládat za m-členný aritmetický vektor.
15.2.2 Věta. Pro libovolnou kružnici k označme C~£ množinu hran vpřed a C^ množinu hran vzad. Ohodnocení hran n je potenciálovým rozdílem právě tehdy, když pro každou kružnici k v grafu platí:
(15.2) £ Tr(e) - £ 7r(e) = 0 .
Poznámka: Podmínka (15.2) je analogií druhého Kirchhoffova zákona (součet napětí podél obvodu je roven nule). Ve větě 15.3.4 ukážeme, že podmínku (15.2) stačí ověřit pro fundamentální soustavu kružnic.
důkaz: Nechť tt je potenciálový rozdíl a p je příslušný potenciál. Vezměme libovolnou kružnici, tj. posloupnost vrcholů a hran
v0,ei,vi,e2,v2, ■ ■ ■ ,ek,vk,
kde Vk = vq. Pro každou její hranu platí:
p{v{) — p(vi-i) =   7r(ei),   je-li    hranou vpřed, a p(vi) — p(ví-i) = — 7r(e;),   je-li e; hranou vzad.
Sečtením těchto rovnic pro všechny hrany kružnice dostaneme platnost podmínky (15.2):
e€C+ e€C- i=1
Nechť nyní naopak 7r je ohodnocení hran, které splňuje podmínku (15.2) pro každou kružnici k. Popíšeme postup, který vede k nalezení potenciálu p splňujícího podmínku (15.1).
15.2. Potenciály a potenciálové rozdíly
235
V každé souvislé komponentě zvolíme libovolný vrchol v a ohodnotíme jej libovolným potenciálem p(v). Dalším vrcholům v komponentách vypočteme jejich potenciály postupem, který připomíná značkovací proceduru: Existuje-li hrana e taková, že Pv(e) je ohodnocen a Kv(e) nikoli, položíme
p(Kv(e)) := p(Pv(e)) + 7r(e) .
Je-li naopak hrana e taková, že Kv(e) je ohodnocen a Pv(e) není, položíme
p(Pv(e)) := p(Kv(e)) - jr(e) .
Platnost podmínky (15.2) pro všechny kružnice zaručuje, že každá hrana, jejíž oba vrcholy jsou již ohodnoceny, splňuje podmínku (15.1). □
15.2.3 Věta. Množina všech potenciálových rozdílů v grafu G tvoří vektorový prostor, který je podprostorem prostoru Km, kde m je počet hran.
Důkaz: Vezměme dva libovolné potenciálové rozdíly 7Ti,7r2. K nim existují potenciály pi,P2 takové, že pro každou hranu e platí:
xx[e) = Pl(Kv(e))-Pl(Pv(e)), ?T2(e)   =   p2(Kv(e))-p2(Pv(e)) .
Součet potenciálů p\ + P2 je samozřejmě také potenciál, a poněvadž
Tri (e) + 7r2(e) =pi(Kv(e)) + p2(Kv(e)) -pi(Pv(e)) -p2(Pv(e)) ,
je součet potenciálových rozdílů 7Ti +7r2 také potenciálovým rozdílem. Podobně násobek potenciálu je potenciál, a tedy i násobek potenciálového rozdílu je potenciálový rozdíl. □
15.2.4 Rezy a potenciálové rozdíly. Každému řezu Wq(A) v orientovaném grafu G můžeme přiřadit potenciál p definovaný předpisem
p(v) =
0 pro v £ A,
1 pro v & A.
Odpovídající potenciálový rozdíl tt nazýváme elementárním potenciálovým rozdílem. Platí:
(    1   pro e G W+(Ä), 7r(e) = <  -1   pro e £ W~(A), {    0   pro e i W{A).
Připomeňme, že zvláštním případem řezu je okolí E (v) vrcholu v.
236
Kapitola 15. Cirkulace a potenciály
15.2.5   Fundamentální soustava řezů. Mějme graf G a jeho napnutý les K.
Odstraněním libovolné hrany e S E(K) se podle věty 4.2.9 rozpadne některá komponenta lesa K (tj. strom) na dvě komponenty. Označme A tu z nich, která obsahuje počáteční vrchol hrany e, druhou z nich označme B. Fundamentální řez re určený hranou e lesa K nyní definujeme jako řez Wq(A).
Množinu všech fundamentálních řezů vůči napnutému lesu K nazýváme fundamentální soustavou řezů.
Fundamentální potenciálový rozdíl 7re určený hranou e napnutého lesa definujeme jako elementární potenciálový rozdíl, určený fundamentálním řezem re. Platí tedy 7re(e) = 1 a potenciál pe, který tomuto potenciálovému rozdílu odpovídá, splňuje pe (A) = 0 a pe (B) = 1, kde A, B jsou komponenty lesa K oddělované hranou e.
Fundamentální matice řezů je matice, jejíž řádky jsou tvořeny všemi fundamentálními potenciálovými rozdíly, chápanými jako řádkové vektory.
n!   Ira H'      *"s 1 fs'   '• rio        ?"i2 1 n3
Obrázek 15.2: Fundamentální soustava řezů.
15.2.6 Příklad. Fundamentální soustava řezů v grafu z obrázku 15.1 vzhledem k témuž napnutému lesu K je na obrázku 15.2 znázorněna čárkovaně. Fundamentální matice řezů má tvar
		ei	Ě2	Ě3	e4	es	eg	e-7	es	eg	eio	en	ei2	ei3	ei4	
n	(	1	0	-1	0	0	0	0	0	0	0	0	0	0	0	\
r-i		0	1	-1	0	0	0	0	0	0	0	0	0	0	0	
		0	0	0	1	0	-1	0	0	0	0	0	0	0	1	
rs		0	0	0	0	1	1	0	0	0	0	0	0	0	-1	
ri		0	0	0	0	0	1	1	0	-1	0	0	0	0	0	
rs		0	0	0	0	0	0	0	1	-1	0	0	0	0	1	
rio		0	0	0	0	0	0	0	0	1	1	1	0	0	-1	
ri2		0	0	0	0	0	0	0	0	0	0	1	1	0	-1	
ri3	\	0	0	0	0	0	0	0	0	0	0	-1	0	1	0	/
Řádky této matice tvoří bázi vektorového prostoru potenciálových rozdílů, což vyplývá z následující věty.
15.2. Potenciály a potenciálové rozdíly
237
15.2.7 Věta. V grafu G zvolme libovolný napnutý les K. Potom množina všech fundamentálních potenciálových rozdílů vzhledem k lesu K tvoří bázi vektorového prostoru potenciálových rozdílů.
Důkaz je podobný důkazu věty 15.1.5 pro cirkulace. Nezávislost fundamentálních potenciálových rozdílů vyplývá z faktu, že každá hrana e G E(K) je obsažena pouze v jediném fundamentálním řezu.
Vezměme nyní libovolný potenciálový rozdíl ir. Ukážeme, že 7r je lineární kombinací fundamentálních potenciálových rozdílů. Uvažujme postupně všechny hrany e G E(K) a od potenciálového rozdílu 7r odečtěme vždy 7r(e)-násobek fundamentálního potenciálového rozdílu ne. Je zřejmé, že tím získáme potenciálový rozdíl
7r' = 7T -    ]T    7T(e) • 7Te ,
který je nulový na všech hranách lesa K. Odpovídající potenciál tedy nabývá týchž hodnot vždy na celé souvislé komponentě grafu G, proto je potenciálový rozdíl n' nulový na všech hranách grafu (hrany vedou jen mezi vrcholy téže komponenty). Tím je dokázáno, že
eEB(K)
je lineární kombinací fundamentálních potenciálových rozdílů. □
15.2.8 Věta. V grafu o n vrcholech a k komponentách souvislosti je dimenze vektorového prostoru potenciálových rozdílů rovna n — k.
Důkaz: Dimenze je rovna počtu prvků báze, tedy podle předchozí věty počtu fundamentálních potenciálových rozdílů, tj. počtu hran napnutého lesa, který podle věty 4.2.8 má přesně n - k hran. □
15.2.9 Poznámka. Vektorový prostor potenciálových rozdílů má i jiné báze než fundamentální soustavy určené nějakým napnutým lesem. Důležité jsou zejména báze tvořené z řezů tvaru E(x), neboť příslušné elementární potenciálové rozdíly jsou shodné s řádky incidenční matice.
15.2.10 Věta. Vektorový prostor potenciálových rozdílů grafu G je generován množinou elementárních potenciálových rozdílů určených řezy tvaru E(x), kde x je vrchol grafu G.
důsledek: Vektorový prostor potenciálových rozdílů je generován řádky incidenční matice. Z řádků incidenční matice tedy lze vybrat bázi vektorového prostoru potenciálových rozdílů.
Důkaz: Dokážeme, že z elementárních potenciálových rozdílů určených okolími vrcholů, tj. řezy ve tvaru E(x), lze získat jako lineární kombinaci libovolný elementární potenciálový rozdíl. Z toho pak již snadno plyne, že lze vygenerovat i jakoukoli fundamentální soustavu potenciálových rozdílů a ta již podle 15.2.7 generuje celý prostor.
238
Kapitola 15. Cirkulace a potenciály
Vezměme libovolný řez PF(yl) a jím určený potenciálový rozdíl tt. Označme irx elementární potenciálový rozdíl určený okolím E(x) libovolného vrcholu x € A. Ukážeme, že pro všechny hrany grafu platí:
(15.3) ff(e) = 2%,(e).
Pro hrany z řezu W7^) tato rovnost vyplývá z faktu, že hrana e je obsažena pouze v jedné z množin E(x) a příslušný sčítanec má správné znaménko. Má-li hrana e oba vrcholy v množině A, je obsažena ve dvou množinách hran £(Pv(e)) a íľ(Kv(e)), přičemž na hraně e mají příslušné sčítance opačná znaménka, a součet je tedy nulový Hrany, jejichž oba vrcholy leží mimo množinu A, neleží v žádném z uvažovaných okolí, a proto je na nich součet také nulový. Platí tedy:
x£Á
Potenciálový rozdíl n tedy je lineární kombinací elementárních potenciálových rozdílů, které jsou určeny okolími E{x) vrcholů x £ A. □
15.2.11 Hodnost grafu. Dimenze vektorového prostoru potenciálových rozdílů je rovna hodnosti incidenční matice grafu. Tuto dimenzi nazýváme též hodností grafu.
15.3   Vztahy cirkulací a potenciálových rozdílů
15.3.1 Skalární součin a kolmost vektorů. Dva vektory u,v 6 Km jsou kolmé, je-li jejich skalární součin roven nule. Jsou-li P a P' dva podprostory téhož prostoru Km a je-li každý vektor z P kolmý na každý vektor z P', pak prostory P a P' nazýváme vzájemně kolmými. Z vlastností skalárního součinu snadno plyne toto tvrzení:
Je-li každý vektor z množiny generátorů prostoru P kolmý na každý vektor z množiny generátorů prostoru P', pak prostory P a P' jsou vzájemně kolmé.
15.3.2 Věta. Vektorový prostor cirkulací a vektorový prostor potenciálových rozdílů jsou vzájemně kolmé.
důkaz: Stačí dokázat, že libovolná fundamentální cirkulace je kolmá na libovolný fundamentální potenciálový rozdíl vůči témuž napnutému lesu. To je však snadné: Stačí si uvědomit, že libovolná fundamentální kružnice a libovolný fundamentální řez buď nemají žádnou společnou hranu, nebo mají přesně dvě společné hrany. Tyto dvě hrany buď jsou stejně orientovány vůči kružnici (obě vpřed nebo obě vzad) a rozdílně vůči řezu (jedna dovnitř druhá ven), nebo jsou rozdílně orientovány vzhledem ke kružnici a stejně vůči řezu. Ve všech těchto případech mají ve skalárním součinu činitelé odpovídající těmto hranám opačná znaménka a vzájemně se ruší. Skalární součin fundamentální cirkulace a fundamentálního potenciálového rozdílu je tedy nulový. □
15.3. Vztahy cirkulací a potenciálových rozdílů
239
15.3.3 Lemma. Mějme kružnici k a jí odpovídající elementární cirkulaci /. Potom ohodnocení hran ir splňuje podmínku (15.2) (druhý Kirchhoffův zákon) právě tehdy, když vektory 7r a / jsou kolmé.
Důkaz vyplývá bezprostředně z definice elementární cirkulace a skalárního součinu. □
15.3.4 Věta. Buď G orientovaný graf a n ohodnocení jeho hran. Potom následující podmínky jsou ekvivalentní:
1. tt je potenciálový rozdíl.
2. Podmínka (15.2) (druhý Kirchhoffův zákon) platí pro každou kružnici.
3. Podmínka (15.2) platí pro každou fundamentální kružnici.
4. Vektor 7r je kolmý na každou fundamentální cirkulaci vzhledem k nějakému napnutému lesu K.
5. Vektor ir je kolmý na každou cirkulaci / v grafu G.
Důkaz: 1 o 2 vyplývá z věty 15.2.2; 2 =$> 3 platí triviálně; 3 4 vyplývá z lemmatu 15.3.3; 4 => 5 vyplývá z vlastností vektorových prostorů; 5 => 2 vyplývá opět z lemmatu 15.3.3. □
15.3.5 Lemma. Mějme řez W(A) a jemu odpovídající elementární potenciálový rozdíl 7T. Potom ohodnocení hran / splňuje podmínku
(i5.4) £ m-      /(e) = °
e€W+(A) eíW-(A)
právě tehdy, když vektory / a ir jsou kolmé.
Důkaz   plyne bezprostředně z definice elementárního potenciálového rozdílu. □
15.3.6 Věta. Buď G orientovaný graf a / ohodnocení jeho hran. Potom následující podmínky jsou ekvivalentní:
1. / je cirkulace.
2. Podmínka (15.4) platí pro každý řez.
3. Podmínka (15.4) platí pro každý fundamentální řez.
4. Vektor / je kolmý na každý fundamentální potenciálový rozdíl vzhledem k nějakému napnutému lesu K.
5. Vektor / je kolmý na každý potenciálový rozdíl.
důkaz: 1 <=> 2 je zřejmé z definice cirkulace a řezu; 2 =>• 3 platí triviálně; 3 => 4 vyplývá z lemmatu 15.3.5; 4 => 5 vyplývá z vlastností vektorových prostorů; 5 => 2 opět vyplývá z lemmatu 15.3.5. □
240
Kapitola 15. Cirkulace a potenciály
15.3.7 Cirkulace a potenciálové rozdíly v rovinných grafech mají další zajímavé vlastnosti. Uvažujme orientovaný topologický rovinný graf G a k němu duální graf GD (viz 14.2.3, str. 227). Každou cirkulaci v grafu G můžeme pokládat za potenciálový rozdíl v GD, a také naopak každý potenciálový rozdíl v G můžeme pokládat za cirkulaci v GD. (Ověřte na příkladě!) Z toho také plyne, že cyklomatické číslo grafu G je rovno hodnosti grafu GD, a naopak hodnost grafu G je rovna cyklomatickému číslu grafu GD.
15.4   Analýza elektrické sítě
V tomto oddíle naznačíme, jak lze vlastnosti vektorových prostorů cirkulací a potenciálových rozdílů použít při analýze elektrické sítě složené ze zdrojů stejnosměrného napětí a z rezistorů. Podrobnější výklad týkající se obecnějších obvodů by přesahoval rámec této knížky, zájemce odkazujeme na knihy [SwTh81, KŠCh89] a na speciální elektrotechnickou literaturu .
15.4.1 Kirchhoffovy zákony. Uvažujme elektrickou síť složenou z rezistorů a ze zdrojů napětí. Síť snadno znázorníme orientovaným grafem. Orientaci hran můžeme zvolit libovolně. Vrcholy grafu odpovídají uzlům elektrické sítě (vodičům), hrany odpovídají větvím. V každé větvi může být jeden nebo několik zdrojů napětí a jeden nebo několik rezistorů. Každou větev e ovšem můžeme zjednodušit tak, že obsahuje vždy jeden zdroj napětí ee (může mít i nulovou velikost) a jeden rezistor o odporu Re: pro tento účel ve větvi sečteme napětí všech zdrojů a podobně sečteme odpory všech rezistorů a vnitřní odpory všech zdrojů.
Proud protékající větví e označíme Ie> napětí Ue na této větvi je součtem napětí zdroje ee a úbytku napětí na rezistorů, který podle Ohmová zákona je roven ReIe. Platí tedy Ue = ee — ReIe-
Proudy a napětí v síti musí splňovat 1. a 2. Kirchhoffův zákon. Jinými slovy, ohodnocení hran Ifí musí být cirkulací ve smyslu definice 8.1.1, str. 129, a ohodnocení hran Ue musí pro každý obvod (tj. kružnici) splňovat podmínku (15.2), a tedy podle věty 15.2.2 musí být potenciálovým rozdílem.
Všechny tyto podmínky můžeme snadno vyjádřit pomocí soustavy lineárních rovnic, v nich jako neznámé vystupují proudy v jednotlivých hranách Ie. U podmínek z 1. Kirchhoffova zákona to je zcela přímočaré. Pro podmínky plynoucí z 2. Kirchhoffova zákona vyjádříme napětí Ue pomocí vztahu Ue = se — ReIe, v němž ee pokládáme za konstantu a převedeme ji na pravou stranu. Typická rovnice pro některou kružnici tedy má tvar
Rih + Rzh + ■ ■ ■ = Gi + £2 + - • •
Soustava rovnic pro všechny vrcholy a všechny kružnice má ovšem zbytečně mnoho rovnic a je lineárně závislá. Pro řešení soustavy je výhodné, aby rovnice byly lineárně nezávislé. Toho lze docílit takto:
Zvolíme kostru grafu (předpokládáme, že síť je souvislá) a vzhledem k této kostře nalezneme fundamentální soustavu řezů a fundamentální soustavu kružnic. Rovnice
ť .-, potenciály
15.4. Analýza elektrické sítě
241
ch mají další 'G a k němu • pokládat . "■' G můžeme vklomatické i G je rovna
relací a poten-ř.Tiosměrného xiů by přesa-vSCh89] a na
rízistorů a ze ..: in můžeme Lřům), hrany napětí a jeden k. že obsahuje sror o odporu č:eme odpory
mčtem napětí roven ReIe.
Jinými slovy, :nodnocení a tedy podle
py lineárních -\-. U pod-lynoucí z 2.
v němž rovnice pro
"ně mnoho fly lineárně
této kostře ic. Rovnice
pro proudy (1. Kirchhoffův zákon) sestavíme pouze pro fundamentální řezy, rovnice pro napětí (2. Kirchhoffův zákon) sestavíme pouze pro fundamentální kružnice. Z vět 15.3.4 a 15.3.6 vyplývá, že platí-li oba Kirchhoffovy zákony pro fundamentální řezy a fundamentální kružnice, platí oba v plném rozsahu, tj. pro všechny řezy i pro všechny kružnice (obvody).
Podle vět 15.1.6 a 15.2.8 má tato soustava celkem m rovnic o m neznámých, kde m je počet hran grafu. Kdybychom tuto soustavu rovnic vyřešili, získali bychom velikosti proudů v jednotlivých větvích sítě. Napětí bychom pak dopočítali podle Ohmová zákona.
Výpočet však lze ještě dále usnadnit podstatným zmenšením velikosti soustavy rovnic. Rovnice sestavené podle 1. Kirchoffova zákona pro fundamentální řezy totiž mají velmi jednoduchý tvar a umožňují snadno vyjádřit proudy v hranách kostry jako lineární kombinace tzv. smyčkových proudů, tj. proudů v hranách mimo kostru. Tato vyjádření dosadíme do rovnic získaných ze 2. Kirchhoffova zákona pro fundamentální kružnice, čímž dostaneme soustavu m — n + 1 rovnic pro m — n + 1 smyčkových proudů. Řešením této soustavy získáme smyčkové proudy a z nich pak již snadno dopočítáme proudy v ostatních hranách.
Lze dokázat, že matice S soustavy rovnic pro smyčkové proudy je symetrická a že její prvky     lze získat i zcela mechanickým způsobem podle vzorce
(15.5)
Sij — ^ ^ Rtkukjt
t=i
kde ku, kjt jsou prvky fundamentální matice kružnic K. Matici S lze získat také jako maticový součin S = KRKT, kde K je fundamentální matice kružnic, KT je transponovaná fundamentální matice kružnic a R je matice, jejíž prvky na diagonále jsou rovny odporům Ri a ostatní prvky jsou nulové. Celý postup výpočtu předvedeme na příkladě.
fíi
ei
T
R3
Ä4
fis
Ä8
£7
Ä2
s5
Ä9
I
£9
		
		rz 6
kg		9
		T6 0
r2
ra
Obrázek 15.3: Příklad elektrické sítě a fundamentální soustavy kružnic a řezů.
242
Kapitola 15. Cirkulace a potenciály
15.4.2 Příklad. Nalezněme proudy a napětí v jednotlivých větvích elektrické sítě z obr. 15.3 na předchozí straně. Rovnice vyjadřující 1. Kirchhoffův zákon pro fundamentální soustavu řezů mají tvar
(15.6)
T2 ■	h	+ h	+ h	= o,
r3 :	-h	+ h	+ h	= o,
r5 ■	h	+ h	+ h	= o,
re ■	h	+ h	-h	= o,
rs ■	h	+ h	+ h	= 0
a rovnice vyjadřující 2. Kirchhoffův zákon pro fundamentální soustavu kružnic mají
£\ ,
—£9 — £5 ■
Řešením této soustavy 9 rovnic o 9 neznámých bychom mohli přímo získat proudy v jednotlivých větvích. Méně pracný však je tento postup: Proudy ve větvích, které jsou částí kostry, vyjádříme ze soustavy (15.6) jako lineární kombinace ostatních. Stejné vztahy však lze snadno vyčíst přímo z grafu na obr. 15.3 vpravo.
(15.8)
h =	-h	-h
h =	h	-h
h =	-h	-h
h =	-h	+ I7
h =	-h	-h
Nyní dosadíme ze vztahů (15.8) do soustavy (15.7), čímž získáme pouze m — n + + 1=4 rovnice o 4 neznámých li, I4, Ij, Ig:
£1 , £7 ,
—£9 — £5 .
Vyřešením této soustavy získáme proudy Ii,l4,Iy,Ig a dosazením do (15.8) zbývající proudy. Ověřte, že tytéž koeficienty soustavy rovnic (15.9) poskytuje i vzorec (15.5).
15.4.3 Cvičení. Vyřešte příklad 15.4.2 pro konkrétní hodnoty e\ — £5 = £7 — 5= 6V, e9 = 12V, Ri = Rs = R7 = 1 fi, R9 = 2 ft, R2 = R3 = R4 = R6 = Rs = 10 SI.
Pak zvolte jinou kostru, popř. i jinou orientaci hran a řešení opakujte. Výsledek musí být samozřejmě týž.
(15.7)
k7 k0
-R3I3
R\I\ — R2I2 + R3I3 + R4I4 — R5I5 — Rsh Rsle + R7I7 — Rsh —R2I2 — R5I5 — Rsh + R9I9
(Ri + R2 + Rs)h — R3I4 + R2I9 =
-Rsh + {Rs + R4 + R5 + Re)h - Rsh + Rsh =
—Reh + (i?6 + R7 + Rs)h + Rsh =
R2h +Rsh + Rsh + {Ri + R5 + Rs + R9)h =
243
Výsledky cvičení
V-l.3.2 (str. 16).
2. Platí d(x) > \E(x)\ > \V{x)\ .
3. Platí m(x,x) = m+(x,x) = počet smyček ve vrcholu x .
4. Nemůže. Její vrchol by musel zároveň patřit i nepatřit do množiny A .
5. Platí \W{A)\ > \V(A) \A\ .
V-l.4.3 (str. 18). Vrcholy označte počínaje levým vrcholem ve směru hodinových ručiček d, c, e, b, /, a. Není to jediná možnost.
V-l.4.4 (str. 18). Prvé tři jsou navzájem izomorfní, čtvrtý nikoli.
V-l.5.4 (str. 20). Ze sledu, který není cestou, můžeme vynecháním částí mezi opakujícími se vrcholy získat cestu, která vede z téhož vrcholu do téhož vrcholu, a zajišťuje tedy stejnou dostupnost.
V-l.8.2 (str. 24). Dvanáct hran. Kdyby graf H měl navíc smyčku, bylo by to 13 hran.
V-l.8.3 (str. 25). Mohou. Všechny hrany obou grafů jsou smyčkami, neboť jiné hrany by se v obou maticích sousednosti projevily nestejnými hodnotami.
V-l.8.5 (str. 25). Pro orientovaný graf je
pro i ŕ j, pro i = j,
zatímco pro neorientovaný graf je
m(i,j) proi^j, d(i)       pro i = j.
V-2.2.9 (str. 41). Vzhledem k obrovskému počtu vrcholů (několik trilionů) je hledání cest v takovém grafu nereálné. V takových případech je vždy třeba využít speciálních vlastností konkrétní úlohy.
244
Výsledky cvičení
V-3.1.6 (str. 49). V kroku 2 vybíráme vždy hranu, jejíž jeden vrchol má značku a druhý nikoli.
V-3.1.7 (str. 49). V algoritmu 3.1.1, str. 47, upraveném podle cvičení 3.1.6, zařadíme do kroku 2 test, zda existuje hrana, která spojuje dva označkované vrcholy a která nebyla použita v kroku 3 k označkovaní žádného z těchto dvou vrcholu. K tomu lze použít hodnoty Odkud.
V-3.3.8 (str. 55). Není to pravda. Například v grafu na obr. 5.2, str. 72, v době návratu z vrcholů 5 nebo 6 není označkován vrchol 9.
V-4.2.10 (str. 60). Všechny vrcholy jsou (dokonce orientovane) dostupné z kořene, proto je graf souvislý. Z vlastností vstupních stupňů plyne, že je-li n počet vrcholů, je počet hran n — 1. Podle věty 4.2.9 je tedy stromem.
V-4.2.12 (str. 60). Je-li souvislý a má-li alespoň tolik hran, kolik má vrcholů.
V-4.2.13 (str. 60). Dvě nebo tři.
V-4.2.14 (str. 61). K\ má dvě neizomorfní kostry, K*> má tři.
V-4.3.12 (str. 64). Kdyby ceny hran nebyly různé, mohla by přidáním všech hran splňujících podmínku (*) vzniknout v grafu L kružnice. Jednoduchým příkladem je graf, kde několik nejlevnějších hran má stejnou cenu a tvoří kružnici.
Úprava Borůvková algoritmu spočívá v tom, že ceny hran učiníme různými. Lze to udělat buď zvětšením všech cen o velmi malá různá čísla, anebo lépe tak, že při porovnávání cen dvou hran v případě stejných cen rozhodneme podle pořadových čísel obou hran.
V-4.4.6 (str. 66). Cesty, které jsou vrcholově disjunktní, jsou i hranově disjunktní. Naopak to ovšem neplatí.
Rovnost vrcholového a hranového stupně souvislosti neplatí např. pro graf, který dostaneme z K4 odstraněním jedné hrany.
V-5.2.10 (str. 77). V grafu na obr. 5.3 je 9 různých topologických uspořádání vrcholů: 123456879, 123546879, 123564879, 123568479, 124356879, 132456879, 13254-6879, 132564879, 132568479, 123456879.
V-5.2.11 (str. 77). Je-li «1,^2, ■ ■ ■ ,vn topologické uspořádání vrcholů, pak topologické uspořádání hran získáme tak, že nejprve zařadíme všechny hrany z množiny E+(vi), pak všechny hrany z E+(v2) atd.
Je-li ei, e2,..., em topologické uspořádání hran, můžeme topologické uspořádání vrcholů získat tak, že nejprve zařadíme vrcholy s kladným výstupním stupněm, a to v pořadí, v němž se vyskytují poprvé v posloupnosti Pv(ei), Pv(e2),..., Pv(em) a na konec zařadíme v libovolném pořadí vrcholy s výstupním stupněm nulovým.
Výsledky cvičení
245
V-5.3.5 (str. 79). Tvrzení 8 a 9 přidat lze, viz následující důkaz. Tvrzení 10 splňují i grafy, které mají více než n — 1 hran, proto tvrzení 10 přidat nelze. 4    8:    z existence kořene plyne souvislost.
8 => 9: z vlastností stupňů vrcholů plyne, že graf má přesně n — 1 hran. Ze souvislosti a počtu hran plyne, že G je stromem, a proto neobsahuje kružnici.
9 =>■ 5:    neobsahuje-li graf kružnici, neobsahuje ani cyklus.
V-5.5.5 (str. 84). Graf hry je podobný jako na obrázku 5.7, ale bez vrcholu 0. Jádrem je množina {1,5,9,13}.
V-6.3.9 (str. 98).
vrchol	1	2	3 4	5	6	7 8	9 10
vzdálenost	0	14	6 10	22	28	31 42	30 35
Odkud		3-2	1-3 3-4	4-5	5-6	6-7 7-8 4-7	5-9 6-10
b:	vrchol	1	2      3      4      5      6      7 8	9
	vzdálenost	0	2      2      6      1      0      9 4	6
	Odkud		1-2   2-3   2-4   3-5   5-6   5-7 6-8 3-6	8-9
V-6.5.3 (str. 101). Příkladem je graf z obr. 6.3, str. 97.
V-6.7.5 (str. 106). Výsledná matice vzdáleností:
/0 2
8 0
3 -5
7 -1
\ 6 -2
4\
2
-3 1
0 }
V—6.7.6 (str. 106). Matici Q inicializujeme příkazem Q(i,j) := pro všechna i, j a výkonný příkaz uvnitř cyklů nahradíme příkazem:
když M(i,j) > M(i,k)+M(k,j), pak proveď M(i, j) := M(i,k) + M(k,j) a navíc Q(i, j) := Q(i,k).
V-7.3.5 (str. 121). Oba algoritmy začínají s rozdílně definovanými maticemi.
Výchozí matice A ve Floydově algoritmu 6.7.3 zahrnuje kromě hodnot hran také hodnoty triviálních sledů (nuly na diagonále), neboť jejich opakované zahrnutí do součtů © nevadí. Kleeneho algoritmus však musí kvůli obecným uzavřeným polookruhům započítat triviální sledy jen jednou, proto jsou hodnoty triviálních sledů z výchozí matice vyloučeny a jsou započítány až na konci výpočtu.
246
Výsledky cvičení
Výs
V-7.3.7 (str. 121). Matice šířek nejširších sledů: V-;
dob:
/	cc	6	7	7	7	7 >	ome
	4	oo	5	4	4	4	1
	4	6	oo	4	4	4	por:
	4	6	8	oo	4	4	příp
	4	6	7	7	co	7	obsc
\	4	6	8	8	4	oo y	v pť
V-7.4.7 (str. 125). a(vi,Vi) = 1, s(vuv2) = 3|, a(«i,«s) = 3§, = 1.
S{VI,V5) = |. S(U1,D6) = |.
V—8.1.14 (str. 133). Záporný tok v hraně incidentní s v by nemusel procházet hranou e„ a omezení toku v hraně ev by bylo neúčinné.
V-8.1.17 (str. 133). Je-li např. tok v hraně h omezen na interval (£1,2:4) a je-li závislost ceny toku na jeho velikosti dána grafem na obr. 15.4, nahradíme hranu h čtveřicí rovnoběžných hran h\,..., Ä4 takto:
a{e)
		e l(e)		c(e)
hi			Xl	Xi
h2			0	X2 - Xi
h3			0	X-í - Xi
			0	Xi - Xz
cena				
			/	ž/4
2/1	\		/	
	\		2/3	
				
				tok
yiľ-Ľi
Xi    x2    x3 X4 Obrázek 15.4: Konvexní závislost ceny toku na velikosti toku.
V-8.2.10 (str. 139). Kapacity hran budou jednotkové, dolní omezení nulové. Ke grafu přidáme návratovou hranu z cílového vrcholu c do výchozího vrcholu r a v této jediné hraně bude dolní i horní omezení toku jednotkové. Nejkratší cestu budou tvořit původní hrany s jednotkovým tokem.
Cyklus se zápornou délkou může způsobit chybný výsledek, neboť jeho hrany mohou být nasyceny tokem, a tím mohou být nepoužitelné pro tok, který má určit nejkratší cestu.
Výsledky cvičení
247
V-8.4.10 (str. 149). Pokud přípustný tok najdeme, bylo omezení stanoveno dobře. (To platí pro hledání přípustného toku. Pro hledání toku maximálního by omezení mohla být i takto příliš silná.)
Pokud přípustná cirkulace neexistuje a návratová hrana je součástí řezu se zápornou kapacitou, pak je třeba omezení v návratové hraně změnit (uvolnit). Pokud přípustná cirkulace neexistuje, ale řez se zápornou kapacitou návratovou hranu neobsahuje, pak omezení v návratové hraně bylo stanoveno dobře, ale přípustný tok v původním grafu neexistuje.
V-9.1.5 (str. 162). Doprostřed hromady hnoje umístíme fiktivní stromek.
V-9.1.8 (str. 162). Nechť je dána úloha o nejlevnějším maximálním párování. Zvolíme nějaké dosti velké kladné číslo M, např. větší než součet cen všech hran, a pak pro každou hranu e její cenu c(e) nahradíme cenou M — c(e). V grafu s takto změněnými cenami pak řešíme úlohu o nejdražším párování.
Označme m počet hran v maximálním párování. Výsledné párování P, které je nejdražší vůči novým cenám, musí obsahovat také m hran, neboť jinak by kterékoli maximální párování mělo lepší (totiž vyšší) cenu. Párování P je ovšem nejdražší i mezi všemi maximálními párováními a jeho cena je mM — ^e,p c(e). Párování P tedy má ze všech maximálních párování nejmenší hodnotu J]eep c(e).
V-9.3.6 (str. 171). Kdyby bylo \X\ > \Y\, platilo by £xeX d{x) > £,6yd(s), což není možné, neboť součty stupňů na obou stranách grafu musí být stejné. Rovnost \X\ = \Y\ je možná pouze tak, že všechny vrcholy mají stejný stupeň.
V-9.3.7 (str. 171). Předpoklady věty 9.3.5 jsou splněny, existuje tedy párování, které nasycuje jednu z obou množin. Graf je však regulární (všechny vrcholy mají stejný stupeň), proto \X\ = \Y\. Zmíněné párování je tedy perfektní.
V—10.1.6 (str. 179). Pro k = 3 a n = 2 jsou de Bruijnovy posloupnosti dvě: 00011101 a 00010111. (Posloupnost, kterou získáme cyklickou záměnou, pokládáme za tutéž cyklickou posloupnost.)
Pro k = 2 a n = 3 má de Bruijnova posloupnost délku 9 a těchto posloupností je 22.
V—10.2.4 (str. 180). Graf splňuje předpoklady věty 10.2.2, existuje v něm tedy uzavřený orientovaný tah, který prochází všemi hranami. Díky souvislosti tento tah prochází i všemi vrcholy. Každé dva vrcholy tedy jsou spojeny orientovaným sledem.
V—10.2.8 (str. 181). Oba vrcholy lichého stupně leží v téže komponentě souvislosti. Pro každou komponentu souvislosti tedy bude stačit jeden tah, jeden z těchto tahů bude neuzavřený.
Kdyby počet vrcholů lichého stupně byl 4, byly by nutné 3 nebo 4 tahy v závislosti na tom, zda všechny vrcholy lichého stupně leží v téže komponentě, nebo dva a dva v různých komponentách.
248
Výsledky cvičení
ry,..
V-10.2.10 (str. 182). Označme K = J2vev \R(V)\- Je-1' K = °> pokrývá hrany grafu jeden uzavřený (a eulerovský) orientovaný tah. Je-li K > 0, je k pokrytí hran třeba K/2 neuzavřených orientovaných tahů.
důkaz: Je-li K > 0, označme k+ součet všech kladných a k~ součet všech záporných hodnot R. Poněvadž Ylvev R(v) ~ 0, platí k+ = —k~ = K/2. Můžeme tedy ke grafu přidat celkem k+ hran, které vedou z vrcholů se záporným R do vrcholů s kladným R, a to tak, aby vznikl graf G", v němž každý vrchol má stejný vstupní i výstupní stupeň. V grafu G' existuje orientovaný uzavřený eulerovský tah. Odstraněním přidaných hran se tento tah rozpadne na k+ neuzavřených tahů, které pokrývají hrany původního grafu.
Méně než K/2 tahů k pokrytí hran nestačí, neboť přidáním menšího počtu hran nelze získat graf, v němž by existoval orientovaný uzavřený eulerovský tah. □
V—10.3.4 (str. 184). Každou hranu, kterou sled prochází fc-krát, nahraďme k kopiemi. Kdyby pro některou hranu bylo k > 2, bylo by možno dvě z těchto hran odebrat. Sudost stupňů by tím zůstala zachována, ale eulerovský tah by se zkrátil.
V-10.3.5 (str. 184). Kdyby některé dvě cesty měly společnou hranu e, párování P by nebylo nejlevnější. Vynecháním hrany e z obou cest se tyto cesty rozpadnou na části, z nichž lze sestavit jiné dvě cesty o menší celkové délce. Viz obr. 15.5.
Obrázek 15.5: Náhrada dvou cest se společnou hranou e dvěma hranově disjunkt-
V-10.3.7 (str. 184). Je-li v grafu hrana se zápornou délkou, úloha ztrácí smysl. Opakovaným procházením takovou hranou sem a tam lze totiž dosáhnout libovolně malé (záporné) délky sledu. Žádný sled pak není nejkratší, vždy existuje sled ještě kratší.
V-12.2.7 (str. 201). Jsou-li fixovány vrcholy x, y, pak prodloužíme o dostatečně velkou hodnotu M všechny hrany z množiny E(x) U E(y). Hamiltonovské cesty, které začínají ve vrcholu x a končí ve vrcholu y (nebo naopak), se tím prodlouží o 2M, zatímco všechny ostatní hamiltonovské cesty se prodlouží o 3M nebo o 4M. Pokud v daném grafu existuje vůbec nějaká hamiltonovská cesta spojující x a y, pak nejkratší hamiltonovská cesta v grafu s prodlouženými hranami bude spojovat právě vrcholy x a y.
V-12.2.8 (str. 201). Stačí, aby M bylo větší než délka optimální cesty. Poněvadž ji předem neznáme, lze zvolit např. délku nejdelší hrany vynásobenou počtem vrcholů.
V-l
O
V-l
V-l
stři::; vrchc
V-l*
kost násl'
V-l.
zvýší nejle'. -2Y
cvičení
Výsledky cvičení
249
•irv.á hrany : krytí hran
:\i:et všech 1 Můžeme rr.vm R do I má stejný ;r:vský tah. tahů, které
z : čtu hran tah. □
.ĚJiraďme k těchto hran ■ íí zkrátil.
e. párování :: zpadnou 15.5.
V-12.2.9 (str. 202). Viz obr. 15.6.
6
Obrázek 15.6: Příklad, že nejkratší hamiltonovská cesta nemusí být obsažena v nejkratší hamiltonovská kružnici.
V-12.3.1 (str. 202). Příkladem je graf K2,3.
V—12.3.4 (str. 203). V bipartitním grafu musí hamiltonovská kružnice přecházet střídavě mezi oběma stranami grafu, obě strany by tedy musely mít stejný počet vrcholů.
V-12.4.3 (str. 205). V prvých třech podúlohách sice dostaneme stejné minimální kostry jako v 12.4.2, ale s podstatně silnějšími přidanými omezeními, což urychlí následující výpočet. Průběh výpočtu může být tento:
c—°	podúloha	zakázané	vynucené	odhad	komentář
		hrany	hrany		
	1	-	-	30	větveno na 2, 3, 4
	2	(1,3)	-	38	umrtveno odhadem
; =;unkt-					
	3	(1,4)	(1,3)	37	umrtveno odhadem
:rácí smysl.	4	(1, 2), (1, 5),	(1,3), (1,4)	33	větveno na 5, 6, 7
it libovolně		(1,6)			
- i.ed ještě	5	(1, 2), (1, 5),	(1, 3), (1, 4)	38	hamilt. cesta
		(1, 6), (2, 5)			
::;:atečně	6	(1, 2), (1, 5),	(1,3), (1, 4),	36	umrtveno odhadem
v;r:é cesty,		(1, 6), (2, 3)	(2, 5)		
; prodlouží					
:o o 4M.	7	(1,2), (1,5),	(1,3), (1,4),	36	optimální řešení
njící x a y,		(1, 6), (2, 4),	(2, 5), (2, 3)		
:t spojovat		(2,6)			
■ Poněvadž : i počtem
V-12.4.7 (str. 210). Délky všech hamiltonovských cest z x do y se penalizací zvýší o hodnotu (2 X^ÍLi ~P(X) ~P(y)- Jestliže jsme při použití penále p dostali nejlevnější 1-strom o ceně C, lze jako dolní odhad použít číslo C + p(x) + p(y) —
-2£ľ=ii>(0-
250
Výsledky cvičení
V-13.1.2 (str. 211). V obarvení podle obrázku 13.1 stačí barvu D nahradit barvou A. Graf, který má smyčku, nelze obarvit.
V-13.1.12 (str. 215). Strom o alespoň dvou vrcholech je vždy dvoubarevný.
V-13.2.4 (str. 218). Nejrychlejší výpočet bude při uspořádání vrcholů vzestupně podle jejich hloubky, tj. kořen jako první a vrchol v hloubce 2 jako poslední. Naopak výpočet bude nejpomalejší, když všechny listy budou na začátku a kořen na konci.
V-13.2.6 (str. 219). Vrcholy mezi nejvyšším a druhým nejvyšším v P(y) mohou ovlivnit barvu vrcholu x — max(P(y)) a tím i barvu vrcholu y. Viz graf na obr. 15.7, kde „vylepšený" algoritmus přehlédne možnost zvýšit barvu vrcholu 3 a v důsledku toho nenajde optimální obarvení.
vrchol:      1 2 3 4 5
barva:      1 2 2 3 4
Obrázek 15.7: Protipříklad ke cvičení 13.2.6.
V-14.2.2 (str. 227). Krychle je duální k pravidelnému osmistěnu, pravidelný dvanáctistěn je duální k pravidelnému dvacetistěnu. Čtyřstěn je duální sám k sobě.
V-14.3.2 (str. 229). Důkaz je podobný důkazu věty 14.3.1, ale namísto kostry použijeme napnutý les (viz 4.2.4, str. 58, a 4.2.8, str. 59).
V-14.4.3 (str. 230). Viz obr. 15.8.
V—15.4.3 (str. 242). Rozšířená matice soustavy rovnic pro smyčkové proudy má tvar
21	-10	0	10	6 \
10	31	-10	1	6
0	-10	21	10	6
10	1	10	22	18 J
Jejím řešením dostaneme h = 2,56468 A, J4 = 1,56498 A, I7 = 2,56468 A, ig = = -3,22084 A a dále pak h = 0,65616 A, I3 = 0,99970 A, J5 = 1,65596 A, I6 = = 0,99970 A, I8 = 0,65616 A.
251
Literatura
[AHU74]      Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms. Reading, Addison-Wesley, 1974.
[Berge58]     Berge, C: Theorie des Graphes et ses Applications. Paris, Gautier--Villars, 1958.
[Berge73]     Berge, C: Graphs and Hypergraphs. Amsterdam, North-Holland Publ. Co., 1973.
[Demel91] Demel, J.: Teorie grafů. Praha, skripta ČVUT, 1982, 2. vydání 1991. [Demel88]    Demel, J.: Grafy. Praha, SNTL, 1988.
[FF62] Ford, L. R. Jr., Fulkerson, D. R.: Flows in Networks. Princeton,
Princeton University Press, 1962.
[GJ79] Garrey, M. R., Johnson, D. S.: Computers and Intractability: a Guide
to the Theory of NP-Completeness. San Francisco, W. H. Freeman, 1979.
[Harary69]   Harary, F.: Graph Theory. Reading, Addison-Wesley, 1969.
[Chr75]        Christofides, N.: Graph theory - An Algorithnic Approach. New York, Academic Press, 1975.
[Chytil82]    Chytil, M.: Automaty a gramatiky. Praha, SNTL, 1982.
[KŠCh89]     Kolář, J., Štěpánková, O., Chytil, M.: Logika, algebry a grafy. Praha, SNTL, 1989.
[Kučera83]   Kučera, L.: Kombinatorické algoritmy. Praha, SNTL, 1983.
[Lawlei'76]    Lawler, E., L.: Combinatorial Optimization - Networks and Matroids. New York, Holt, Reinhart and Winston, Inc., 1976.
[MN96]       Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. Praha, Matfyzpress, 1996.
252
Literatura
[Nečas78]     Nečas, J.: Grafy a jejich použití. Praha, SNTL, 1978.
[Nešetřil79]   Nešetřil, J.: Teorie grafů. Praha, SNTL, 1979.
[Plesník83]   Plesník, J.: Grafové algoritmy. Bratislava, VEDA, 1983.
[Sedláček64] Sedláček, J.: Kombinatorika v teorii a praxi. Praha, NCSAV, 1964, 2. vydání, 1977.
[Sedláček81] Sedláček, J.: Úvod do teorie grafů. Praha, Academia, 1981.
[SwTh81]     Swamy, M. N. S., Thulasiraman, K.: Graphs, Networks and Algorithms. New York, John Wiley & Sons, Inc., 1981.
[Sišma97]     Sišma, P.: Teorie graß 1736-1963. Praha, Prometheus, 1997.
[Töpfer95]    Töpfer, P.: Algoritmy a programovací techniky. Praha, Prometheus, 1995.
Rejstřík
l-strom, 208
algoritmus
Borůvkův, 63
Dijkstrův, 101
Floydův, 105
Fordův-Fulkersonův, 141
heuristický, 189
hladový, 62, 196
Jarníkův-Primův, 63
Kleeneho, 119
maďarský, 171, 172
modifikovaný Dijkstrův, 95
Out of Kilter, 154
ověřovací, 187
polynomiální, 31, 187
Tarjanův, 69 artikulace, 66 automat, 120
barevnost
hranová, 215
vrcholová, 211 Bellmanovy rovnice, 88
centrum grafu, 46 certifikát, 187 cesta, 20
alternující, 163
hamiltonovská, 197
kritická, 44
střídavá, 163
zlepšující, 139, 140 cirkulace, 129
elementární, 232 cyklus, 20
číslo cyklomatické, 233
de Bruijn, 178 defekt, 147, 155 délka sledu, 20 diagram Hasseův, 35 dostupnost, 20, 58, 69 dualita
lineárního programování, 154
rovinných grafů, 226 dvanáctistěn, 226 dynamické programování, 88
ekvivalence, 34
nakreslení, 225 eliminace
smyčky, 123
vrcholu, 123 Euler, 177, 229
faktor, 18
formule Eulerova, 229 fronta, 50, 95 fundamentální soustava
kružnic, 232
řezů, 236 funkce účelová, 32
graf, 11
acyklický, 73 bipartitní, 21, 52, 214
254
diskrétní, 21 doplňkový, 212 duální, 226 hranový, 215 ohodnocený, 14 orientovaný, 11 Petersenův, 230 planární, 12, 223 prostý, 16 regulární, 21 rovinný, 12, 145, 223
topologický, 223 rovnosti, 172 řídký, 95, 229 síťový, 42 symetrický, 14 úplný, 21
halda, 96
hledání
do hloubky, 52, 69, 76 do šířky, 49, 144 značkováním, 47, 141
hodnost grafu, 238
homeomorfní grafy, 230
hra dvou hráčů, 83
hrana, 11
návratová, 129, 135, 149 vpřed, vzad, 140, 231
hranová barevnost, 215
hrany rovnoběžné, 11, 12
chromatický index, 215
incidence, 11, 224 inorder, 23, 56 instance úlohy, 32, 185 izomorfismus, 17
jádro grafu, 83
kapacita
řezu, 131, 139, 142, 146, 228
zlepšující cesty, 140 kilter, 154 Kirchhoff, 129, 234
Rejstřík
Kleene, 119, 120 klika, 212
kolmost vektorů, 238 komponenta
silné souvislosti, 67
souvislosti, 57 kořen grafu, 77 kořenový strom, 21 kostra, 58
minimální, 61, 204 kružnice, 20
střídavá, 163
zlepšující, 139 květ, 167
les, 58
napnutý, 58, 232-242 lineární programování, 154
markovský řetězec, 116
Masonovo pravidlo, 128
matice
délek hran, 86 dostupnosti, 69, 114 incidenční, 25, 237 sousednosti, 24, 114 vzdáleností, 86
metoda
CPM, 44
hrubé síly, 189, 190, 203
větví a mezí, 191 množina, 32
nezávislá, 212, 219 most, 65
mosty města Královce, 177 multigraf, 16
nakreslení grafu, 223 napnutý les, 58, 232-242 následník, 15 násobnost hrany, 16 nekonečno oo, 28, 93, 113 nezávislá množina, 212, 219 NP-úloha, 187
obarvení, 211
Rejstřík
255
očíslování topologické, 74 odhad
doby práce algoritmu, 30, 186
v backtrackingu, 190
v metodě větví a mezí, 192
okolí vrcholu, 15
operace uzávěru, 112
optimalizace, 31
orientovaný graf, 11
Out of Kilter, 154
párování, 161 penalizace, 208 Platonova tělesa, 226 podgraf, 18
podmínka omezující, 31 podúloha, 191 polookruh, 110
posloupnost de Bruijnova, 178 postorder, 23, 56 potenciál, 154, 234 preorder, 23, 56
princip optimality Bellmanův, 88 problém obchodního cestujícího, 198 proces náhodný, 116 prostor řešení, 31 proud smyčkový, 241 průzkum lokální, 196 předchůdce, 15 převody úloh, 188, 199 přípustné řešení, 31
redukce
polynomiální, 188
tranzitivní, 79 rekurzivní procedura, 55 relace, 33
relaxace podmínky, 192 rozklad, 35
řešení přípustné, 31, 187, 190, 191 řetězec markovský, 116 řez, 16, 131, 146, 235
minimální, 131, 139, 142, 228
síť, 14
transportní, 130, 148
vrstvená, 151 sled, 19 složitost, 185 smyčka, 11 součin kartézský, 33 soused, 15 souvislost, 57
silná, 67 spotřebič, 129 stav, 37
absorbující, 117
hry, 83
markovského řetězce, 116 stěna, 224
stereografická projekce, 224 strom, 58
kořenový, 21, 77
napnutý, 58
řešení, 189, 192
střídavý, 166
uspořádaný, 22 stupeň
souvislosti, 65, 134, 225, 226 stěny, 224 vrcholu, 16
tah, 20
eulerovský, 177 tok, 129, 231
maximální, 131
nejlevnější, 131, 152, 207
od zdroje ke spotřebiči, 129
přípustný, 130 topologické uspořádání, 74, 83, 98 topologický rovinný graf, 223 tranzitivita, 34, 79 trojúhelník, 20 typ úlohy, 32, 185
účelová funkce, 32 úloha, 32, 185
čínského pošťáka, 182
dopravní, 134
NP-těžká, 31, 185
256
Rejstřík
P
NP-úplná, 188
optimalizační, 31, 187, 191
přiřazovací, 135, 171, 206
rozhodovací, 187
třídy NP, 187
třídy P, 187 uspořádání, 35
cyklické, 225
topologické, 74, 83, 98 uzávěr, 112
tranzitivní, 79, 114
velikost toku, 130
věta
Fordova-Fulkersonova, 142 Hallova, 170 Konigova, 169 Kuratowského, 230 Mengerova, 66, 134 vrchol, 11
zákon Kirchhoffův, 129, 234 zásobník, 53, 70-73 zdroj, 129
značkování vrcholů, 47, 141 zobrazení, 36
Rejstřík
Přehled značení
257
142
Přehled značení
E, N = množina reálných a přirozených čísel (včetně nuly)
\M\ = počet prvků množiny M
A \ B = rozdíl množin A a B
n = obvykle počet vrcholů grafu
m = obvykle počet hran grafu
oo = nekonečno
O(f) = asymptotický odhad funkce / shora
V(G) = množina vrcholů grafu G
E(G) = množina hran grafu G
Pv(e) = počáteční vrchol hrany e
Kv(e) = koncový vrchol hrany e
V(x) = množina sousedů vrcholu x
V+(x) — množina následníků vrcholu x
V~(x) = množina předchůdců vrcholu x
E(v), E+(v), E-(v) d{v), d+(v), d~(v) W(A), W+(A), W-{A) m(v,w), m+(v,w)
= okolí vrcholu
= stupeň vrcholu
= řez určený množinou A
= násobnost hrany
G = G' = izomorfismus grafů G a G'
Kn — úplný graf o n vrcholech
Km,n = úplný bipartitní graf se stranami oman vrcholech
D+ (v) — množina vrcholů orientovane dostupných z vrcholu v
G+ = tranzitivní uzávěr grafu G
G* = reflexivní a tranzitivní uzávěr grafu G
©, ®, * = operace v polookruhu
cj(G) = klikovost grafu
cx(G) = nezávislost grafu
x(G) = vrcholová barevnost grafu
x'{G) = hranová barevnost grafu
—G = doplňkový graf
GD — duální graf
1.12.1, str. 32 1.12.1, str. 33 1.12.1, str. 33 1.10.6, str. 31 1.10.6, str. 31 6.2.10, str. 93 1.10.6, str. 30
1.3, str. 15 1.3, str. 15 1.1.2, str. 11 1.1.2, str. 11
1.3, str. 15 1.3, str. 15 1.3, str. 15
1.3, str. 15 1.3, str. 15 1.3, str. 15 1.3, str. 15
1.4.2, str. 17 1.6, str. 21 1.6, str. 21 5.1.10, str. 69 5.4.1, str. 79 5.4.1, str. 79 7.1.1, str. 110
13.1.4, str. 212
13.1.3, str. 212 13.1.1, str. 211 13.1.15, str. 215
13.1.4, str. 212 14.2, str. 226