GRAFOVÉ ALGORITMY
2005/2006 - 1. termín
1. Malování
Nechť G = (V, E) je souvislý neorientovaný graf. Cesta p = (v0, v1, . . . , vk, v0), k ≥ 1 se
nazývá uzavřená. Uzavřená cesta je nakreslení, prochází-li každou hranou právě jednou.
a) Věta. G má nakreslení, právě když je stupeň každého vrcholu sudý.
Důkaz. =⇒ : Hint : Uvažujme nějaké nakreslení a diskutujme počty příchodů a odchodů
z jednotlivých vrcholů.
⇐= : níže uděláme konstruktivně.
Vrchol v je nasycený vzhledem k množině hran F ⊆ E, je-li každá hrana incidentní s v
prvkem množiny F.
b) Algoritmus :
V algoritmu se střídají fáze ”vpřed z vrcholu v” a ”zpět”. Začíná se z libovolného
vrcholu v.
”vpřed z vrcholu v” : Z vrcholu v budujeme cestu z dosud neobjevených (coby neorientovaných)
hran, které jsou jako orientované (ve směru objevení) ukládany do zásobníku.
Nelze-li pokračovat, je vrchol v zřejmě nasycený a přejdeme k fázi ”zpět”.
”zpět” : Nechť v zásobníku jsou hrany odpovídající cestě (u0, . . . , uk), k ≥ 1. Pokud
jsou uk, . . . , u0 nasycené, dáme na výstup (uk, uk−1), (uk−1, uk−2), . . . , (u1, u0) a končíme.
Pokud jsou uk, . . . , ul+1 nasycené a ul ne, dáme na výstup
......................................................,
odstraníme je ze zásobníku a pokračujeme fází ”vpřed z vrcholu .....................” .
Doplňte.
c) Příklad : Níže je zadán graf seznamem sousedů. Začněte z vrcholu 1 a v seznamech
postupujte zleva doprava (průběh algoritmu je jednoznačný). Pro snadné vynechávání objevených
hran máme v jednotlivých řádcích i ukazatele zprava doleva i ukazatele z hrany (i, j)
na hranu (j, i).
1 : 2 3
2 : 1 3 12 13
3 : 2 4 1 5
4 : 3 5
5 : 4 3 6 8 7 9
6 : 5 7 10 11
7 : 6 5
8 : 5 9
9 : 8 5
10 : 6 11
11 : 10 6
12 : 2 13
13 : 12 2
Místo označení hran dvojicemi (i, j) je číslujte v pořadí jejich objevení.
Průběh algoritmu :
Hrany objevené při ”vpřed z 1” : ........................................
hrany na výstupu při ”vzad” : ...........................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
.....................................................................
Diagram :
2
d) Dokažte korektnost algoritmu.
e) Odhadněte složitost algoritmu.
f) Jak uděláme linky z každého (i, j) do (j, i) v čase O(m + n) ?
3
2. Toky v sítích
Na síti z obrázku se zdrojem s a cílem t uveďte nějaký ”velký” tok. Dále používejte
algoritmus Edmonse a Karpa. Na každém řádku vždy vlevo uveďte reziduální graf s nějakou
nejkratší s − t-cestou, vpravo pak příslušný zvětšený tok.
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
4
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
1
2
3
6
7
8
10
6
8
14
2
5
3
7
1
8
9
12
2
6
9
2
9
1
7
4
6
3
8
9
5
4
5
4
8
11
s t
3
5
GRAFOVÉ ALGORITMY
2005/2006 - 2. termín
1. Svědomitý zametač
Nechť G = (V, E) je neorientovaný multigraf (t.j. připouští se násobné hrany). Cesta
p = (v0, v1, . . . , vk, v0), k ≥ 1 se nazývá uzavřená. Uzavřená cesta je nakreslení, procházíli
každou hranou právě jednou. Uzavřená cesta je pokrytí, prochází-li každou hranou alespoň
jednou. G = (V, E) se nazývá eulerovský, je-li souvislý a stupeň každého jeho vrcholu je
sudý.
Fakt. Multigraf G má nakreslení, právě když je eulerovský. Lze to realizovat v čase O(m),
kde m je počet hran.
Věta. Pro souvislý neorientovaný graf G = (V, E) a jeho uzavřenou cestu P je ekviva-
lentní:
(i) P je minimální pokrytí (vzhledem k počtu hran).
(ii) P je pokrytí, libovolná hrana z E je v P použita maximálně dvakrát a množina F
těch hran z E, které jsou v P použity vícekrát, je minimální (vzhledem k počtu) s následující
vlastnosti :
(*) přidáním disjunktní kopie F ke G vznikne eulerovský multigraf.
Důkaz. a) (i) ⇒ (ii) :
b) (ii) ⇒ (i) :
6
Nechť (V, E) je souvislý graf, nechť H ⊆ V, |H| = 2k > 0. Párování množiny H je
rozklad {h1, . . ., hk}, {h′
1, . . . , h′
k} této množiny spolu s cestami
c1 : h1 → . . . → h′
1 ,
...
ck : hk → . . . → h′
k .
Minimalita párování se chápe vzhledem k součtu délek příslušných cest.
Lemma. (i) V libovolném multigrafu je počet vrcholů lichého stupně sudý.
(ii) V minimálním párování se žádná hrana nevyskytuje více jak jednou.
c) Důkaz.
7
Lemma. Nechť G = (V, E) je souvislý graf. Množiny hran minimální vzhledem k (*)
jsou právě množiny hran minimálních párování množiny všech vrcholů lichého stupně.
d) Důkaz.
e) Je dán souvislý graf G = (V, E), |V | = n, |E| = m. Algoritmus pro minimální
pokrytí :
1. Najdeme množinu L všech vrcholů lichého stupně, nechť |L| = 2k – to umíme v čase
......
2. Spočteme vzdálenosti mezi všemi dvojicemi vrcholů z L – to umíme v čase ..............
pomocí ...................
3. Najdeme minimální párování množiny L – to umíme v čase O(f(k)) (fakt). Nechť F
je množina jeho hran.
4. Najdeme nakreslení grafu G obohaceného o disj. kopii hran z F.
To umíme v čase ............., neboť máme celkem .............. hran.
Celkem je tedy složitost .......................................
f) Demonstrujte algoritmus na grafu
e
h
f
b
i
d
g
a
c
8
2. Silně souvislé komponenty
Orientovaný graf G = (V, E), V = {1, . . ., 20} je dán seznamy sousedů :
1 : 6
2 :
3 : 2,7
4 : 9
5 : 4,10
6 : 2,15
7 : 2,6
8 : 1,3,4
9 : 2,5,8,11
10 : 3
11 : 17
12 : 10,17
13 : 12,18
14 : 15,17
15 : 18,20
16 : 11,13
17 : 16
18 : 12
19 : 13,14,18
20 : 14
Obrázek :
6 8
9
12
14 15
19
20
7
17 1816
10
543
13
1 2
11
a) Aplikujte na graf G průzkum do hloubky. Přitom každý seznam, sousedů procházíme
zleva a seznam seznamů shora. Nakreslete příslušný les i s časy objevení a ukončení
jednotlivých vrcholů.
9
b) Připravte si seznamy sousedů pro transponovaný graf. Využijte přitom řádky výše
uvedeného seznamu pro G. Nechť položky v každém řádku jsou uspořádány rostoucím způ-
sobem.
c) Dokončete algoritmus pro hledání silně souvislých komponent. Nakreslete příslušný les
a v diagramu výše vyznačte komponenty.
d) Uveďte příslušný faktorový graf.
10
GRAFOVÉ ALGORITMY
2005/2006 - 3. termín
1. Izomorfismus stromů.
Nechť G = (V, E) a G′
= (V ′
, E′
) jsou neorientované grafy. Zobrazení α : V → V ′
je
izomorfismus G na G′
, je-li to bijekce a pro libovolná u, v ∈ V platí :
{u, v} ∈ E právě když {α(u), α(v)} ∈ E′
.
Grafy G a G′
jsou izomorfní, existuje-li mezi nimi izomorfismus.
Nechť G = (V, E) je neorientovaný strom. Nechť V1 je množina všech vrcholů stromu G
stupně 1, nechť pro V 1
= V \ V1 = ∅ je G1
= (V 1
, {e ∈ E | e ⊆ V 1
}). Nechť V2 je množina
všech vrcholů stromu G1
stupně 1, nechť pro V 2
= V 1
\ V2 = ∅ je G2
= (V 2
, {e ∈ E |
e ⊆ V 2
}),. . . Poslední neprázdný graf je buď jediný vrchol nebo jediná úsečka – hovoříme o
centru resp. bicentru stromu G.
Algoritmus :
1. Pro stromy G a G′
spočítáme jejich centra/bicentra. Má-li jeden ze stromů centrum a
druhý bicentrum, nejsou izomorfní – konec. Mají-li oba bicentrum, vsadíme do jejich centrální
hrany u každého grafu nový vrchol tak, aby oba měli centrum. (Zřejmě jsou původní stromy
izomorfní, pravě když jsou izomorfní nové stromy.)
2. Oba stromy orientujeme směrem od jejich centrálních vrcholů. Nechť takto dostaneme
patra 1, 2, . . ., r resp. 1, 2, . . ., r′
, kde v patře 1 jsou právě centrální vrcholy. Pokud r = r′
nejsou stromy izomorfní – konec.
3. Současně pro oba stromy počínaje patrem r přiřazujeme vrcholům jednotlivých pater
jejich ohodnocení o[v] a typ t[v] takto :
(i) Všem vrcholům patra r dáme ohodnocení λ (= posloupnost délky nula) a typ 1.
(ii) Máme-li určeny typy všech vrcholů k-tého patra (k = r, . . . , 2), ohodnotíme každý
vrchol (k − 1)-ního patra neklesající posloupností typů všech jeho synů. Získaná ohodnocení
uspořádáme lexikograficky (tj. jako ve slovníku s prvním slovem λ). Vrcholy s nejmenším
ohodnocením budou mít typ 1, další typ 2, atd.
a) Věta. Stromy G a G′
jsou izomorfní právě když
.....................................................................
Důkaz.
b) =⇒:
11
c) ⇐=:
d) Demonstrujte algoritmus na příkladě :
Níže jsou stromy G a G′
zadány seznamy sousedů.
a : d, f 1 : 7
b : d 2 : 4, 7, 9
c : h 3 : 5, 7
d : a, b 4 : 2, 10, 15
e : j 5 : 3
f : a, j, k 6 : 13
g : n 7 : 1, 2, 3
h : c, j 8 : 9
i : o 9 : 2, 8, 13
j : e, f, h 10 : 4, 14, 16, 17
k : f, o, p 11 : 17
l : n 12 : 17
m : o 13 : 6, 9
n : g, l, o 14 : 10
o : i, k, m, n 15 : 4, 19
p : k, r, s 16 : 10
q : r 17 : 10, 11, 12
r : p, q 18 : 19
s : p 19 : 15, 18
12
e) Uveďte (až na izomorfismus) všechny neorientované stromy o sedmi vrcholech.
f) Jak hledáte centrum/bicentrum stromu G ? Odhadněte složitost. ( Pro snadné vynechávání
neorientovaných hran máme pro každou orientovanou hranu (u, v) link na (v, u).)
13
2. Nejkratší cesty
Orientovaný graf G = (V, E) je zadaný diagramem
A
C
D
E
F
B
1
−22 0
1
2
1 3
6
4
4
Určete pro každou dvojici vrcholů z množiny V = {A, B, C, D, E, F} délku nejkratší
cesty mezi nimi. Jestliže mezi nimi nevede žádná cesta, označte délku jako ∞, jestliže mezi
nimi nějaká cesta vede, ale žádná není nejkratší, označte ji −∞.
Použijte (modifikaci) některého z algoritmů kapitoly 26. Musíte skutečně počítat s maticemi
řádu 6 ?
Může se vám hodit “matice”
A B C D E F
A -2 2
B 1
C 1 4
D 1 2 6
E 3
F 4 0
14