dvojice těchto prvků. Takto si můžeme například i znázorňovat možnosti jak cestovat z

Grafy

V této kapitole se seznámíme se základními pojmy teorie grafů, ukážeme si možnosti jejich použití a také se seznámíme s některými algoritmy, které řeší úlohy teorie grafů. Grafy slouží často jako prostředek k lepšímu porozumění vztahů mezi nějakými dvojicemi prvků. Často si tak vypomáháme i při řešení úloh v běžném životě. Prvky znázorňujeme jako tečky, kolečka či čtverečky a vztahy mezi nimi znázorňujeme čarami spojujícími dvojice těchto prvků. Takto si můžeme například i znázorňovat možnosti jak cestovat z jednoho města do druhého a vybírat tu možnost, která je pro nás výhodnější z nějakého hlediska. Cesta z Prahy do Ostravy může vést po dálnici do Olomouce přes Brno a poté do Ostravy. Do Olomouce je možné se dostat také přes Hradec Králové a Svitavy. Dále je také možnost cesty z Prahy přes Hradec Králové, Vamberk, Šumperk, Opavu do Ostravy. Poslední uvedená cesta je nejkratší, cesta po dálnici přes Brno, Olomouc a Fulnek zase časově nejkratší a cesta přes Hradec Králové do Olomouce a dále do Ostravy může být nejvýhodnější pokud kombinujeme vzdálenost a časovou náročnost cesty. Ostatně za počátek teorie grafů je obvykle považováno řešení problému mostů přes řeku Pregel ve městě Královci, později K¨onigsbergu a dnes Kaliningradu. Město se rozkládá po obou stranách řeky a na dvou ostrovech uprostřed řeky. Mezi oběma břehy a ostrovy je celkem sedm mostů, tak jak je to schematicky znázorněno v levé polovině obr. 1. Řeka je znázorněna šrafovaně. Úloha, kterou se v 18. století bavili obyvatelé města zní: je možno z nějakého místa vyjít, projít všemi mosty a žádným mostem dvakrát a vrátit se do výchozího města? Tuto úlohu vyřešil v roce 1736 známý matematik Euler, který ukázal, že to není možné. Pro zjednodušení si břehy a ostrovy znázornil jako body a mosty jako spojnice těchto bodů. Tím dostal mnohem přehlednější náčrtek problému. Tento náčrtek je znázorněn v pravé polovině obr. 1. Poté poměrně jednoduše ukázal nemožnost nalézt požadovanou cestu. Toto si ukážeme později.

strana A A

ostrov B

ostrov C

B

C

Pregel D strana D

´m sedmi most˚ ´ lovci Obr. 1: Proble u v kra

Další úloha, kterou si ukážeme, patří do kategorie zábavné či rekreační matematiky. Je to známá úloha o vlku, koze a zelí. Převozník má za úkol převézt vlka, kozu a hlávku zelí z jednoho břehu řeky na druhý a přitom smí vézt pouze nejvýše jednu věc. Přitom nesmí bez dozoru převozníka zůstat sami vlk a koza nebo koza a zelí. Ukažme si, jak je možno úlohu řešit. Označme si písmenem P převozníka, písmenem K kozu, písmenem V vlka a písmenem Z zelí. V tabulce si uvedeme všechny možnosti, jak lze rozdělit P,K,V,Z na dvě podmnožiny, které reprezentují stav na obou březích řeky. Tyto možnosti si očíslujeme. Možnosti, které odporují zadání úlohy nečíslujeme, ale označíme je ×. Dostaneme: 1

2

možnost 1. břeh 1 P KV Z 2 P KZ 3 PV K 4 PV Z × KV Z 5 PK × PV × PZ

2. břeh

možnost 6 7 8 9 × 10 × ×

V Z K P VZ KZ KV

1. břeh V Z K P VZ KZ KV

2. břeh P KZV P KZ PV K PV Z KV Z PK PV PZ

Máme 10 možností, které mohou teoreticky nastat. Pokusme se spojit čarou ty dvojice možností, kdy se lze z jedné dostat do druhé. Můžeme dostat různé přehledné či méně přehledné „obrázky”. Dva takové jsou uvedeny na následujícím obr. 2.

1

2

3

4

5

2

3 4

1

5

10 9 6

7

8

9

6 8

10

7

´m koza, vlk, zel´i Obr. 2: Proble Z obrázků není na první pohled vidět řešení, ale je možno ho poměrně snadno nalézt. Řešením úlohy je dostat se z možnosti 1 do možnosti 6. Pokud si ale „obrázek” nakreslíme ve vhodnějším tvaru, například tak, jak je to uděláno na obr. 3, vidíme na první pohled, že úloha má dvě různá řešení. Jsou to řešení: 1 → 10 → 4 → 7 → 3 → 9 → 5 → 6 nebo 1 → 10 → 4 → 8 → 2 → 9 → 5 → 6.

7

4 1

3

9 5

10

8

6

2

´m koza, vlk, zel´i Obr. 3: Proble Zkusme řešit ještě jednu velmi podobnou úlohu, tzv. úlohu o dvou misionářích a dvou kanibalech. Úloha zní: je možno a jak přepravit dva misionáře a dva kanibaly (bez převozníka) přes řeku za použití jediné loďky, která je schopna uvézt nejvýše dvě osoby? Přitom na žádném břehu nelze ponechat jednoho misionáře se dvěma kanibaly. Předpokládejme, že roli převozníka (schopnost převést loďku z jednoho břehu na druhý)

3

může zastávat každý misionář i každý kanibal. Uvědomme si, že úloha připouští situace, při kterých se na jednom břehu ocitnou loďka, jeden misionář a dva kanibalové. Toto možnost je povolena pouze dočasně při vystupování a nastupování do loďky. Označme si písmenem L loďku, písmenem K kanibala a písmenem M misionáře. Loďku musíme uvažovat, abychom mohli rozhodovat, z které možnosti do které se lze dostat (loďka musí změnit břeh). Utvořme opět tabulku všech možností, jak rozdělit skupinu L,M,M,K,K na dvě části, které odpovídají situaci na obou březích řeky. Přípustné možnosti očíslujeme, nepřípustné možnosti označíme symbolem ×. Mezi nepřípustné možnosti patří i možnost, že je loďka na jednom břehu a ostatní jsou na druhém. možnost 1. břeh 1 LM M KK 2 LM M K 3 LM KK × M M KK 4 LM M 5 LKK 6 LKM 7 KM M × M KK

2. břeh

možnost 8 9 10 × 11 12 13 14 ×

K M L KK MM KM LK LM

1. břeh K M L KK MM KM LK LM

2. břeh LM M KK M M KL M KKL M M KK LM M LKK LKM MMK M KK

Nyní si vytvoříme opět „obrázek”, kde jsou spojeny čarou ty dvojice možností, kdy se lze z jedné dostat do druhé. Grafické znázornění naší úlohy je na obr. 4.

12

2

10

4

14

7

1

13

11

3

6

8

9

5

´m dvou misiona ´r ˇ˚ Obr. 4: Proble u a dvou kanibal˚ u Vidíme, že úloha má více řešení. Jistě bychom některá z nich získali metodou zkoušení, určitě bychom takto našli alespoň jedno řešení. Těžko bychom bez nějakého systematického přístupu mohli získat více. Náhledem na obr. 4 však můžeme získat i další informace. Například, že je zapotřebí nejméně pět přejezdů řeky a že existuje 16 různých takovýchto řešení úlohy. Nejnáročnější řešení vyžaduje devět přejezdů řeky a existují čtyři různá taková řešení. V obou případech samozřejme nepředpokládáme opakování situace. Poznámka. Úlohu je možno formulovat i „přísněji” požadavkem, že se na žádném břehu nesmí ani na okamžik ocitnout kanibalové v početní převaze. Při této modifikaci se stávají nepřípustnými další dvě možnosti, a to možnosti 3 a 10. Grafické znázornění této modifikované úlohy je na obr. 4–1. Vidíme, že modifikovaná úloha má čtyři různá řešení a každé z nich vyžaduje pět přejezdů řeky.

4

6

12

14

7 2

9

1

11

8

5

13

4

´ proble ´m dvou misiona ´ r˚ Obr. 4–1: Modifikovany u a dvou kanibal˚ u Výše uvedené úlohy nás přesvědčují, že je asi vhodné zavést do podobných úvah nějaký řád, kde bude dostatečně obecně specifikováno, co je „situace”, co čára spojující vhodné situace a co znamená získaný „obrázek”. V našich úvodních úvahách jsme se mohli při přechodu od jedné situace k druhé vrátit i zpět od druhé situace k první. Toto může být ale v některých úvahách nepřijatelné, například průjezd jednosměrnou ulicí je touto ulicí nemožné opakovat zpět. Budeme proto rozlišovat orientované a neorientované grafy. Neorientované grafy Definice. Neorientovaným grafem G rozumíme trojici G = (V, H, p), kde V je neprázdná množina, jejíž prvky budeme nazývat vrcholy, H je množina (může být i prázdná), jejíž prvky nazýváme hrany a p je zobrazení z H do množiny všech maximálně dvouprvkových podmnožin množiny V , tj. do {{a, b}; a, b ∈ V }, které určuje, které vrcholy daná hrana „spojuje”. Je–li p(h) = {a, b}, říkáme, že vrcholy a, b jsou koncovými (nebo krajními) vrcholy hrany h, nebo že hrana h končí nebo začíná ve vrcholu a či vrcholu b. Též říkáme, že vrcholy a a b jsou koncovými vrcholy hrany h. Poznámka. Definice umožňuje situaci, kdy je p(h) = {a, a}. V tomto případě budeme říkat, že hrana h je smyčka (u vrcholu a). Je také možné, že pro různé h1 , h2 nastane p(h1 ) = p(h2 ) = {a, b}; zde musí ale být a 6= b. V tomto případě se říká, že hrany h1 , h2 jsou rovnoběžné a graf s takovouto situací se nazývá multigraf. Příklad multigrafu je na obr. 1 vpravo. Existují dvě extrémní situace, a to, že graf nemá žádnou hranu, pak tento graf nazýváme diskrétním grafem, nebo že každé dva vrcholy grafu jsou spojeny právě jednou hranou, pak tento graf nazýváme úplným grafem nad danou množinou vrcholů. Úplné grafy nad dvou, tří, čtyř a pětiprvkovou množinou vrcholů jsou zobrazeny na obr. 5.

´ ´ grafy Obr. 5: Upln e

5

Je samozřejmě problém odhadnout jak rozmístit vrcholy grafů aby jejich zobrazení bylo co nejpřehlednější. Pro „obrázky” grafů můžeme opět používat termín diagram grafu zavedený v souvislosti se zobrazováním uspořádaných množin. V případě Booleových algeber, které lze také zobrazovat pomocí diagramů, se jevil jako užitečný pojem izomorfizmu, který nám říkal, kdy jsou dvě Booleovy algebry vlastně stejné, i když na diagramech mohou vypadat jinak. Proto si pojem izomorfizmus zavedeme i při studiu grafů. Poznámka. Skutečnost, že dva grafy jsou izomorfní znamená, že mezi nimi existuje vzájemně jednoznačné zobrazení vrcholů a hran takové, že dva vrcholy jsou spojeny hranou v jednom grafu právě tehdy, když ve druhém grafu jsou odpovídající vrcholy spojeny odpovídající hranou. Tedy řekneme, že dva grafy G1 = (V1 , H1 , p1 ) a G2 = (V2 , H2 , p2 ) jsou izomorfní, jestliže existují dvě vzájemně jednoznačná zobrazení f : V1 −→ V2 a g : H1 −→ H2 taková že pro každou hranu h ∈ H1 platí: p1 (h) = {x, y} právě tehdy, když je p2 (g(h)) = {f (x), f (y)}. Příkladem jsou grafy na obr. 2 a obr. 3, které zobrazují problém „koza, vlk, zelí”. Na následujícím obrázku (obr. 6) jsou příklady dvou dvojic navzájem izomorfních grafů. Samozřejmě ihned poznáme, o které dvojice jde. Jsou–li totiž dva grafy izomorfní, pak nutně mají stejný počet vrcholů a stejný počet hran.

Obr. 6: Dvojice izomorfn´ich graf˚ u Obdobně je účelné zavést pojem podgrafu daného grafu. Definice. Budeme říkat, že neorientovaný graf G1 = (V1 , H1 , p1 ) je podgrafem grafu G2 = (V2 , H2 , p2 ), jestliže je V1 ⊆ V2 , H1 ⊆ H2 a platí: kdykoliv je p1 (h) = {a, b}, pak je p2 (h) = {a, b}. Poznámka. To, že je graf G1 = (V1 , H1 , p1 ) podgrafem grafu G2 = (V2 , H2 , p2 ) tedy znamená, že je V1 ⊆ V2 , H1 ⊆ H2 a kdykoliv jsou dva vrcholy spojeny v grafu G1 , pak jsou také spojeny v grafu G2 . Graf G1 tedy vzniká z grafu G2 vynecháním některých (nebo žádných) vrcholů a vynecháním některých (nebo žádných) hran. Přitom s odstraněním vrcholů musí být odstraněny i ty hrany, pro které jsou odstraněné vrcholy koncové. Planární grafy Problém jak rozmístit a jak malovat diagramy grafů souvisí i s velmi známým problémem teorie grafů, totiž charakterizovat ty grafy, kde je možno nalézt jejich diagramy tak, že se různé hrany neprotínají, tj. nemají společné body, samozřejmě mimo koncových vrcholů hran. Takovýmto grafům se říká planární (nebo rovinné) grafy, ostatním grafům se říká neplanární grafy.

6

Teorie grafů zná velmi pěkné řešení tohoto problému. Existují dva základní neplanární grafy. Jsou to úplný graf na pětiprvkové množině, který je zobrazen na obr. 5. Dalším je jistý graf se šestiprvkovou množinou vrcholů. Oba základní neplanární grafy jsou zobrazeny na obr. 7. Základní neplanární graf se šestiprvkovou množinou vrcholů je i zobrazením známé úlohy z rekreační matematiky, a to úlohy o „třech zahradních domcích a třech zařízeních”, která zní: propojte tři zahradní domky se třemi zařízeními (WC, koupelna, kůlna) tak, aby z každého zahradního domku do každého zařízení vedla přímá cesta a cesty se nekřížily. My tedy už víme, že požadavky úlohy nelze splnit.

´ kladn´i neplana ´ rn´i grafy Obr. 7: Za Na planaritu grafu nemá vliv odstraníme–li z grafu libovolný vrchol a, který je stupně dva a ty dvě hrany, jejichž koncovým vrcholem je právě vrchol a nahradíme jedinou novou hranou. Takovéto změny nazýváme zcelování hran. Dva grafy nazýváme homeomorfní, jestliže je možno jejich úpravami (obou grafů) metodou scelování hran dostat dva izomorfní grafy. Pro ilustraci jsou na obr. 8 zobrazeny diagramy dvou grafů, které jsou se základními neplanárními grafy homeomorfní. Každý z nich má dva odstranitelné vrcholy.

´ kladn´imi neplana ´rn´imi grafy Obr. 8: Grafy homeomorfn´i se za Již zmíněná krásná charakteristika neplanárních grafů je uvedena v následující větě. Věta. Neorientovaný graf je planární, právě tehdy, když neobsahuje žádný podgraf, který by byl s jedním ze základních neplanárních grafů izomorfní nebo homeomorfní. Tato charakteristika planárních grafů je důležitá nejen z hlediska matematického řešení problému. Planarita grafu má i důležitá použití v praxi, například v elektrotechnice při navrhování integrovaných obvodů a tištěných spojů. Sledy v grafech

7

