Hledaní nejkrat ooooooooo Matematika III - 9. přednáška Nejkratší cesty, eulerovské grafy, stromy, rovinné grafy Michal Bulant Masarykova univerzita Fakulta informatiky 25. 11. 2009 □ S Obsah přednášky Q Hledání nejkratších cest • Dijkstruv algoritmus pro hledání nejkratších cest • Floyd-Warshallův algoritmus Q Eulerovské grafy a hamiltonovské kružnice Q Stromy Q Rovinné grafy • Platónská tělesa » Barvení map □ 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). 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). Hledaní nejkrat ooooooooo Plán přednášky Q Hledání nejkratších cest • Dijkstruv algoritmus pro hledání nejkratších cest • Floyd-Warshallův algoritmus Stromy Q Rovinné grafy • Platónská tělesa • Barvení map □ s Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Tento algoritmus hledá nejkratší cesty za (reálného) předpokladu, kdy jednotlivé hrany e jsou ohodnoceny vzdálenostmi, tj. kladnými reálnými čísly w(e). Kromě aplikace na hledání vzdáleností v silničních nebo jiných sítích to mohou být také výnosy, toky v sítích atd. 17 Hledaní nejkrat o«ooooooo • Vstupem algoritmu je graf G počáteční vrchol vq. (V, E) s ohodnocením hran a □ s Hledaní nejkrat o«ooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol i/o- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu i/o do vrcholu v. Všimněte si, že místo původní úlohy (nalézt nejkratší cestu mezi dvěma vrcholy) řešíme i něco navíc - nalezneme nejkratší cestu z v do všech vrcholů. Postup dobře funguje v orientovaných i neorientovaných grafech. □ s Hledaní nejkrat o«ooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol i/o- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu i/o do vrcholu v. Všimněte si, že místo původní úlohy (nalézt nejkratší cestu mezi dvěma vrcholy) řešíme i něco navíc - nalezneme nejkratší cestu z v do všech vrcholů. Postup dobře funguje v orientovaných i neorientovaných grafech. Je skutečně podstatné, že všechna naše ohodnocení jsou kladná. Zkusme si rozmyslet třeba cestu P3 se záporně ohodnocenou prostřední hranou. Při procházení sledu mezi krajními vrcholy bychom vzdálenost zmenšovali každým prodloužením sledu o průchod prostřední hranou tam a zpět. □ s Hledaní nejkrat oo«oooooo Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. □ s Hledaní nejkrat oo«oooooo Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. • Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d (v) = dw(v). □ S Hledaní nejkrat oo«oooooo Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. • Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d (v) = dw(v). • Do množiny aktivních (právě zpracovávaných) vrcholů W zařadíme vždy právě ty vrcholy y z množiny spících vrcholů Z, pro které je d{y) = min{c/(z); z G Z}. □ s Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. • Inicializační krok: Nastavíme hodnoty u všech v G V, d (v) nastavíme Z = V, W = 0 pro v = vq OO pro V ^ Vq, □ s - Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. • Inicializační krok: Nastavíme hodnoty u všech v G V, d (v) 0 pro v = vo oo pro v ^ vq, nastavíme Z = V, W = 0. • Test cyklu: Pokud není ohodnocení všech vrcholů y G Z rovno oo, pokračujeme dalším krokem, v opačném případě algoritmus končí. □ s Hledaní nejkrat oooo»oooo • Aktualizace stavu vrcholů: • Najdeme množinu N všech vrcholů v G Z, pro které d(v) nabývá nejmenší možné hodnoty ô = min{c/(y); y G Z}; • posledně zpracované aktivní vrcholy 1/1/ přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme 1/1/ = N a odebereme je ze spících, tj. množina spících bude nadále Z\N. □ s • Aktualizace stavu vrcholu: • Najdeme množinu N všech vrcholů v G Z, pro které d(v) nabývá nejmenší možné hodnoty ô = min{c/(y); y G Z}; • posledně zpracované aktivní vrcholy 1/1/ přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme 1/1/ = N a odebereme je ze spících, tj. množina spících bude nadále Z\N. • Tělo hlavního cyklu: Pro všechny hrany v množině Ewz všech hran vycházejících z některého aktivního vrcholu v a končících ve spícím vrcholu y opakujeme: • Vybereme dosud nezpracovanou hranu e{x,y} G Ewz', • Pokud je d(x) + w(e) < d{y), nahradíme d(y) touto menší hodnotou. Pro všechny vrcholy v ležící v souvislé komponentě vrcholu s najde Dijsktrův algoritmus vzdálenosti dw{v). Vrcholy ostatních souvislých komponent zůstanou ohodnoceny d (v) = oo. Algoritmus lze implementovat tak, že ukončí svoji práci v čase 0{n log n + m), kde n je počet vrcholů a m je počet hran v grafu G. Důkaz. • během celého algoritmu platí d(v) > dw{v) pro všechna ve V. Pro všechny vrcholy v ležící v souvislé komponentě vrcholu s najde Dijsktrův algoritmus vzdálenosti dw{v). Vrcholy ostatních souvislých komponent zůstanou ohodnoceny d (v) = oo. Algoritmus lze implementovat tak, že ukončí svoji práci v čase 0{n log n + m), kde n je počet vrcholů a m je počet hran v grafu G. Důkaz. během celého algoritmu platí d(v) > dw{v) pro všechna ve V. po skončení algoritmu platí d(v) < dw{v) pro všechna v G V (Prostřednictvím silnějšího tvrzení: jsou-li 0 = d\ < di < ... < d k < oo všechny různé konečné vzdálenosti vrcholů od s a označíme-li Mi = {v G V; dw{v) = dj}, pak se krok Aktualizace stavu vrcholů provede přesně /(-krát a po jeho /-tém vykonání platí N = Mj,ö = di a V\Z = u'k=1Mj.) Modifikace algoritmu • Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. □ s Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. Doporučení: h(v) je dolní odhad vzdálenosti v do cílového vrcholu (např. vzdálenost "vzdušnou čarou"). Místo minimalizace d{y) pro y G Z tak v algoritmu minimalizujeme d{y) + h(y). Hledaní nejkrat ooooooo«o Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. □ s Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. Bellman-Fordův algoritmus • pracuje na stejném principu jako Dijkstruv; místo postupu po uzlech je zpracovává "naráz" - cyklus relaxace probíhá (\V\ — 1) krát přes všechny hrany • připouští záporné hrany a detekuje záporné cykly o je obvykle časově náročnější než Dijkstruv • distribuovaná verze je (či spise byla) používána v distance-vector routing protocol □ g - = ^ -00*0 Hledaní nejkrat oooooooo» Floyd-Warshallův algoritmus (all pairs shortest paths) • v čase 0(n3) vypočte vzdálenosti mezi všemi vrcholy • vychází z matice A délek hran a postupně počítá matice Uo, U\,..., U\v\, kde Uk(iJ) je délka nejkratší cesty z / do j, kde cesta prochází pouze vrcholy z {1,2,..., k}. • výpočet vychází ze vztahu Uk(iJ) = min{tyfc_i(/,j), "fc-i('\ ^) + Wfc-i(/f,j)}- • je efektivnější než "upravená mocnina" Ac (násobení —> sčítání, sčítání —>■ minimum) - ta je totiž 0(n4), resp. (optimalizovaná) O(n3logn). □ s Hledaní nejkratsic ooooooooo Plán přednášky 9 Hledaní nejkratších cest 9 Dijkstrův algoritmus pro hledání nejkratších cest a Floyd-Warshallův algoritmus Q Eulerovské grafy a hamiltonovské kružnice Q Stromy Q Rovinné grafy • Platónská tělesa • Barvení map □ s Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek Jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. □ s Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek Jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. Definice Sled, který prochází právě jednou všemi hranami a začíná a končí v jednom vrcholu, se nazývá uzavřený eulerovský tah. Grafům, které takový sled připouští říkáme eulerovské. Hovoříme rovněž o (neuzavřeném) eulerovském tahu, kde vypouštíme požadavek na stejný výchozí a cílový vrchol. Hledaní nejkrat ooooooooo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. □ s Hledaní nejkrat ooooooooo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. Situace je znázorněna na obrázku. Nalevo dobová mapa, napravo odpovídající (multi)graf. Vrcholy tohoto grafu odpovídají souvislé pevnině, hrany mostům. □ s Hledaní nejkra ooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. □ s Hledaní nejkra ooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. □ s Hledaní nejkra ooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. D □ s Hledaní nejkra ooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. D Důsledek Graf lze nakreslit jedním tahem právě tehdy když má všechny stupně vrcholů sudé nebo když existují právě dva vrcholy se stupněm lichým. Hledaní nejkrat ooooooooo Příklad Určete nejmenší počet mostů, které je třeba v Královci přistavět, aby byl graf eulerovský. Jaká je situace v Kaliningradu nyní (od dob Eulerových doznalo zejména působením válek město mnoho změn)? Byl by dnes schopen Euler svoji procházku realizovat? □ s Hledaní nejkratsic ooooooooo Eulerovské orientované grafy Definice Orientovaný graf (V, E) nazveme eulerovský, jestliže v něm existuje uzavřený orientovaný tah, který obsahuje každou hranu právě jednou a každý vrchol aspoň jednou. Orientované eulerovské grafy lze rovněž velmi dobře charakterizovat. K tomu ovšem potřebujeme některé nové pojmy. Definice Orientovaný graf nazveme vyvážený, jestliže pro každý jeho vrchol v platí deg+(i/) = deg_(i/). Symetrizacíorientovaného grafu (V, E) nazýváme neorientovaný graf (V,Ě), kde E = Ux, y}; (x, y) e E nebo (y, x) G E}. Hledaní nejkrat ooooooooo Orientovaný graf G Je eulerovský právě když Je vyvážený a Jeho symetrizace Je souvislý graf (tj. graf G je slabě souvislý). Důkaz. Analogický jako v neorientovaném případe. □ s - = ■€. -o<\(y Problém čínského poštáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Problém čínského poštáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. Problém čínského poštáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. V opačném případě nutně graf obsahuje sudý počet vrcholů lichého stupně. Tento graf je třeba přidáváním hran doplnit na eulerovský (multi)graf (později ukážeme, že v případě stromů to znamená nutnost zdvojení všech hran). Snadno lze ukázat, že to lze udělat v polynomiálním čase jak v orientovaném, tak neorientovaném případě, v případě multigrafů je to však problém NP-úplný. Hledaní nejkratsic ooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Hledaní nejkratsic ooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. Hledaní nejkratsic ooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. V praxi je ovšem problém nalezení hamiltonovské kružnice (či jeho modifikace - např. problém obchodního cestujícího) podstatou mnoha problémů v logistice, je proto často žádoucí nalezení i suboptimálního řešení (v případě problému obchodního cestujícího). Hledaní nejkrat ooooooooo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenovš grafu? □ s Hledaní nejkrat ooooooooo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenově grafu? Věta (Dirac (1952)) Má-li v grafu G s n > 3 vrcholy každý vrchol stupeň alespoň n/2, je G hamiltonovský. Věta (Ore (I960)) Má-li v grafu G s n > 4 vrcholy každá dvojice nesousedních vrcholů součet stupňů alespoň n, je G hamiltonovský. Hledaní nejkrat ooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf cl{G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(i/) > n. □ s Hledaní nejkrat ooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf cl{G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(i/) > n. Věta (Bondy, Chvátá I (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. □ s Hledaní nejkrat ooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf cl{G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(i/) > n. Věta (Bondy, Chvátá I (1972)) Graf G je hamiltonovský, právě když je cl{G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je triviálním důsledkem této věty. □ s - Hledaní nejkratsic ooooooooo Plán přednášky :est 9 Dijkstrův algoritmus pro hledání nejkratších cest a Floyd-Warshallův algoritmus Stromy Q Rovinné grafy • Platónská tělesa • Barvení map n S - = -E -00*0 Hledaní nejkra ooooooooo Definice Souvislý graf neobsahující kružnici, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). □ s Hledaní nejkra ooooooooo Definice Souvislý graf neobsahující kružnici, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). Obecněji, graf neobsahující kružnice nazýváme les._____________________________________________________ Tato definice nicméně není úplně nejvhodnější pro praktickou kontrolu - uvedeme proto za chvíli hned 5 ekvivalentních definic. Následující lemma ukazuje, že každý strom lze vybudovat postupně z jediného vrcholu přidáváním listů: □ s Hledaní nejkra ooooooooo Definice Souvislý graf neobsahující kružnici, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). Obecněji, graf neobsahující kružnice nazýváme les.___________________________________________________________ Tato definice nicméně není úplně nejvhodnější pro praktickou kontrolu - uvedeme proto za chvíli hned 5 ekvivalentních definic. Následující lemma ukazuje, že každý strom lze vybudovat postupně z jediného vrcholu přidáváním listů: Lemma Každý strom s alespoň dvěma vrcholy obsahuje alespoň dva listy. Pro libovolný graf G s listem v jsou následující tvrzení ekvivalentní: 9 G je strom; • G \v je strom. Charakterizace stromů Pro každý graf G = (V, E) jsou následující podmínky ekvivalentní O G je strom; Q pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; O graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf Q graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne Q G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah (Eulerův vzorec) \V\ = \E\ + 1. Důkaz jednotlivých implikací obvykle vedeme indukcí podle počtu vrcholů s využitím lemmatu o výstavbě stromů. Charakterizace stromů Pro každý graf G = (V, E) jsou následující podmínky ekvivalentní O G je strom; Q pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; O graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf Q graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne Q G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah (Eulerův vzorec) \V\ = \E\ + 1. Důkaz jednotlivých implikací obvykle vedeme indukcí podle počtu vrcholů s využitím lemmatu o výstavbě stromů. Ke stromům se vrátíme později v souvislosti s praktickými aplikacemi. Hledaní nejkratsic ooooooooo Plán přednášky :est 9 Dijkstrův algoritmus pro hledání nejkratších cest a Floyd-Warshallův algoritmus Stromy Q Rovinné grafy • Platónská tělesa » Barvení map □ s Hledaní nejkratsic ooooooooo Rovinné grafy Velice často se setkáváme s grafy, které jsou nakresleny v rovině. To znamená, že každý vrchol grafu je ztotožněn s nějakým bodem v rovině a hrany mezi vrcholy v a w odpovídají spojitým křivkám c : [0,1] —> R2 spojujícím vrcholy c(0) = v a c(l) = w. Pokud navíc platí, že se jednotlivé dvojice hran protínají nejvýše v koncových vrcholech, pak hovoříme o rovinném grafu G. Hledaní nejkratsic ooooooooo Rovinné grafy Velice často se setkáváme s grafy, které jsou nakresleny v rovině. To znamená, že každý vrchol grafu je ztotožněn s nějakým bodem v rovině a hrany mezi vrcholy v a w odpovídají spojitým křivkám c : [0,1] —> R2 spojujícím vrcholy c(0) = v a c(l) = w. Pokud navíc platí, že se jednotlivé dvojice hran protínají nejvýše v koncových vrcholech, pak hovoříme o rovinném grafu G. Otázka, jestli daný graf připouští realizaci (nakreslení) jako rovinný graf, vyvstává velice často v aplikacích. Hledaní nejkra ooooooooo Jednoduchý příklad je následující: Tři dodavatelé vody, elektřiny a plynu mají každý své jedno přípojné místo v blízkosti tří rodinných domků. Chtějí je všichni napojit tak, aby se jejich sítě nekřížily (třeba se jim nechce kopat příliš hluboko.. .). Je to možné zvládnout? Odpověď zní není. □ s Hledaní nejkra ooooooooo Jednoduchý příklad je následující: Tři dodavatelé vody, elektřiny a plynu mají každý své jedno přípojné místo v blízkosti tří rodinných domků. Chtějí je všichni napojit tak, aby se jejich sítě nekřížily (třeba se jim nechce kopat příliš hluboko.. .). Je to možné zvládnout? Odpověď zní není. Jde o bipartitní úplný graf K33, kde tři vrcholy představují přípojná místa, další tři pak domky. Hrany jsou linie sítí. Všechny hrany umíme zvládnout, jedna poslední ale už nejde, viz obrázek na kterém neumíme čárkovanou hranu nakreslit bez křížení: □ s Hledaní nejkrat ooooooooo Obecně se dá ukázat tzv. Kuratowského věta: Graf G Je rovinný právě tehdy když žádný Jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. □ g - = Hledaní nejkrat ooooooooo Obecně se dá ukázat tzv. Kuratowského věta: Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. Jedna implikace je zřejmá - dělením rovinného grafu vzniká vždy opět rovinný graf a jestliže podgraf nelze v rovině nakreslit bez křížení, totéž musí platit i pro celý graf G. Opačný směr důkazu je naopak velice složitý a nebudeme se jím zde zabývat. □ s Hledaní nejkrat ooooooooo Obecně se dá ukázat tzv. Kuratowského věta: Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. Jedna implikace je zřejmá - dělením rovinného grafu vzniká vždy opět rovinný graf a jestliže podgraf nelze v rovině nakreslit bez křížení, totéž musí platit i pro celý graf G. Opačný směr důkazu je naopak velice složitý a nebudeme se jím zde zabývat. Problematice rovinných grafů je věnováno ve výzkumu a aplikacích hodně pozornosti, my se zde omezíme pouze na vybrané ilustrace. Zmiňme alespoň naokraj, že existují algoritmy, které testují rovinnost grafu na n vrcholech v čase 0{rí), což určitě nejde přímou aplikací Kuratowského věty. □ s Hledaní nejkrat ooooooooo Uvažme (konečný) rovinný graf G, včetně jeho nakreslení v R2 a nechť S je množina všech bodů x G R2, které nepatří žádné hraně, ani nejsou vrcholem. Množina R2 \ G se rozpadne na disjunktní souvislé podmnožiny S/, kterým říkáme stěny rovinného grafu G. Jedna stěna je výjimečná - ta jejíž doplněk obsahuje všechny vrcholy grafu. Budeme jí říkat neohraničená stěna So. Množinu všech stěn budeme označovat S = {So, Si,..., Sk} a rovinný graf G = (l/,E,S). □ S Hledaní nejkrat ooooooooo Jako příklad si můžeme rozebrat stromy. Každý strom je zjevně rovinný graf, jak je vidět například z možnosti realizovat jej postupným přidáváním listů k jedinému vrcholu. Samozřejmě také můžeme použít Kuratowského větu - když není v G žádná kružnice, nemůže obsahovat jakékoliv dělení grafů K33 nebo K5. Protože strom G neobsahuje žádnou kružnici, dostáváme pouze jedinou stěnu So a to tu neohraničenou. Protože víme, jaký je rozdíl mezi počty vrcholů a hran pro všechny stromy, dostáváme vztah W\ \E\ + \S\ 2. □ s Hledaní nejkrat ooooooooo 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. Hledaní nejkrat ooooooooo 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 Hledaní nejkrat ooooooooo Rovinné grafy si můžeme dobře představit jako namalované na povrchu koule místo v rovině. Sféra vznikne z roviny tak, že přidáme jeden bod v nekonečnu. Opět můžeme stejným způsobem hvořit o stěnách a pro takovýto graf pak jsou všechny jeho stěny rovnocenné (i stěna So je ohraničená). □ s Hledaní nejkrat ooooooooo Rovinné grafy si můžeme dobře představit jako namalované na povrchu koule místo v rovině. Sféra vznikne z roviny tak, že přidáme jeden bod v nekonečnu. Opět můžeme stejným způsobem hvořit o stěnách a pro takovýto graf pak jsou všechny jeho stěny rovnocenné (i stěna So je ohraničená). Naopak, každý konvexní mnohostěn P c M3 si můžeme představit jako graf nakreslený na povrchu koule. Vypuštěním jednoho bodu uvnitř jedné ze stěn (ta stane neohraničenou stěnou So) pak obdržíme rovinný graf jako výše. □ s Hledaní nejkrat ooooooooo Rovinné grafy, které vzniknou z konvexních mnohostěnů, jsou zjevně 2-souvislé, protože každé dva vrcholy v konvexním mnohostěnu leží na společné kružnici. Navíc v nich platí, že každá stěna kromě So je vnitřkem nějaké kružnice a So je vnějškem nějaké kružnice. Názorné se zdá i to, že ve skutečnosti budou grafy vznikající z konvexních mnohostěnů 3-souvislé. □ s Hledaní nejkrat ooooooooo Rovinné grafy, které vzniknou z konvexních mnohostěnů, jsou zjevně 2-souvislé, protože každé dva vrcholy v konvexním mnohostěnu leží na společné kružnici. Navíc v nich platí, že každá stěna kromě So je vnitřkem nějaké kružnice a So je vnějškem nějaké kružnice. Názorné se zdá i to, že ve skutečnosti budou grafy vznikající z konvexních mnohostěnů 3-souvislé. Ve skutečnosti platí dosti náročná Steinitzova věta: Libovolný vrcholově 3-souvislý rovinný graf G vzniká z konvexního mnohostěnu vM3. □ s Hledaní nejkrat ooooooooo 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 Hledaní nejkrat ooooooooo 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 Hledaní nejkrat ooooooooo 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 □ S Hledaní nejkrat ooooooooo 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 M»I WW] 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 /c 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. n 3 - = -E -00*0 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 Hledaní nejkrat ooooooooo Důsledek K. 5 není rovinný; ■»I«I»I»I I»I»M □ s Hledaní nejkrat ooooooooo Důsledek • K5 není rovinný; 9 K33 není rovinný; ■»I«I»I»I I»I»M □ s Hledaní nejkrat ooooooooo ■»I«I»I»I I»I»M Důsledek • K5 není rovinný; • K33 není rovinný; 9 každý rovinný graf obsahuje alespoň Jeden vrchol stupně nejvýše 5; □ s Hledaní nejkrat ooooooooo ■»I«I»I»I I»I»M Důsledek • K5 není rovinný; • K33 není rovinný; 9 každý rovinný graf obsahuje alespoň Jeden vrchol stupně nejvýše 5; 9 každý rovinný graf bez trojúhelníků obsahuje alespoň Jeden vrchol stupně nejvýše 3. □ s Hledaní nejkratsic ooooooooo 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). Hledaní nejkrat ooooooooo 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