Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Matematika III - 7. prednáška Teórie grafu - základní pojmy Michal Bulant Masarykova univerzita Fakulta informatiky 3. 11. 2010 Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah přednášky Q Základní pojmy teorie grafů • Dva příklady • Základní definice • Galerie základních typů grafů Q (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy Q Prohledávání v grafech » Prohledávání do šířky a do hlou Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo 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: //is.muni.cz/el/1433/podzim2010/MA010/index.qwarp Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo 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: //is.muni.cz/el/1433/podzim2010/MA010/index.qwarp • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/~knuth/sgb.html). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo 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šetřil, Kapitoly z diskrétni matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http: //is.muni.cz/el/1433/podzim2010/MA010/index.qwarp • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/~knuth/sgb.html). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) • určování lokálních a globálních extrémů včetně slovních úloh na ně vedoucích Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) • určování lokálních a globálních extrémů včetně slovních úloh na ně vedoucích • integrály funkcí dvou proměnných, transformace (zejména do polárních souřadnic), aplikace integrálního počtu (hmotnost, těžiště), numerické integrování Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Obsah druhé písemky 12.11. v 17.00 • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) • určování lokálních a globálních extrémů včetně slovních úloh na ně vedoucích • integrály funkcí dvou proměnných, transformace (zejména do polárních souřadnic), aplikace integrálního počtu (hmotnost, těžiště), numerické integrování • interpolace, aproximace metodou nejmenších čtverců Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Plán přednášky Q Základní pojmy teorie grafů • Dva příklady • Základní definice • Galerie základních typů grafů Q (Iso)Morfismy grafů a podgrafy • Podgrafy • Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy 9 Prohledávání do šířky a do hloubky Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech •ooooooooo ooooooooooo ooooooo ooooooo 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? Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech •ooooooooo ooooooooooo ooooooo ooooooo 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é? Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech •ooooooooo ooooooooooo ooooooo ooooooo 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é? Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech •ooooooooo ooooooooooo ooooooo ooooooo 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. □ s - ■ Základní pojmy teorie grafů (Iso)Morfismy gra' ů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech o«oooooooo ooooooooooo ooooooo OOOOOOO 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: 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oo«ooooooo ooooooooooo ooooooo ooooooo Různé úvodní úlohy • Bludiště - transformací do řeči grafů převedeme na relativně snadnou úlohu • Převozník, vlk, koza a zelí • a další (i reálnější) aplikace ... Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech ooo«oooooo ooooooooooo ooooooo ooooooo 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 (^) 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í (někdy o takových hranách a vrcholech říkáme, že jsou vzájemně incidentní). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech ooo«oooooo ooooooooooo ooooooo ooooooo 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 (^) 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í (někdy o takových hranách a vrcholech říkáme, že jsou vzájemně incidentní). 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. Multigraf pak může mít mezi dvěma vrcholy více hran (příp. i orientovaných). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooo»ooooo ooooooooooo ooooooo ooooooo Definice (... pokračovaní) 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooo»ooooo ooooooooooo ooooooo ooooooo Definice (... pokračovaní) 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech ooooo«oooo ooooooooooo ooooooo ooooooo Grafy - příklad kompromisu mezi přirozeným sklonem k „přemýšlení v obrázcích" a přesným matematickým vyjadřováním. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech ooooo«oooo ooooooooooo ooooooo ooooooo Grafy - příklad kompromisu mezi přirozeným sklonem k „přemýšlení 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 či vrcholů apod.) Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech ooooo«oooo ooooooooooo ooooooo ooooooo Grafy - příklad kompromisu mezi přirozeným sklonem k „přemýšlení 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 či vrcholů 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, s n 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooo»ooo ooooooooooo ooooooo ooooooo 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooo»ooo ooooooooooo ooooooo ooooooo 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ů (vo,... ,vn) takové, že E = {e\,..., en}, kde e; = {V;-i, 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 Základní pojmy teorie grafů (Iso)Morfismy gra' ů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech ooooooo«oo ooooooooooo ooooooo OOOOOOO Ú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 Kl,3, ^2,3 a ^3,3- v w m Pro Vi = {ui,um}, V2 = {1/1,..., vn} je Km>n = (V, E), kde V = V1 (J V2 a E = V1 x V2. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOO0O ooooooooooo ooooooo ooooooo 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 1111 0000 0001 Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOO0O ooooooooooo ooooooo ooooooo 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 1111 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. Základní pojmy teorie grafů (Iso)Morfismy gra fů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech 0OOOOOOOO« ooooooooooo ooooooo OOOOOOO 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Plán přednášky • Dva příklady a Základní definice • Galerie základních typů grafů £ (Iso)Morfismy grafů a podgrafy • Morfismy • Podgrafy • Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy » Prohledávání do šířky a do hloubky Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO »0000000000 ooooooo ooooooo Definice Pro grafy G = (V, E) a G' = (V, E') budeme za (homo)morfismus f : G —> G1 považovat zobrazení fy : V —> V1 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO »0000000000 ooooooo ooooooo Definice Pro grafy G = (V, E) a G' = (V, E') budeme za (homo)morfismus f : G —> G1 považovat zobrazení fy : V —> V1 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo o«ooooooooo ooooooo ooooooo 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 Ks. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OO0OOOOOOOO ooooooo ooooooo 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ů. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OO0OOOOOOOO ooooooo ooooooo Definice V prípade, že je morfismus f : G —> G1 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é. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooo«ooooooo ooooooo ooooooo Jednoduchými a mimořádně užitečnými příklady morfismů grafů jsou pojmy cesta, sled a kružnice v grafu: Definice 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. Cestou délky n v grafu G pak rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů vo,..., vn z Pn jsou různé). Kružnicí v grafu G rozumíme izomorfní obraz nějaké kružnice Ca/. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooo«ooooooo ooooooo ooooooo Jednoduchými a mimořádně užitečnými příklady morfismů grafů jsou pojmy cesta, sled a kružnice v grafu: Definice 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. Cestou délky n v grafu G pak rozumíme morfismus p : Pn —> G takový, že p je injektivní zobrazení (tj. všechny obrazy vrcholů vo,..., vn z Pn jsou různé). Kružnicí v grafu G rozumíme izomorfní obraz nějaké kružnice Ca/. 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(vo) do koncového f{vn) bez takových zbytečných oklik. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v j grafech oooooooooo oooo»oooooo OOOOOOO ooooooo Obrazy cest i sledů jsou příkladem tzv. podgrafů: Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo oooo»oooooo ooooooo ooooooo Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G = (V, E), jestliže V Cl/, £'C E. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo oooo»oooooo ooooooo ooooooo Obrazy cest i sledů jsou příkladem tzv. podgrafů: Definice Graf G' = (V, E') je podgrafem v grafu G = (V, E), jestliže V Cl/, £'C 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 (£' = E n (^')). Faktor G' = (V, E') je takový graf, který má stejnou množinu vrcholů jako G, ale jeho množina hran E' je libovolnou podmnožinou. Obecný případ je kombinací těchto dvou. Klika(clique) je takový podgraf grafu G, který je izomorfní nějakému úplnému grafu. Základní pojmy teorie grafů oooooooooo (Iso)Morfismy grafů a podgrafy ooooo«ooooo Algoritmy a reprezentace grafů OOOOOOO Prohledávání v grafech OOOOOOO Věta Každý obraz homomorfismu (tj. obraz jak vrcholu, tak hran) tvoří podgraf. Neizomorfních grafů nemůže být méně než 2(2) k(n) = —. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooo«ooooo ooooooo ooooooo Každý obraz homomorfismu (tj. obraz jak vrcholu, tak hran) tvoří podgraf. Neizomorfních grafů nemůže být méně než Pro n —> oo lze přímo odvodit log2 k(n) = -n2 - 0(n log2 n). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooo«ooooo ooooooo ooooooo Každý obraz homomorfismu (tj. obraz jak vrcholu, tak hran) tvoří podgraf. Neizomorfních grafů nemůže být méně než Pro n —> oo lze přímo odvodit log2 k(n) = ^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\ Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo oooooo«oooo ooooooo ooooooo Poznámka (Graph isomorphism problem) Gl problém je pomerne 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, že je NP-úplný. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooo«ooo ooooooo 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ů. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooo«ooo ooooooo 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 e 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. Graf se nazývá /(-regulární, pokud mají jeho všechny vrcholy týž stupeň k, spec. pak pro k = 3 mluvíme o kubickém grafu. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooo«ooo ooooooo 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 e 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. Graf se nazývá /(-regulární, pokud mají jeho všechny vrcholy týž stupeň k, spec. pak pro k = 3 mluvíme o kubickém grafu. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. Skóre grafu G s vrcholy V = (v\,..., vn) je posloupnost (deg vi, deg v2,..., deg vn) O O. o- Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v j grafech oooooooooo oooooooo«oo OOOOOOO ooooooo 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo oooooooo«oo ooooooo ooooooo 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 Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo oooooooo«oo ooooooo ooooooo 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 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? 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 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í vev Zejména tedy musí být součet všech hodnot skóre sudý. Základní pojmy teorie grafů (Iso)Morfismy gra' ů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech oooooooooo ooooooooo»o OOOOOOO 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 (di, di,..., dn_dn - 1, dn_dn+1 - 1,..., dn-i - 1) na n — 1 vrcholech. Základní pojmy teorie grafů (Iso)Morfismy gra' ů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech oooooooooo ooooooooo»o ooooooo 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 (d\, d2,..-, dn-dn - 1, dn-dn+i dn-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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO 0000000000« OOOOOOO OOOOOOO Důkaz. " ^=" zřejmé. "=>" idea: ukáže se, že při pevně zadaném (vzestupném) skóre (d\,,..., dn) existuje graf s tímto skóre, jehož vrchol vn je spojen hranou právě s posledními dn vrcholy vn_cjn,..., vn-i. □ Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Plán přednášky Q Základní pojmy teorie grafů • Dva příklady • Základní definice 9 Galerie základních typů grafů Q (Iso)Morfismy grafů a podgrafy • Podgrafy • Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů • Grafové algoritmy 9 Prohledávání do šířky a do hloubky Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v j grafech oooooooooo ooooooooooo •oooooo OOOOOOO Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 ooooooo 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í, Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 ooooooo 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 Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 ooooooo 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 OOOOOOO 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 ooooooo 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í. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO «000000 ooooooo 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. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v ) grafech oooooooooo ooooooooooo O0OOOOO OOOOOOO Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO O0OOOOO ooooooo 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo oo«oooo ooooooo □ s - ■ ► -5 -O^O Základní pojmy teorie grafů (Iso)Morfismy gra' ů a podgrafy Algoritmy a reprezentace gral ů Prohledávání v grafech oooooooooo ooooooooooo ooo»ooo OOOOOOO Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Aq = (a//) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: 1 jestliže je hrana e-,j = {V;, vj} v E 0 jestliže není hrana e// = {V;, vj} v E Matici Ac nazýváme matice sousednosti grafu G (obdobně v případě orientovaných grafů či multigrafů). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooo»ooo ooooooo Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Aq = (a//) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: Matici Ac nazýváme matice sousednosti grafu G (obdobně v případě orientovaných grafů či multigrafů). 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. 1 jestliže je hrana e-,j = {v,, vj} v E 0 jestliže není hrana e// = {V;, vj} v E Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo oooo«oo ooooooo Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooo«o ooooooo Základní operace nad grafem "* • odebrání hrany 9 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? Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO 000000« ooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta 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í. □ Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO 000000« ooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta 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ůsledek Jsou-li G = (V, E) a Aq jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy když má matice (A + In)n_1 samé nenulové členy (zde in označuje jednotkovou matici s n řádky a sloupci). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo ooooooo Plán přednášky Q Základní pojmy teorie grafů • Dva příklady • Základní definice 9 Galerie základních typů grafů Q (Iso)Morfismy grafů a podgrafy • Podgrafy • Stupně uzlů a skóre grafu Ai r° Algoritmy a reprezentace gratu • Grafové algoritmy Q Prohledávání v grafech • Prohledávání do šířky a do hloubky Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO «000000 Prohledávání v grafech 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ákladní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO «000000 Prohledávání v grafech 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo o»ooooo Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo o»ooooo 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í pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo o»ooooo 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í pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo o»ooooo 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í. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oo«oooo 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. Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO OOO0OOO 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í: Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO OOO0OOO 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í: Věta 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. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech oooooooooo ooooooooooo ooooooo oooo«oo Ilustrace prohledávání do šírky: •........• •........• •........• •........• 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ů". Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Základní pojmy teorie grafů (Iso)Morfismy graf ů a podgrafy Algoritmy a reprezentace graf ů Prohledávání v { grafech oooooooooo ooooooooooo ooooooo OOOOO0O Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Prohledávání "do hloubky"odpovídá interpretaci rekurze v běžných imperativních jazycích (např. i v Maplu) - v těchto případech je ale stavový graf potenciálně nekonečný a prohledávání do hloubky tak samozřejmě nemusí nalézt všechny vrcholy dostupné z daného vrcholu po cestách konečné délky (narozdíl od prohledávání do šířky). Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále • jsou-li již všechny chodby vedoucí z místnosti použity, vracíme se zpět chodbou, která je označena jen jednou čarou Základní pojmy teorie grafů (Iso)Morfismy grafů a podgrafy Algoritmy a reprezentace grafů Prohledávání v grafech OOOOOOOOOO OOOOOOOOOOO OOOOOOO 000000« Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále • jsou-li již všechny chodby vedoucí z místnosti použity, vracíme se zpět chodbou, která je označena jen jednou čarou • pokud z dané místnosti vedou pouze chodby, které jsou označeny 2 čarami, hledání ukončíme (nutně jde o výchozí místnost, východ neexistuje a můžeme s klidem umřít).