V této části se vrátíme k „problému sedmi mostů v Královci”. Abychom se mohli vyjadřovat exaktněji, zavedeme si několik pojmů. Definice. Posloupnost s = (v1 , h1 , v2 , h2 , . . . , hn , vn+1 ) vrcholů a hran (spojujících tyto vrcholy) v grafu G = (V, H, p), tj. v1 , v2 , . . . , vn+1 ∈ V , h1 , h2 , . . . , hn a p(hi ) = {vi , vi+1 }, kde v = v1 a w = vn+1 budeme nazývat sledem grafu G mezi vrcholy v a w. Vrchol v je počáteční a vrchol w koncový vrchol sledu. Počet hran v posloupnosti, tj. n, nazýváme délkou sledu a budeme ji značit d(s). Pokud jsou počáteční a koncový vrchol sledu totožné, tj. v = w, nazýváme sled uzavřený a jsou–li počáteční a koncový vrchol sledu různé, tj. v 6= w, hovoříme o otevřeném sledu. Poznámka. Protože každé hraně přísluší jednoznačně dvojice koncových vrcholů, můžeme sled popisovat pouze pomocí hran. Tak sled s = (v1 , h1 , v2 , h2 , . . . , hn , vn+1 ) je možno popsat i posloupností s = (h1 , h2 , . . . , hn ). V případě prostých grafů, tj. grafů, které nemají žádné dvě rovnoběžné hrany, se nabízí i další možnost popisu sledu. Totiž jsou–li dva vrcholy prostého grafu spojeny hranou, pak tato hrana je určena jednoznačně, a proto můžeme sled s = (v1 , h1 , v2 , h2 , . . . , hn , vn+1 ) popsat i jako posloupnost vrcholů, tj. s = (v1 , v2 , . . . , vn+1 ). V praktických úlohách nás budou zejména zajímat zejména sledy, ve kterých se neopakují hrany nebo ve kterých se neopakují vrcholy. Toto je například nutnou podmínkou při hledání nejkratších sledů. V grafech mohou existovat sledy, ve kterých se neopakují hrany, ale opakují se vrcholy. Pokud se neopakují vrcholy, nemůže se ve sledu žádná hrana vyskytnout dvakrát. Definice. Sled mezi vrcholy v a w v grafu G budeme nazývat tahem, jestliže se v něm neopakuje žádná hrana (tj. je hi 6= hj pro i 6= j). Je–li v 6= w, hovoříme o otevřeném tahu a je–li v = w, hovoříme o uzavřeném tahu. Sled, ve kterém se neopakuje žádný vrchol, s výjímkou maximálně v = w, nazýváme cestou. Je–li v 6= w, hovoříme o otevřené cestě a je–li v = w, hovoříme o uzavřené cestě. Uzavřená cesta se také nazývá kružnicí. Graf G se nazývá souvislý graf, jestliže existuje sled mezi jeho každými dvěma vrcholy. Poznámka. Je velmi snadné ukázat, že pokud existuje v grafu G sled mezi vrcholy v a w, pak také existuje cesta mezi v a w. Toho dosáhneme tak, že pokud najdeme ve sledu nějaký vrchol a dvakrát, odstraníme všechny hrany mezi prvním a druhým výskytem vrcholu a. Tím dostaneme sled mezi vrcholy v a w, který je kratší. Po konečně mnoha krocích již takováto situace nemůže nastat a nám zůstane cesta mezi vrcholy v a w. Proto v souvislém grafu existuje mezi libovolnými dvěma vrcholy cesta. Je také jasné, že každá cesta v grafu G je také tahem (a sledem). Nemohou–li se totiž ve sledu opakovat hrany, nemohou se v něm opakovat ani vrcholy. Toto by ovšem neplatilo v případě multigrafů. Tah v grafu samozřejmě nemusí být cestou. Na obr. 9 jistě naleznete příklady tahů, ve kterých se nutně některé vrcholy opakují. Již dříve jsme zmínili, že každé dva navzájem izomorfní konečné neorientované grafy mají stejný počet vrcholů a stejný počet hran. Tato podmínka je pouze nutnou podmínkou a zdaleka ne postačující. Existují grafy, které nejsou izomorfní i když mají stejné počty vrcholů a hran. Na obr. 9 jsou zobrazeny diagramy pěti grafů. Každý graf má pět vrcholů a šest hran a žádné dva z těchto grafů nejsou izomorfní.

8

ˇti vrcholy a ˇ Obr. 9: Neizomorfn´i grafy s pe sesti hranami Izomorfní grafy musí mít i další vlastnosti stejné, například počet hran, které z vrcholu „odcházejí”, musí být pro odpovídající si vrcholy stejný. Tuto charakteristiku vrcholu si pojmenujeme jako stupeň vrcholu. Definice. Počet hran v konečném neorientovaném grafu G, pro které je vrchol v grafu G koncovým vrcholem, nazveme stupněm vrcholu v a budeme ho označovat st(v). Jestliže vrchol v grafu G není koncovým vrcholem žádné hrany, je st(v) = 0. Poznámka. Pokud v grafu G existuje smyčka kolem vrcholu a, pak je bod a považován za počáteční i koncový bod hrany a smyčka tak zvyšuje stupeň vrcholu a o dva. Z toho, že dva grafy mají stený počet vrcholů stejných stupňů a stejný počet hran, ještě zdaleka neplyne, že musí být izomorfní. Vidíme to například na obr. 9, kde první i druhý graf mají dva vrcholy stupně tři a tři vrcholy stupně dva a oba mají šest hran a přesto nejsou izomorfní. Je zřejmé, že každá hrana grafu přispívá do součtu stupňů všech vrcholů právě číslem dva. Z tohoto faktu ihned plyne následující tvrzení. Věta. V konečném neorientovanémP grafu G = (V, H, p) je součet stupňů všech vrcholů st(v) = 2 · |H|, kde |H| označuje počet prvků roven dvojnásobku počtu hran, tj. v∈V

množiny H. Proto graf G buďto nemá žádný vrchol lichého stupně nebo jich má sudý počet. Nyní si ukážeme řešení „problému sedmi mostů v Královci”. Platí následující věta. Věta. Nechť G je konečný souvislý neorientovaný graf. Potom existuje uzavřený tah, který obsahuje všechny hrany grafu (tzv. Eulerův tah) právě tehdy, když každý vrchol grafu G má sudý stupeň. Je jasné, že pokud v grafu G existuje Eulerův tah, pak nutně každý vrchol je sudého stupně. To vidíme například tak, že si tento tah projdeme. Jistě platí, že kolikrát do nějakého vrcholu přijdeme, tolikrát z něho musíme odejít, a tedy stupeň vrcholu je sudý. Obráceně je důkaz věty komplikovanější. Mějme tedy graf G, jehož každý vrchol je sudého stupně. Vyberme nějaký jeho vrchol, například vrchol a. Vrchol a je sudého stupně, a proto existuje hrana h1 , jejíž koncové vrcholy jsou a, b (a 6= b). Vrchol b je sudého stupně, a proto existuje hrana h2 , jejíž koncové vrcholy jsou b, c (b 6= c). Takto vytváříme tah t1 = (a, h1 , b, h2 , . . . ) tak dlouho, až se opět dostaneme do bodu a. Tam se dostat musíme díky tomu, že každý vrchol je sudého stupně a že jsme použili pouze jednu hranu vycházející z vrcholu a. Pokud jsou v tomto tahu obsaženy všechny hrany grafu G, jsme hotovi. Předpokládejme naopak, že v tomto tahu t1 nejsou obsaženy všechny

9

hrany grafu G. Potom existuje vrchol x, který je obsažen v našem tahu t1 a který je koncovým bodem hrany (označme ji g), která v tahu t1 není obsažena. Nechť y je druhý koncový bod této hrany g. Podgraf H grafu G, který je tvořen všemi hranami grafu (a jejich koncovými vrcholy), které nejsou obsaženy v tahu t1 splňuje opět podmínku, že každý vrchol grafu H má sudý stupeň (počítají se zde hrany patřící do H). Postup proto můžeme opakovat v grafu H, s tím, že vytváříme uzavřený tah h = (x, g1 , y, . . . , x) v grafu H, který začíná a končí ve vrcholu x. Nyní vytvoříme tah t2 v grafu G, který vznikne spojením tahů t1 a h. Bude to tah t2 = (a, h1 , b, h2 , . . . , x, g1 , y, . . . , x . . . , a). Nyní jsou opět dvě možnosti: buďto je tah t2 hledaným tahem, nebo existuje vrchol z, který je obsažen v tahu t2 a který je koncovým bodem hrany, která v tahu t2 není obsažena. Nyní nalezneme tah m = (z, . . . , z), který následně spojíme s tahem t2 . Tento postup musí skončit po konečném počtu kroků nalezením Eulerova tahu. Postup uvedený v důkazu věty si můžeme ilustrovat na prvním grafu na obr. 10. Vyjděme z bodu 0. Tah budeme vyjadřovat pomocí vrcholů. První uzavřený tah může být t1 = (0, a, 1, b, 0), přidáním dalšího tahu dostaneme tah t2 = (0, a, 1, c, 0, d, 1, b, 0) a ve třetím kole dostaneme Eulerův tah t2 = (0, a, 1, c, 0, d, 1, e, 0, f, 1, b, 0). Další grafy, jejichž diagramy jsou na obr. 10, jsou také tzv. Eulerovy grafy, tj. grafy, ve kterých existuje Eulerův tah. V řeči rekreační matematiky je možno jejich diagram „namalovat” jedním tahem a při „malování” začít a skončit ve stejném vrcholu. U těchto grafů je naprosto jedno, ve kterém vrcholu grafu začneme vytvářet Eulerův tah. Eulerovým grafem je také každý úplný graf, který má lichý počet vrcholů. Dva takové lze nalézt na obr. 5.

Obr. 10: Eulerovy grafy Jednoduše z minulé věty dostaneme charakterizaci těch grafů, ve kterých existuje otevřený tah, který v sobě obsahuje všechny hrany daného grafu. Předpokládejme, že v souvislém konečném grafu G = (V, H, p) existuje otevřený tah (obsahující všechny jeho hrany), který začíná v nějakém vrcholu a a končí v jiném vrcholu b (tj. a 6= b). Vytvořme nový graf G0 = (V 0 , H 0 , p0 ) tak že ke grafu G přidáme právě jeden nový vrchol z (tj. V 0 = V ∪ {z}) a dvě nové hrany h1 a h2 (tj. H 0 = H ∪ {h1 , h2 }), které spojují vrcholy a, z a b, z (tj. p0 (h1 ) = {z, a}, p0 (h2 ) = {b, z}) a vše ostatní je nezměněno (tj. p0 (h) = p(h) pro h ∈ H). Nyní v tomto grafu G0 existuje uzavřený tah, který obsahuje všechny hrany grafu G0 . Stačí totiž k otevřenému tahu z grafu G přidat hrany h2 a h1 a dostáváme Eulerův tah v grafu G0 . Stupně vrcholů grafu G0 jsou tedy sudá čísla. Protože se v grafu G0 zvětšily stupně obou vrcholů a, b o jednotku, musely být v grafu G stupně vrcholů a, b lichá čísla.

10

Naformulujme si to jako větu. Věta. Nechť G je konečný souvislý neorientovaný graf. Potom existuje otevřený tah, který obsahuje všechny hrany grafu právě tehdy, když má graf G dva vrcholy lichého stupně a ostatní vrcholy jsou sudého stupně. Tento tah musí začínat v jednom z vrcholů lichého stupně a končí ve druhém vrcholu lichého stupně. Na obr.11 jsou zobrazeny diagramy čtyř grafů, ve kterých existuje otevřený tah obsahující všechny hrany, tj. jejich diagram je možno „namalovat” jedním tahem. Ke každému grafu přidejte jeden vrchol a dvě hrany tak, aby vznikl Eulerův graf. Každý graf také obsahuje Eulerův podgraf, který z daného grafu vzniká odstraněním jedné hrany.

ˇeny ´m tahem obsahuj´ic´im vˇ Obr. 11: Grafy s otevr sechny jeho hrany Stromy Velmi důležitými typy grafů jsou ty grafy, jejichž struktura je nějakým způsobem přehledně popsatelná. Extrémní grafy, jako jsou úplné grafy nebo diskrétní grafy, jsou příkladem jednoduše popsatelných grafů. Další velmi důležitou třídou grafů jsou grafy, které nemají kružnice. Připomeňme, že za kružnici považujeme každou uzavřenou cestu. Délkou kružnice rozumíme počet jejích hran. Je samozřejmé, že minimální délka kružnice je 3. Definice. Graf G, který neobsahuje žádnou kružnici, budeme nazývat les. Graf G, který je souvislý a neobsahuje žádnou kružnici, budeme nazývat strom. Stromy mají velký význam v teorii grafů a aplikacích teorie grafů. K popisu vztahů je používají i lidé, kteří ani netuší, že existuje něco jako teorie grafů. Sem patří například i rodokmeny lidí či průkazy původu u psů apod. Graf, který obsahuje kružnice, zřejmě obsahuje i hrany, které jsou zbytečné pro dodržení požadavku souvislosti grafu, tj. pro dodržení existence cest spojujících libovolné dvojice vrcholů. Stromy takto zbytečné hrany neobsahují, což je velmi důležité v praktických aplikacích. Z čistě matematického hlediska jsou stromy velmi dobře charakterizovatelnou třídou grafů. To uvidíme v následujících větách. Les je disjunktní sjednocení jednoho či více stromů. Na obr. 12 je zobrazen les, který se skládá ze čtyř stromů. Věta. Nechť G je konečný souvislý neorientovaný graf bez kružnic, tj. strom. Má–li G alespoň dva vrcholy, pak má G alespoň dva vrcholy stupně 1. Dokažme to. V konečném grafu zcela jistě existuje cesta, která má ze všech možných cest největší délku. Nechť tato cesta spojuje vrcholy a a b. Nechť x je vrchol na této cestě

11

´ je sjednocen´im c ˇtyr ˇ strom˚ Obr. 12: Les, ktery u a nechť h1 je hrana spojující vrcholy a, x. Předpokládejme dále, že je stupeň vrcholu a alespoň 2. Potom existují vrchol y a hrana h2 , takové že hrana h2 spojuje vrcholy a, y a vrchol y neleží na naší cestě (jinak by v grafu existovala kružnice). Pak ovšem můžeme nejdelší možnou cestu prodloužit o vrchol y (a hranu h2 ), což je ve sporu s maximalitou cesty. Stupeň vrcholu a musí tedy být 1. Obdobně musí být st(b) = 1. Je snadné ukázat, že přidání jedné hrany ke stromu (při zachování stromu) musí být doprovázeno přidáním jednoho vrcholu. Na základě tohoto faktu se již dá dokázat následující charakterizace stromů. Věta. Nechť G je konečný souvislý neorientovaný graf s n vrcholy. Graf G je stromem, právě tehdy, když má n − 1 hran. Důsledkem je, že každý konečný souvislý neorientovaný graf s n vrcholy musí mít alespoň n − 1 hran. Je více vlastností, které jednoznačně charakterizují stromy. Některé z nich si uvedeme v následující větě. Věta. Nechť G je konečný neorientovaný graf s n vrcholy, kde n ≥ 1. Následující tvrzení jsou ekvivalentní: 1. G je strom; 2. G neobsahuje kružnici a má právě n − 1 hran; 3. G je souvislý a má právě n − 1 hran; 4. G je souvislý a odebráním kterékoliv hrany přestane být souvislý; 5. každá dvojice vrcholů G je spojena právě jednou neorientovanou cestou. Důležitými podgrafy grafu G jsou ty podgrafy, které vznikají z grafu G vynecháním některých hran a žádných vrcholů. Takovéto podgrafy se nazývají faktory grafu G. Definice. Podgraf grafu G, který obsahuje všechny jeho vrcholy, budeme nazývat faktor grafu G. Faktor grafu G, který je navíc stromem budeme nazývat kostrou grafu G. Poznámka. Faktor grafu G je tedy podgraf, který vznikl z grafu G = (V, H, p) ponecháním všech jeho vrcholů a případným vynecháním některých jeho hran. Extrémními případy faktorů grafu G jsou celý graf G (nevynechána žádná hrana) a diskrétní graf (vynechány všechny hrany) daný množinou vrcholů V . Poznámka. Každý konečný souvislý graf má zcela jistě nějakou kostru, kterou získáme případným vynecháváním nějakých hran. Je zřejmé, že kostra grafu nemusí být určena jednoznačně a kostry grafu nemusí být ani izomorfní. Pokud souvislý graf není stromem, pak obsahuje kružnici, která má alespoň tři hrany. Odebíráním hran kružnice dostáváme různé grafy a následně získáme, že takový graf má alespoň dvě různé kostry. Například

12

úplný graf U (3) se třemi vrcholy obsahuje právě jednu kružnici (trojúhelník) a tři různé kostry, které vznikají z grafu vynecháním právě jedné hrany kružnice. Tyto tři různé kostry jsou navzájem izomorfní. Příklad grafu, který má různé neizomorfní kostry je zobrazen na obr. 13. Zde je zobrazen graf a jeho tři navzájem neizomorfní kostry.

ˇi neizomorfn´i kostry Obr. 13: Graf a jeho tr Příklad. Nalezněme všechny kostry úplného grafu U (4) se čtyřmi vrcholy. Kolik z nich je neizomorfních? Všechny kostry úplného grafu U (4) jsou zobrazeny na následujícím obrázku. Z obrázku vidíme, že graf U (4) má 16 různých koster. Neizomorfní kostry jsou pouze dvě.

´ plne ´ho grafu U (4) Obr. 13-1: Kostry u Příklad. Na následujícím obrázku je znázorněn graf T (n). Určeme kolik má graf T (n) různých koster. Dále určeme maximální možný počet neizomorfních koster.

..... 1

2

3

n

Obr. 13-2: Graf T (n) Graf T (1) má tři různé kostry, všechny jsou navzájem izomorfní. Graf T (2) má 3·3 = 9 různých koster. Graf T (2) obsahuje jediný vrchol stupně 4. V kostře grafu T (2) může tento vrchol mít stupeň 2, 3 nebo 4. Ve čtyřech kostrách má vrchol stupeň 2 a všechny tyto kostry jsou izomorfní, ve čtyřech kostrách má vrchol stupeň 3 a opět jsou všechny tyto kostry jsou izomorfní. V jedné jediné kostře má tento vrchol stupeň 3. Graf T (2) má

13

