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 - 8. prednáška Teórie grafu - základní pojmy
Michal Bulant
Masarykova univerzita Fakulta informatiky
7. 11. 2012
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 hloubky
(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.
• Předmětové záložky v IS MU
Základní pojmy teorie grafů
oooooooooo
(Iso)Morfismy grafů a podgrafy
ooooooooooo
Algoritmy a reprezentace grafů
ooooooo
Prohledávání v grafech OOOOOOO
Doporučené zdroje
• 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étni matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s.
• Petr Hliněný, Teorie grafů, studijní materiály, https://is. muni.cz/auth/el/1433/podzim2012/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.
• Předmětové 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, https://is. muni.cz/auth/el/1433/podzim2012/MA010/index.qwarp
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2009.
• Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993
(http://www-cs-facuity.Stanford.edu/-knuth/sgb.html).
• Radek Pelánek, Logické úlohy ve výuce informatiky, http:// www.fi.muni.cz/~xpelanek/ucitele/?action=logicke.
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.
• Předmětové 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, https://is. muni.cz/auth/el/1433/podzim2012/MA010/index.qwarp
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2009.
• Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993
(http://www-cs-facuity.Stanford.edu/-knuth/sgb.html).
• Radek Pelánek, Logické úlohy ve výuce informatiky, http:// www.fi.muni.cz/~xpelanek/ucitele/?action=logicke.
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 » 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 hloubky
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        Prohledávání v grafech
•ooooooooo ooooooooooo ooooooo ooooooo
Prí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é bud' navzájem znát budou nebo navzájem znát nebudou?
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é bud' navzájem znát budou nebo navzájem znát nebudou?
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 bud' 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é bud' navzájem znát budou nebo navzájem znát nebudou?
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 bud' 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é bud' navzájem znát budou nebo navzájem znát nebudou?
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 bud' 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 postůj bude alespořb ^,«,0
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	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í bud' 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 I
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 príkladu.
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 antireflexními 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.
4Ľ3k4l3*4 = k4 = *      -š -O^O
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í vrcholu, 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í vrcholu, 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 (-4=>- ) 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 = (^)) říkáme úplný graf. Značíme symbolem Kn, kde n je počet vrcholu 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 = (^)) říkáme úplný graf. Značíme symbolem Kn, kde n je počet vrcholu 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í vrcholu (vq, ..., vn) takové, že E = {ei,..., e„}, kde e,- = v,}, 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
A Cľ rU
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	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
V W
Pro Vi = {ui,..., um}, V2 = {1/1, ...,i/n} je Km,n = (V, E), kde V = Vi U V2 a E = Vi x V2.
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	Prohledávání	v grafech
00000000*0	ooooooooooo	ooooooo	OOOOOOO	
Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla O,..., 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 níže je H4 a popis vrcholu 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
ooooooooso ooooooooooo ooooooo ooooooo
Hyperkostka Hn v dimenzi n vznikne tak, že vrcholy jsou všechna čísla O,..., 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 níže je H4 a popis vrcholu 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 H3 čárkovanými hranami. Samozřejmě ale můžeme tímto způsobem rozložit H4 mnoha různými způsoby.
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	Prohledávání	v grafech
000000000»	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 prednáš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 a 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 hl<
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 —» G' považovat zobrazení fy : V —> V mezi množinami vrcholu 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í    : 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 —» G' považovat zobrazení fy : V —> V mezi množinami vrcholu 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í    : 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í vrcholu 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.
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        Prohledávání v grafech
oooooooooo oo»oooooooo 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 oo»oooooooo ooooooo ooooooo
Definice
V prípade, ž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é.
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ů vq, ... ,vn z Pn jsou různé). Kružnicí v grafu G rozumíme izomorfní obraz nějaké kružnice C/y.
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ů vq, ... ,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 ^(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 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 c v, e 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 C V, E' 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 (£' = £(1 (^')). Faktor G' = (V, E1) 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 je takový podgraf grafu G, který je izomorfní nějakému úplnému grafu.
Věta
Každý obraz homomorfismu (tj. obraz jak vrcholů, tak hran) tvoří podgraf.
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	Prohledávání	v grafech
oooooooooo	ooooo»ooooo	ooooooo	OOOOOOO	
Neizomorfních grafů nemůže být méně než
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        Prohledávání v grafech
oooooooooo ooooo»ooooo ooooooo ooooooo
Neizomorfních grafů nemůže být méně než
2(;)
«„) = —.
Pro n —> 00 lze přímo odvodit
1 2
log2 k(n) = -n - 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	
Neizomorfních grafů nemůže být méně než
2©
k(n)
Pro n —» 00 lze přímo odvodit
n\
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 vrcholu. 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 vrcholu. 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 je v. Píšeme v takovém případě deg v = k. Graf se nazývá /c-regulární, pokud mají jeho všechny vrcholy týž stupeň k, speciálně 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.
i 00.O
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 vrcholu. 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 je v. Píšeme v takovém případě deg v = k. Graf se nazývá /c-regulární, pokud mají jeho všechny vrcholy týž stupeň k, speciálně 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 = (vi,..., vn) je posloupnost
(deg 1/1, deg 1/2,..., deg i/„) -i
00.O
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.
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 C§. Zjevně ale izomorfní nejsou, protože v C§ 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 C§. Zjevně ale izomorfní nejsou, protože v C§ existuje cesta délky 5, která v druhém grafu být nemůže.
Jaká skóre mohou grafy mít?
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 C§. Zjevně ale izomorfní nejsou, protože v C§ 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í
■1 Handshake lemma		
	^degi/ = 2|E|. vev	
Zejména tedy musí být součet všech hodnot skóre sudý.
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	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 bud' zjistit, že graf s takovým skóre neexistuje nebo jak 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, d2,..., dn_dn - 1, dn_dn+1 - 1,..., c/„_i - 1)
na n — 1 vrcholech.
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	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 bud' zjistit, že graf s takovým skóre neexistuje nebo jak 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, 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.
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 (di,,..., dn) existuje graf s tímto skóre, jehož vrchol vn je spojen hranou právě s posledními dn vrcholy vn-d„, ■ ■ ■, vn-\. □
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
• 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 hloubky
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	Prohledávání	v 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	o«ooooo	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 o«ooooo 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
►   1 -o^o
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        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 vrcholu V = (1/1,..., vn) a definujme matici Ag = (ay) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto:
1   jestliže je hrana e y = {v,, vj} v E 0  jestliže není hrana e y = {v,, vj} v E
Matici Ag 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 vrcholu V = (1/1,..., vn) a definujme matici Aq = (ay) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto:
Matici Ag 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 = {1//, vj} v E 0  jestliže není hrana e-,j = {1//, 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	
• přidání hrany	
« přidání vrcholu	
» odebrání vrcholu	
« 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 = (vi,... ,vn) a maticisousednosti Ag- Označme AkG = (aj^) prvky k-té mocniny
(k)
matice Aq. Pak a-  je počet sledů délky k mezi vrcholy v, a vj.
Důkaz.
Indukcí._□ J
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        Prohledávání v grafech
oooooooooo ooooooooooo oooooo* ooooooo
Jednoduchou aplikací maticového počtu je tvrzení:
Věta
Necht G = (V, E) je graf s uspořádanými vrcholy V = (vi,... ,vn) a maticisousednosti Ag- Označme AkG = (a]p) prvky k-té mocniny
(k)
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 Ag jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy, když má matice (Ag +        1 samé nenulové členy (zde I„ označuje jednotkovou matici s n řádky a sloupci).
Základní pojmy teorie grafů        (l^o)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
• Morfismy
• Podgrafy
o Stupně uzlů a skóre grafu O Algoritmy a reprezentace grafů
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 grafec
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	OOOOOOO	
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	OOOOOOO	
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í.
4Ľ3k4l3*4 = k4 = *      -š -O^O
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 000*000
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 000*000
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.
:Ä>jjjs op jueAepa|qojd aoej^snn
	OOÄOOOO	ooooooo	ooooooooooo	oooooooooo
	iueAep3moj,-|	njej§ 3Deq.u3Z3jd3J e ÄLuq.uo§|\/	Äjej§pod e njEJ§ älusijjo|/\|(os|)	njEJ§ su031 ÄLuľod iupe|>|ez
Základní pojmy teorie grafů        (Iso)Morfismy grafů a podgrafy        Algoritmy a reprezentace grafů        Prohledávání v grafech
oooooooooo ooooooooooo ooooooo oooo»oo
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
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
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 šíř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ů".
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 šíř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ů".
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 šíř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ů".
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 ooooo«o
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	ooooo«o	
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 ooooo«o
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 ooooo«o
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 ooooo«o
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	ooooo«o	
Základní pojmy teorie grafů	(Iso)Morfismy grafů a podgrafy	Algoritmy a reprezentace grafů	Prohledávání	v grafech
oooooooooo	ooooooooooo	ooooooo	ooooo«o	
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 ooooo«o
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 - 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).