Rovinne grafy ooooooo Matematika atika III - 10. přednáška Stromy a kostry Michal Bulant Masarykova univerzita Fakulta informatiky 2. 12. 2009 □ S Obsah přednášky Q Rovinné grafy • Platónska tělesa 9 Barvení map Izomorfismy stromu Kostra grafu Q Minimálni kostra □ s Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU □ s Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetril, Kapitoly z diskrétni matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ □ s Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetril, Kapitoly z diskrétni matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). □ s Plán přednášky O Rovinné grafy • Platónská tělesa 9 Barvení map Izorrn stromu Kostra grafu Q Minimální kostra □ s Rovinne grafy ooooooo Vztah mezi počty hran, stěn a vrcholů lze odvodit pro všechny rovinné grafy. Jde o tzv. Eulerův vztah. Všimněme si, že z něho zejména vyplývá, že počet stěn v rovinném grafu nezávisí na způsobu, jaké jeho rovinné nakreslení vybereme. Rovinne grafy ooooooo Vztah mezi počty hran, stěn a vrcholů lze odvodit pro všechny rovinné grafy. Jde o tzv. Eulerův vztah. Všimněme si, že z něho zejména vyplývá, že počet stěn v rovinném grafu nezávisí na způsobu, jaké jeho rovinné nakreslení vybereme. ' Věta Necht G = (V, E,S) je souvislý rovinný graf. Pak platí \V\ -\E\ + \S\ =2. Důkaz. Indukcí podle počtu hran. D □ s Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelních mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelných mnohoúhelníků tak, že se jich v každém vrcholu dotýká stejný počet. Již v dobách antického myslitele Platóna se vědělo, že jich je pouze pět: □ s Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelních mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelných mnohoúhelníků tak, že se jich v každém vrcholu dotýká stejný počet. Již v dobách antického myslitele Platóna se vědělo, že jich je pouze pět: □ s Přeložíme si požadavek pravidelnosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň d > 3 a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů. Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s počtem hran: dn = 2e Rovinne grafy o«ooooo Přeložíme si požadavek pravidelnosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň d > 3 a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů. Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s počtem hran: dn = 2e a podobně počítáme počet hran, které ohraničují jednotlivé stěny, a bereme v úvahu, že každá je hranicí dvou stěn, tj. ks. 2e Eulerův vztah pak říká 2 = n e + s 2e 2e -J-e + T- Úpravou odtud dostáváme pro naše známé d a k vztah 1 1 -d + ~k 1 1 2 + ě- □ s Rovinne grafy oo«oooo Protože e a n musí být přirozená čísla (tj. zejména je \ > 0) a minimum pro d i k je 3, dostáváme přímou diskusí všech možností tento výčet: d k n e s 3 3 4 6 4 3 4 8 12 6 4 3 6 12 8 3 5 20 30 12 5 3 12 30 20 Tabulka zadává všechny možnosti. Ve skutečnosti ale také všechny odpovídající pravidelné mnohostěny existují - již jsme je viděli. □ s Maximální počet hran Nechi (V, E, S) je rovinný graf s aspoň třemi vrcholy. Pak \E\ <3\V\ -6. Rovnost přitom nastává pro maximální rovinný graf tj. rovinný graf k němuž nejde při zachování rovinnosti přidat žádnou hranu. Pokud navíc uvažovaný graf neobsahuje trojúhelník (tj. K3 jako podgraf), platí dokonce \E\ < 2\V\ —4. Maximální počet hran Nechi (V, E, S) je rovinný graf s aspoň třemi vrcholy. Pak \E\ <3\V\ -6. Rovnost přitom nastává pro maximální rovinný graf, tj. rovinný graf, k němuž nejde při zachování rovinnosti přidat žádnou hranu. Pokud navíc uvažovaný graf neobsahuje trojúhelník (tj. K3 jako podgraf), platí dokonce \E\ < 2\V\ —4. Důkaz. Maximální rovinný graf má všechny stěny ohraničené kružnicí délky 3, z čehož plyne 3|S| = 2\E\ a odtud již pomocí Eulerova vztahu dostáváme první tvrzení. Podobně v druhé části. D Rovinne grafy oooo»oo Důsledek K. 5 nem rovinný; □ s Rovinne grafy oooo»oo Důsledek • K5 není rovinný; 9 K33 není rovinný; □ s Rovinne grafy oooo»oo Důsledek • K5 není rovinný; • K33 není rovinný; 9 každý rovinný graf obsahuje alespoň Jeden vrchol stupně nejvýše 5; □ s Rovinne grafy oooo»oo Důsledek K5 není rovinný; K33 není rovinný; každý rovinný graf obsahuje alespoň Jeden vrchol stupně nejvýše 5; každý rovinný graf bez trojúhelníků obsahuje alespoň Jeden vrchol stupně nejvýše 3. □ s Rovinne grafy ooooo«o Problém čtyř barev Jedním z nejznámějších kombinatorických problémů je otázka: Je možné každou mapu obarvit 4 barvami? Tento problém sice na první pohled vypadá ryze geometricky, ale dá se přeformulovat do kombinatorické podoby. Definice Mapou nazýváme souvislý rovinný multigraf bez mostů. Normální mapou pak mapu, jejíž všechny vrcholy jsou stupně 3. Obarvení mapy je funkce, která každé stěně mapy přiřadí číslo (barvu). Problém čtyř barev byl rozřešen teprve po více než sto letech bádání- mnoho matematiků na prezentovaný důkaz stále pohlíží s despektem, protože je založen na prověření velkého množství případů pomocí počítače. Elementárními kombinatorickými prostředky je možné alespoň dokázat možnost obarvení normálních map pěti barvami -viz literatura. Věta (Appel, Haken (1976)) Každou normální mapu je možné obarvit pomocí čtyř barev. □ s Plán přednášky Q Rovinné grafy • Platónská tělesa a Barvení map Izomorfismy stromů Kostra grafu Q Minimální kostra □ s Rovinne grafy ooooooo Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. □ s Rovinne grafy ooooooo Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. Po výběru kořenu se začíná graf více podobat skutečnému stromu v přírodě. Stromy s jedním vybraným kořenem nazýváme kořenové stromy. □ s Rovinne grafy ooooooo Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. Po výběru kořenu se začíná graf více podobat skutečnému stromu v přírodě. Stromy s jedním vybraným kořenem nazýváme kořenové stromy. Definice V kořenovém stromu T = (V, E) je vrchol w je následník vrcholu v a naopak i/je předchůdce vrcholu w právě tehdy, když existuje cesta z kořene stromu do w která prochází v a v ^ w. Přímý následník a přímý předchůdce vrcholu jsou pak následníci a předchůdci přímo spojení hranou. Mluvíme také o synech a otcích (patrně v narážce na genealogické stromy). Rovinne grafy ooooooo Definice Binární stromy jsou speciálním případem kořenového stromu, kdy každý otec má nejvýše dva následníky (někdy se ale pod stejným označením binární strom předpokládá, že všechny vrcholy kromě listů mají právě dva následníky). □ s Rovinne grafy ooooooo Definice Binární stromy jsou speciálním případem kořenového stromu, kdy každý otec má nejvýše dva následníky (někdy se ale pod stejným označením binární strom předpokládá, že všechny vrcholy kromě listů mají právě dva následníky). Často jsou vrcholy stromu spojeny s klíči v nějaké úplně uspořádané množině (např. reálná čísla) a slouží k hledání vrcholu s daným klíčem. Je realizováno jako hledání cesty od kořene stromu a v každém vrcholu se podle velikosti rozhodujeme, do kterého ze synů budeme pokračovat (resp. zastavíme hledání, pokud jsme již ve hledaném vrcholu). Abychom mohli tuto cestu jednoznačně krok po kroku určovat, požadujeme aby jeden syn společně se všemi jeho následníky měli menší klíce než druhý syn a všichni jeho následníci. □ s Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Izomorfismus stromů Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Pro popis všech možných izomorfismu (kořenových) stromů je užitečné kromě vztahů otec-syn ještě užitečné mít syny uspořádány v pořadí (třeba v představě odleva doprava nebo podle postupného růstu atd.). Izomorfismus stromů Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Pro popis všech možných izomorfismu (kořenových) stromů je užitečné kromě vztahů otec-syn ještě užitečné mít syny uspořádány v pořadí (třeba v představě odleva doprava nebo podle postupného růstu atd.). Definice Pěstěný strom T = (V,E, vn v) je kořenový strom společně s částečným uspořádáním v na hranách takovým, že srovnatelné jsou vždy právě hrany směřující od jednoho otce k synům. Morfismem kořenových stromů T = (V,E, vr) a T' = (V, E', v'r) rozumíme takový morfismus grafů ip : T —> T', který převádí vr na v'r. Obdobně pro izomorfismy. Pro pěstěné stromy navíc požadujeme aby zobrazení hran zachovávalo částečná uspořádání v a v''. Rovinne grafy ooooooo Kódy stromů Pro pěstěné stromy T = (V, E, vn u) zavedeme jejich (jak uvidíme) jednoznačný popis pomocí slov z nul a jedniček. Obrazně si můžeme představit, že strom kreslíme a každý přírůstek naznačíme dvěma tahy, které si označíme 0 (dolů) a 1 (nahoru). Začneme od listů (příp. mimo kořene), kterým všem přiřadíme slovo 01. Celý strom pak budeme popisovat zřetězováním částí slov tak, že má-li otec v syny uspořádány jako posloupnost v\,... ,V£, a jsou-li již jednotliví synové označeni slovy 1/Vi,... 1/V^, pak pro otce použijeme slovo OWi... W*l. Hovoříme o kódu pěstěného stromu. Rovinne grafy ooooooo Kódy stromů Pro pěstěné stromy T = (V, E, vn u) zavedeme jejich (jak uvidíme) jednoznačný popis pomocí slov z nul a jedniček. Obrazně si můžeme představit, že strom kreslíme a každý přírůstek naznačíme dvěma tahy, které si označíme 0 (dolů) a 1 (nahoru). Začneme od listů (příp. mimo kořene), kterým všem přiřadíme slovo 01. Celý strom pak budeme popisovat zřetězováním částí slov tak, že má-li otec v syny uspořádány jako posloupnost v\,... ,V£, a jsou-li již jednotliví synové označeni slovy 1/Vi,... 1/V^, pak pro otce použijeme slovo OWi... W*l. Hovoříme o kódu pěstěného stromu. Skutečně, kreslením cest dolů a nahoru získáme skutečně původní strom s jednou hranou směřující shora do kořene navíc. □ s Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. Pro nejkratší kód 01 je situace snadná. Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. Pro nejkratší kód 01 je situace snadná. V indukčním kroku je dán kód délky 2(n + 1) tvaru 041, přičemž A = AXA2 ... At je zřetězením několika kódů pěstovaných stromů. Část A\ je tvořena nejkratším prexifex A, který má stejný počet 0 a 1, dále A2, atd. Podle indukčního předpokladu každé A, jednoznačně odpovídá pěstěnému stromu, z čehož zřejmě dostáváme jediný pěstěný strom odpovídající kódu 041. D Rovinne grafy ooooooo Nyní převedeme testovaní izomorfismu kořenových stromů, resp. stromů na testovaní pěstěných stromů. n S - = -E -00*0 Rovinne grafy ooooooo Nyní převedeme testování izomorfismu kořenových stromů, resp. stromů na testování pěstěných stromů. U kořenových stromů lze využít kódy, pokud se podaří určit pořadí jejich synů jednoznačně až na izomorfismus. Na pořadí synů ovšem nezáleží právě tehdy, když jsou podgrafy určené jejich následníky izomorfní. □ s Rovinne grafy ooooooo Nyní převedeme testovaní izomorfismu kořenových stromů, resp. stromů na testovaní pěstěných stromů. U kořenových stromů lze využít kódy, pokud se podaří určit pořadí jejich synů jednoznačně až na izomorfismus. Na pořadí synů ovšem nezáleží právě tehdy, když jsou podgrafy určené jejich následníky izomorfní. Využijeme proto obdobu (rekurzivní) konstrukce kódu pro pěstěné stromy - budeme postupovat obdobně s využitím lexikografického (slovníkového) uspořádní synů podle jejich kódů. Kořenový strom budeme tedy popisovat zřetězováním částí slov tak, že má-li otec v syny již označeny kódy W\,... Wf, pak pro otce použijeme slovo 0Wi...Wel kde pořadí Wi,...,W£je zvoleno tak aby 1/Vi < W2 < ■ ■ ■ < W£. □ S Rovinne grafy ooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl přibližně uprostřed stromu. □ s Rovinne grafy ooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl přibližně uprostřed stromu. Každému vrcholu stromu T přiřadíme hodnotou exc(v) tzv. výstřednosti (excentricity), kterou definujeme pro každý vrchol v jako maximální vzdálenost z v do jiného vrcholu w v T. Tvrzení Bud C( T) množina vrcholů stromu T, jejichž výstřednost nabývá minimální hodnoty (C{T) se nazývá střed/centrum grafu, minimální hodnota pak poloměr grafu). Pak C{T) má jeden vrchol nebo dva vrcholy spojené hranou v T. □ s Rovinne grafy ooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl přibližně uprostřed stromu. Každému vrcholu stromu T přiřadíme hodnotou exc(v) tzv. výstřednosti (excentricity), kterou definujeme pro každý vrchol v jako maximální vzdálenost z v do jiného vrcholu w v T. Tvrzení Bud C( T) množina vrcholů stromu T, jejichž výstřednost nabývá minimální hodnoty (C{T) se nazývá střed/centrum grafu, minimální hodnota pak poloměr grafu). Pak C{T) má jeden vrchol nebo dva vrcholy spojené hranou v T. Snadno indukcí s využitím triviálního faktu, že nejvzdálenějším vrcholem od každého vrcholu i/je nutně list. Centrum T tedy splývá s centrem stromu V', který vznikne z T vypuštěním listů a příslušných hran. D Rovinne grafy ooooooo Libovolnému stromu přiřadíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném případě vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,X2 v C{T) a kód vznikne zřetězením kódů obou kořenových stromů (7~i,xi), (7~2,X2) v pořadí podle lexikografického uspořádání těchto kódů. □ s Rovinne grafy ooooooo Libovolnému stromu přiřadíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném případě vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,X2 v C{T) a kód vznikne zřetězením kódů obou kořenových stromů (7~i,xi), (7~2,X2) v pořadí podle lexikografického uspořádání těchto kódů. Dva stromy T a T1 jsou izomorfní právě, když mají společný kód. □ s Rovinne grafy ooooooo Libovolnému stromu priradíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném prípade vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,X2 v C{T) a kód vznikne zřetězením kódů obou kořenových stromů (7~i,xi), (7~2,X2) v pořadí podle lexikografického uspořádání těchto kódů. Dva stromy T a T1 jsou izomorfní právě, když mají společný kód. Poznámka Z uvedených úvah lze snadno nahlédnout, že algoritmus na testování izomorfismu stromů lze implementovat v lineárním čase vzhledem k počtu vrcholů. □ s Plán přednášky Q Rovinné grafy • Platónská tělesa a Barvení map Izorrn stromu Kostra grafu Q Minimální kostra □ s V praktických aplikacích často zadává graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. V praktických aplikacích často zadává graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. Definice Libovolný strom T = {V E') v grafu G = (V,E), E'CEse nazývá kostra {spanning tree) grafu G (tj faktor grafu, který neobsahuje kružnice). ____, V praktických aplikacích často zadává graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. Definice Libovolný strom T = {V E') v grafu G = (V,E), E'CEse nazývá kostra {spanning tree) grafu G (tj faktor grafu, který neobsahuje kružnice). ____, Evidentně může kostra v grafu existovat pouze pokud je graf G souvislý. Místo formálního důkazu, že platí i opak uvedeme přímo algoritmus, jak kostru grafu sestrojit. Rovinne grafy Izomo ooooooo oooooooo Počet koster grafu Kn Věta (Cayleyho formule) Pro n > 2 je počet koster n{Kn) na Kn (tj. počet stromu na daných n vrcholech) roven nn~2. Poznámka Počet koster je významný pojem používaný v mnoha aplikacích. Např. v elektrotechnice, při hypotetickém předpokladu jednotkového odporu mezi každými dvěma vrcholy spojenými hranou, naměříme mezi 2 vrcholy spojenými hranou (vodičem) odpor, který je roven počtu koster obsahujících tuto hranu lomeno celkový počet koster v grafu □ s Rovinne grafy ooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). □ s Rovinne grafy ooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). Spočítáme dvěma způsoby povykosy (povykos = postup výroby kořenového stromu). Povykos je definován jako trojice (T, r, v), kde T je strom na n vrcholech, r jeho kořen a v očíslování hran, neboli bijekce v : E( T) —> {1, 2,..., n — 1} (začínáme s prázdnou množinou hran a postupně přidáváme hranyv pořadí podle v). □ s Rovinne grafy ooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). Spočítáme dvěma způsoby povykosy (povykos = postup výroby kořenového stromu). Povykos je definován jako trojice (T, r, v), kde T je strom na n vrcholech, r jeho kořen a v očíslování hran, neboli bijekce v : E( T) —> {1, 2,..., n — 1} (začínáme s prázdnou množinou hran a postupně přidáváme hranyv pořadí podle v). Pro každý strom T můžeme kořen r zvolit n způsoby a očíslování hran (n — 1)1 způsoby, proto je počet povykosů n{n — 1)1 • n{Kn). □ s Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností. Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. V každé komponentě již vytvořeného grafu je právě jeden vrchol, z něhož nevychází šipka. Šipka číslo k + 1 musí vést do některého vrcholu a vycházet z kořene některé z ostatních komponent -n(n — k — 1) možností. Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. V každé komponentě již vytvořeného grafu je právě jeden vrchol, z něhož nevychází šipka. Šipka číslo k + 1 musí vést do některého vrcholu a vycházet z kořene některé z ostatních komponent -n(n — k — 1) možností. Celkem máme n-2 Y\n(n-k-l) = (n-l)\n"-1 k=0 způsobů a porovnáním s prvním výpočtem dostaneme tvrzení Seřadíme zcela libovolně všechny hrany e\,..., em v E do pořadí a postupně budujeme množiny hran E,(; = 0,..., m) tak, že Eo = 0 v ř-tém kroku přidáme hranu e-, k E,_i (tj. E-, = E,_i U {e,} ), jestliže tím nevznikne v grafu G; = {V, E) kružnice, a ponecháme Ej = E;_i beze změny v případě opačném. Algoritmus skončí pokud buď má již graf G-, pro nějaké / právě n — 1 hran nebo je již / = m. Pokud zastavujeme z druhého důvodu, byl původní graf nesouvislý a kostra neexistuje. Algoritmus pro nalezení kostry 1 Seřadíme zcela libovolně všechny hrany e\,..., em v E do pořadí a postupně budujeme množiny hran E,(; = 0,..., m) tak, že Eo = 0 v ř-tém kroku přidáme hranu e-, k E;_i (tj. E; = E,_i U {e,} ), jestliže tím nevznikne v grafu G; = {V, E) kružnice, a ponecháme Ej = E/_i beze změny v případě opačném. Algoritmus skončí pokud buď má již graf G-, pro nějaké / právě n — 1 hran nebo je již / = m. Pokud zastavujeme z druhého důvodu, byl původní graf nesouvislý a kostra neexistuje. Výsledkem předchozího algoritmu je vždy les T. Jestliže algoritmus skončí s k < n — 1 hranami, má původní graf n — k komponent. Zejména je tedy T kostrou právě, když algoritmus skončí pro dosažení n — 1 hran. □ s Rovinne grafy ooooooo Tvrzení, že výsledný graf T je lesem, je zřejmé z postupu konstrukce. Je-li k = n — 1, je navíc T strom podle charakterizační věty o stromech. Je-li k < n — 1, je T lesem, s n — k stromovými komponentami, neboť každá další komponenta přispívá jedničkou k hodnotě (n — í) — k (rozdíl počtu hran ve stromu a počtu hran v grafu T). D □ S Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. V abstraktní podobě nám stačí umět pro již zadané třídy ekvivalence na dané množině (v našem případě jsou to vrcholy) slučovat dvě třídy ekvivalence do jedné a nalézat pro daný prvek, do které třídy patří. Pro sjednocení jistě potřebujeme 0{k) času, kde k je počet prvků slučovaných tříd a jistě můžeme použít ohraničení počtu k celkovým počtem vrcholů n. Se třídami si můžeme pamatovat i počty jejich prvků a průběžně pro každý vrchol uchovávat informaci do které třídy patří. Sjednocení dvou tříd tedy představuje přeznačení jména u všech prvků jedné z nich. Máme tedy n — 1 operací sjednocení a m operací testování ekvivalence vrcholů, proto lze složitost ohraničit 0(n2 + tri). Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. V abstraktní podobě nám stačí umět pro již zadané třídy ekvivalence na dané množině (v našem případě jsou to vrcholy) slučovat dvě třídy ekvivalence do jedné a nalézat pro daný prvek, do které třídy patří. Pro sjednocení jistě potřebujeme 0{k) času, kde k je počet prvků slučovaných tříd a jistě můžeme použít ohraničení počtu k celkovým počtem vrcholů n. Se třídami si můžeme pamatovat i počty jejich prvků a průběžně pro každý vrchol uchovávat informaci do které třídy patří. Sjednocení dvou tříd tedy představuje přeznačení jména u všech prvků jedné z nich. Máme tedy n — 1 operací sjednocení a m operací testování ekvivalence vrcholů, proto lze složitost ohraničit 0(n2 + tri). Budeme-li vždy přeznačovat menší ze slučovaných tříd, pak celkový počet operací v našem algoritmu lze ohraničit O(nlogn + m). Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. To = ({V},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v T;_i, mají v T;_i jeden koncový vrchol, ale druhý koncový vrchol do T;_i nepatří. První takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,-. Algoritmus skončí, až taková hrana neexistuje. Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. To = ({V},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v T;_i, mají v T;_i jeden koncový vrchol, ale druhý koncový vrchol do T;_i nepatří. První takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,-. Algoritmus skončí, až taková hrana neexistuje. Evidentně je výsledný graf T (v případě, že má n vrcholů) souvislý a podle počtu vrcholů a hran je to strom. Vrcholy T splývají s vrcholy souvislé komponenty G. Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. To = ({V},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v T;_i, mají v T;_i jeden koncový vrchol, ale druhý koncový vrchol do T;_i nepatří. První takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,-. Algoritmus skončí, až taková hrana neexistuje. Evidentně je výsledný graf T (v případě, že má n vrcholů) souvislý a podle počtu vrcholů a hran je to strom. Vrcholy T splývají s vrcholy souvislé komponenty G. Algoritmus v čase 0{n + tri) nalezne kostru souvislé komponenty zvoleného počátečního vrcholu v. Plán přednášky Q Rovinné grafy • Platónská tělesa a Barvení map Izorrn stromu Kostra grafu Q Minimální kostra □ s Rovinne grafy ooooooo Kromě nalezení kostry je často účelné znát nejlepší možnou kostru vzhledem k nějakému ohodnocení hran. Protože je to obecnou vlastností stromů, každá kostra grafu G má stejný počet hran. V grafech s ohodnocenými hranami, budeme hledat kostry s minimálním součtem ohodnocení použitých hran. Definice Nechť G = (V, E, w) je souvislý graf s ohodnocenými hranami s nezápornými vahami w(e) pro všechny hrany. Jeho minimální kostra {minimum spanning tree) T je taková kostra grafu G, která má mezi všemi jeho kostrami minimální součet ohodnocení všech hran. □ s Rovinne grafy ooooooo Kromě nalezení kostry je často účelné znát nejlepší možnou kostru vzhledem k nějakému ohodnocení hran. Protože je to obecnou vlastností stromů, každá kostra grafu G má stejný počet hran. V grafech s ohodnocenými hranami, budeme hledat kostry s minimálním součtem ohodnocení použitých hran. Definice Nechť G = (V, E, w) je souvislý graf s ohodnocenými hranami s nezápornými vahami w(e) pro všechny hrany. Jeho minimální kostra {minimum spanning tree) T je taková kostra grafu G, která má mezi všemi jeho kostrami minimální součet ohodnocení všech hran. 0 praktičnosti takové úlohy můžete přemýšlet třeba v souvislosti s rozvodnými sítěmi elektřiny, plynu, vody apod (viz např. problém elektrifikace části jižní Moravy, který vyřešil Otakar Borůvka v roce 1926 pomocí algoritmu - v dnešní terminologii - minimální kostry, přestože obor teorie grafů, čekal ještě cca 10 let na svůj oficiální vznik). Kruskaluv algoritmus Předpokládejme, že jsou všechna ohodnocení w(e) hran v grafu G nezáporná. Následujícímu postupu se říká Kruskaluv algoritmus: • Setřídíme všech m hran v E tak, aby w(e1) < w(e2) <••• < w{em). • v tomto pořadí aplikujeme na hrany postup z Algoritmu 1 pro kostru. Kruskalův algoritmus Předpokládejme, že jsou všechna ohodnocení w(e) hran v grafu G nezáporná. Následujícímu postupu se říká Kruskalův algoritmus: • Setřídíme všech m hran v E tak, aby M/(ei) < w(e2) <••• < w{em). • v tomto pořadí aplikujeme na hrany postup z Algoritmu 1 pro kostru. Jde o typický příklad takzvaného hladového (greedy) přístupu, kdy se k maximalizaci zisku (nebo minimalizaci nákladů) snažíme dostat výběrem momentálně nejvýhodnějšího kroku. Často tento přístup zklame, protože nizké náklady na začátku procesu mohou zavinit vysoké na jeho konci. V tomto případě (naštěstí) hladový přístup funguje, nemusíme tedy prohledávat a porovnávat až nn~2 koster na daném grafu. Kruskaluv algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0{m log m), kde m je počet hran v G. □ s Kruskaluv algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0{m log m), kde m je počet hran v G. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. □ s Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0{m log m), kde m je počet hran v G. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. Předpokládejme T) 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e,- G T\ To). □ s Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0{m log m), kde m je počet hran v G. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. Předpokládejme T) 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e,- G T\ To). Pak To U {e,-} obsahuje právě jednu kružnici C. □ s Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0{m log m), kde m je počet hran v G. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. Předpokládejme T) 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e,- G T\ To). Pak To U {e,-} obsahuje právě jednu kružnici C. Na této kružnici tedy existuje hrana ek(k > j). která není v T. Pak ale w{ej<) > w(ej) a kostra s hranami To \ {e^} U {e,-} není horší než To a protože se od T liší "později", měli jsme ji na začátku vybrat místo T). Spor. D □ s I druhý z našich algoritmů pro kostru grafu v předchozím odstavci vede na minimální kostru, když v každém okamžiku volíme ze všech možných hran e-, = {v-,, v/+i}, v-, G V-,, v,+\ G V \ {v;} tu, která má minimální ohodnocení. Rovinne grafy ooooooo I druhý z našich algoritmů pro kostru grafu v předchozím odstavci vede na minimálni kostru, když v každém okamžiku volíme ze všech možných hran e; = {V;, v/+i}, v-, G V-,, v,+\ G V \ {v;} tu, která má minimální ohodnocení. Výsledný postup je Primův algoritmus z roku 1957. Byl ale popsán Jarníkem již v roce 1930. Říkáme mu tedy Jarníkův algoritmus. Jarník vycházel z algoritmu O. Borůvky z r. 1926. Jarníkův algoritmus najde minimální kostru pro každý souvislý graf s libovolným ohodnocením hran. raf I □ s Rovinne grafy ooooooo I druhý z našich algoritmů pro kostru grafu v předchozím odstavci vede na minimálni kostru, když v každém okamžiku volíme ze všech možných hran e; = {V;, v/+i}, v-, G V-,, v,+\ G V \ {v;} tu, která má minimální ohodnocení. Výsledný postup je Primův algoritmus z roku 1957. Byl ale popsán Jarníkem již v roce 1930. Říkáme mu tedy Jarníkův algoritmus. Jarník vycházel z algoritmu O. Borůvky z r. 1926. Jarníkův algoritmus najde minimální kostru pro každý souvislý graf s libovolným ohodnocením hran. raf I Poznámka Borůvkův algoritmus tvoří stále co nejvíce souvislých komponent zaráz. Začneme s jednoprvkovými komponentami v grafu 7o = (V,0) a pak postupně každou komponentu propojíme nejkratší možnou hranou s komponentou jinou. Opět takto obdržíme minimální kostru. Tento algoritmu je základem nejrychlejšího známého algoritmu, běžícího v čase 0{n + m). Rovinne grafy ooooooo Příklad ^ Určete pomocí uvedených algoritmů minimální kostru grafu 8 2 16 12 13 5 7 4 10 6 9 17 3 11 1 15 14 □ s - = ■€. -o<\(y