3 neizomorfní kostry. Kostra grafu T (2) může být rozšířena na kostru grafu T (3) třemi způsoby, z toho jsou dvě rozšíření izomorfní. Graf T (3) má tedy celkem 3·9 = 27 různých koster a maximálně 3·2 = 6 neizomorfních koster. V této úvaze můžeme pokračovat dále a dostaneme, že graf T (n) má celkem 3n různých koster a maximálně 2·3n−1 neizomorfních koster. Ukažte, že neizomorfních koster je ve skutečnosti méně než 2 · 3n−1 . Příklad. Na následujícím obrázku je znázorněn graf V (n). Určeme kolik má graf V (n) různých koster. Graf V (1) má 3 různé kostry. Graf V (2) musí mít 9 různých koster protože každou kostru grafu V (1) lze rozšířit třemi různými způsoby na kostru grafu V (2). Zcela obecně platí: má-li graf V (n) prřesně k(n) koster, pak každou z nich lze rozšířit třemi různými způsoby na kostru grafu V (n + 1). Proto platí k(n + 1) = 3 · k(n). Jelikož je k(1) = 3, je počet různých koster grafu V (n) roven číslu k(n) = 3n .

..... 1

2

3

n

Obr. 13-2: Graf V (n) Hledání kostry grafu Najít kostru souvislého grafu, který má malý počet vrcholů a hran není obtížné, to po chvíli vždy nějakou kostru nalezneme. V případech grafů s velkým počtem vrcholů a hran je potřeba postup hledání kostry grafu fomulovat nějak precizněji, nejlépe tak, aby úloha mohla být řešena algoritmicky. Jednu takovou možnost si ukážeme. Algoritmus hledání kostry grafu Mějme konečný souvislý ohodnocený graf G = (V, H, p) o n vrcholech, který nemá rovnoběžné hrany (jinak ponecháme pouze jednu). Hrany grafu si nějakým libovolným způsobem očíslujeme. Dostaneme, že je H = {h1 , h2 , . . . , hk }. Pro lepší porozumění algoritmického postupu uvedeme inicializaci algoritmu, první krok a poté obecný krok a ukážeme, kdy algoritmus končí. 1. (inicializace algoritmu) Vyjdeme z diskrétního grafu (H = ∅) s množinou vrcholů V . Tento faktor grafu G označme F0 = (V, ∅). 2. (první krok) Vezměme první hranu v posloupnosti hran (h1 , h2 , . . . , hk ). Nechť jsou vrcholy a, b koncovými vrcholy hrany h1 . Označme H1 = {h1 } a symbolem V1 = {a, b} označíme vrcholy grafu, které jsou koncovými vrcholy hran z H1 . Faktor grafu G, který obsahuje pouze hrany z H1 , označíme F1 = (V, H1 ). 3. (k–tý krok) Mějme faktor Fk−1 = (V, Hk−1 ) a množinu Vk−1 . Nyní vezmeme první hranu h z posloupnosti hran (h1 , h2 , . . . , hk ), která splňuje tyto dvě podmínky: (∗) h 6∈ Hk−1 , (∗∗) jeden z koncových vrcholů hrany h patří do Vk−1 a druhý nepatří do Vk−1 . Tuto hranu přidáme do vytvářeného faktoru. Nechť x je koncový vrchol hrany h, x 6∈ Vk−1 . Označme Hk = Hk−1 ∪ {h}, Vk = Vk−1 ∪ {x} a Fk = (V, Hk ).

14

4. (konec algoritmu) Algoritmus končí jakmile je Vk = V , což ale nastává právě tehdy, když je k = n − 1. Čili algoritmus končí po provedení n − 1 kroků. 5. (složitost algoritmu) Vzhledem k tomu, že v průběhu tvorby kostry grafu testujeme každou hranu, je časová složitost algoritmu O(m), kde m je počet vrcholů grafu. Chceme–li vyjádřit časovou složitost algoritmu na základě počtu vrcholů grafu, zjistíme, že je časová složitost kvadratická (tj. O(n2 )), protože graf mající n vrcholů může mít až n2 · (n − 1) hran. Poznámka. Existence hrany h v k–tém kroku je dána tím, že graf G je souvislý. Pokud tedy nejsou ve vytvářené kostře grafu obsaženy všechny vrcholy grafu, existuje alespoň jeden, který tam není obsažen. Jelikož ale existuje cesta spojující tento vrchol s vrcholem a, musí existovat i hrana, která má jeden vrchol v množině Vk−1 a druhý mimo tuto množinu. Podmínka (∗∗) v k–tém kroku zaručuje, že při postupu tvorby kostry grafu nevzniknou kružnice. Postup popsaný v tomto algoritmu je ilustrován na obr. 14. Postupně vznikají faktory grafu, jejichž množiny hran jsou množiny H1 = {h1 }, H2 = {h1 , h2 }, H3 = {h1 , h2 , h3 }, H4 = {h1 , h2 , h3 , h6 }, H5 = {h1 , h2 , h3 , h6 , h7 }, H6 = {h1 , h2 , h3 , h6 , h7 , h10 } a v posledním kroku to je kostra H7 = {h1 , h2 , h3 , h6 , h7 , h10 , h11 }. Zkuste si hrany grafu očíslovat jinak a můžete dostat jinou kostru grafu.

h1

h3 h4

h10

h6

h2 h5

h7 h8

h9

h11 h13

h2 h1

h3

h6 h7

h10 h11

h12

Obr. 14: Graf a jeho kostra Poznámka. Pokud nalezneme kostru neorientovaného souvislého grafu G, pak již bez problémů můžeme určit cestu mezi libovolnými dvěma vrcholy grafu. Kostru grafu je souvislý podgraf a cesta mezi libovolnými dvěma vrcholy grafu je na kostře určena jednoznačně. Samozřejmě tato cesta nemusí být nejkratší cestou, jak ostatně vidíte na obr. 14. Problém najít nejkratší cestu mezi dvěma vrcholy konečného souvislého neorientovaného grafu je mnohem složitější problém a musí se řešit pro každou dvojici vrcholů zvlášť. S řešením zmíněného problému se seznámíme později. Ohodnocené grafy Z předchozích částí víme, že mnohé úlohy teorie grafů, například nalézt cestu mezi vrcholy a a b nebo nalézt kostru grafu, mohou mít více řešení. V reálných aplikacích, je možné z nich vybírat nějakým způsobem optimální. Přitom tyto optimální podmínky nemusí vůbec souviset s počtem hran či vrcholů. Proto se jeví pro praktická použití studovat i grafy, ve kterých má každá hrana nějakou hodnotu, např. délku v kilometrech, časovou či finanční náročnost pro průchod hranou. Proto si uvedeme několik základních informací o tzv. ohodnocených grafech. Definice. Ohodnoceným neorientovaným grafem G rozumíme trojici G = (V, H, p, c), kde G = (V, H, p) je neorientovaný graf a c je zobrazení množiny H do množiny všech reálných čísel R, které budeme nazývat ohodnocení hran (resp. cenou hran).

15

Poznámka. Přirozené je předpokládat, že ohodnocení hran c bude nezáporné. Toto bude zcela jistě platit ve většině reálných úloh. V některých případech však i záporné ohodnocení hrany má svůj význam. Budeme–li například sledovat finanční výnosnost vložených prostředků (na účtech, v různých fondech apod.), mohou některé operace (například zřízení účtu, náklady s vedením účtu či vstupní poplatky), nabývat i záporných hodnot. Proto se v definici neomezujeme pouze na nezáporná ohodnocení. Ve skutečných aplikacích mohou být grafy ohodnoceny i vícenásobně. Je přirozené například sledovat při cestě automobilem z Prahy do Ostravy nejen kilometrovou vzálenost (1. ohodnocení), ale též časovou náročnost (2. ohodnocení) a jistě i finanční náročnost (3. ohodnocení). A najít v takovémto případě optimální cestu je velmi složité a závisí na exaktně vyjádřených prioritách a důležitosti jednotlivých ohodnocení. V předcházející části jsme si ukázali algoritmus pro nalezení kostry daného konečného neorientovaného grafu. Kostra takového grafu nám zaručuje existenci cesty spojující libovolné dva vrcholy grafu. V reálných situacích, např. při nutnosti zajistit spojení mezi libovolnými dvěma městy nějakého regionu, může hrát i velmi významnou úlohu cena tohoto zajištění (třeba cena údržby silnic v zimních měsících). Je proto velmi praktickou úlohou nalézt nějakou kostru grafu, kde součet ohodnocení všech hran na kostře je minimální. Proto bude nutné algoritmus z předchozí části trochu pozměnit. Ve zmíněném algoritmu jsme důsledně zakazovali existenci kružnic. V ohodnoceném grafu nesmí samozřejmě kostra obsahovat kružnice, ale při vytváření kostry se může stát, že přidáním nějaké hrany (při kterém by vznikala kružnice, což bylo nemyslitelné) by mohlo při současném odebrání jiné hrany dojít ke „zlevnění ceny kostry”. V tomto smyslu je proto nutno algoritmus hledání kostry v ohodnoceném grafu modifikovat. Existuje několik různých řešení, jak tento požadavek splnit. Ukážeme si nyní algoritmus, který požadavek splňuje a je přitom velmi jednoduchou modifikací již uvedeného algoritmu hledání kostry v neohodnoceném grafu. Algoritmus hledání kostry nezáporně ohodnoceného grafu Mějme konečný souvislý ohodnocený graf G = (V, H, p, c) o n vrcholech. Hrany grafu si očíslujeme tak, že je H = {h1 , h2 , . . . , hk } a c(h1 ) ≤ c(h2 ) ≤ · · · ≤ c(hk ). Při popisu algoritmického postupu uvedeme pouze inicializaci algoritmu a poté obecný krok a ukážeme, kdy algoritmus končí. 1. (inicializace algoritmu) Vyjdeme z diskrétního grafu (H = ∅) s množinou vrcholů V . Tento faktor grafu G označme F0 = (V, ∅). 2. (k–tý krok) Mějme faktor Fk−1 = (V, Hk−1 ) a množinu Vk−1 . Nyní vezmeme první hranu h z posloupnosti hran (h1 , h2 , . . . , hk ), která splňuje tyto dvě podmínky: (∗) h 6∈ Hk−1 , (∗∗) jeden z koncových vrcholů hrany h patří do Vk−1 a druhý nepatří do Vk−1 . Tuto hranu přidáme do vytvářeného faktoru. Nechť x je koncový vrchol hrany h, x 6∈ Vk−1 . Označme Hk = Hk−1 ∪ {h}, Vk = Vk−1 ∪ {x} a Fk = (V, Hk ). 3. (konec algoritmu) Algoritmus končí jakmile je Vk = V , což ale nastává právě tehdy, když je k = n − 1. Čili algoritmus končí po provedení n − 1 kroků. 4. (složitost algoritmu) Časová složitost algoritmu pro graf s n vrcholy je O(n2 ), časová složitost setřídění m hran do neklesající posloupnosti dle jejich cen má při jednoduchých třídících programech časovou složitost O(m2 ), při lepších programech je nejlepší možná časová složitost O(m·log m). Celkově se vždy jedná o algoritmus s polynomiální časovou složitostí. Správnost algoritmu je třeba dokázat. Nejjednoduší asi bude ukázat matematickou

16

indukcí tvrzení: pro každé přirozené číslo k ∈ {0, 1, . . . n − 1} existuje minimální kostra grafu G, která obsahuje faktor Fk jako podgraf. 1. krok (platost tvrzení pro F1 = (V, H1 )) Nechť K = (V, HK ) je nějaká minimální kostra grafu G. Předpokládejme, že kostra K neobsahuje hranu h1 , která spojuje vrcholy a a b. Kostra K (stejně jako každá jiná kostra) v sobě obsahuje cestu mezi vrcholy a, b. Přidáním hrany h1 k podgrafu F1 = (V, H1 ) v něm vznikne kružnice. Odstraňme nyní libovolnou hranu této kružnice, označme ji g. Kostra obsahující hrany (HK ∪ h1 ) \ g je opět kostra grafu G a její cena nemůže být větší, protože je c(h1 ) ≤ c(g). Existuje tedy minimální kostra grafu G, která v sobě obsahuje hranu h1 . 2. krok (indukční) Předpokládejme, že tvrzení platí pro faktor Fi = (V, Hi ) pro nějaké i < n − 2. Nechť K = (V, HK ) je nějaká minimální kostra grafu G, která obsahuje jako svůj podgraf faktor Fi = (V, Hi ) a nechť h je první hrana v posloupnosti hran (h1 , h2 , . . . , hk ), která splňuje podmínky (∗) a (∗∗), nechť její koncové vrcholy jsou x ∈ Vi a y 6∈ Vi . Předpokládejme, že hrana h není obsažena v kostře K. Kostra K v sobě obsahuje cestu mezi vrcholy x, y. Přidáním hrany h ke kostře K tak vznikne kružnice a alespoň jedna hrana této kružnice, označme ji w, má jeden koncový vrchol ve Vi a druhý mimo Vi . Odstraňme nyní hranu w této kružnice. Faktor grafu G obsahující hrany (Hi ∪ h) \ w je opět kostra grafu G a její cena nemůže být větší, protože je c(h) ≤ c(w) (h je první hrana v posloupnosti hran, která má jeden koncový vrchol ve Vi a druhý mimo Vi ). Existuje tedy minimální kostra grafu G, která v sobě obsahuje hranu h. Postup algoritmu je ilustrován na obr. 15. Zde si hrany označíme pomocí jejich koncových vrcholů. Hrany si zároveň očíslujeme podle jejich ceny tak, aby cena hran neklesala. Dostaneme h1 = {c, d}, h2 = {d, f }, h3 = {e, g}, h4 = {b, d}, h5 = {a, c}, h6 = {c, f }, h7 = {g, h}, h8 = {e, h}, h9 = {a, b}, h10 = {a, d}, h11 = {f, h}, h12 = {c, e} a h13 = {e, f }. Prováděním algoritmu získáváme: H1 = {h1 }, H2 = {h1 , h2 }, H3 = {h1 , h2 , h4 }, H4 = {h1 , h2 , h4 , h5 }, H5 = {h1 , h2 , h4 , h5 , h11 }, H6 = {h1 , h2 , h4 , h5 , h11 , h7 } a nakonec H7 = {h1 , h2 , h4 , h5 , h11 , h7 , h3 }, což je minimální kostra. Cena minimální kostry je 12. Poznámka. Pokud bychom na začátku algoritmu hrany seřadili v jiném pořadí při dodržení podmínky neklesání cen, mohli bychom získat i jiné kostry. Kdybychom v našem příkladě zaměnili pořadí hran h7 = {g, h} a h8 = {e, h} na h7 = {e, h}, h8 = {g, h}, minimální kostra by místo hrany {g, h} obsahovala hranu h7 = {e, h}. Je zřejmé, že při vytváření minimální kostry grafu nejsou ani tak důležité skutečné ceny hran, důležité jsou cenové relace mezi hranami. Pokud by žádné dvě hrany neměly stejnou cenu, pak je minimální kostra grafu určena zcela jednoznačně.

a 3 b

2 3 2

c 1 d

4 2 1

e 4 f

1 2 3

g

a

2

2 h

c

e

1

1 b

2

d

g 2

1

f

3

h

´ ln´i kostra Obr. 15: Graf a jeho minima Poznámka. V předchozím algoritmu jsme při hledání kostry postupně vytvářely podgraf, který byl souvislý a bez kružnic (tedy strom). Kdybychom opustili požadavek sou-

17

vislosti obsažený v podmínce ∗∗, a tuto podmínku nahradili obecnější podmínkou „nemožnost vzniku kružnice”, což je také obsaženo v podmínce ∗∗, dostali bychom poněkud jiný algoritmus, který je nazýván hladovým algoritmem. Je možno ho stručně formulovat následujícím způsobem. Hladový algoritmus hledání minimální kostry nezáporně ohodnoceného grafu Hrany grafu uspořádáme (očíslujeme) tak, aby jejich cena neklesala. Poté hrany v tomto pořadí probíráme v uvedeném pořadí a do vytvářeného faktoru přidáváme ty hrany, jejichž přidáním nevzniká kružnice. Algoritmus můžeme ukončit po probrání všech hran nebo tehdy, je–li počet hran ve vytvářeném faktoru o jedno menší než počet vrcholů výchozího grafu. Při použití tzv. hladového algoritmu bychom v našem příkladě (z obr. 15) dostávali postupně tyto faktory: H1 = {h1 }, H2 = {h1 , h2 }, H3 = {h1 , h2 , h3 }, H4 = {h1 , h2 , h3 , h4 }, H5 = {h1 , h2 , h3 , h4 , h5 }, H6 = {h1 , h2 , h3 , h4 , h5 , h11 } a H7 = {h1 , h2 , h3 , h4 , h5 , h11 , h7 }, což je hledaná minimální kostra. Poznámka. Je velmi jednoduché ukázat, že je možno také algoritmicky nalézt maximální kostru grafu (tj. kostru s maximálním součtem ohodnocení hran). Stačí modifikovat tzv. hladový algoritmus. Hrany grafu uspořádáme (očíslujeme) tak, aby jejich cena nerostla a poté budeme hrany v tomto pořadí probírat a do vytvářeného faktoru přidávali pouze ty hrany, jejichž přidáním nevzniká kružnice. Algoritmus skončí, je–li počet hran ve vytvářeném faktoru o jedno menší než počet vrcholů výchozího grafu. Na obr. 16 je nalezena tímto postupem maximální kostra daného grafu. Hrany grafu si očíslujeme, tak aby jejich cena nerostla. Můžeme to udělat například takto: h1 = {c, e}, h2 = {e, f }, h3 = {a, b}, h4 = {a, d}, h5 = {f, h}, h6 = {a, c}, h7 = {b, d}, h8 = {c, f }, h9 = {e, h}, h10 = {g, h}, h11 = {c, d}, h12 = {d, f } a h13 = {e, g}. Ověřte, že při tomto očíslování hran je c(h1 ) = c(h2 ) = 4, c(h3 ) = c(h4 ) = c(h5 ) = 3, c(h6 ) = c(h7 ) = c(h8 ) = c(h9 ) = c(h10 ) = 2 a c(h11 ) = c(h12 ) = c(h13 ) = 1. Maximální kostru grafu získáme postupným přidáváním hran v pořadí h1 , h2 , h3 , h4 , h5 , h6 , h10 . Cena maximální kostry grafu je 21.

