MA2BP_PDM1 Diskrétní matematika 1
9. Prohledávání grafu
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
6. 12. 2017
6. 12. 2017 1/24
Program prezentace
□ Vlastnosti stromů Q Kořenový strom
B Prohledávání grafů
■ Prohledávání do sirky
■ Prohledávání do hloubky
□ Použité zdroje
6. 12. 2017       2 / 24
Základní pojmy
Definice 4.1, 4.2, 4.3 (MILKOVA):
□ Les je graf, který neobsahuje kružnici.
Q Strom je souvislý graf, který neobsahuje kružnici.
B Buď T = {V, E) strom. Vrchol u G V stupně 1 nazývame listem, vrchol v E V stupně většího než 1 nazývam vnitřním vrcholem stromu T.
j
Poznámka:
■ Strom obsahující pouze jeden vrchol nazývame triviálním stromem.
■ Každá komponenta lesa je strom.
6. 12. 2017       3 / 24
Ukázka stromu
6. 12. 2017       4 / 24
Charakteristika listů
Mějme strom T = {V, E). Pak platí následující tři tvrzení.
■ Tvrzení 4.1 (MILKOVA): Je-li T netriviální strom, pak obsahuje list.
■ Věta 4.4 (FUCHS): Je-li T netriviální strom, pak obsahuje alespoň dva listy.
■ Tvrzení 4.2 (MILKOVA): Je-li T netriviální strom a odebereme z T list, pak dostaneme opět strom.
■ Tvrzení 4.3 (MILKOVA): Pro libovolný vrchol w £ V platí, že spojíme-li jej hranou s vrcholem v E V, dostaneme opět strom. (Nově přidaný vrchol w je listem.)
Příklad:
□ Strom s právě dvěma listy se nazývá had.
B Strom o n vrcholech s právě n — 1 listy se nazývá hvězda.
6. 12. 2017       5 / 24
Charakteristika stromů
Věta 4.1 (MILKOVA): Pro každý graf G = {V,E) jsou následující podmínky ekvivalentní:
H Graf G je strom.
B Pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y.
B Graf G je souvislý a každá jeho hrana je most.
□ Graf G je souvislý a platí vztah \ V\ — \E\ + 1.
B Graf G neobsahuje kružnici a každý graf vzniklý z grafu G přidáním hrany, která spojuje libovolné dva vrcholy grafu G, které nejsou sousední, již kružnici obsahuje.
6. 12. 2017       6 / 24
Charakteristika stromů
Věta 4.1 (MILKOVA): Pro každý graf G = (V,E) jsou následující podmínky ekvivalentní:
Q Graf G je strom.
Pro každé dva vrcholy x,y G V existuje právě jedna cesta z vrcholu x do vrcholu y.
Graf G je souvislý a každá jeho hrana je most.
□ Graf G je souvislý a platí vztah \ V\ = \E\ + 1.
B Graf G neobsahuje kružnici a každý graf vzniklý z grafu G přidáním hrany, která spojuje libovolné dva vrcholy grafu G, které nejsou sousední, již kružnici obsahuje.
Důkaz je poměrně zdlouhavý a opírá se o prokázání ekvivalencí tvrzení 1     2,1     3,1     4,1     5. My si uvedeme pouze důkaz 1 o 2.
6. 12. 2017       6 / 24
Věta 4.1, důkaz 1 => 2
Předpokládáme, že G = (\/, E) je strom. Chceme ukázat, že pro každé dva vrcholy x,y E V existuje právě jedna cesta z vrcholu x do vrcholu y.
6. 12. 2017       7 / 24
Věta 4.1, důkaz 1 => 2
Předpokládáme, že G = (\/, E) je strom. Chceme ukázat, že pro každé dva vrcholy x,y E V existuje právě jedna cesta z vrcholu x do vrcholu y.
Důkaz: G je strom, tedy souvislý graf bez kružnic. Z definice souvislosti existuje mezi x a y alespoň jedna cesta.
6. 12. 2017       7 / 24
Věta 4.1, důkaz 1 => 2
Předpokládáme, že G = (\/, E) je strom. Chceme ukázat, že pro každé dva vrcholy x,y E V existuje právě jedna cesta z vrcholu x do vrcholu y.
Důkaz: G je strom, tedy souvislý graf bez kružnic. Z definice souvislosti existuje mezi x a y alespoň jedna cesta.
Předpokládejme sporem, že mezi vrcholy x,y £ V □ neexistuje žádná cesta, nebo B existuje více cest než právě jedna.
6. 12. 2017       7 / 24
Věta 4.1, důkaz 1 => 2
Předpokládáme, že G = (\/, E) je strom. Chceme ukázat, že pro každé dva vrcholy x,y E V existuje právě jedna cesta z vrcholu x do vrcholu y.
Důkaz: G je strom, tedy souvislý graf bez kružnic. Z definice souvislosti existuje mezi x a y alespoň jedna cesta.
Předpokládejme sporem, že mezi vrcholy x,y £ V
H neexistuje žádná cesta, nebo
B existuje více cest než právě jedna. Ad 1: když mezi x,y neexistuje cesta, není graf G souvislý. Spor.
6. 12. 2017       7 / 24
Věta 4.1, důkaz 1 => 2
Předpokládáme, že G = (\/, E) je strom. Chceme ukázat, že pro každé dva vrcholy x,y E V existuje právě jedna cesta z vrcholu x do vrcholu y.
Důkaz: G je strom, tedy souvislý graf bez kružnic. Z definice souvislosti existuje mezi x a y alespoň jedna cesta.
Předpokládejme sporem, že mezi vrcholy x,y £ V
□ neexistuje žádná cesta, nebo
B existuje více cest než právě jedna. Ad 1: když mezi x,y neexistuje cesta, není graf G souvislý. Spor.
Ad 2: uvažujme dvě různé cesty Ci, C2 mezi x,y. Obě začínají v x,
v nějakém vrcholu v se "rozcházejí". Poté pokračují odděleně a v nějakém
vrcholu w se opět "sejdou" . Vytvoří tedy kružnici (v,..., w,..., v). Spor.
-<^^ < ± >     1    -O Q, O
6. 12. 2017       7 / 24
Věta 4.1, důkaz 2 => 1
Předpokládáme, že pro každé dva vrcholy x,y6 1/ existuje právě jed cesta z vrcholu x do vrcholu y. Chceme ukázat, že G je strom.
6. 12. 2017       8 / 24
Věta 4.1, důkaz 2 => 1
Předpokládáme, že pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y. Chceme ukázat, že G je strom.
Důkaz: Z předpokladu ihned vyplývá, že graf G je souvislý. Sporem uvažujme, že obsahuje kružnici.
6. 12. 2017       8 / 24
Věta 4.1, důkaz 2 => 1
Předpokládáme, že pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y. Chceme ukázat, že G je strom.
Důkaz: Z předpokladu ihned vyplývá, že graf G je souvislý. Sporem uvažujme, že obsahuje kružnici. Označme
C = (v0, ei> ľi> • • • > ľ/c-i, e/o vo)
kružnici v G. Všimněte si, že mezi vrcholy vq, v\ existují dvě cesty:
6. 12. 2017       8 / 24
Věta 4.1, důkaz 2 => 1
Předpokládáme, že pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y. Chceme ukázat, že G je strom.
Důkaz: Z předpokladu ihned vyplývá, že graf G je souvislý. Sporem uvažujme, že obsahuje kružnici. Označme
C = (v0, ei> vi> • • • > v/c-i, e/o vo)
kružnici v G. Všimněte si, že mezi vrcholy vq, v\ existují dvě cesty: H (vo, ei, vi) a
6. 12. 2017       8 / 24
Věta 4.1, důkaz 2 => 1
Předpokládáme, že pro každé dva vrcholy x,y6 1/ existuje právě jedna cesta z vrcholu x do vrcholu y. Chceme ukázat, že G je strom.
Důkaz: Z předpokladu ihned vyplývá, že graf G je souvislý. Sporem uvažujme, že obsahuje kružnici. Označme
C = (v0, ei> ľi> • • • > ľ/c-i, e/o vo)
kružnici v G. Všimněte si, že mezi vrcholy vq, v\ existují dvě cesty:
H (vo, ei, vi) a
B (vi, • • •, Vk-i, e/c, vq).
Spor s předpokladem, že mezi každými dvěma vrcholy x,y e V existuje právě jedna cesta.
6. 12. 2017       8 / 24
Charakteristika lesa
Tvrzení 4.4 (MILKOVA): Pro každý graf G = (V,E) platí:
Jestliže G je les, který obsahuje k komponent (/c > 1), pak \ V\ = \E\ + k.
Příklad 1: Je dáno skóre lesa (0, 1, 1, 1, 1, 1, 2, 2, 3). Určete počet jeho komponent a hran. Následně zkuste les nakreslit.
6. 12. 2017       9 / 24
Charakteristika lesa
Tvrzení 4.4 (MILKOVA): Pro každý graf G = (V,E) platí: Jestliže G je les, který obsahuje k komponent (/c > 1), pak \ V\ = \E\ + k
Příklad 1: Je dáno skóre lesa (0, 1, 1, 1, 1, 1, 2, 2, 3). Určete počet jeho komponent a hran. Následně zkuste les nakreslit.
Řešení: Sečteme všech devět hodnot ve skóre a získáme číslo 12. Platí: V\ = 9, \E\ = 6, z čehož můžeme usoudit, že graf má 3 komponenty. Počáteční číslo 0 znamená, že jedna komponenta je izolovaný vrchol. Zbylé komponenty intuitivně nakreslíme takto:
O
6. 12. 2017       9 / 24
Kořenový strom
Definice 4.4 (MILKOVA):
Dvojici (7", r), kde T = (\/, E) je strom a r £ V je pevně zvolený vrchol, nazýváme kořenový strom a vrchol r kořen stromu (7~, r).
Další pojmy (viz Definice 4.5, MILKOVA):
H Jestliže vrchol x leží na cestě z kořene r do vrcholu y, říkáme, že x je předchůdce y, y je následník x.
B Jsou-li navíc x,y sousední vrcholy, pak x je přímý předchůdce (rodič, otec) y, y je přímý následník (syn) x.
6. 12. 2017       10 / 24
Příklad 2.4
Na obrázku je kořenový strom (T,g), zvýrazněný vrchol c a jeho □ předchůdci - uzly g a d (přímý předchůdce) B následníci - uzly /7, / (oba přímí následníci) a k
6. 12. 2017       11 / 24
Hloubka kořenového stromu
Definice 4.6 (MILKOVA):
Nechť (7", r) je kořenový strom, v jeho libovolný vrchol a k délka cesty z kořene r do vrcholu v. Pak říkáme, že
□ vrchol v leží v /c-té vrstvě stromu (7", r) nebo též ve vrstvě k.
Q Hloubka stromu (7", r) je rovna největšímu číslu z čísel vrstev, ve kterých leží listy stromu (7", r).
Poznámka: Kořen r leží ve vrstvě 0, jeho přímí následníci (synové) v 1. vrstvě.
Definice 4.7 (MILKOVA):
Nechť (7", r) je kořenový strom a (7";, v) je podgraf (7, r) indukovaný vrcholem v a všemi jeho následníky. Podgraf (7";, \/) nazýváme podstromem stromu (7", r) s kořenem \/.
-<^^ ě    -OQ,O
6. 12. 2017       12 / 24
Příklad 2.4
Na obrázku je kořenový strom (T,g). Barevně jsou vyznačeny vrstvy.
Hloubka stromu je 4.
6. 12. 2017       13 / 24
Příklad 2.4
Na obrázku je podstrom (T',c) kořenového stromu (T,g)
6. 12. 2017       14 / 24
Prohledávání grafů
■ Motivace: potřebujeme systematicky prozkoumat všechny vrcholy zadaného grafu.
■ Existují dva algoritmy, u nichž je třeba stanovit počátek prohledávání (vrchol, odkud začneme):
H Prohledávání do hloubky - založeno na principu LIFO (Last In, First Out) - vrcholy prohledáváme po podstromech dolů
Q Prohledávání do šířky - založeno na principu FIFO (First In, First Out) - vrcholy prohledáváme po vrstvách
< □ ►  < g ►  < ± >  <     ►     E     -O Q, O
6. 12. 2017       15 / 24
Příklad 7.1 - prohledávání do sirky
Je dán následující graf, který chceme prohledat do do šírky, přičemž začínáme ve vrcholu c.
6. 12. 2017       16 / 24
Příklad 7.1 - prohledávání do sirky (řešení)
Nejprve si graf překreslíme do uspořádání odpovídající kořenovému stromu, tj. počátek prohledávání bude nahoře (ve vrstvě 0), ostatní vrcholy pak rozmístěny po vrstvách podle toho, jaká je jejich vzdálenost od vrcholu c.
6. 12. 2017       17 / 24
Příklad 7.1 - prohledávání do sirky (řešení)
Začínáme vrcholem c, který vložíme do fronty. Prozkoumáme přímé následníky vrcholu c.
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do sirky (řešení)
Dle lexikografického pravidla vybereme nejdříve a a vložíme jej na konec fronty, přičemž označíme modře hranu {c, a}.
Fronta:
a c
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do sirky (řešení)
Dle lexikografického pravidla vybereme dále d a vložíme jej na konec fronty, přičemž označíme modře hranu {c, d}.
Fronta:
d a c
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do sirky (řešení)
Dle lexikografického pravidla vybereme nakonec f a vložíme jej na konec fronty, přičemž označíme modře hranu {c, f}.
Fronta:
f d a c
< □ ►   < [fP ►   < -E ►   < -E ►      E     -O Q, O
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Vrchol c nemá další přímé následníky. Označíme jej jako vyřešený a odebereme ze začátku fronty.
Fronta:
fda
Pořadí:
□   g ► < -e ► < =
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol a, vybereme jej ke zpracování.
Fronta:
fda
Pořadí: c
□ [3
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla vybereme nejdříve e a vložíme jej na konec fronty, přičemž označíme modře hranu {a, e}.
Fronta:
e f d a
Pořadí: c
□ ►   < rD? ►   < -E ►   < E ►      E     -O Q, O
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla poté vybereme ŕ - je však již obarvený (navštívený), proto pouze označíme červeně hranu {a, f}.
Fronta:
e f d a
Pořadí: c
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Vrchol a nemá další přímé následníky. Označíme jej jako vyřešený a odebereme ze začátku fronty.
Fronta:
e f d
Pořadí: c
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol d, vybereme jej ke zpracování.
Fronta:
efd
Pořadí: c, a
□ S
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla vybereme nejdříve b a vložíme jej na konec fronty, přičemž označíme modře hranu {c/, b}.
Fronta:
befd
Pořadí: c, a
□ S1
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla poté vybereme e - je však již obarvený (navštívený), proto pouze označíme červeně hranu {c/, e}.
Fronta:
befd
Pořadí: c, a
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Vrchol d nemá další přímé následníky. Označíme jej jako vyřešený a odebereme ze začátku fronty.
Fronta:
bef
Pořadí: c, a
□   g ► < -e ► < =
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol f, vybereme jej ke zpracování.
Fronta:
bef
Pořadí: c, a, d
□ s
Příklad 7.1 - prohledávání do šířky (řešení)
Z vrcholu ŕ již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze začátku fronty.
□    g ► < -e ► < =
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol e, vybereme jej ke zpracování.
□ S
Příklad 7.1 - prohledávání do šírky (řešení)
Dle lexikografického pravidla vybereme nejdříve b - je však již obarvený (navštívený), proto pouze označíme červeně hranu {e, b}.
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla vybereme dále g a vložíme jej na konec fronty, přičemž označíme modře hranu {e,g}.
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Vrchol e nemá další přímé následníky. Označíme jej jako vyřešený odebereme ze začátku fronty.
□ i3>
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol b, vybereme jej ke zpracování.
□ S
Příklad 7.1 - prohledávání do šířky (řešení)
Dle lexikografického pravidla vybereme nejdříve g - je však již obarvený (navštívený), proto pouze označíme červeně hranu {b,g}.
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Vrchol b nemá další přímé následníky. Označíme jej jako vyřešený a odebereme ze začátku fronty.
□    g ► < -e ► < =
6. 12. 2017       18 / 24
Příklad 7.1 - prohledávání do šířky (řešení)
Na začátku fronty je vrchol g, vybereme jej ke zpracování.
□ [3
Příklad 7.1 - prohledávání do šířky (řešení)
Z vrcholu g již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze začátku fronty.
Fronta:
Pořadí:
6. 12. 2017       18 / 24
Prohledávání do šírky - shrnutí
Definice 7.1 (MILKOVA, mírně pozměněno): Při prohledávání souvislého grafu G — {V^E) konstruujeme modrý strom prohledávání do šířky
(7~s, v) s kořenem v £ V jako počátkem prohledávání. Hrany, které nepatří do (7~s, v), označujeme červenou barvou a nazýváme nestromové hrany. Pro libovolný vrchol w G V je zavedeno nezáporné číslo h(w) udávající číslo vrstvy stromu (7~s, v), ve které leží vrchol w.
Poznámka:
■ Aktuální vrchol je na začátku fronty. Označíme jej za zpracovaný a odebereme z fronty, až projdeme veškeré neobarvené hrany s ním incidentní.
■ Koncové vrcholy neobarvených hran vkládáme na konec fronty pouze tehdy, když nebyly dříve navštíveny. V takovém případě značíme hranu modře. Pokud neobarvená hrana vede do navštíveného vrcholu, tak pouze obarvíme hranu červeně.
■ Algoritmus končí vyprázdněním fronty.
6. 12. 2017       19 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Začínáme vrcholem c, který vložíme do zásobníku. Prozkoumáme přímé následníky vrcholu c.
Zásobník: Pořadí: c
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme a, vložíme jej na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {c, a}.
Zásobník: Pořadí: c, a
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme e, vložíme jej na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {a, e}.
Zásobník: Pořadí: c, a, e
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme b, vložíme jej na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {e, b}.
b
Zásobník: Pořadí: c, a, e, b
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme d, vložíme jej na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {b, d}.
Zásobník:
Pořadí: c, a, e, b, d
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme c, který však už byl navštívený. Pouze obarvíme červeně hranu {c/, c}.
Zásobník:
Pořadí: c, a, e, b, d
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Dle lexikografického pravidla vybereme e, který však už byl navštívený. Pouze obarvíme červeně hranu {c/, e}.
Zásobník:
Pořadí: c, a, e, b, d
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu d již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
b
Zásobník:
Pořadí: c, a, e, b, d
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je b. Označíme jej jako aktuální a hledáme přímé následníky.
b
Zásobník:
Pořadí: c, a, e, b, d
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu b vede jediná neobarvená hrana do nenavštíveného uzlu g. Vložíme g na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {b,g}.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu g vede jediná neobarvená hrana do navštíveného uzlu e. Pouze obarvíme červeně hranu {g,e}.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu g již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
b
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je b. Označíme jej jako aktuální a hledáme přímé následníky.
b
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu b již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je e. Označíme jej jako aktuální a hledáme přímé následníky.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu e již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je a. Označíme jej jako aktuální a hledáme přímé následníky.
Zásobník:
Pořadí: c, a, e, b, d, g
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu a vede jediná neobarvená hrana do nenavštíveného uzlu f. Vložíme f na zásobník a označíme jako aktuální, přičemž obarvíme modře hranu {a, f}.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu f vede jediná neobarvená hrana do navštíveného uzlu c. Pouze obarvíme červeně hranu {ŕ, c}.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu ŕ již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je a. Označíme jej jako aktuální a hledáme přímé následníky.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu a již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Na vrcholu zásobníku je c. Označíme jej jako aktuální a hledáme přímé následníky.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Příklad 7.1 - prohledávání do hloubky (řešení)
Z vrcholu c již nevede žádná neobarvená hrana. Označíme jej jako vyřešený a odebereme ze zásobníku.
Zásobník:
Pořadí: c, a, e, b, d, g, f
6. 12. 2017       20 / 24
Prohledávání do hloubky - shrnutí
Definice 7.2 (MILKOVA, mírně pozměněno): Při prohledávání souvislého grafu G — {V^E) konstruujeme modrý strom prohledávání do hloubky
(T"/,, v) s kořenem v £ V jako počátkem prohledávání. Hrany, které nepatří do (7~s, v), označujeme červenou barvou a nazýváme nestromové hrany.
Poznámka:
■ Aktuální vrchol je vždy na vrcholu zásobníku. Označíme jej za zpracovaný a odebereme ze zásobníku, až projdeme veškeré neobarvené hrany s ním incidentní.
■ Koncové vrcholy neobarvených hran vkládáme na zásobník pouze tehdy, když nebyly dříve navštíveny. V takovém případě značíme hranu modře. Pokud neobarvená hrana vede do navštíveného vrcholu, tak pouze obarvíme hranu červeně.
■ Algoritmus končí vyprázdněním zásobníku.
6. 12. 2017       21 / 24
Stromy prohledávání z Příkladu 7.1
■ Pořadí vrcholů při procházení do šířky: c,
■ Pořadí vrcholů při procházení do hloubky
(Th, c):
Příklad 2
Prohledejte následující graf do šírky a do hloubky, přičemž začněte v obou případech z vrcholu a. Na závěr nakreslete oba stromy prohledávání a zapište pořadí, ve kterém jste navštívili uzly.
Použité zdroje
□ FUCHS, Eduard. Diskrétní matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001. 178 s. ISBN 80-210-2703-7.
B MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6.
6. 12. 2017       24 / 24