U vod Budova iní strom j v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo PB165 - Grafy a sítě Kostry grafu Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Obsah přednášky O Úvod Q Budování stromu v grafu Q Průchody grafem • Průchod do šířky • Průchod do hloubky Q Minimální kostra grafu • Primův algoritmus • Kruskalův algoritmus o Borůvkův algoritmus id> <1> « O^O Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Terminologický úvod Definice Stromem v grafu G rozumíme podgraf grafu G, který je stromem. Hrany a vrcholy, které do tohoto stromu náleží, nazýváme stromové. V opačném případě se hrana zve nestromová. Hranu, jejíž jeden krajní vrchol je součástí stromu T v neorientovaném grafu, budeme značit jako okrajovou hranu stromu T. Je-li graf orientovaný, značíme hranu jako okrajovou pokud je součástí stromu T její počáteční vrchol. Obrázek: Strom v grafu je vyznačen plnými vrcholy a tučnými hranami, okrajové hrany čárkovaně. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Růst stromu v grafu Věta Je-li G gráfa T strom v G, potom graf vzniklý z T přidáním jeho libovolné okrajové hrany je také stromem. Důkaz. Jelikož hrana má alespoň jeden ze svých koncových vrcholů v T, existuje cesta z přidaného vrcholu do všech vrcholů T a graf zůstává spojitý. Přidaná hrana má mezi vrcholy stromu T zároveň nejvýše jeden vrchol. Nemůže tedy žádným způsobem vzniknout cyklus a graf zůstává i acyklický, tedy strom. □ Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Kostra grafu Definice Kostra grafu G je takový strom T v grafu G, pro který platí V(T) = V(G)._ • Graf může mít více než jednu kostru. • Každý acyklický podgraf grafu G je obsažen v alespoň jedné kostře grafu G. Obrázek: Kostra je vyznačena tučnými hranami. Uvod Budování stromu v grafu Průchody grafem oooooooooooooooo Minimální kostra grafu oooooooooooo Kostra komponent grafu Graf může mít kostru zřejmě jen v případě, že je souvislý. Pokud souvislý není, mohou ale mít kostru jeho komponenty souvislosti. Kostra nesouvislého grafu je tedy lesem, nikoliv stromem, přičemž každý jeho strom je kostrou jedné komponenty grafu. Uvod Budování stromu v grafu Průchody grafem oooooooooooooooo Minimální kostra grafu oooooooooooo Budování stromu v grafu Vstupem algoritmu je graf G a jeho vrchol v. Výstupem je graf s očíslovanými (přirozenými čísly ohodnocenými) vrcholy 1,..., n. inicializuj strom T jako vrchol v. Nastav počitadlo vrcholů na 1 a označ vrchol v, Dokud strom T neobsahuje všechny vrcholy komponenty, již je podgrafem: Vyber okraj ovou hranu e. Nechť u je jeji vrchol, který neni součásti stromu. Přidej vrchol u a hranu e do stromu T. Zvyš hodnotu počitadla vrcholů o 1. Dčisluj vrchol u. Vrať strom T. Uvod Budování stromu v grafu Průchody grafem oooooooooooooooo Minimální kostra grafu oooooooooooo Budov; ání stromu v grafu - příklad Obrázek: Růst stromu. Výstupní strom T je vyznačen tučně, okrajové hrany čárkovaně. Uvod Budování stromu v grafu Průchody grafem oooooooooooooooo Minimální kostra grafu oooooooooooo Budování stromu v grafu - vlastnosti • Výběr okrajové hrany musí být proveden podle deterministického pravidla, aby výstup byl jednoznačný. • Hranám je přidělena priorita a do grafu je přidána vždy ta s prioritou nejvyšší. • Je-li algoritmus spuštěn z počátečního vrcholu v, strom T složený z očíslovaných vrcholů a stromových hran je kostrou komponenty grafu G, jíž je vrchol v součástí. » Graf je spojitý právě když algoritmus budování stromu připojí všechny vrcholy tohoto grafu. Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Budování stromu v orientovaném grafu Algoritmus budování stromu v orientovaném grafu je stejný jako v případě grafu neorientovaného. Výstupní stromy se ovšem mohou lišit počtem vrcholů v závislosti na tom, který vrchol je vybrán jako počáteční. u v w x y •-*->•->•-«• Výstup algoritmu budování stromu v orientovaném grafu na obrázku se bude lišit v závislosti na vybraném počátečním vrcholu. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Strom v grafu - cvičení O Nakreslete výstup algoritmu budování stromu v grafu, je-li vstupem graf na obrázku. Priorita hran je určena lexikografickým pořadím sestupně (lexikograficky menší hrana má vyšší prioritu) a výpočet začíná ve vrcholu: O a & c Problém v nezáporně hranově ohodnoceném grafu Nalezení minimálního spojitého podgrafu obsahujícího podmnožinu vrcholů Ve většině variant N F'-úplný, v praxi heuristiky Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu •ooooooooooooooo oooooooooooo • BFS (Breadth-First Search) • Předpokládáme, že vstupem je souvislý neorientovaný graf. • Slouží k prohledání a navštívení všech vrcholů grafu. • Vrcholy jsou navštěvovány v pořadí podle vzdálenosti od počátečního vrcholu. • Nalezne nej kratší cestu z počátečního vrcholu do všech ostatních. • Při průchodu grafem je budován strom cest do všech jeho vrcholů. • Pro implementaci algoritmu se používá fronta. Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu o»oooooooooooooo oooooooooooo Inicializuj strom T vrcholem v. Nastav dist [v] = 0, dist[x]=nedosažitelný pro x != v. Inicializuj množinu okrajových hran jako prázdnou. Inicializuj počitadlo vrcholů na 1 a označ jim vrchol v. Dokud nejsou označeny všechny vrcholy, opakuj: Aktualizuj seznam okrajových hran. Vyber okrajovou hranu e, jež vycházi z očíslovaného vrcholu w s nejnižším možným číslem. Přidej hranu e a její koncový vrchol u do stromu T. Zvyš počítadlo vrcholů o 1. Očísluj přidaný vrchol u. Nastav dist[u] = dist[w] + 1. Vrať strom T. U vod Budova iní strom j v grafu Průchody grafem Minimální kostra graft 00*0000000000000 oooooooooooo U vod Budova iní strom j v grafu Průchody grafem Minimální kostra graft ooo»oooooooooooo oooooooooooo Inicializuj strom T vrcholem v. Nastav dist [v] = 0, dist [x] = -1 pro x != v. Inicializuj frontu vrcholů jako prázdnou a vlož v. Inicializuj počitadlo vrcholů na 1 a označ jim vrchol v. Dokud jsou ve frontě nějaké vrcholy, opakuj: Z počátku fronty odeber vrchol w. Dokud je e hrana vycházející z w do x: Je-li x neočíslovaný: Zvyš počítadlo vrcholů o 1. Očísluj x. Nastav dist [x] = dist [w] + 1. Přidej x na konec fronty. Přidej vrchol x a hranu e do T. Vrať strom T. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooo»ooooooooooo oooooooooooo Průchod do šírky - vlastnosti Necht u, v jsou vrcholy v grafu G. Vzdálenost vrcholů u, v (počet hran na nejkratší cestě mezi těmito vrcholy) budeme značit S(u, v). Neexistuje-li cesta mezi těmito vrcholy, klademe S(u, v) — oo. Lemma 1 Necht (u, v) je hrana v grafu G. Potom platí Vse V{G) : S{s, v) S{s, v) Důkaz. Důkaz je veden indukcí k počtu vložení vrcholů do fronty: « Tvrzení zřejmě platí po vložení počátečního vrcholu s do fronty. • Uvažujme vkládání do fronty vrcholu x, do nějž vede hrana z w. Z indukčního předpokladu dist[w] > ô(s, w) a Lemmatu 1 plyne: dist[x] = dist[w] + 1 > ó(s, w) + l> 5(s,x) □ Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooo»ooooooooo oooooooooooo Průchod do šířky - vlastnosti Lemma 3 Pro vrcholy < vi,..., > fronty v BFS platí dist[i/7r] < dist[vi] A dist[i/,-] < dist[i//+i] Důkaz. Indukcí k počtu operací vkládání a odebírání na frontě: • Po vložení počátečního vrcholu zřejmě tvrzení platí. • Indukční krok: odebráním vrcholu se platnost tvrzení změnit nemůže. Pokud dist[i/i] = distfi/^], pak po odebrání dist[i/i] jsou přidány vrcholy o vzdálenosti rovné distfi/^] + 1. V druhém případě, kdy dist[i/i] + 1 = distfi/^], jsou po odebrání dist[i/i] přidány vrcholy o vzdálenosti rovné distfi/^]. _□ Uvod Budova ní strom j v grafu Průchody grafem Minimální kostra grafu ooooooo»oooooooo oooooooooooo Průcho d do šír ky- - důkaz Věta Po skončení algoritmu BFS s počátečním vrcholem s na grafu G jsou očíslovány všechny vrcholy dosažitelné z s a v poli dist jsou hodnoty 5(s, v). Důkaz. Pro nedosažitelné vrcholy tvrzení zřejmě platí. Označme množinu vrcholů, pro něž 5(s, v) = k. Dokážeme, že pro každý vrchol v jsou následující kroky provedeny právě jednou: O Očíslování vrcholu. Q Nastavení dist [v] O Vložení v do fronty. Důkaz bude veden indukcí ke k. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooo»ooooooo oooooooooooo Průchod do šířky - důkaz Důkaz - pokračování. • Pro k = 0, tedy počáteční vrchol, jsou tyto kroky provedeny jedinkrát při inicializaci. • Indukční krok: Fronta se před skončením výpočtu nikdy nevyprázdní a poté, co je do ní vrchol vložen, se jeho vypočtená vzdálenost ani očíslování nemění. Uvažujme libovolný vrchol v G V^,k > 1. Z lemmat 2 a 3 plyne, že vrchol v může být navštíven až poté, co jsou do fronty přidány všechny vrcholy z množiny V^-i- Jelikož ô(s, v) = k, existuje na cestě z s do v vrchol u G V^-i takový, že existuje hrana (u, v). Nechť u je první takový vrchol přidaný do fronty. Potom je vrchol v objeven právě z vrcholu u a platí dist[v] = dist [u] +1. Budování stromu v grafu Průchody grafem Minimální kostra grafu ooooooooo»oooooo oooooooooooo Průchod do šírky - složitost Každou hranu " projdeme" právě jednou a všechny vrcholy také navštívíme právě jednou. Při vhodné implementaci fronty, která umožňuje přidávání a odebírání vrcholů v konstantním čase, je tedy časová složitost BFS 0{\V\ + |E|). Poznámka Prezentovaný algoritmus lze snadno upravit tak, aby krom výpočtu vzdálenosti od počátečního vrcholu s vypočítal i jeho předchůdce na nej kratší cestě z s. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooo»ooooo oooooooooooo Průchod grafem do hloubky • DFS - Depth First Search » Namísto postupného procházení vrcholů od nejbližších ke kořeni postupuje algoritmus do hloubky - dokud je to možné, vybere vždy hranu vedoucí dále z vrcholu, do kterého právě vstoupil. Poté se vrací stromem ke kořenu - " backtrackuje" . • Algoritmus i jeho implementace velice podobné BFS - stejná časová složitost. • Projde všemi vrcholy grafu. • Vstupem je rovněž neorientovaný souvislý graf • Nenalezne nejkratší cesty do vrcholů. • DFS vhodnější pro prohledávání stavových prostorů a heuristiky. • K implementaci se používá zásobník. Budování stromu v grafu Průchody grafem Minimální kostra grafu ooooooooooo»oooo oooooooooooo Průchod grafem do hloubky Inicializuj strom T vrcholem v. Inicializuj množinu okrajových hran jako prázdnou. Inicializuj počitadlo vrcholů na 1 a označ jim vrchol v. Dokud nejsou označeny všechny vrcholy, opakuj: Aktualizuj seznam okrajových hran. Vyber okrajovou hranu e, jež vycházi z očíslovaného vrcholu w s nejvyšším možným číslem. Přidej hranu e a její koncový vrchol u do stromu T. Zvyš počítadlo vrcholů o 1. Očísluj přidaný vrchol u. Vrať strom T. Uvod Budova iní strom j v grafu Průchody grafem Minimální kostra grafu 000000000000*000 oooooooooooo Průcho d do hic Dllbk ;y - impl ementace Inicializuj strom T vrcholem v. Inicializuj zásobník vrcholů jako prázdný a vlož v. Inicializuj počítadlo vrcholů na 1 a označ jím vrchol v. Dokud jsou v zásobníku nějaké vrcholy, opakuj: Z vrcholu zásobníku odeber vrchol w. Dokud je e hrana vycházející z w do x: Je-li x neočíslovaný: Zvyš počítadlo vrcholů o 1. Očísluj x. Přidej x na vrchol zásobníku. Přidej vrchol x a hranu e do T. Vrať strom T. U vod Budovaní stromu v grafu Průchody grafem ooooooooooooo^oo Minimální kostra grafu oooooooooooo Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooo»o oooooooooooo Průchod do hloubky - vlastnosti Věta Necht T je strom, jenž je výstupem běhu DFS na grafu G, a e hrana z G, která nepatří do stromu T. Necht x, y jsou koncové vrcholy hrany e a platí, že x je algoritmem označen nižším číslem než y. Potom y je následníkem vrcholu x ve stromu T. Důkaz. Vrchol y byl algoritmem zřejmě navštíven později než x. Při vstupu algoritmu do x je hrana (x,y) označena jako okrajová. Vrchol y je však očíslován dříve než algoritmus vrchol x definitivně "opustí"- y je tedy následníkem vrcholu x. □ Budování stromu v grafu Průchody grafem Minimální kostra grafu 000000000000000» oooooooooooo Průchod grafem - cvičení O Pro graf z předchozího cvičení a počáteční vrchol b nakreslete výstup včetně očíslování O průchodu do šířky. © průchodu do hloubky. & Charakterizujte grafy, jejichž výstupní strom včetně očíslování je shodný v případě průchodu do šířky i do hloubky. O Upravte algoritmus BFS, aby u každého vrcholu uložil i jeho předchůdce na cestě z počátečního vrcholu. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Minimální kostra grafu Definice Necht G je souvislý graf s ohodnocenými hranami. Kostra grafu G, jejíž součet ohodnocení všech hran je nejnižší, se nazývá minimální kostra grafu G. • Nalezení nejlevnější, ale neredundantní, počítačové či např. elektrické sítě spojující všechny koncové a aktivní prvky, resp. přípojná místa. • Speciální případ Steinerová stromu Obrázek: Minimální kostra je vyznačena tučně. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooooo Primův algoritmus • Hledání minimální kostry. • Neprohledává systematicky všechny kostry grafu. • Začíná v libovolném vrcholu a buduje strom. • Nejvyšší prioritu mají hrany s nejnižším ohodnocením. • Stále existuje jen jedna komponenta minimální kostry, která postupně roste. • Složitost závisí na datové struktuře ukládající okrajové hrany: Matice sousednosti Binární halda Fibonacciho halda 0{V2) 0(Elog(V)) 0{E+Vlog{V)) Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo »00000000000 Primův algoritmus Vyber libovolný vrchol s vstupního grafu. Inicializuj výstupní strom T vrcholem s. Inicializuj množinu okrajových hran jako prázdnou. Dokud T neobsahuje všechny vrcholy: Aktualizuj množinu okrajových hran. Nechť e je okrajová hrana s nejnižším ohodnocením a její koncový vrchol v nepatřící do T. Přidej vrchol v a hranu e do stromu T. Vrať strom T. Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo o0oooooooooo Primův algoritmus - důkaz Věta Výstupní strom vytvořený k iteracemi Primová algoritmu je podstromem minimální kostry grafu. Důkaz. * Indukcí přes k: O Pro k = 0 patří do grafu jen vrchol s. O Nechť T"^ je podstromem minimální kostry T a strom Tk+i vznikne přidáním hrany e s minimálním ohodnocením, jejíž vrchol u patří do a v nikoliv. □ Pokud T obsahuje hranu e, je 7Vi-i podstromem minimální kostry. V případě, že hrana e do minimální kostry nepatří, existuje v grafu T + e (minimální kostra s přidanou hranou e) cyklus hranou e procházející. Nechť f je první hrana na "delšfcestě mezi vrcholy u, v taková, že nepatří do T^. Potom je i f okrajová hrana stromu Tk, ale má nižší prioritu (tudíž vyšší ohodnocení) než hrana e. Nahradíme-li tedy v T hranu f hranou e, celková váha se nezvýší a vzniklá kostra bude minimální. oooooooäoooo njEJ§ Ejq.SO>| IU|ELUIUI[/\| oooooooooooooooo uuajejS Äpoipn.1,-1 njej§ a riLuojq.s lueAopng poAn Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo ooooo»oooooo Kruskalův algoritmus • Druhý algoritmus pro hledání minimální kostry grafu. • Nepostupuje cestou budování stromu, naopak vzniká les. • Přidává hrany seřazené vzestupně podle jejich ohodnocení. • Při použití vhodných datových struktur časová složitost 0(Elog(V)). Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooo»ooooo Kruskalův algoritmus Setřicť hrany grafu G vzestupně podle ohodnocení. Inicializuj seznam komponent souvislosti všemi vrcholy. Dokud je ve výstupním stromu T více než 1 komponenta: Vyber hranu s nejnižším ohodnocením, která spojuje vrcholy ležící v různých komponentách. Přidej tuto hranu do výstupního stromu T. Aktualizuj seznam komponent. Vrať strom T. Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo ooooooooo»oo Borůvkův algoritmus • Vznik roku 1926 pro návrh efektivní elektrické sítě, znovuobjeven 1938, 1951 a v 60. letech • Vycházel z něj Kruskal při návrhu svého algoritmu. • Metoda budování lesa (stejně jako Kruskalův alg.) • Komponenty lesa rostou stejným způsobem jako v Primově algoritmu, ale paralelně • Velmi rychlý růst kostry • Omezení: žádné dvě hrany v grafu nesmějí mít stejné ohodnocení Cvičení: • Proč nesmějí mít dvě hrany v grafu stejné ohodnocení? • Co se může stát, když mají? Musí se to stát vždy? • Jak můžeme algoritmus upravit, aby toto omezení neměl? Úvod Budování stromu v grafu Průchody grafem Minimální kostra grafu oooooooooooooooo oooooooooo»o Borůvkův algoritmus - pseudokód Nechť T je prázdná množina hran Dokud T neni kostra grafu: Nechť E je prázdná množina hran Pro všechny komponenty souvislosti: Nechť S je prázdná množina hran Pro všechny vrcholy komponenty: Přidej do S hranu s nejnižšim ohodnocením, která vede do jiné komponenty Přidej do E nej levněj ši hranu z S Přidej E do T T je minimálni kostra grafu O Na graf na obrázku aplikujte některý z algoritmů hledání minimální kostry. Q Graf na obrázku představuje komunikační síť, kde ohodnocení hran udává pravděpodobnost nechybovosti linky. Pravděpodobnost nechybové cesty v grafu je součinem pravděpodobností všech linek na trase. Najděte nejspolehlivější cestu z s do ŕ.