a 3 b

2 3 2

c 1 d

4 2 1

e 4 f

1 2 3

g 2 h

a 3 b

2

c

4

e

g

4

3 d

f

2 3

h

´ ln´i kostra Obr. 16: Graf a jeho maxima Hledání minimálních cest Je samozřejmé, že pokud známe minimální kostru v konečném souvislém ohodnoceném grafu, tak jsme schopni nalézt i cestu, která spojuje libovolné předem určené vrcholy grafu. Tyto cesty ale nemusí být ani zdaleka minimální (vzhledem k součtu cen všech hran na cestě), což můžeme například velmi dobře vidět v případě cesty mezi vrcholy c a e v grafu na obr. 15. Protože v konečném souvislém ohodnoceném grafu je jen konečně mnoho cest mezi danými vrcholy, určitě musí existovat i minimální cesty mezi libovolnými dvěma vrcholy. Hledáním takových cest se budeme nyní zabývat. Zároveň si

18

uvědomme, že si současně ukážeme i hledání minimálních cest (vzhledem k počtu všech hran na cestě) spojujících dané vrcholy konečného souvislého (a neohodnoceného) grafu. Stačí totiž každou hranu ohodnotit stejně, např. cenou 1, a máme ohodnocený graf, kde minimální cena cesty je totéž jako minimální počet hran na cestě. Při hledání minimálních cest spojujících dva vrcholy u a v grafu G budeme chtít znát nejen cenu cesty, ale také i cestu samotnou, tj. pořadí vrcholů, přes které minimální cesta vede. Vyjdeme z jednoho z vrcholů, např. z vrcholu u a zjistíme jedním postupem minimální cesty do všech ostatních vrcholů. V průběhu zpracovávání úlohy si budeme u každého vrcholu x uchovávat „dočasně nejlepší cestu od vrcholu u do x”, která se postupně bude stávat „trvale nejlepší cestou od vrcholu u do x”. Algoritmus, který si uvedeme, je klasický algoritmus a v literatuře je nazýván Dijkstrův algoritmus. Dijkstrův algoritmus hledání minimální cesty Mějme konečný souvislý graf (G, V, H), jehož hrany jsou ohodnoceny nezápornými čísly, tj. zobrazením h : H → h0, ∞). Můžeme předpokládat, že graf neobsahuje rovnoběžné hrany. V opačném případě vždy ponecháme mezi dvěma vrcholy pouze jednu hranu, a to hranu s nejmenší cenou. Nechť u je vrchol grafu G. Pro každý vrchol v, v 6= u, nechť C = (u, . . . , P (v), v) je minimální cesta mezi vrcholy u a v, nechť H(v) je cena této minimální cesty a nechť P (v) označuje vrchol, který na této cestě předchází vrcholu v. Symboly dH(v) a dP (v) budeme označovat „dočasně nejmenší délku cesty do vrcholu v” a „dočasného předchůdce vrcholu v” (v průběhu zpracovávání algoritmu se mohou i několikrát změnit). Symbolem T budeme značit tu množinu vrcholů x grafu G, kde již platí dH(x) = H(x) a dP (x) = P (x), tj. kde jsou již údaje H(x) a P (x) získány. Cenu hrany, která spojuje vrcholy x a y budeme značit h(x, y). Při popisu algoritmu popíšeme pro větší názornost také první krok algoritmu, i když to není nutné. První krok je speciálním případem obecného kroku. 1. (inicializace algoritmu) Definujeme T = T0 = {u} a H(u) = 0. Pro každý vrchol x, který je spojen hranou s vrcholem u, definujeme dH(x) = h(u, x) a dP (x) = u. Pro ostatní vrcholy grafu definujeme dH(x) = ∞ (nebo nějaké dostatečně velké číslo) a dP (x) označíme nějakým nesmyslným symbolem, třeba ∗. 2. (první krok) Vybereme ten vrchol, pro který je dH(x) minimální. Nechť je to vrchol w. Označme T = T1 = T0 ∪{w} a H(w) = h(u, w), P (w) = u. U každého vrcholu x, který je spojen hranou s vrcholem w, porovnáme hodnoty dH(x) a H(w) + h(w, x). Jestliže je dH(x) ≤ H(w) + h(w, x), ponecháme hodnoty dH(x) a dP (x) = u beze změn. Je–li ale H(w) + h(w, x) < dH(x), pak změníme hodnoty dH(x) a dP (x). Dosavadní hodnotu dH(x) nahradíme hodnotou H(w)+h(w, x) a dosavadní hodnotu předchůdce dP (x) = u nahradíme novým předchůdcem w. Dále tedy bude dH(x) = H(w)+h(w, x) a dP (x) = w. 3. (obecný k–tý krok). Máme již množinu T = Tk−1 a pro každé x ∈ Tk−1 i H(x) a P (x). Vybereme ten vrchol m grafu, který nepatří do T a jehož dočasná hodnota dH(m) je minimální. Vrchol m přidáme do množiny T , bude tedy T = Tk = Tk−1 ∪ {m}, dále hodnotu dH(m) prohlásíme za trvalou hodnotu, tj. definujeme H(m) = dH(m) a dočasného předchůdce prohlásíme ze trvalého, tj. definujeme P (m) = dP (m). U každého vrcholu x, který je spojen hranou s vrcholem m, porovnáme hodnoty dH(x) a H(m) + h(m, x). Jestliže je dH(x) ≤ H(m) + h(m, x), ponecháme hodnoty dH(x) a dP (x) beze změn. Je–li ale H(m) + h(m, x) < dH(x), pak změníme hodnoty dH(x) a dP (x). Dosavadní hodnotu dH(x) nahradíme hodnotou H(m) + h(m, x) a dosavadní hodnotu předchůdce dP (x) nahradíme novým předchůdcem m. V dalších krocích tedy bude dH(x) = H(m) + h(m, x) a dP (x) = m.

19

4. (konec algoritmu) Algoritmus končí v okamžiku, kdy je Tn−1 = V . Tedy algoritmus končí jakmile všem vrcholům x grafu jsou přiřazeny trvalé hodnoty H(x) a P (x). Při každém kroku se množina T zvětšuje přesně o jeden vrchol. Proto, má–li graf n vrcholů, algoritmus končí po (n − 1) krocích. V případě, že bychom hledali výhradně pouze nejkratší cestu mezi vrcholy u a v, pak algoritmus končí po k–tém kroku, je–li v ∈ Tk . 5. (časová složitost) Protože v průběhu provádění algoritmu na grafu s n vrcholy, testujeme u každého vrcholu všechny jeho následníky, kterých může být až n − 1, je časová složitost tohoto algoritmu O(n2 ). Ukažme si správnosti algoritmu, tj. že pro každý vrchol x, x 6= u, je H(x) skutečně nejmenší možná cena cesty z vrcholu u do vrcholu x. Tvrzení evidentně platí po provedení 1. kroku. Předpokládejme, že tvrzení platí pro všechny vrcholy x ∈ Tk a neplatí v případě vrcholu m dodaného do množiny T v kroku k + 1. Předpokládejme tedy, že existuje cesta C = (u, x1 , . . . , xr , m), jejíž cena je menší než H(m). Nechť vrchol xi+1 je první vrchol z této cesty, který nepatří do množiny T . Evidentně vrchol xi ∈ T a proto je H(xi ) nejmenší možná cena cesty z vrcholu u do vrcholu xi . V i–tém kroku algoritmu je vrcholu xi+1 přidělena dočasná hodnota dH(xi + 1) = H(xi ) + h(xi , xi+1 ), která nemohla být později zmenšena, protože oba vrcholy xi a xi+1 jsou podle předpokladu následníky v nějaké minimální cestě. Tato hodnota ale byla v každém dalším kroku uvažována. V k–tém kroku algoritmu je do množiny T přidán nějaký vrchol t a vrcholu m je přidělena dočasná hodnota dH(m) = H(t) + h(t, m), a to na základě zjištění, že je hodnota dH(m) minimální ze všech hodnot dH(x), které jsou známy. Speciálně bylo dH(m) ≤ dH(xi + 1). Protože jsou hrany grafu ohodnoceny nezápornými čísly, je H(m) ≤ d(C) = dH(xi+1 ) + d(D), kde d(C) je cena cesty C a d(D) je cena cesty D = (xi+1 , . . . , xr , m). Poznámka. Uvědomme si, že nalezením minimální cesty mezi vrcholy u a v grafu G, jsme zároveň nalezli i minimální cesty mezi vrcholy x a y grafu G, které na této cestě leží. Zároveň jsme získali kostru grafu G, která se často nazývá kořenový strom minimálních cest s kořenem ve vrcholu v. Úloha nalézt minimální cesty z daného vrcholu nemusí mít jednoznačné řešení, a to i v případě, že žádné dvě hrany nejsou ohodnoceny stejně (např. trojúhelník o stranách 1, 2 a 3. Algoritmus nám ale nalezne vždy nějaké řešení. Dále si uvědomme, že tento algoritmus je také možno použít na hledání nejkratších cest v konečném souvislém neohodnoceném grafu, kde mírou ceny cesty je počet jejích hran. Stačí tedy každou hranu ohodnotit stejným číslem, např. číslem 1, a máme problém převeden na problém hledání minimálních cest v ohodnocených grafech. Uvažujte neohodnocený graf z obr.17 a všimněte si, že existují tři různé nejkratší cesty mezi vrcholy a a g. Postup Dijkstrova algoritmu si ukážeme na ohodnoceném grafu, jehož diagram je na obr. 17. Ukážeme si, jak se tvoří množina T a jak se vytvářejí hodnoty H(x), P (x), dH(x) a dP (x) pro jednotlivé vrcholy grafu. Výchozím vrcholem bude vrchol a. inicializace algoritmu T0 = {a}, H(a) = 0, dH(b) = 5, dH(c) = 1, dH(d) = 3, dH(e) = dH(f ) = dH(g) = dH(h) = ∞, dP (b) = dP (c) = dP (d) = a, dP (e) = dP (f ) = dP (g) = dP (h) = ∗. 1. krok T1 = {a, c},

20

H(a) = 0, H(c) = 1, P (c) = a, dH(b) = 5, dH(d) = 2, dH(e) = 5, dH(f ) = 3, dH(g) = dH(h) = ∞, dP (b) = a, dP (d) = c, dP (e) = c, dP (f ) = c, dP (g) = dP (h) = ∗. 2. krok T2 = {a, c, d}, H(a) = 0, H(c) = 1, H(d) = 2, P (c) = a, P (d) = c, dH(b) = 4, dH(e) = 5, dH(f ) = 3, dH(g) = dH(h) = ∞, dP (b) = d, dP (e) = c, dP (f ) = c, dP (g) = dP (h) = ∗. 3. krok T3 = {a, c, d, f }, H(a) = 0, H(c) = 1, H(d) = 2, H(f ) = 3, P (c) = a, P (d) = c, P (f ) = c, dH(b) = 4, dH(e) = 4, dH(g) = ∞, dH(h) = 5, dP (b) = d, dP (e) = f , dP (h) = f , dP (g) = ∗. 4. krok T4 = {a, c, d, f, b}, H(a) = 0, H(b) = 4, H(c) = 1, H(d) = 2, H(f ) = 3, P (b) = d, P (c) = a, P (d) = c, P (f ) = c, dH(e) = 4, dH(g) = ∞, dH(h) = 5, dP (e) = f , dP (h) = f , dP (g) = ∗. 5. krok T5 = {a, c, d, f, b, e}, H(a) = 0, H(b) = 4, H(c) = 1, H(d) = 2, H(e) = 4, H(f ) = 3, P (b) = d, P (c) = a, P (d) = c, P (e) = f , P (f ) = c, dH(g) = 6, dH(h) = 5, dP (g) = e, dP (h) = f . 6. krok T6 = {a, c, d, f, b, e, h}, H(a) = 0, H(b) = 4, H(c) = 1, H(d) = 2, H(e) = 4, H(f ) = 3, H(h) = 5, P (b) = d, P (c) = a, P (d) = c, P (e) = f , P (f ) = c, P (h) = f , dH(g) = 6, dP (g) = e. 7. krok T6 = {a, c, d, f, b, e, h, g}, H(a) = 0, H(b) = 4, H(c) = 1, H(d) = 2, H(e) = 4, H(f ) = 3, H(g) = 6, H(h) = 5, P (b) = d, P (c) = a, P (d) = c, P (e) = f , P (f ) = c, P (f ) = c, P (g) = e. Tady algoritmus končí, kořenový strom (kořenem je vrchol a) minimálních cest je zobrazen na obr. 17. Například minimální cestou mezi vrcholy a a g je cesta C = (a, c, f, e, g) a minimální cestou mezi vrcholy c a g (oba leží na cestě C) je cesta D = (c, f, e, g). Vrchol h na cestě C neleží a proto minimální cesta mezi vrcholy h a g může být jiná, a také je. Všimněte si, že v průběhu výpočtu došlo ke změně hodnot dH(b), dH(d), dH(e) a souvisejícím změnám hodnot dP (b), dP (d), dP (e).

21

a 5 b

1 3 2

c 1 d

4 2 3

e 1 f

2 1 2

g

a

1

4 h

1 b

2

e

c 2

d

2

g

2

h

1 f

´ ln´ich cest Obr. 17: Graf a jeho strom minima Vícenásobně ohodnocené grafy Hrany grafů je možno jistě ohodnotit více než jedním ohodnocením a při řešení praktických úloh to není nic neobvyklého. Představme si, že máme síť autobusových linek mezi jednotlivými městy. Máme–li se dostat z jednoho města do druhého, může nás zajímat nejen cena, kterou zaplatíme, ale i čas, který je na cestu potřeba. Obdobně v běžné silniční síti nás nezajímá pouze vzdálenost, ale také třeba předpokládaná spotřeba pohonných hmot a čas, za který je možno cestu absolvovat. Proto má význam studovat i grafy, na kterých je dáno více než jedno ohodnocení hran. Aby taková úloha byla řešitelná musí být zadána i kriteria, podle kterých je jasné, jakou „váhu” mají jednotlivá ohodnocení. Nejjednodušším vztahem dvou ohodnocení je absolutní preference jednoho ohodnocení před druhým. V tomto případě používáme druhé ohodnocení pouze tehdy, kdy máme možnost výběru na základě prvního kriteria. Ukažme si na příkladě hledání minimálních cest v grafech, jejichž hrany jsou ohodnoceny dvěma nezápornými funkcemi. Hledání minimálních cest v grafech s dvojím ohodnocením Mějme konečný souvislý graf G = (V, H, p) a dvě zobrazení f a g z množiny H do h0, ∞). Předpokládejme, že zobrazení f je vždy preferováno před g. Naším úkolem je nalézt minimální cestu (vzhledem k f ag) z vrcholu a grafu G do jeho vrcholu b. K algoritmickému řešení použijeme mírně modifikovaný Dijkstrův algoritmus. Pro každý vrchol x ∈ V označíme symboly dF (x), F (x), dG(x), G(x), dP (x) a P (x) postupně „dočasnou hodnotu cesty z vrcholu a do vrcholu x dle ohodnocení f ”, „trvalou hodnotu cesty z vrcholu a do vrcholu x dle ohodnocení f ”, „dočasnou hodnotu cesty z vrcholu a do vrcholu x dle ohodnocení g ”, „trvalou hodnotu cesty z vrcholu a do vrcholu x dle ohodnocení g”, „dočasného předchůdce vrcholu x 6= a” a „dočasného předchůdce vrcholu x 6= a”. Symbolem T budeme značit tu množinu vrcholů x grafu G, kde již platí dF (x) = F (x), dg(x) = G(x) a dP (x) = P (x), tj. množinu vrcholů, u kterých jsou již získány definitivně údaje F (x), g(x) a P (x). Dále budeme postupovat analogicky jako v případě jednoho ohodnocení hran. Na rozdíl od již popsaného algoritmu zde nebudeme popisovat první krok, spokojíme se s obecným krokem. 1. (inicializace algoritmu) Definujeme T = T0 = {a} a F (a) = G(a) = 0. Pro každý vrchol x, který je spojen hranou s vrcholem a, definujeme dF (x) = f (a, x), dG(x) = g(a, x) a dP (x) = a. Pro ostatní vrcholy grafu definujeme dF (x) = dG(x) = ∞ (nebo nějaké dostatečně velké číslo) a dP (x) označíme symbolem ∗. 2. (obecný k–tý krok). Máme již množinu T = Tk−1 a pro každé x ∈ Tk−1 i F (x), G(x) a P (x). Vybereme ten vrchol m grafu, který nepatří do T a jehož dočasná hodnota dF (m) je minimální. Je–li takových vrcholů více, vybereme z nich ten vrchol, jehož dočasná hodnota dG(m) je minimální mezi dočasnými hodnotami dG(x) těchto vrcholů. Vrchol m přidáme do množiny T , bude tedy T = Tk = Tk−1 ∪ {m}, dále

