Matematika III - 7. přednáška Teorie grafů - základní pojmy Michal Bulant Masarykova univerzita Fakulta informatiky 11. 11. 2009 □ S Obsah přednášky Q Základní pojmy teorie grafů • Dva příklady • Základní definice • Galerie jednoduchých grafů O (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy Q Prohledávání v grafech • Prohledávání do šířky a do hloubky □ s - Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU □ s • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní 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/TG.html • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní 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/TG.html • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní 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/TG.html • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). Q Základní pojmy teorie grafů • Dva příklady • Základní definice • Galerie jednoduchých grafů 9 (Iso)Morfismy grafu a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy O Prohledávání v grafech 9 Prohledávání do šířky a do hloubky Příklad Na večírku se někteří návštěvníci po dvojicích znají a jiné dvojice se naopak neznají. Kolik lidí musíme pozvat, abychom zaručili, že se alespoň tři hosté budou buď navzájem znát nebo neznát? □ s Příklad Na večírku se někteří návštěvníci po dvojicích znají a jiné dvojice se naopak neznají. Kolik lidí musíme pozvat, abychom zaručili, že se alespoň tři hosté budou buď navzájem znát nebo neznát? * Představíme situaci pomocí obrázku. Puntíky nám představí jednotlivé hosty, plnou čarou spojíme ty dvojice, které se znají, čárkovanou ty ostatní. Naše tvrzení pak zní: při jakém počtu puntíků vždy najdeme trojúhelník, jehož strany jsou buď všechny plné nebo všechny čárkované? □ s Příklad Na večírku se někteří návštěvníci po dvojicích znají a jiné dvojice se naopak neznají. Kolik lidí musíme pozvat, abychom zaručili, že se alespoň tři hosté budou buď navzájem znát nebo neznát? * Představíme situaci pomocí obrázku. Puntíky nám představí jednotlivé hosty, plnou čarou spojíme ty dvojice, které se znají, čárkovanou ty ostatní. Naše tvrzení pak zní: při jakém počtu puntíků vždy najdeme trojúhelník, jehož strany jsou buď všechny plné nebo všechny čárkované? □ s Příklad Na večírku se někteří návštěvníci po dvojicích znají a jiné dvojice se naopak neznají. Kolik lidí musíme pozvat, abychom zaručili, že se alespoň tři hosté budou buď navzájem znát nebo neznát? * Představíme situaci pomocí obrázku. Puntíky nám představí jednotlivé hosty, plnou čarou spojíme ty dvojice, které se znají, čárkovanou ty ostatní. Naše tvrzení pak zní: při jakém počtu puntíků vždy najdeme trojúhelník, jehož strany jsou buď všechny plné nebo všechny čárkované? Na levém obrázku takový trojúhelník není, uprostřed je. Pravý naznačuje důkaz, že existuje vždy, když počet hostů bude alespoň šest. Představme si krabičku, která požírá jeden bit za druhým podle toho, jestli dveřmi zrovna prošel muž nebo žena -jednička nechť označuje třeba ženu. Přitom svítí buď modře nebo červeně podle toho, zda byl poslední bit nula nebo jednička (a bodle barvy světla tedy poznáme, zda je za dveřmi muž nebo žena. Znázorníme funkci schématem: CQ' Třetí uzel, ze kterého pouze vychází dvě šipky naznačuje start před prvním zaslaným bitem. Takovým schématům se říká konečný automat. □ s Zachytíme společné rysy předchozích příkladů. Definice Grafem G = (V, E) rozumíme množinu V jeho vrcholů (někdy též uzlů) spolu s podmnožinou E množiny (2) všech dvouprvkových podmnožin ve V. Prvkům E říkáme hrany grafu. Vrcholům ve hraně e = {v, w}, v ^ w, říkáme hraniční vrcholy hrany e. O hranách, které mají daný vrchol v za hraniční říkáme, že z vrcholu v vycházejí. □ s Zachytíme společné rysy předchozích příkladů. Definice Grafem G = (V, E) rozumíme množinu V jeho vrcholů (někdy též uzlů) spolu s podmnožinou E množiny (2) všech dvouprvkových podmnožin ve V. Prvkům E říkáme hrany grafu. Vrcholům ve hraně e = {v, w}, v ^ w, říkáme hraniční vrcholy hrany e. O hranách, které mají daný vrchol v za hraniční říkáme, že z vrcholu v vycházejí. Orientovaným grafem G = {V,E) rozumíme množinu V jeho vrcholů spolu s podmnožinou E C V x V. Prvnímu z vrcholů definujících hranu e = (v, w) říkáme počáteční vrchol hrany, druhému pak koncový vrchol. □ s Definice (... pokračování) Hrana e vychází ze svého počátečního vrcholu a vchází do koncového. U orientovaných hran mohou být koncový a počáteční vrchol totožný, hovoříme pak o smyčce. Sousední hrany grafu jsou ty, které sdílí hraniční vrchol, u sousedních hran orientovaného grafu musí být vrchol pro jednu koncový a pro druhou počáteční. Naopak, sousední vrcholy jsou ty, které jsou hraničními pro tutéž hranu. □ s Definice (... pokračování) Hrana e vychází ze svého počátečního vrcholu a vchází do koncového. U orientovaných hran mohou být koncový a počáteční vrchol totožný, hovoříme pak o smyčce. Sousední hrany grafu jsou ty, které sdílí hraniční vrchol, u sousedních hran orientovaného grafu musí být vrchol pro jednu koncový a pro druhou počáteční. Naopak, sousední vrcholy jsou ty, které jsou hraničními pro tutéž hranu. Jistě umíme grafy popisovat pomocí relací, viz první kapitola prvního semestru. Jednoduchým věcem se dá říkat i složitě: □ s Definice (... pokračování) Hrana e vychází ze svého počátečního vrcholu a vchází do koncového. U orientovaných hran mohou být koncový a počáteční vrchol totožný, hovoříme pak o smyčce. Sousední hrany grafu jsou ty, které sdílí hraniční vrchol, u sousedních hran orientovaného grafu musí být vrchol pro jednu koncový a pro druhou počáteční. Naopak, sousední vrcholy jsou ty, které jsou hraničními pro tutéž hranu. Jistě umíme grafy popisovat pomocí relací, viz první kapitola prvního semestru. Jednoduchým věcem se dá říkat i složitě: Např. v prvním příkladu pracujeme na množině hostů se dvěma komplementárními symetrickými a a nti reflexním i relacemi. □ s Grafy - příklad kompromisu mezi přirozeným sklonem k přemýšlením v obrázcích a přesným matematickým vyjadřováním. □ s Grafy - příklad kompromisu mezi přirozeným sklonem k přemýšlením v obrázcích a přesným matematickým vyjadřováním. Časté použití- dodatečné informace o vrcholech nebo hranách (obarvení vrcholů, příp. map, ohodnocení hran apod.) □ s Grafy - příklad kompromisu mezi přirozeným sklonem k přemýšlením v obrázcích a přesným matematickým vyjadřováním. Časté použití- dodatečné informace o vrcholech nebo hranách (obarvení vrcholů, příp. map, ohodnocení hran apod.) Náš první příklad můžeme tedy chápat jako graf s obarvenými hranami. Dokázané tvrzení v této řeči zní: V grafu Kn = (V, (2))sn vrcholy a se všemi možnými hranami obarvenými dvěma barvami, je vždy alespoň jeden trojúhelník z hran o stejné barvě, pokud (-<==> ) je počet vrcholů alespoň šest. □ s Grafu se všemi možnými hranami (tj. E = (2)) říkáme úplný graf. Značíme symbolem Kn, kde n je počet vrcholů grafu. Graf K4 a K5 jsme již viděli, K3 je trojúhelník, K2 je úsečka. □ s Grafu se všemi možnými hranami (tj. E = (2)) říkáme úplný graf. Značíme symbolem Kn, kde n je počet vrcholů grafu. Graf K4 a K5 jsme již viděli, K3 je trojúhelník, K2 je úsečka. Cesta je graf, v němž existuje uspořádání vrcholů (1/0,... ,vn) takové, že E = {e\,..., en}, kde e-, = {1//-1, vj}, pro všechny / = 1,..., n. Hovoříme o cestě délky n a značíme ji Pn. Pokud cestu upravíme tak, že poslední a první vrchol splývají, dostaneme kružnici délky n a značíme Ca/. Na obrázku jsou K3 = C3, C5 a P5 r-J □ S Úplný bipartitní graf vznikne tak, že vrcholy rozdělíme do dvou skupin (tj. obarvíme dvěma barvami) a pak přidáme všechny hrany, které spojí vrcholy z různých skupin. Značíme jej Kmn, kde man jsou počty vrcholů v jednotlivých skupinách. Na obrázku je vidět Ki3, K23 a ^3,3- Y Pro Ví = {ui,..., um}, V2 = {1/1, V =V1UV2a E =V1xV2. ■ ,vn} je Km>n = (V,E), kde □ S Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla 0,..., 2" — 1. Hrany spojí právě ta čísla, která se v zápisu v dvojkové soustavě liší v právě jednom bitu. Na obrázku niže je ŕ/4 a popis vrcholů je naznačen. 1110 nil 0100 1011 0000 0001 □ s Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla 0,..., 2" — 1. Hrany spojí právě ta čísla, která se v zápisu v dvojkové soustavě liší v právě jednom bitu. Na obrázku niže je ŕ/4 a popis vrcholů je naznačen. 1110 nil 1011 0100 0000 0001 Přímo z definice vyplývá, že hyperkostku v dané dimenzi vždy dostaneme tak, že vhodně spojíme hranami dvě hyperkostky o jednu dimenzi menší. Na obrázku je naznačeno spojení dvou ŕ/3 čárkovanými hranami. Samozřejmě ale můžeme tímto způsobem rozložit ŕ/4 mnoha různými způsoby. Cyklický žebřík CLn s 2n vrcholy je složen propojením dvou kopií kružnice Cn tak, že hrany spojí odpovídající vrcholy dle pořadí. Tzv. Petersenův graf je sice docela podobný C/.5, ale ve skutečnosti je to nejjednoduší „vyvraceč nesprávných úvah" - graf, na němž se vyplatí testovat tvrzení, než je začneme dokazovat. O Základní pojmy teorie grafů • Dva příklady • Základní definice a Galerie jednoduchých grafů O (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy O Prohledávání v grafech 9 Prohledávání do šířky a do hloubky Definice Pro grafy G = (V, E) a G' = (V, E') budeme za (homo)morfismus f : G —> G' považovat zobrazení fy : V —> V mezi množinami vrcholů takové, že je-li e = {v, w} hrana v E, pak e' = {f(v), f(w)} musí být hranou v E'. V dalším textu nebudeme ve značení odlišovat morfismus f a zobrazení fy. Zároveň pak takové zobrazení fy určuje i zobrazení f£ : E —> E', f (e) = e', kde e a e' jsou jako výše. Pro orientované grafy je definice shodná, jen pracujeme s uspořádanými dvojicemi e = (v, w) v roli hran. □ s Definice Pro grafy G = (V, E) a G' = (V, E') budeme za (homo)morfismus f : G —> G' považovat zobrazení fy : V —> V mezi množinami vrcholů takové, že je-li e = {v, w} hrana v E, pak e' = {f(v), f(w)} musí být hranou v E'. V dalším textu nebudeme ve značení odlišovat morfismus f a zobrazení fy. Zároveň pak takové zobrazení fy určuje i zobrazení f£ : E —> E', f (e) = e', kde e a e' jsou jako výše. Pro orientované grafy je definice shodná, jen pracujeme s uspořádanými dvojicemi e = (v, w) v roli hran. Všimněme si, že tato definice znamená, že pokud f (v) = f{w) pro dva různé vrcholy ve V, pak mezi nimi nesměla být hrana. U orientovaných grafů je taková hrana přípustná, pokud je na společném obrazu smyčka. □ s Speciálním případem je morfismus libovolného grafu G do úplného grafu Km. Takový morfismus je ekvivalentní vybranému obarvení vrcholů grafu V pomocí m různých jmen vrcholů Km tak, že stejně obarvené vrcholy nejsou spojeny hranou. Hovoříme v tomto případě o barvení grafu pomocí m barev. Příklad Určete počet morfismů grafu P2 do K5. □ s Definice V případě, že je morfismus f : G —> G' bijekcí na vrcholech takovou, že i f_1 je morfismem, hovoříme o izomorfismu grafů. Izomorfní grafy se liší pouze různým pojmenováním vrcholů. □ s Definice V případě, že je morfismus f : G —> G' bijekcí na vrcholech takovou, že i f_1 je morfismem, hovoříme o izomorfismu grafů. Izomorfní grafy se liší pouze různým pojmenováním vrcholů. Snadno umíme načrtnout až na izomorfismus všechny grafy na málo vrcholech (třeba třech nebo čtyřech). Obecně jde ale o nesmírně složitý kombinatorický problém a i rozhodnutí o konkrétních dvou daných grafech, zda jsou izomorfní, je obecně mimořádně obtížné. □ s Jednoduchými a mimořádně užitečnými příklady morfismů grafů jsou pojmy cesta, sled a kružnice v grafu: Definice Cestou délky n v grafu G rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů vo,... ,vn z Pn jsou různé). Sled délky n v grafu G je jakýkoliv morfismus s : Pn —> G (tj. v obrazu se mohou opakovat vrcholy i hrany). Tah je speciální případ sledu, v němž se mohou opakovat vrcholy, ale nikoliv hrany. □ s Jednoduchými a mimořádně užitečnými příklady morfismů grafů jsou pojmy cesta, sled a kružnice v grafu: Definice Cestou délky n v grafu G rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů vo,... ,vn z Pn jsou různé). Sled délky n v grafu G je jakýkoliv morfismus s : Pn —> G (tj. v obrazu se mohou opakovat vrcholy i hrany). Tah je speciální případ sledu, v němž se mohou opakovat vrcholy, ale nikoliv hrany. Sled si můžeme představit jako dráhu přičinlivého, ale tápajícího poutníka z uzlu f{vo) do uzlu f(vn). Poutník totiž zdárně dojde, ale klidně se po cestě grafem vrací do uzlů nebo i dokonce po hranách, kterými dříve šel. Táhnoucí poutník je již o něco moudřejší. Cesta je naopak průchod grafem z počátečního uzlu f(vb) do koncového f{vn) bez takových zbytečných oklik. □ s Obrazy cest i sledů jsou příkladem tzv. podgrafů: □ s Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G = (V, E), jestliže V C1/,£'C E. □ S Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G V C1/,£'C E. (V,E), jestliže Speciální příklady: Uvažujme graf G = (V, E) a nějakou podmnožinu V C V. Indukovaný podgraf je graf G' = (V, E'), kde e G E patří i do E' právě, když oba krajní vrcholy hrany e patří do V (£' = £n (^')). Faktor G' = (V, E') je takový graf, který má stejnou množinu vrcholů jako G, ale jeho množina hran E1 je libovolnou podmnožinou. Obecný případ je kombinací těchto dvou. □ s Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G V C1/,£'C E. (V,E), jestliže Speciální příklady: Uvažujme graf G = (V, E) a nějakou podmnožinu V C V. Indukovaný podgraf je graf G' = (V, E'), kde e G E patří i do E' právě, když oba krajní vrcholy hrany e patří do V (£' = £n (^')). Faktor G' = (V, E') je takový graf, který má stejnou množinu vrcholů jako G, ale jeho množina hran E1 je libovolnou podmnožinou. Obecný případ je kombinací těchto dvou. Každý obraz homomorfismu (tj. obraz jak vrcholů, tak hran) tvoří podgraf. ff □ s Neizomorfních grafů nemůže být méně než 2(2) k(n) = —. □ s - = ■€. -o<\(y Neizomorfních grafů nemůže být méně než Pro n —> oo lze přímo odvodit log2 k{rí) = -n2 - 0(n log2 n). □ S - = .= -OQ^O Neizomorfních grafů nemůže být méně než k(„) = -. Pro n —> oo lze přímo odvodit log2 k{rí) = -n2 - 0(n log2 n). Můžeme to nepřesně formulovat tak, že velká většina všech možných grafů bude po dvou neizomorfní. Poznámka Vlastní konstrukce „mnoha" neizomorfních grafů na n vrcholech ale není triviální. Zkuste jich sestrojit alespoň více než n2\ □ s Poznámka (Graph isomorphism problem) Gl problém je poměrně zvláštním příslušníkem třídy NP-problémů - není o něm známo ani, je-li NP-úplný, ani je-li polynomiální složitosti. Naproti tomu, o Subgraph isomorphism problem je známo, zeje NP-úplný. □ s Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Algoritmy a ooooooo Stupně uzlů a skóre grafu Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Definice Pro vrchol v G V v grafu G = (V, E) říkáme, že jeho stupeň je k, jestliže v E existuje k hran, jejichž hraničním vrcholem i/je. Píšeme v takovém případě deg v = k. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. □ s Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Definice Pro vrchol v G V v grafu G = (V, E) říkáme, že jeho stupeň je k, jestliže v E existuje k hran, jejichž hraničním vrcholem v je. Píšeme v takovém případě deg v = k. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vre holu v a výstupní stupeň deg_ v. Skóre grafu G s vrcholy V = (v\, , vn) je posloupnost (deg i/i, deg v2 , deg vn) Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Jaká skóre mohou grafy mít? □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Jaká skóre mohou grafy mít? Protože každá hrana vychází ze dvou vrcholů, musí být v celkovém součtu skóre započtena každá hrana dvakrát. Proto platí ^degi/ = 2|E|. vev Zejména tedy musí být součet všech hodnot skóre sudý. □ s afu a podgrafy Algoritmy a oo»o ooooooo Následující věta je vlastně o návod, jak pro dané skóre buď zjistit, že graf s takovým neexistuje nebo takový graf sestrojit. Věta (Havel, Hakimi - Algoritmus na sestrojení grafu s daným skóre) Pro libovolná přirozená čísla 0 < d\ < ■ ■ ■ < dn existuje graf G na n vrcholech s těmito hodnotami skóre tehdy a jen tehdy, když existuje graf se skóre (c/i, d2,..., dn_dn - 1, dn_dn+1 - 1,..., c/„_i - 1) na n — 1 vrcholech. Příklad Existuje graf, jehož skóre je (2,3,3,3,3,3,4,5)? Pokud ano, sestrojte jej. □ s Důkaz. „<= zrejme. „=>" idea: ukáže se, že při pevně zadaném (vzestupném) skóre (c/i,,..., dn) existuje graf s tímto skóre, jehož vrchol vn je spojen hranou právě s posledními dn vrcholy vn-d„, ■ ■ ■, vn-i- D □ s O Základní pojmy teorie grafů • Dva příklady • Základní definice a Galerie jednoduchých grafů O (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy O Prohledávání v grafech 9 Prohledávání do šířky a do hloubky Grafy jsou jazykem, ve kterém často formulujeme algoritmy. □ s - = ■€. -o<\(y Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, □ s Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme □ s Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. □ s Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. □ s Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. Při zpracování informace se zároveň rozhodujeme, kterými výstupními hranami budeme pokračovat a v jakém pořadí. □ s Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. Při zpracování informace se zároveň rozhodujeme, kterými výstupními hranami budeme pokračovat a v jakém pořadí. Pokud je graf neorientovaný, můžeme všechny hrany považovat za dvojice hran orientované opačnými směry. □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Definice (Hranový seznam/Edge List) Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazateli tak, že každý vrchol ukazuje na všechny z něj vycházející hrany (případně také na všechny do něj vcházející hrany u orientovaných grafů) a každá hrana ukazuje na svůj počáteční a koncový vrchol. □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Definice (Hranový seznam/Edge List) Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazateli tak, že každý vrchol ukazuje na všechny z něj vycházející hrany (případně také na všechny do něj vcházející hrany u orientovaných grafů) a každá hrana ukazuje na svůj počáteční a koncový vrchol. Je vidět, že pamět potřebná na uchování grafu je v tomto případě 0(\V\ + \E\), protože na každou hranu ukazujeme právě dvakrát a na každý vrchol ukazujeme tolikrát, kolik je jeho stupeň a součet stupňů je také roven dvojnásobku počtu hran. Až na konstantní násobek jde tedy stále o optimální způsob uchovávání grafu v paměti. □ s Directed Graph Ja) S*Í Oŕ nptrej NQtiW A&SWKV tots fitXrJi him PiŤYft^f.fHm Cor Lac l n v k FVxJurts-aofiK Čeriaci nun About Hm K ..' ■.■ i- . ' Prf*C* Wř* taft «p HfetMffl /*ou ',■■., Adjacency List Representation (a) 5aŕof/JDďes WorfaťdriwcwKťllíste ■ [ • r ■ Undiroctod Graph (b} Adjacency Lisi Representation (b) □ S Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Ac = (a//) nad Z2 (tj zaplněnou jen nulami a jedničkami) takto: {1 jestliže je hrana e// = {v,, vj} v E 0 jestliže není hrana e-,j = {v-n vj} v E Matici Ac nazýváme matice sousednosti grafu G. □ s - Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Ac = (a//) nad Z2 (tj zaplněnou jen nulami a jedničkami) takto: {1 jestliže je hrana e// = {v,, vj} v E 0 jestliže není hrana e-,j = {v-n vj} v E Matici Ag nazýváme matice sousednosti grafu G. Zadání grafu pomocí matice sousednosti potřebuje vždy 0(n2) místa v paměti. Pokud je ale v grafu málo hran, dostáváme tzv. řídkou matici se skoro všemi prvky nulovými. Takové lze naopak reprezentovat pomocí hranových seznamů odpovídajících grafů a to i včetně obecných číselných hodnot pro jednotlivé hrany. Příklad pro procvičení - násobení matic pomocí reprezentace hranovým seznamem. □ s b D jr f \\ e jCy* f □irBctnrl Grapľi (a) b ô/j\ Jk~^ ' ' ■ Undirected Graph (t>) 2 h C j H i v/ y y v' y ■y y y y v/ Adjacency Matrix Representation (a) n b c d * t a y :> y y y C y y -: y y y y ü y f y Adjacency Malrix Representation (b) □ S Definice (Základní operace nad grafem) • odebrání hrany • přidání hrany 9 přidání vrcholu 9 odebrání vrcholu 9 dělení hrany nově přidaným vrcholem Jak se projeví tyto operace v našich reprezentacích? □ s - Jednoduchou aplikací maticového počtu je tvrzení: Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticisousednosti Aq. Označme AkG = (a)- ) prvky k-té mocniny matice Aq. Pak a)- je počet sledů délky k mezi vrcholy v\ a vj. Důkaz. Jednoduchou aplikací maticového počtu je tvrzení: Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticisousednosti Aq. Označme AkG = (a)- ) prvky k-té mocniny matice Aq. Pak a)- je počet sledů délky k mezi vrcholy v\ a vj. Důkaz. Indukcí. D Důsledek Jsou-li G = (V, E) a Ac jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy, když má matice (A + In)"-1 samé nenulové členy (zde In označuje jednotkovou matici s n řádky a sloupci). □ s O Základní pojmy teorie grafů • Dva příklady • Základní definice a Galerie jednoduchých grafů O (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy Q Prohledávání v grafech • Prohledávání do šířky a do hloubky Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průběhu procesu pak v každém okamžiku jsou vrcholy • již zpracované, tj. ty, kterými jsme již při běhu algoritmu prošli a definitivně je zpracovali; • aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracování; » spící, tj. ty vrcholy, na které teprve dojde. Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průběhu procesu pak v každém okamžiku jsou vrcholy • již zpracované, tj. ty, kterými jsme již při běhu algoritmu prošli a definitivně je zpracovali; • aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracování; • spící, tj. ty vrcholy, na které teprve dojde. Zároveň si udržujeme přehled o již zpracovaných hranách. V každém okamžiku musí být množiny vrcholů a/nebo hran v těchto skupinách disjunktním rozdělením množin vrcholů V a množin E hran grafu G a některý z aktivních vrcholů je aktuálně zpracováván. Algoritmy a ooooooo Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. □ s Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. • V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. • V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. V konkrétních úlohách se můžeme omezovat na některé z hran, které vychází z aktuálního vrcholu. Na principu to ale nic podstatného nemění. Pro realizaci algoritmů je nutné se rozhodnout, v jakém pořadí zpracováváme aktivní vrcholy a v jakém pořadí zpracováváme hrany z nich vycházející. V zásadě přichází v úvahu dvě možnosti zpracovávání vrcholů: O vrcholy vybíráme pro další zpracování ve stejném pořadí, jak se stávaly aktivními (fronta - FIFO) O dalším vrcholem vybraným pro zpracování je poslední zaktivněný vrchol (zásobník - LIFO). V prvním případě hovoříme o prohledávání do šířky, ve druhém o prohledávání do hloubky. Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: □ s Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: Celkový čas realizace vyhledávání do šířky i do hloubky Je 0{{n + m) * K), kde n Je počet vrcholů v grafu, m Je počet hran v grafu a K Je čas potřebný na zpracování Jedné hrany, resp. Jednoho vrcholu. □ s Ilustrace prohledávání do šířky: □ s - = ■€. -o<\(y Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: * <*. Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: * <*. Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: •........• •........• Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: . 1*'^ / \ f"'®, : \ 9"^ : \ W"^ í •........• •........• •........• •........• Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. n S - = -E -00*0 Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® ■*-. '' A •- H f *~®A^''f *~*/V-®''* • • □ S - = .= -OQ^O Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® •........