22

hodnoty dF (m), dG(m) a dP (m) prohlásíme za již neměnné trvalé hodnoty, tj. definujeme F (m) = dF (m), G(m) = dG(m) a P (m) = dP (m). U každého vrcholu x, který je spojen hranou s vrcholem m, porovnáme hodnoty dF (x) a F (m) + f (m, x). Jestliže je dF (x) < F (m) + F (m, x), ponecháme hodnoty dF (x), dG(x) a dP (x) beze změn. Je–li ale F (m) + f (m, x) < dF (x), pak změníme hodnoty dF (x), dG(x) a dP (x). Dosavadní hodnotu dF (x) nahradíme hodnotou F (m) + f (m, x), dosavadní hodnotu dG(x) nahradíme hodnotou G(m)+g(m, x) a dosavadní hodnotu předchůdce dP (x) nahradíme novým předchůdcem m. Dále tedy bude dF (x) = F (m) + f (m, x), dG(x) = F (m)+g(m, x) a dP (x) = m. Je–li dF (x) = F (m)+f (m, x), pak porovnáme hodnotu dG(x) s hodnotou G(m) + g(m, x). Jestliže je dG(x) ≤ G(m) + g(m, x) ponecháme údaje dF (x), dG(x) a dP (x) beze změn. Je–li ale dG(x) > G(m) + g(m, x), pak změníme údaje dG(x) a dP (x). Novou hodnotou dG(x) bude G(m) + g(m, x) a novou hodnotou pro dP (x) bude m. V dalším tedy bude dF (x) beze změny a bude dG(x) = G(m) + g(m, x), dP (x) = m. 3. (konec algoritmu) Algoritmus končí v okamžiku, kdy je Tn−1 = V . Tedy algoritmus končí jakmile všem vrcholům x grafu jsou přiřazeny trvalé hodnoty F (x), G(x) a P (x). Při každém kroku se množina T zvětšuje přesně o jeden vrchol. Proto, má–li graf n vrcholů, algoritmus končí po provedení n − 1 kroků. V případě, že bychom hledali výhradně pouze nejkratší cestu mezi vrcholy u a v, pak algoritmus končí po k–tém kroku, je–li v ∈ Tk . 4. (časová složitost) V průběhu provádění algoritmu na grafu s n vrcholy, testujeme u každého vrcholu všechny jeho následníky (případně ze dvou hledisek), kterých může být až n − 1, je časová složitost tohoto algoritmu O(n2 ). Důkaz správnosti tohoto modifikovaného Dijkstrova algoritmu plyne z jeho konstrukce a je analogický již uvedenému důkazu správnosti originálního Dijkstrova algoritmu. Tuto úlohu si ukažme jenom na jednom jednoduchém příkladě. Mějme ohodnocený graf, který je zobrazen na obr 17. Zobrazené ohodnocení hran označme f . Je tedy f ({a, c}) = 1, f ({c, e}) = 4, atd. Nechť pro ohodnocení g platí g(h) = f 2 (h). Je tedy g({a, c}) = 1, g({c, e}) = 16, atd. Ohodnocení hran f má absolutní preferenci před ohodnocením g. Pro konečné ceny cest do vrcholu x použijeme značení F (x) a G(x). Algorimické řešení hledání dvojitě ohodnoceného grafu z obr. 17 bude probíhat úplně stejně jako v případě s jedním ohodnocením až do 4–tého kroku. V pátém kroku byl do množiny T přidán vrchol e a byly porovnávány hodnoty dH(h) a H(e) + h({e, h}. Protože obě hodnoty byly rovny 5, nedocházelo ke změně dH(h) a dP (h). V našem případě opět při stejném porovnávání hodnot dF (h) a F (e) + f ({e, h} zjistíme, že je dF (h) = F (e) + f ({e, h}. Musíme proto porovnat hodnoty dG(h) = G(e) + g({e, h}. Protože je dG(h) = 1 + 4 + 4 = 9, G(e) = 1 + 4 + 1 = 6 a g({e, h} = 1, je dG(h) > G(e) + g({e, h} = 1 + 4 + 1 + 1 = 7. Musí proto dojít ke změně hodnot dG(h) = 9 a dP (h) = {f } na dG(h) = 7 a dP (h) = {e}. Dále doběhne algoritmus stejně jako v případě grafu s jedním ohodnocením. Podgraf minimálních cest z vrcholu a vzhledem k ohodnocení f a g je vlevo na obr. 18. Proveďte si podrobně jednotlivé kroky algoritmu. Kdybychom za druhé ohodnocení vzali konstantní funkci g(h) = 1, dostali bychom podgraf, který je stejný jako kdybychom druhé ohodnocení neuvažovali. Tento podgraf je zobrazen vpravo na obr. 18.

23

a

1

c

1

b

2

e

2

d

1

f 2

g(h) = f (h)

2

g

a

1

c

e

1

1

h

b

2

d

2

2

g

2

h

1

f

g(h) = 1

´ ln´ich cest vzhledem k f a g Obr. 18: Stromy minima Příklady k procvičení 1) Zjistěte, zda má řešení úloha o 3 misionářích a 3 kanibalech. Úloha zní: jak přepravit 3 misionáře a 3 kanibaly (bez převozníka) přes řeku za použití jediné loďky, která je schopna uvézt nejvýše dvě osoby? Přitom nesmí zůstat na žádném břehu větší počet kanibalů než misionářů. Předpokládejme, že roli převozníka (schopnost převést loďku z jednoho břehu na druhý) může zastávat kdokoliv. Pokud má úloha řešení, uveďte minimální počet přejezdů řeky. 2) Zjistěte, zda má řešení modifikovaná úloha o 3 misionářích a 3 kanibalech. Úloha zní: jak přepravit 3 misionáře a 3 kanibaly (bez převozníka) přes řeku za použití jediné loďky, která je schopna uvézt nejvýše dvě osoby? Přitom se nesmí ani na okamžik ocitnout na žádném břehu větší počet kanibalů než misionářů. Předpokládejme, že roli převozníka (schopnost převést loďku z jednoho břehu na druhý) může zastávat kdokoliv. Pokud má úloha řešení, uveďte minimální počet přejezdů řeky. 3) Zjistěte, zda má řešení modifikovaná úloha o vlku, koze a zelí, kdy má převozník za úkol převést navíc ještě jednu věc (zelí,vlka nebo kozu). 4) Máme k dispozici tři sklenice o objemech 5l, 3l a 2l. V první slenici jsou 4l vody. Chceme pouhým přeléváním vody bez použití dalších odměrek dosáhnout stavu a) v první sklenici jsou 2l, ve druhé a třetí 1l; b) v některé sklenici jsou 2l, v dalších po 1l. Je to možné? V případě že ano určete minimální počet nutných kroků, tj. „přelévání” vody z jedné sklenice do jiné. 5) Nechť U (n) je úplný graf mající právě n vrcholů. Kolika tahy lze pokrýt graf U (n)? 6) Nechť U (n) je úplný graf mající právě n vrcholů. Určete a) počet hran grafu U (10); b) počet různých kružnic délky 3 v grafu U (10); c) počet různých kružnic délky 6 v grafu U (10); d) počet všech různých kružnic v grafu U (10); e) počet různých cest délky n − 1 v grafu U (10); 7) Nechť U (4) je úplný graf mající právě 4 vrcholy. Určete a) počet různých koster grafu U (4); b) počet různých neizomorfních koster grafu U (4). 8) Na následujícím obrázku jsou diagramy grafů R(n). Určete počet k(R(n)) všech možných koster grafu R(n). 9) Na následujícím obrázku jsou diagramy grafu S(n). Určete počet k(S(n)) všech možných koster grafu S(n) 10) Na následujícím obrázku jsou diagramy grafů Z(n) a C(n).

24

... 1

2

...

n

1

n

2

R(n)

S(n) Obr. k cv. 10 a 11): Grafy R(n) a S(n)

a) Nalezněte všechny kostry grafů Z(1), Z(2), Z(3), a Z(4) a určete jejich počet k(Z(n)) pro 1 ≤ n ≤ 4. b) Nalezněte všechny kostry grafů C(1), C(2), C(3), a C(4) a určete jejich počet k(C(n)) pro 1 ≤ n ≤ 4.

...

... 1

2

... n

3 Z(n)

1

2

n

3 C(n)

Obr. k cv. 10 ): Grafy Z(n) a C(n) 11) Na následujícím obr. cv11 je ohodnocený graf G. V levé části je vyznačeno číslování hran, v pravé části je uvedeno ohodnocení hran. Jsou též označeny vrcholy a a w. a) Nalezněte minimální kostru grafu G Dijktsrovým algoritmem a hrany vypisujte v pořadí ve kterém jsou získávány. b) Nalezněte minimální kostru grafu G„hladovým algoritmem” a hrany vypisujte v pořadí ve kterém jsou získávány. c) Nalezněte strom minimálních cest v grafu G„ z vrcholu a. d) Nalezněte strom minimálních cest v grafu G„ z vrcholu w.

a h1

h3 h4

h10

h6

h2 h5

h7 h8

h9

h11 h13 h12

w

7

1

11

´ graf G Obr. cv.11): Ohodnoceny

Výsledky 1) Úloha má řešení, minimální počet přejezdů řeky je 9. 2) Úloha má řešení, minimální počet přejezdů řeky je 11. 3) Modifikovaná úloha nemá řešení.

4

10

9

a

6

8 13

5

3 12

2

w

25

4) a) Úloha nemá řešení; b) úloha má řešení, jsou potřeba minimálně 2 kroky. 5) Pro každé přirozené číslo k ≥ 1 platí: U (2k − 1) = 1 a U (2k) = k. 6) a) 45; b) 120; c) 210; d) 968; e) 1 814 400. 7) a) 16; b) 4. 8) k(R(n)) = 4n . 9) k(S(n)) = 16n . 10) a) k(Z(1)) = 1, k(Z(2)) = 4, k(Z(3)) = 15, k(Z(4)) = 56; b) k(C(1)) = 1, k(C(2)) = 3, k(C(3)) = 8, k(C(4)) = 21. 11) a) Dijkstrův algoritmus: {h1 , h3 , h5 , h7 , h9 , h10 , h13 }. b) „hladový algoritmus: {h1 , h13 , h9 , h10 , h5 , h3 , h7 }. c) strom minimálních cest z vrcholu a: {h1 , h2 , h3 , h6 , h7 , h10 , h13 }. d) strom minimálních cest z vrcholu w: {h13 , h11 , h9 , h6 , h5 , h2 , h1 } nebo {h13 , h11 , h9 , h6 , h8 , h2 , h1 }. Orientované grafy V mnoha úlohách je nutno uvažovat i další omezenení při procházení hranami grafu. Jde o to, že může být zakázán průchod hranou v jednom směru, tj. od jednoho koncového vrcholu hrany k druhému, a povolen ve směru opačném. Jsou to příklady jednosměrných cest apod. Při těchto úvahách nebude hrana h určena pouze množinou jejích koncových vrcholů {a, b}, ale uspořádanou dvojicí vrcholů (a, b) (hrana od a do b) nebo (b, a) (hrana od b do a). Pak budeme hovořit o orientaci hran a o orientovaných grafech. Je velmi jednoduché každý orientovaný graf převést na neorientovaný pouhým ignorováním orientace, tj. náhradou uspořádané dvojice vrcholů (a, b) množinou koncových vrcholů {a, b}. V praxi se samozřejmě velmi často vyskytují problémy, kdy některé hrany v grafu jsou orientované a jiné ne. Taková situace se dá zase snadno převést na orientované grafy tím, že neorientovanou hranu určenou koncovými vrcholy {a, b} nahradíme dvěma orientovanými hranami, které jsou určeny uspořádanými dvojicemi (a, b) a (b, a). Je jasné, že studium orientovaných a neorientovaných grafů spolu úzce souvisí, a proto v některých učebnicích jsou zkoumány společně. My jejich studium z tradičních důvodů rozdělujeme, ale budeme si uvědomovat, že mnohé výsledky formulované pro jeden typ grafů platí i pro druhý typ, případně i pro smíšené typy. V této části se budeme zabývat konečnými orientovanými grafy a začneme pro jistotu opět definicí. Definice. Orientovaným grafem G rozumíme trojici G = (V, H, p), kde V je neprázdná množina, jejíž prvky budeme nazývat vrcholy, H je množina (může být i prázdná), jejíž prvky nazýváme hrany a p je zobrazení z H do množiny všech uspořádaných dvojic prvků z V , tj. do {(a, b); a, b ∈ V } = V × V , které určuje počáteční a koncové vrcholy hran. Poznámka. Je–li p(h) = (a, b), říkáme, že vrchol a je počátečním vrcholem hrany h a že vrchol b je koncovým vrcholem hrany h. Totéž vyjadřujeme také tak, že říkáme, že hrana h začíná ve vrcholu a a končí ve vrcholu b. Není–li orientace v nějakém okamžiku důležitá, říkáme, že vrcholy a a b jsou koncovými vrcholy hrany h. Hrany, jejichž počáteční vrchol je stejný jako koncový, se nazývají smyčky. V dalším textu budeme uvažovat pouze orientované grafy bez smyček.

26

Nejprve se stručně podíváme, jak by vypadalo řešení některých úloh z kapitoly o neorientovaných grafech v případě orientovaných grafů. Definici izomorfismu dvou orientovaných grafů je třeba trochu upravit a zajistit i správný přenos orientace hran. Formulujme to přesněji. Řekneme, že dva orientované grafy G1 = (V1 , H1 , p1 ) a G2 = (V2 , H2 , p2 ) jsou izomorfní, jestliže existují dvě vzájemně jednoznačná zobrazení f : V1 −→ V2 a g : H1 −→ H2 taková že pro každou hranu h ∈ H1 platí: p1 (h) = (x, y) právě tehdy, když je p2 (g(h)) = (f (x), f (y)). Provedené úvahy o planaritě grafů byly na orientaci či neorientaci hran naprosto nezávislé. Úvahy o cestách či sledech v grafech jistě na orientaci záviset budou. Pojem sled či cesta se nahradí pojmy orientovaný sled a orientovaná cesta zcela přirozeným způsobem. Pro posloupnost s = (v1 , h1 , v2 , h2 , . . . , hn , vn+1 ) vrcholů a hran budeme požadovat, aby P (hi ) = (vi , vi+1 ). Pojem stupeň vrcholu bude nutno jistě upravit s ohledem na hrany do vrcholu přicházející a z vrcholu odcházející. Počet hran, pro které je vrchol v počátečním vrcholem označíme st+ (v) a počet hran, pro které je vrchol v koncovým vrcholem označíme st− (v). Pak platí, že je st(v) = st+ (v) + st− (v), kde st(v) označuje známý pojem stupeň vrcholu v. Orientovaný graf G se nazývá souvislý graf, jestliže existuje orientovaný sled mezi jeho každými dvěma vrcholy. Věta o uzavřeném Eulerově tahu bude v případě orientovaných grafů znít takto. Věta. Nechť G je konečný souvislý orientovaný graf. Potom existuje uzavřený tah, který obsahuje všechny hrany grafu (tzv. Eulerův tah) právě tehdy, když pro každý vrchol v grafu G platí: a st+ (v) = st− (v) Poznámka. Ve větě zůstává zachováno, že stupeň každého vrcholu musí být sudý. To ale nestačí. Musí platit, že počet hran končících ve vrcholu je roven počtu hran z vrcholu vycházejících. Při realizaci uzavřeného orientovaného tahu je možno začít v kterémkoliv vrcholu. Důkaz této věty je naprosto stejný, jako v případě neorientovaných grafů. Obdobné je to pro grafy s otevřeným Eulerovým tahem. Věta. Nechť G je konečný souvislý orientovaný graf. Potom existuje otevřený tah, který obsahuje všechny hrany grafu právě tehdy, když v grafu G existuje vrchol a, pro který je st+ (a) = st− (a) + 1 a existuje vrchol b, pro který je st+ (b) = st− (b) − 1 a pro ostatní vrcholy x, je st+ (x) = st− (x). Tento tah musí začínat ve vrcholu a a končí ve vrcholu b. Pojem kostra v neorientovaném grafu je založen na souvislosti grafu a neexistenci kružnice ve faktoru grafu, což dává možnosti minimalizace počtu hran grafu při zachování souvislosti. V orientovaných grafech by analogoie tohoto pojmu přinášela problémy. Buďto by nebyla dodržena souvislost v podgrafu, tj. existence cesty mezi libovolnými dvěma vrcholy grafu, nebo bychom museli připustit existenci kružnic (cesta z jednoho vrcholu do druhého a také zpět). Proto se zobecněním tohoto pojmu nezabýváme. Jiná situace nastává při hledání cest z jednoho vrcholu orientovaného grafu do jiného vrcholu a případně nějaké minimalizace těchto cest. Minimalizace může být dána počtem hran a nebo součtem jejich ohodnocení, pokud nějaké existuje. Řešení problému si ukážeme v další části. Ohodnocené orientované grafy Ze studia ohodnocených neorietovaných grafů víme, že ohodnocení hran grafu je přirozený a praktický požadavek související s řešením reálných problémů. Totéž samozřejmě musí platit i v případě orientovaných grafů. V aplikacích se opět spokojíme s nezáporně

27

ohodnocenými grafy, i když v definici to nepožadujeme. V některých reálných situacích je dokonce výhodné a nutné záporné ohodnocení uvažovat. Definice. Ohodnoceným orientovaným grafem G rozumíme trojici G = (V, H, p, c), kde G = (V, H, p) je orientovaný graf a c je zobrazení množiny H do množiny všech reálných čísel R, které budeme nazývat ohodnocením hran (resp. cenou hran). Hledání minimálních orientovaných cest Pro hledání minimálních cest z vrcholu a do ostatních vrcholů orientovaného ohodnoceného grafu lze použít Dijkstrův algoritmus prakticky beze změny. Pouze musíme hlídat, abychom při přidávání vrcholů do vytvářené množiny T přidávali pouze ty vrcholy, které jsou koncovými vrcholy hrany, jejíž počáteční vrchol v množině T leží. Pro jistotu si raději algoritmus stručně zopakujeme. Všimněme si drobné modifikace algoritmu, která je vynucena tím, že nepředpokládáme existenci orientované cesty z vrcholu a do všech ostatních vrcholů. Samozřejmě, že stejná modifikace byla možná i u grafů neorientovaných. Máme konečný orientovaný graf G, jehož hrany jsou nezáporně ohodnoceny zobrazením h : H → h0, ∞) a jeho vrchol a. Úkolem je určit cestu z vrcholu a do každého „dosažitelného” vrcholu b, tak aby součet cen hran na této cestě byl co nejmenší. V průběhu výpočtu budeme používat symboly T pro množinu vrcholů, pro které již byla minimální cesta nalezena, pro x ∈ T bude H(x) označovat cenu nalezené minimální cesty a P (x) bude označovat předchůdce vrcholu x na této cestě. Pro vrchol x 6∈ T bude dH(x) označovat dočasnou hodnotu ceny zatím nejlepší cesty do x a dP (x) bude označovat předchůdce vrcholu x na této cestě. Algoritmus pracuje takto: 1. (inicializace algoritmu) Položíme T0 = {a}, c(a) = 0. Vrcholům x, pro které existuje hrana h = (a, x) ∈ H, přiřadíme dH(x) = c(h) a dP (x) = a. Ostatním vrcholům x 6= a přiřadíme dH(x) = ∞ a dP (x) označíme ∗. 2. (obecný krok algoritmu) Máme Tk−1 . Vybereme ten vrchol x grafu G s hodnotou dH(x) 6= ∞, pro který je dH(x) minimální mezi hodnotami dH(x) pro x 6∈ Tk−1 . Nechť je to vrchol w. Položme Tk = Tk−1 ∪ w, H(w) = dH(w) a P (w) = dP (w). U každého vrcholu x, pro který existuje hrana h = (w, x) ∈ H, porovnáme hodnoty dH(x) a H(w) + h(w, x). Je–li dH(x) ≤ H(w) + h(w, x), necháme dH(x) a dP (x) beze změn. Je–li dH(x) > H(w) + h(w, x), pak hodnotu dH(x) nahradíme hodnotou H(w) + h(w, x) a hodnotu dP (x) nahradíme vrcholem w. 4. (konec algoritmu) Algoritmus končí v okamžiku, kdy nelze provést krok 2. Buďto jsou všechny vrcholy grafu G již zařazeny do množiny T , nebo je dH(x) = ∞ pro každý vrchol x 6∈ T , což znamená, že zbývající vrcholy nejsou z vrcholu a v grafu G dosažitelné. Má–li graf n vrcholů, algoritmus končí nejpozději po provedení (n − 1) kroků. 5. (časová složitost) Protože v průběhu provádění algoritmu na grafu s n vrcholy, testujeme u každého vrcholu všechny jeho následníky, kterých může být až n − 1, je časová složitost tohoto algoritmu O(n2 ). Poznámka. Velmi jednoduchou modifikací algoritmu bychom mohli hledat i minimální cesty do daného vrcholu. V algoritmu bychom místo hran „vycházejících z vrcholu” uvažovali hrany „končící ve vrcholu”. Podgraf, který tvoří minimální orientované cesty z vrcholu a do ostatních dosažitelných vrcholů orientovaného grafu G, je orientovaný graf, ve kterém vede z vrcholu a do každého dosažitelného vrcholu přesně jedna (orientovaná) cesta. Tento graf samozřejmě

28

neobsahuje orientované kružnice. Dokonce ale nesmí obsahovat ani neorientované kružnice. Takové orientované grafy jsou velmi důležité v teoretické informatice. Budeme se jimi zabývat v další kapitole a budeme je nazývat kořenové stromy. Postup Dijkstrova algoritmu si ukážeme na ohodnoceném orientovaném grafu, jehož diagram je na obr. 19. Ukážeme si, jak vzniká množina T a jak se vytvářejí hodnoty H(x), P (x), dH(x) a dP (x) pro jednotlivé vrcholy grafu, které jsou dosažitelné z výchozího vrcholu a. Tentokrát si výsledky jednotlivých kroků algoritmu popíšeme stručněji než při ilustraci postupu Dijkstrova algoritmu pro graf z obr. 17. Výsledky jednotlivých kroků budou zřejmé z následující tabulky. Ve sloupci označeném x ∈ T jsou uváděny hrany x, které v jednotlivých krocích přidáváme do množiny T a v dalších dvou sloupcích jsou uvedeny hodnoty H(x) a P (x) těchto prvků. V pátém sloupci jsou uváděny ty prvky x, které mají za dočasnou hodnotu dH(x) reálné číslo, které je uvedeno v závorce za názvem prvku. Údaje v tomto sloupci jsou tedy tvaru x(dH(x)). V posledním sloupci jsou uvedeny ty vrcholy x s dH(x) = ∞. algoritmus x ∈ T H(x) P (x) dH(x) ∈ R dH(x) = ∞ inicializace a 0 −− b(5), c(1), d(3) e, f, g, h 1. krok c 1 a b(5), d(3), e(5), f (3) g, h 2. krok d 3 a b(5), e(5), f (3) g, h 3. krok f 3 c b(5), e(4), h(6) g, h 4. krok e 4 f b(5), h(5) g 5. krok b 5 a h(5) g 6. krok h 5 e g Algoritmus končí po provední šesti kroků, vrchol g není z vrcholu a dosažitelný. Kořenový strom (kořenem je vrchol a) minimálních cest do dosažitelných vrcholů je zobrazen na obr. 19. V průběhu výpočtu došlo ke změně hodnot dH(e), dH(h) a souvisejícím změnám hodnot dP (e), dP (h).

a 5

1 3

b

2

c 1 d

4 2 3

e 1 f

2 1 3

g 5 h

a 5 b

1

c

3

e 2

d

1

g 1

f

h

´ ln´ich cest z vrcholu a Obr. 19: Graf a jeho strom minima

Kořenové stromy Mějme orientovaný graf G = (V, H, p). Vrchol a ∈ V nazveme kořenem grafu G jestliže každý vrchol x ∈ V, x 6= a je z vrcholu a ∈ V orientovaně dosažitelný, tj. existuje orientovaná cesta (a, v1 , . . . , vk , x) z vrcholu a do vrcholu x. Graf může mít kořenů několik a také nemusí mít žádný kořen. Na obr. 19-a je zobrazen graf G1 , jehož každý vrchol je kořenem, graf G2 , který nemá žádný kořen a grafy G3 a G4 , které mají právě jeden kořen.

29

G1

G2

G3

G4

Obr. 19-a: Grafy G1 , G2 , G3 a G4 . V dalším nás budou zajímat především orientované grafy „podobné” grafům G3 a G4 . tyto grafy mají tu důležitou vlastnost, že z kořene grafu vede do každého jiného vrcholu přesně jedna cesta. Všimněme si, že do kořene grafu nevede žádná hrana a do každého jiného vede právě jedna hrana. Dále si uvědomme, že pokud zapomeneme na orientaci hran, patří oba grafy mezi stromy. Grafy s těmito vlastnostmi budeme nazývat kořenovými stromy. Definice. Řekneme, že orientovaný graf G = (V, H, p) je kořenovým stromem, jestliže existuje vrchol w ∈ V mající následující vlastnosti: 1. do vrcholu w nevede žádná hrana, tj. st− (w) = 0; 2. do každého vrcholu x 6= w vede právě jedna hrana, tj. st− (x) = 1; 3. z vrcholu w existuje cesta do každého vrcholu x 6= w. Poznámka. Je samozřejmé, že v kořenovém stromu existuje právě jeden kořen. Pokud zapomeneme na orientaci hran v kořenovém stromu, je tento graf (neorientovaný) strom. Z toho plynou některé známé důsledky. Jsou to např.: 1) kořenový strom s n vrcholy má přesně n − 1 hran; 2) kořenový strom neobsahuje kružnice (ani neorientované); 3) v kořenovém stromu s kořenem w existuje do každého vrcholu x 6= w právě jedna orientovaná cesta. Důležitou vlastností kořenových stromů je to, že do každého vrcholu x (s výjimkou kořene) přichází právě jedna hrana h = (y, x). Vrchol y je vrcholem x určen jednoznačně a nazývá se „předchůdce” vrcholu x. Vrchol y může být předchůdcem pro více vrcholů, které nazýváme „ následníkem” vrcholu y. Často se také používá terminologie „otec” pro předchůdce a „syn” pro následníka. Vrcholy, které nemají následníky, se nazývají listy. Listem je tedy každý vrchol x, pro který je st+ (x) = 0. Každý kořenový strom je možno zobrazit tak, že jeho kořen umístíme „nahoru”, pod něho umístíme jeho následovníky atd. Vznikne tak uspořádaná množina, kde je uspořádání dáno orientací hran. Je proto možno kořenové stromy zobrazovat jako uspořádané množiny a není nutno do diagramů grafů uvádět orientaci hran. Orientace hran je vždy „ shora dolů”, tj. od vrcholu nakresleného „výše” k vrcholu, který je nakreslen „níže”. Při tomto zobrazení mají stromy kořeny nahoře a „rostou” směrem dolů. Tuto možnost budeme využívat. Binární stromy Kořenové stromy jsou velice vhodným nástrojem k zobrazování mnoha vztahů. Velmi aplikovatelnou třídou kořenových stromů jsou tzv. binární stromy. Definice. Kořenový strom G nazýváme binárním kořenovým stromem jestliže každý jeho vrchol má nejvýše dva následníky, tj. pro každý vrchol x ∈ G je st+ (x) ≤ 2. Podstromem kořenového stromu G, který je určen vrcholem x ∈ G, budeme rozumět podgraf, který je určen množinou všech vrcholů dosažitelných z vrcholu x.

30

V binárních kořenových stromech můžeme velmi jednoduše i uspořádávat a popisovat následníky téhož vrcholu. Jednoho následníka nazveme „levým následníkem” a druhého „pravým následníkem”. Pokud má vrchol jen jednoho následníka, považujeme ho za levého následníka. Samozřejmě následníky také takto zobrazujeme v diagramech grafů (levého následníka vlevo, pravého vpravo). Podstrom určený levým následníkem vrcholu x budeme označovat L(x) a podstrom určený pravým následníkem vrcholu x budeme značit R(x). Na obr. 19-b je zobrazen kořenový strom s kořenem w. V čárkovaně vyznačených obdélnících jsou zobrazeny podstromy L(w), R(w). Množina vrcholů podstromu L(w) je množina {a, c, d, e, f } a množina vrcholů podstromu R(w) je množina {b, g, h, i, j, k}. Dále je např. podstrom R(i) má množinu vrcholů {i, j, k}.

w

a c

d e

b

f

g h

i j

k

´ rn´i strom Obr. 19-b: Bina Reprezentace aritmetických výrazů Při zpracovávání jednoduchých aritmetických výrazů používáme běžně tzv. infixovou notaci, tj. binární operátory vkládáme mezi operandy s kterými se má provést operace. Píšeme tedy x + y, 3 · 5, 7 − 9, a : b resp. a/b. Jsou možné i jiné zápisy, které se používají zejména v programování. Budeme–li psát nejprve operátor a poté operandy, používáme tzv. prefixovou notaci, píšeme–li nejprve operandy a poté oprátory, používáme tzv. postfixovou notaci. Zápis uvedených příkladů (v infixové notaci) by byl v prefixové notaci +xy, −79,: ab resp. /ab a v postfixové notaci xy+, 79−,ab : resp. ab/. Složitější aritmetické výrazy je možno reprezentovat binárním kořenovým stromem. V listech stromu jsou umístěny konstanty nebo proměnné, na ostatních vrcholech jsou binární operátory. Například výraz (3 + 5) ∗ 8 + 6 : (2 − 4) je reprezentován na kořenovém stromu na obr. 19-c. Pro lepší názornost používáme pro násobení symbol ∗. Prexifová notace pro tento výraz je + ∗ +358 : 6 − 27 a v postfixové notaci je to 35 + 8 ∗ 627− : +. Uvědomme si, že při používání prefixové nebo postfixové notace není potřeba požívat závorky a při používání infixové notace jsou závorky nutné. Vezměmě si levý podstrom zkoumaného výrazu, tedy výraz (3 + 5) ∗ 8 a výraz 3 + 5 ∗ 8. V infixové notaci bez závorek bychom u obou výrazů dostali stejný zápis 3 + 5 ∗ 8, v prefixové notaci dostáváme výrazy ∗ + 358 resp. +3 ∗ 58 a v postfixové notaci 35 + 8∗ resp. 358 ∗ +. Ukažme si, jak lze vyhodnotit binární kořenový strom reprezentující aritmetický výraz. Budeme vždy procházet binární kořenový strom metodou „průchod do hloubky”. Začneme u kořene a z každého vrcholu x se jde nejprve do jeho levého následníka a do vrcholu x se vracíme až po projití celým jeho levým podstromem L(x). Poté projdeme celým pravým podstromem R(x) a vrátíme se zpět do vrcholu x. Strom je systematicky prohledáván zleva do prava. Nejprve se dojde až do listu, který je nejvíce vlevo, poté se po stejné cestě vracíme do uzlu, kde je možno prozkoumávat další cestu (pravou). Touto

31

+ :

* + 3

8 5

-

6 2

4

´ razu (3 + 5) · 8 + 10/(2 − 7) bina ´ rn´im stromem Obr. 19-b: Reprezentace vy cestou se dostaneme opět až do listu, stejnou cestou se vracíme atd. Do každého vrcholu vstupujeme celkem až třikrát. Prvně při vstupu od předchůdce, podruhé při návratu z levého podstromu a potřetí při návratu z pravého podstromu. Podle toho v jakém pořadí zapisujeme hodnoty ve vrcholech, rozeznáváme tři metody, které se nazývají preorder, postorder a inorder. Tyto metody lze stručně charakterizovat způsobem v jakém pořadí vrcholy zapisujeme, čili jak je uspořádáváme. Pro každý vrchol x je dodržena zásada zápisu při metodě 1. preorder: vrchol x, všechny vrcholy z L(X), všechny vrcholy z R(x), 2. postorder: všechny vrcholy z L(X), všechny vrcholy z R(x), vrchol x, 2. inorder: všechny vrcholy z L(X), vrchol x, všechny vrcholy z R(x). Při používání metody preorder vypisujeme vrchol při prvním příchodu do vrcholu, při metodě post order zapisujeme vrchol až při jeho definitivním opouštění a při metodě inorder se vrchol zapisuje po návratu do vrchol z levého podstromu. Jak víme, metoda inorder vyžaduje závorkování. Toho je možno docílit tak, že při prvním vstupu do vrcholu napíšeme levou závorku ( a při posledním vstupu do vrcholu připíšeme pravou závorku ). Při vyhodnocování výrazu, který je reprezentován na kořenovém stromu na obr. 19-c, tak dostaneme při použití metody inorder zápis ((((3) + (5)) ∗ (8)) + ((6) : ((2) − (4)))). Tento postup je možno ještě zjednodušit například tak, že „závorkování” nebudeme aplikovat na listy a kořen. Při tomto zjednodušení by zápis vypadal takto: ((3+5)∗8)+(6 : (2−4)). Pozanamenejme ještě, že metody preorder a postorder by bylo možno používat v každém kořenovém stromu, metodu inorder je možno používat pouze v binárních kořenových stromech. Metody preorder a postorder jsou často využívány v různých programovacích technikách a překladačích. Poznámka. Stejné metody je možno používat i při reprezentaci a vyhodnocování výrokových formulí nebo Booleových výrazů. Místo binárních operátorů používáme logické spojky ∨, ∧, ¬, →. Těmto stromům se obvykle říká derivační stromy (formule, výrazu). Na obr. 19-d jsou derivační stromy formulí (¬p ∨ q) ∧ r a p ∨ (¬q ∧ ¬r). Příklad. Určeme hodnotu aritmetického výrazu jehož zápis v prefixové notaci je ∗ − +3 ∗ 257 + 3 : 82. Vytvořme si binární strom, který odpovídá výrazu ∗ − +3 ∗ 257 + 3 : 82. V kořeni stromu bude symbol ∗, v jeho levém následníku symbol −. V levém následníku symbolu − je symbol +. Levým následníkem symbolu + je konstanta 3 a pravým následníkem je symbol ∗. Levým následníkem tohoto symlolu je konstanta 2 a pravým následníkem je konstanta 5. Dále pokračujeme zjištěním, že pravým následníkem symbolu − je konstanta 7. Tím jsme se dostali zpět do kořene a pokraačujeme procházením pravé větve kořene stromu. Pravým následníkem kořene je symbol +, jeho levým následníkem je 3 a prvým násled-

32

ï

î p

r

î

ï

Ø

Ø

Ø

q

r

q p

ˇn´i stromy vy ´ raz˚ Obr. 19-d: Derivac u (¬p ∨ q) ∧ r a p ∨ (¬q ∧ ¬r) níkem je symbol :. Levým následníkem symbolu : je konstanta 8 a pravým následníkem je konstanta 2. Získaný binární stron je zobrazen na obr. 19-e. Nyní již snadno získáme, že se jedná o aritmetický výraz (3 + (2 · 5) − 7) · (3 + 28 ), jehož hodnota je 42.

* + 7

+ 3

:

3

-

8

2

* 5

2

´ rn´i strom vy ´ razu ∗ − +3 ∗ 257 + 3 : 82 Obr. 19-e: Bina Příklad. Určeme hodnotu aritmetického výrazu jehož zápis v postfixové notaci je 25 ∗ 7 − 384 : +∗. Vytvořme si binární strom, který odpovídá výrazu 25 ∗ 7 − 384 : +∗. V kořeni stromu je symbol ∗. Protože se do kořene vracíme z pravé větve, je pravým následníkem kořene symbol + a jeho pravým následníkem je :, peravám následníkem : je konstanta 8 a levým následníkem je konstanta 8. Levým násaledníkem + je konstanta 3. Tím jsme zpracovali pravou větev kořene. Obdobně postupujeme v levé větvi kořene. Binární strom, který odpovídá postfixovému zápisu 25 ∗ 7 − 384 : +∗ je na obr. 19-f. Snadno zjistíme, že se jedná o aritmetický výraz (2 · 5 − 7) · (3 + 84 ), jehož hodnota je 15.

* + 7

* 2

:

3

-

8

5

´ rn´i strom vy ´ razu 25 ∗ 7 − 384 : +∗ Obr. 19-f: Bina

4

33

Toky v sítích Velmi aplikovatelnou částí teorie grafů jsou úlohy, které se týkají „propustnosti” ohodnocených orientovaných grafů, a to zejména optimalizační úlohy o tzv. tocích v sítích. Zatím si tok v síti můžeme představit jako pohyb vody v rozvodu pitné vody (v nějaké lokalitě), rozvod plynu, kanalizační síť, dopravní síť apod. Každá taková síť může, ze zcela pochopitelných důvodů, mít v různých úsecích jinou „propustnost” nebo může být někde pouze jednosměrná. My budeme nejprve studovat takové toky, které „vznikají” na jednom místě (tzv. zdroji) a „končí” v jednom místě (tzv. spotřebiči). Potom si ukážeme i některé další zobecnění této zmíněné základní situace. Nejprve si ujasněme, co budeme rozumět pod pojmy síť a tok v síti. Definice. Sítí G budem rozumět konečný souvislý orientovaný graf G = (V, H) bez smyček a bez násobných hran na kterém je definováno nezáporné ohodnocením hran c, které budeme nazývat kapacitou hran. Dále předpokládáme, že je určen vrchol z ∈ V (zdroj) a vrchol s ∈ V (spotřebič), z 6= s, a že existuje orientovaná cesta od vrcholu z do vrcholu s. Předpokládáme navíc, že st− (z) = st+ (s) = 0. Pro daný vrchol v v orientovaném grafu budeme označovat symbolem H + (v) resp. H − (v) množinu všech hran grafu, pro které je vrchol v jejich počáteční resp. koncový vrchol. Symbolem V + (v) resp. V − (v) budeme označovat množinu všech vrcholů x grafu, pro které je h = (v, x) ∈ H resp. pro které je h = (x, v) ∈ H. Je zřejmé, že h ∈ H + (v), právě tehdy, je–li h = (v, x) pro nějaké x ∈ V + (v) a h ∈ H − (v), právě tehdy, je–li h = (v, x) pro nějaké x ∈ V − (v). Protože ve zdroji nekončí žádná hrana a ve spotřebiči žádná hrana nezačíná, je V − (z) = ∅ a V + (s) = ∅. Definice. Tokem v síti G budeme nazývat takové ohodnocení t hran grafu G, že je splněno 0 ≤ t(h) ≤ c(h) pro každou hranu h grafu G a pro každý vrchol v grafu G, který je různý od vrcholů z a s, platí tzv. Kirchhoffův zákon: P P t(h) = t(h). h∈H + (v)

h∈H − (v)

Poznámka. Za toky v síti tedy budeme považovat každé nezáporné ohodnocení hran, které nepřevyšuje jejich kapacitu a ve vrcholech různých od zdroje a spotřebiče se nic nehromadí ani nevzniká. Místo názvu „spotřebič” pro vrchol s se také často používá název „stok”. Poznamenejme ještě, že budeme také předpokládat, že do zdroje nic „nepřitéká” a ze spotřebiče nic „neodtéká”. Velikostí toku t budeme rozumět číslo, které udává množství toku odcházejícího ze zdroje. Toto množství se rovná množství toku přicházejícího do spotřebiče. Rovnost plyne z platnosti Kirchhoffova zákona pro všechny vrcholy sítě G různé od zdroje a spotřebiče. Velikost toku t tedy definujeme jako P P t(h) = t(h). vel(t) = h∈H + (z)

h∈H − (s)

Pokud budeme hrany popisovat pomocí počátečního a koncového vrcholu a budeme– li místo t(h) používat t(x, y) pro hranu h = (x, y), lze Kirchhoffův zákon pro vrcholy v různé od zdroje a spotřebiče zapisovat takto: P P t(y, v). t(v, x) = x∈V + (v)

y∈V − (v)

Velikost toku t sítí G je při tomto popisu hran definována jako číslo P P t(y, s). vel(t) = t(z, x) = x∈V + (z)

y∈V − (s)

34

Základní úlohou týkající se toků v sítích bude, ze zcela pochopitelných důvodů, úloha zjistit jaký je možný maximální tok danou sítí a jak ho realizovat. Odpověď na první část úlohy, tj. zjistit maximální možnou velikost toku sítí, je poměrně jednoduchá. Princip je založen na tom, že žádný tok nemůže být větší než je kapacita kterékoliv „řezu” sítí, který od sebe odděluje zdroj a spotřebič. Řezem R(A) sítí G, který je určen podmnožinou vrcholů A ⊂ V , rozumíme množinu všech hran sítě, jejichž jeden vrchol leží v A a druhý v A neleží. Pokud množina A obsahuje zdroj z a neobsahuje spotřebič s, říkáme, že řez R(A) odděluje zdroj od spotřebiče. Kapacitou řezu R(A) budeme rozumět číslo C(A), které udává součet kapacit všech P hran, které mají počáteční vrchol v A a koncový vrchol mimo A. Je tedy C(A) = c(h), h∈H + (A) +

kde H (A) je množina všech hran sítě G, jejichž počáteční vrchol leží v množině A a koncový neleží. Kapacita řezu tedy udává maximální možné množství toku, které může hranami řezu odtéci. Pro každý tok t sítí G a P řez sítí R(A) můžeme definovat množství toku procházející P řezem R(A) jako t(A) = t(h) − t(h), kde H − (A) je množina všech hran h∈H + (A)

h∈H − (A)

sítě G, jejichž koncový vrchol leží v množině A a počáteční neleží. Množství toku přes řez tedy udává rozdíl mezi množstvím toku, které hranami řezu odtéká, a množstvím toku, které hranami řezu přitéká. Protože pro každý vrchol různý od zdroje platí Kirchhoffův zákon, je t(A) = vel(t). Odsud je ihned jasné, že musí též platit vel(t) = t(A) ≤ C(A). Protože v síti existuje jen konečně mnoho řezů oddělujících zdroj a spotřebič, existuje řez B, jehož kapacita je minimální mezi kapacitami všech řezů. Tento řez nazveme minimální a jeho kapacitu minimální kapacitou sítě G. Lze ukázat, že je možno zkonstruovat tok sítí, jehož velikost je rovna minimální kapacitě sítě. Při této konstrukci se kapacita toku na hranách minimálního řezu položí rovna kapacitě a na ostatních hranách se vhodně doplní. Platí proto následující věta.

Věta. Velikost maximálního toku sítí G je rovna minimální kapacitě sítě G, tj. kapacitě minimálního řezu oddělujícího zdroj a spotřebič.

Najít minimální řez a jeho kapacitu je algoritmicky řešitelné. Stačí vyšetřit všechny řezy, které oddělují zdroj a spotřebič, což znamená zkoumat ty podmnožiny množiny všech vrcholů sítě, které obsahují zdroj a neobsahují spotřebič. Takový algoritmus je exponenciální časové složitosti, což je nevhodné. Na druhou stranu je jistě důležité, znát minimální řezy sítě, protože na nich lze nalézt „nejslabší” místa sítě. Na obr. 20 je zobrazen příklad sítě. V následující tabulce jsou uvedeny kapacity všech 64 možných řezů této sítě, které oddělují zdroj a spotřebič. V tabulce je vidět, že nejmenší kapacita řezu, která se v ní vyskytuje je číslo 5. Zároveň vidíme, že „nejslabšími” místem sítě je hrana h = (z, a). V pravé polovině obr. 20 je uveden maximální možný tok touto sítí. V našem příkladě je maximální tok sítí určen jednoznačně, což obecně být nemusí. Nechť je například kapacita hran h1 = (z, a), h2 = (z, b) sítě z obr. 20 rovna 1 a nechť je kapacita ostatních hran sítě alespoň 2, pak je hodnota maximálního toku sítí rovna 2 a jistě najdete více možností jak tok sítí realizovat.

35

řez A C(A) z 7 z, d 10 z, a, c 13 z, b, c 5 z, c, d 14 z, d, f 12 z, a, b, e 11 z, a, c, f 18 z, b, c, d 5 z, b, d, f 10 z, c, e, f 16 z, a, b, c, f 12 z, a, c, d, e 11 z, b, c, d, e 7 z, c, d, e, f 15 z, a, b, d, e, f 11

z

1

6 b

a

řez A C(A) z, a 10 z, e 10 z, a, d 9 z, b, d 8 z, c, e 11 z, e, f 15 z, a, b, f 13 z, a, d, e 11 z, b, c, e 5 z, b, e, f 15 z, d, e, f 14 z, a, b, d, e 9 z, a, c, d, f 11 z, b, c, d, f 10 z, a, b, c, d, e 5 z, a, c, d, e, f 13

4

1 4

c

d

3

f 5

1 3

e

2

s

řez A C(A) z, b 5 z, f 12 z, a, e 13 z, b, e 8 z, c, f 16 z, a, b, c 7 z, a, c, d 12 z, a, d, f 11 z, b, c, f 10 z, c, d, e 13 z, a, b, c, d 6 z, a, b, d, f 9 z, a, c, e, f 18 z, b, c, e, f 10 z, a, b, c, d, f 8 z, b, c, d, e, f 8

z

1

4 b

a

řez A C(A) z, c 11 z, a, b 8 z, a, f 15 z, b, f 10 z, d, e 12 z, a, b, d 7 z, a, c, e 13 z, a, e, f 18 z, b, d, e 10 z, c, d, f 16 z, a, b, c, e 7 z, a, b, e, f 15 z, a, d, e, f 13 z, b, d, e, f 12 z, a, b, c, e, f 12 z, a, b, c, d, e, f 7

2

1 4

c

d

3

1 3

e

f 3

2

s

ˇ a maxima ´ ln´i tok s´it´i Obr. 20: S´it Protože nás bude ale také zajímat, jak lze maximální tok sítí realizovat, budeme hledat řešení obou částí základní úlohy najednou. Hledání maximálního toku sítí První nápad, jak nalézt maximální možný tok, spočívá v tom, že nalezneme nějakou cestu od zdroje ke spotřebiči, na této cestě určíme maximální možný tok a budeme zkoumat, zda je možno tento tok „zvětšit” pomocí dalších cest. Předpokládejme, že máme síť G se zdrojem z a spotřebičem s s nezáporným ohodnocením hran (kapacitou) a předpokládejme, že existuje orientovaná cesta od zdroje ke spotřebiči. Příklad takové sítě je uveden na obr. 21. Kapacity hran jsou: c(z, a) = 5, c(z, b) = 6, c(a, b) = 2, c(a, s) = 6 a c(b, s) = 6. Za cestu od zdroje ke spotřebiči vyberme cestu p, která je dána poslouností vrcholů p = (z, a, b, s). Pro větší názornost si ji můžeme popsat pomocí šipek určujících orientaci hran p : z → a → b → s. Jelikož je kapacita hran c(z, a) = 5, c(a, b) = 2 a c(b, s) = 6, je možnou touto cestou realizovat tok, t jehož velikost je vel(t) = 2, na hranách cesty je hodnota toku 2, na ostatních hranách je hodnota toku nulová. Síť G, cesta p a tok sítí t jsou zobrazeny na obr. 21. Hrany s nulovou hodnotou toku nejsou zobrazeny. Pokusme se zjistit, zda existuje ještě další cesta od zdroje ke spotřebiči, která by využívala ještě nepoužité kapacity hran sítě. Vytvoříme si novou síť G1 , tzv. přírustkovou

36

b 6 z

b

5

2 5

s

6

s

6

b 2

2

a

z

5

a

z

a

2

p

G

s

2

t

ˇ G, cesta p a tok t Obr. 21: S´it síť (nebo síť možného zlepšení), kde bude kapacita hran snížena o již použité hodnoty toku t. Bude tedy c1 (z, a) = 3, c1 (z, b) = 6, c1 (a, b) = 0, c1 (a, s) = 6 a c1 (b, s) = 4. Síť G1 je zobrazena obr. 22. Pokud v síti G1 najdeme cestu p1 od zdroje ke spotřebiči, na které lze realizovat nějaký tok , můžeme oba toky spojit v tok t1 , který bude mít velikost rovnou součtu velikostí obou toků (na každé hraně). Vidíme, že taková cesta existuje, je to např. cesta p1 = (z, a, s), tj. z → a → s, na které lze realizovat tok velikosti 3. Po spojení s tokem t dostaneme tok t1 , jehož velikost je vel(t1 ) = 2 + 3 = 5. Cesta p1 i tok t1 jsou zobrazeny na obr. 22.

b

s

5

6 z

s

4

3

b

5 z

a

3

2

a

z

3 a

5

p1

G1

s

2

t1

ˇ G1 , cesta p1 a tok t1 Obr. 22: S´it Nyní můžeme pokračovat, vytvořit si přírůstkovou síť G2 , nalézt, existuje–li, cestu p2 od zdroje ke spotřebiči a vytvořit další tok t2 , který vznikne přidáním získaného toku na cestě p2 k toku t1 . V našem příkladě hledaná cesta existuje, je to cesta p2 = (z, b, s), tj. z → b → s, na které lze realizovat tok velikosti 4. Síť G2 cesta p2 i tok t2 jsou zobrazeny na obr 23.

b

s

4

6

b

2

z

a

G2

4

s

b 4

6 z

z

p2

2 5

s

6 3 a

t2

ˇ G2 , cesta p2 a tok t2 Obr. 23: S´it Kdybychom pokračovali stejným postupem dále, zjistíme, že v přírustkovém grafu G3 (má pouze dvě hrany (z, b) a (a, s)) již neexistuje cesta od zdroje ke spotřebiči. Získali jsme tok sítí G jehož velikost je 9. Na první pohled ale vidíme, že jsme nezískali maximální možný tok sítí G. Ten má velikost 11 a je možno ho realizovat na cestách z → b → s a z → a → s. K tomuto výsledku bychom dospěli, kdybychom za první cestu od spotřebiče

37

ke zdroji zvolili jednu z cest z → b → s nebo z → a → s. Druhou cestu bychom získali ihned v dalším kroku a postup by končil nalezením maximálního toku. Postup, který nás napadl jako první možnost, není korektní protože jeho výsledek závisí např. na volbě první nebo kterékoliv další cesty. Postup umožňoval pouze zvýšit tok na jednotlivých hranách a neumožňoval ho na hranách případně i zmenšovat. Přesto je možno ukázat, že v některých speciálních případech je tento postup, při dobře řízeném hledání dalších cest od zdroje ke spotřebiči, naprosto korektní. Obecně korektní však postup není a proto je vhodné ho poněkud modifikovat. Modifikace bude spočívat v tom, že si u přírůstkového grafu budeme u každé hrany také evidovat o kolik je možno stávající tok na příslušné hraně zvýšit i snížit. V přírůstkovém grafu budeme každou hranu h = (x, y) ohodnocovat dvojicí čísel (m, n), kde číslo m udává kolik toku je ještě možno realizovat ve směru x → y a číslo n bude udávat kolik toku je již ve směru x → y realizováno nebo–li o kolik je možno realizovat tok ve směru y → x. Při hledání cest v přírůstkových grafech nás budou zajímat ty neorientované cesty od zdroje ke spotřebiči, ve kterých je možno realizovat tok kladné velikosti ve směru od zdroje ke spotřebiči. Je–li hrana (x, y) s ohodnocením (m, n) hranou této neorientované cesty, pak pro možnou velikost toku uvažujeme číslo m v případě, že hrana (x, y) je hranou orientovaného grafu G a uvažujeme číslo n v případě, že hranou orientovaného grafu G je hrana (y, x). Někdy se tyto dvě možnosti pro hranu (x, y) rozlišují jako hrana vpřed (je–li (x, y) hranou G) nebo hrana vzad (je–li hranou G hrana (y, x). Algoritmus pro nalezení maximálního toku sítí Nyní si naformulujme algoritmus pro hledání maximálního toku v síti S. Princip bude jednoduchý. Vyjdeme z nějakého toku a budeme hledat neorientované cesty od zdroje ke spotřebiči, na kterých je možno realizovat tok, který po přidání ke stávajícímu toku zlepší stávající tok, tj. zvětší se jeho velikost. Tyto cesty nazýváme zlepšující cesty k danému toku. Poznamenejme, že pro každou zlepšující cestu (z, h1 , . . . , hn , s) musí být první hrana (z, h1 ) a poslední hrana hn , s) na cestě hranami orientované sítě S. V každém kroku vyjdeme ze stávajícího toku, v přírůstkovém grafu nalezneme nějakou zlepšující cestu od zdroje ke spotřebiči a vytvoříme nový tok. Postup budeme ilustrovat na již vyšetřovaném příkladě, a to včetně prvního výběru cesty. 1. (inicializace algoritmu) Mějme síť S, jejíž hrany jsou ohodnoceny nezáporným ohodnocením c. Vyjdeme z nulového toku t0 v síti S, tj. hodnota toku t0 je 0 na každé hraně. Každé hraně h přiřadíme uspořádanou dvojici čísel (c0 (h), p0 (h)) = (c(h), 0). 2. (obecný k–tý krok) Mějme tok tk−1 v síti Sk−1 a každá hrana h je ohodnocena dvojicí čísel (ck−1 (h), pk−1 (h). Vytvořme přírůstkový graf Gk sítě Sk−1 , kde vrcholy grafu Gk jsou stejné jako vrcholy sítě S a hrany h jsou ohodnoceny dvojicí čísel (ck (h), pk (h)), které je definováno takto: ck (h) = c(h) − tk−1 (h) a pk (h) = tk−1 (h). V přírůstkovém grafu Gk nalezneme neorientovanou cestu w od zdroje ke spotřebiči. Nechť m je minimální hodnota ze všech kladných čísel ck (h) pro všechny hrany h, které jsou hranami vpřed na cestě w a ze všech kladných čísel pk (h) pro všechny hrany h, které jsou hranami vzad na cestě w. Definujeme nyní tok tk sítí Sk , jejíž vrcholy jsou stejné jako vrcholy sítě S. Pro každou hranu h = (x, y) sítě S definujeme tk (h) takto: a) tk (h) = tk−1 (h) + m, je–li dvojice vrcholů (x, y) částí cesty w (tj. (x, y) je hranou vpřed na cestě w); b) tk (h) = tk−1 (h) − m, je–li dvojice vrcholů (y, x) částí cesty w (tj. (x, y) je hranou vzad na cestě w); c) tk (h) = tk−1 (h), není–li ani (y, x) ani (y, x) částí cesty w.

38

3. (konec algoritmu) Algoritmus končí, pokud v přírůstkovém grafu Gk neexistuje zlepšující neorientovaná cesta od zdroje ke spotřebiči. Poznámka. Algoritmus musí končit po konečně mnoha krocích, a to už z toho důvodu, že se v každém kroku zvětšuje velikost toku sítí S. To, že jsme získali při neexistenci zlepšující cesty tímto algoritmem skutečně maximální tok sítí S, je nutno dokázat. Předpokládejme, že algoritmus skončil v k – tém kroku nalezením toku tk a že v síti existuje tok t, který má větší velikost vel(t) než je velikost vel(tk ) toku tk nalezeného algoritmem. Potom musí existovat cesta (z, v1 , . . . , vk , s) ze zdroje z ke spotřebiči s, taková že pro každou hranu h vpřed je t(h) − tk (h) > 0 a pro každou hranu h vzad je t(h) − tk (h) < 0. V přírůstkovém grafu Gk tedy existuje zlepšující neorientovaná cesta od zdroje ke spotřebiči, což je ve sporu s ukončením algoritmu. Další problém může být v délce výpočtu. Lze dokázat, že pokud kapacity hran jsou racionální čísla (což lze v praktických úlohách vždy zajistit), výpočet skončí po konečně mnoha krocích. Nyní si algoritmus ilustrujme na našem příkladě. Maximální tok získáme ve čtyřech krocích. Jednotlivé kroky jsou zřejmé z obr. 24.

b H6,0L

z

H6,0L

s

H6,0L

H2,0L H5,0L

H5,0L

H6,0L

z

H4,2L

a

b H6,0L

G3

H3,2L

a

z

H4,2L

s

a

b

a

5

H4,0L

s

b 4 z

p3

3

t2

H6,0L

z

s

2 2

p2

H0,2L H2,3L

H0,5L

b

H5,0L

z

a

a

2

s

H0,2L H5,0L

H3,2L

z

t1

s

G2

z

H5,0L

s

2 2

p1

G1

b

b

H2,0L

z

a

s

2 5

s

6 3 a

t3

Poznámka. To, že jsme skončili již po čtyřech krocích, je také závislé na výběru zlepšujících cest. Kdybychom například pro zlepšující cestu v každém kroku brali zásadně cestu obsahující vrcholy a a b (jednou hranu (a, b) podruhé hranu (b, a)), pak bychom zlepšovali tok o hodnotu 2 resp. o hodnotu 1 a maximální tok bychom dosáhli po 6 krocích. Kdybychom uvažovali síť danou stejným grafem, ale s kapacitou hrany (a, b)

39

b H2,4L

z

H0,6L

s

H0,2L H2,3L

H0,5L

a

s

b H2,4L

a p4

z

s

6 5

6

H0,2L H2,3L

z

G4

b

5

a

t4

´ n´i maxima ´ ln´iho toku v s´iti Obr. 24: Hleda rovnou 1 a kapacitou ostatních hran rovnou 1000, pak by stejně organizovaný algoritmus potřeboval ke svému dokončení 1000 kroků. Modifikace úlohy o maximálním toku sítí Algoritmus nalezení maximálního toku danou sítí je možno použít i v případech, které zcela neodpovídají základnímu zadání úlohy. Požadavek jeden zdroj a jeden spotřebič je lehce odstranitelný pro případ více zdrojů a více spotřebičů. V praktických úlohách tato situace nastává často. Do rozvodné sítě elektrické energie vstupuje více zdrojů a je i více uzlových bodů pro odběr energie. Ve stavebnictví je reálná situace, kdy je k dispozici několik mísíren betonu a několik staveb, které beton odebírají. Mnohé další příklady si jistě najdete i sami. Úlohy o tocích lze samozřejmě kombinovat i s přepravními náklady, např. délkou hrany vynásobenou jednotková cenou za přepravu apod. Úloha s více zdroji a spotřebiči Mějme orientovaný graf G = (V, H) ve kterém je každá jeho hrana h ohodnocena nezáporým číslem c(h), které budeme nazývat kapacitou hrany h. Mějme dále k vrcholů z1 , z2 , . . . , zk , které nazveme zdroje a m vrcholů s1 , s2 , . . . , sm , které nazveme spotřebiče. ,Tokem v této „zobecněné síti” rozumíme každé ohodnocení t(h) hran h, pro které je 0 ≤ t(h) ≤ c(h) a které splňuje v každém vrcholu, který není ani zdroj ani spotřebič, podmínku, že součet toků po hranách přicházející do vrcholu je roven součtu toků po hranách z vrcholu odcházejících (tzv. Kirchhoffův zákon). Maximálním tokem touto „zobecněnou sítí” rozumíme takový tok t, pro který je součet všech toků po hranách i=k P P t(zi , x)) maximálně možný. vycházejících ze zdrojů vel(t) = ( i=1 x∈V + (zi )

Úlohu lze převést na klasickou úlohu o tocích v síti tím, že k danému orientovanému grafu G přidáme dva nové vrcholy z a s a (k + m) nových orientovaných hran (z, z1 ), (z, z2 ) . . . ,(z, zk ) a (s1 , s),(s2 , s), . . . ,(sm , s). Tím dostaneme síť s jedním zdrojem a jedním spotřebičem. Kapacitu nově přidávaných hran volíme dostatečně velkou, tak aby v žádném případě nemohla omezovat tok ve zbytku sítě. Nalezený maximální tok touto sítí nám zároveň dává maximální možný tok od zdrojů z1 , z2 , . . . , zk ke spotřebičům s1 , s2 , . . . , sm . Příklad „zobecněné sítě”, která má dva zdroje a dva spotřebiče a její převod na síť s jedním zdrojem a jedním spotřebičem je uveden na obr. 25. Nalezněte maximální tok touto sítí. Další možná omezení úloh o maximálním toku sítí V praktických úlohách se mohou vyskytovat i další omezující podmínky. Reálnou může být i úloha o nalezení maximálního toku sítí, který splňuje daný požadavek na maximální průchodnost nějakým vrcholem sítě. Mějme dodatečný požadavek na to, aby daným vrcholem v sítě S procházel tok o maximálním povoleném množství max(v).Toto omezení

40

z1 3 a 4 c 2 s1

z1 3 a 4 c 2 s1 10 1

10

z

1

1

s

1

10

10 z2 3 b 1 d 4 s2

z2 3 b 1 d 4 s2

ˇna ´ s´it ˇ a jej´i pr ˇevod na s´it ˇ Obr. 24: Zobece velmi snadno odstraníme tak, že v síti S zdvojíme vrchol v, tj. vrchol v nahradíme dvojicí vrcholů v1 a v2 , které propojíme orientovanou hranou (v1 , v2 ) (tj. v1 → v2 ) s kapacitou max(v). Hrany, které končily ve vrcholu v budou v nové síti končit ve vrcholu v1 a jejich kapacita zůstane zachována. Obdobně hrany, které vycházely z vrcholu v budou v nové síti vycházet z vrcholu v2 a jejich kapacita zůstane zachována. Tím jsme docílili, že tok vrcholem v je omezen požadovaným způsobem. Samozřejmě, že toto lze udělat i pro více vrcholů. Reálnými jsou i úlohy o nalezení toku sítí S, jehož velikost je předem dána a je samozřejmě menší než maximální možná. Nehledáme tedy maximální tok, ale hledáme jak zrealizovat tok o předem dané menší velikosti. Toto se opět odstraní tak, že k dané síti S přidáme nový fiktivní zdroj, např. z0 a orintovanou hranu (z0 , z) (tj. z0 → z), která spojuje fiktivní zdroj s původním zdrojem sítě. Kapacitu této nové hrany položíme rovnu požadavku na velikost toku. Maximální tok novou sítí je roven zadané velikosti toku. Je zřejmé, že maximální tok sítí (resp. tok sítí dané velikosti) nemusí být určen jednoznačně, a proto se jeví účelné hledání toku spojit i s náklady na realizaci toku. Ty mohou být dány například i jednotkovou cenou za realizaci nebo též fixní cenou za použití hrany. Příklady k procvičení 1) Na obr. Cv1 jsou zobrazeny orientované ohodnocené grafy G a H. Nalezněte a) kořenový strom grafu G minimálních (součet ohodnocení hran je co nejmenší) orientovaných cest z vrcholu a do ostatních dosažitelných vrcholů; b) kořenový strom grafu G nejkratších (počet hran je co nejmenší) orientovaných cest z vrcholu a do ostatních dosažitelných vrcholů; c) kořenový strom grafu H minimálních (orientovaných cest z vrcholu a do ostatních dosažitelných vrcholů; d) kořenový strom grafu H nejkratších orientovaných cest z vrcholu a do ostatních dosažitelných vrcholů. a 5 b

3 1 3

c 1 d

2 1 3

e 1 f

2 1 2

g 5 h

a 1 b

7 3 1

G

c

1

3 d

3 1

H Obr. Cv1: Grafy G a H

e 1 f

1 3 1

g 1 h

41

2) Vyjádřete daný aritmetický výraz v v prefixové notaci pre(v) a postfixové notaci post(v), je–li a) v : (3 + 2 · 7) − (1 + 5)(4 − 9); b) v : 9 · (2 + 13 ) + (5 − 7)4 ; Používejte symboly +, −, ∗ (násobení), : (dělení) a ↑ (mocnina). 3) Určete hodnotu aritmetického výrazu v, který je zadán v prefixové notaci pre(v), je–li a) pre(v) : ∗ + 4 ∗ 273; b) pre(v) : +1 + 1 ↑ ∗55 : 12; c) pre(v) : + ∗ −375 ∗ −8 ↑ −95 : 12. 4) Určete hodnotu aritmetického výrazu v, který je zadán postfixové notaci post(v), je–li a) post(v) : 448 ∗ +12 :↑; b) post(v) : 175 ∗ +32 ↑ 5− :; c) post(v) : 1212 :↑ +2 ↑ 1212 :↑ −2 ↑ −. 5) Na obr. Cv5 jsou zobrazeny sítě R a S a kapacity jejich hran. Nalezněte a) maximální toky sítěmi R a S; b) minimální řezy sítí R a S oddělující zdroj a spotřebič s co nejmenším počtem prvků. a

3

c

z

a 5

5 5

1

s

5 5

5 b

2

1

c 4

3 z

3 5

d

3 b

R

s

1 6

d

S Obr. Cv1: Grafy G a H

Výsledky 1) a) V grafu G existují dva kořenové stromy minimálních cest z a. Jsou na zobrazeny na obr. Cv1a); b) v grafu G existují čtyři různé kořenové stromy nejkratších cest z vrcholu a do ostatních dosažitelných vrcholů. Vrchol g je z vrcholu a nedosažitelný. Stromy popíšeme výčtem hran. Jsou to: G1 = {(a, b), (a, c), (a, d), (c, e), (d, f ), (f, h)}, G2 = {(a, b), (a, c), (a, d), (c, e), (d, f ), (e, h)}, G3 = {(a, b), (a, c), (a, d), (c, e), (c, f ), (f, h)}, G4 = {(a, b), (a, c), (a, d), (c, e), (c, f ), (e, h)}; H1 = {(a, b), (a, c), (a, d), (c, e), (d, f ), (f, h)}, H2 = {(a, b), (a, c), (a, d), (c, e), (d, f ), (e, h)}, H3 = {(a, b), (a, c), (a, d), (c, e), (c, f ), (f, h)}, H4 = {(a, b), (a, c), (a, d), (c, e), (c, f ), (e, h)}; c) v grafu G existují dva kořenové stromy minimálních cest z a. Jsou na zobrazeny na obr. Cv1c; d) v grafu H existují čtyři různé kořenové stromy nejkratších cest z vrcholu a do ostatních vrcholů. Stromy popíšeme výčtem hran. Jsou to: H1 = {(a, b), (a, c), (a, d), (d, f ), (f, e), (f, h), (h, g)}, H2 = {(a, b), (a, c), (a, d), (d, f ), (f, e), (f, h), (e, g)}, H3 = {(a, b), (a, c), (a, d), (c, f ), (f, e), (f, h), (h, g)},

42

a 5

c 1

b

1

e 1

d

1

g

5

1

f

a

h

c 1

b

1

e 1

d

g

1 f

1

h

G G ´ ´ Obr. Cv1a): Grafy minimalnich cest v G z vrcholu a a

c

1

1 b

e

g

1 1

d

1

f

1 1

h

a

c

1

1 b

e

1

g

1

h

1 1

d

1

f

H H ´ ln´ich cest v H z vrcholu a Obr. Cv1c): Grafy minima H4 = {(a, b), (a, c), (a, d), (c, f ), (f, e), (f, h), (e, g)}. 2) a) pre(v) : − + 3 ∗ 27 ∗ +15 − 49, post(v) : 327 ∗ +15 + 49 − ∗−; b) pre(v) : + ∗ 9 + 2 : 13 ↑ −574, post(v) : 9213 : + ∗ 57 − 4 ↑ +; 3) a) v = 54; b) v = 6; c) v = 4.√ 4) a) v = 6; b) v = 9; c) v = 4 · 2. 5) a) Maximální toky sítěmi jsou R a S na obr. Cv5a); b) minimální řez sítí R je množina {z, a, b} a minimální řez sítí S je množina {z, a, b, d}. a

3

c

4 z

a 2

1

1

s

2 4

2 b

2

d

1

c

2 z

2 1

s

1

3

3 b

4

R S ´ ln´i toky s´ite ˇmi R a S Obr. Cv5a): Maxima

d