GRAFOVÉ ALGORITMY
2006/7 - 1. termín
1. Izomorfismus na podstrom
Nechť S = (V, E) a T = (W, F) jsou orientované stromy s kořeny v0 resp. w0, nechť
V ∩ W = ∅. Zobrazení f : V → W je homomorfismus stromu S do stromu T, platí-li
( ∀ u, v ∈ V ) ( (u, v) ∈ E ⇒ (f(u), f(v)) ∈ F ) .
Úkolem je efektivně zjistit, zda existuje prostý homomorfismus S do T.
Nechť (V0, . . . , Vp) je rozklad množiny V podle vzdáleností od v0 (V0 = {v0}). Podobně
pro strom T dostáváme rozklad (W0, . . . , Wq).
Nechť pro v ∈ V je S(v) podstrom stromu S určený vrcholem v (dáme tam vše z S, co je
dosažitelné z v), nechť S[v] = {v′
∈ V | (v, v′
) ∈ E}. Podobně, pro w ∈ W definujeme T(w)
a T[w].
Definujme relaci ρ ⊆ V × W vztahem
(v, w) ∈ ρ právě když
existuje prostý homomorfismus f stromu S(v) do stromu T(w) splňující f(v) = w .
Platí :
existuje prostý homomorfismus S do T právě když
..................................................................∈ ρ.
Pro v ∈ V a w ∈ W definujeme pomocný (neorientovaný bipartitní) graf
G(v, w) = ( S[v] ∪ T[w], { {x, y} | x ∈ S[v], y ∈ T[w], (x, y) ∈ ρ } ) .
Platí : (v, w) ∈ ρ právě když
v grafu G(v, w) existuje párování splňující................................................................ (∗)
Relaci ρ uchováváme v booleovské (tj. nad {0, 1}) V × W matici, v níž položka v řádku
v a sloupci w (označujeme ji ρ(v, w) ) je 1 právě když (v, w) ∈ ρ. Celý problém se tedy
redukuje na výpočet této matice. Dokonce ji nepotřebujeme celou, pro v ∈ Vi nám stačí
hodnoty ρ(v, w) pro w ∈ Wi ∪ · · · ∪ ..............
Algoritmus :
1 for v ∈ Vp, w ∈ W do ρ(v, w) ←− 1 endfor
2 for i = p − 1, . . . , 0, v ∈ Vi, w ∈ Wi ∪ · · · ∪ W..... do spočítej ρ(v, w) podle (∗) endfor
Spočtěte hledanou matici pro následující stromy :
0000
0000
0000
1111
1111
1111
000
000
111
111
000
000
111
111
000
000
111
111
0000
0000
0000
1111
1111
1111
0000
0000
1111
1111
000
000
111
111
000
000
111
111
0000
0000
0000
1111
1111
1111
000
000
111
111
0000
0000
0000
1111
1111
1111
000
000
111
111
000
000
111
111
0000
0000
1111
1111
000
000
000
111
111
111
00000
00000
00000
00000
00000
11111
11111
11111
11111
11111
000000
000000
000000
000000
000000
111111
111111
111111
111111
111111
000000
000000
000000
000000
111111
111111
111111
111111
00000
00000
00000
00000
11111
11111
11111
11111
000000
000000
000000
000000
000000
111111
111111
111111
111111
111111
00000
00000
00000
00000
11111
11111
11111
11111
000000
000000
000000
000000
111111
111111
111111
111111
000000
000000
000000
000000
000000
111111
111111
111111
111111
11111100000
00000
00000
00000
00000
00000
00000
11111
11111
11111
11111
11111
11111
11111
000000
000000
000000
000000
000000
000000
000000
111111
111111
111111
111111
111111
111111
111111
00000
00000
00000
00000
00000
11111
11111
11111
11111
11111
000000
000000
000000
000000
000000
111111
111111
111111
111111
111111
000000
000000
000000
000000
000000
111111
111111
111111
111111
111111
a
b c
d
3
5
8
9
e f 7
1
2
4
6
Kvůli jednoznačnosti výpočtu : tam, kde máme volbu dáváme přednost vrcholům podle
uspořádání 1,2,... či a, b, ....
Maximální párovaní v bipartitním (neorientovaném) grafu s n vrcholy a m hranami
umíme najít v čase ....................... – zdůvodněte. Poněvadž se možná netrefíte, používejte
v dalším O(α(n, m)).
Nechť |V | = s, |W| = t. Nechť k je maximální out-degree vrcholu z S, podobně l pro T.
Složitost celého algoritmu je .................... – zdůvodněte.
2. Diferenční podmínky.
Uvažujme soustavu m nerovnic n proměnných x1, . . . , xn tvaru
xj1 − xi1 ≤ b1
...
xjm − xim ≤ bm
kde 1 ≤ ik, jk ≤ n, ik = jk a bk ∈ Z pro všechna k, 1 ≤ k ≤ m.
Definujeme pro danou soustavu orientovaný graf G = (V, E), kde V = {v0, v1, . . ., vn} a
E = {(vi, vj) | xj − xi ≤ b je některá z nerovnic} ∪ {(v0, vi) | 1 ≤ i ≤ n}. Dále definujeme
ohodnocení w hran takto: w(v0, vi) = 0 a w(vi, vj) = b kdykoli xj − xi ≤ b je některá z
nerovnic.
Věta ze strany 542 v brožurce říká :
Obsahuje-li graf příslušný k dané soustavě nerovnic záporně ohodnocený cyklus, nemá
daná soustava řešení. Neobsahuje-li tento graf záporně ohodnocený cyklus, má soustava řešení
(δ(v0, v1), . . . , δ(v0, vn)).
Uvažujme nerovnice:
x1 − x2 ≤ 1 (1)
x3 − x1 ≤ −3 (2)
x1 − x4 ≤ 4 (3)
x5 − x3 ≤ 5 (4)
x2 − x3 ≤ 1 (5)
K soustavám nerovnic (1) – (4) a (1) – (5). udejte příslušný graf. Algoritmem BellmanFord
z vrcholu v0 a aplikací výše uvedené věty rozhodněte, zda daná soustavy mají řešení.
V případě, že některá ze soustav řešení má, uveďte ho.
V každé sérii relaxací bereme hrany v pořadí (v0, v1), (v0, v2), . . . , pak hrany z podmínek
(1),...,(4), resp. (5).
2
GRAFOVÉ ALGORITMY
2006/7 - 2. termín
1. Minimální pokrytí
Je dán orientovaný graf G = (V, E), |V | = n, |E| = m. Množina P jeho cest (připouštíme
i cesty délky 0 ) je jeho pokrytí, je-li každý vrchol z V na právě jedné cestě z P. Úkolem je
v daném acyklickém grafu najít pokrytí minimální kardinality.
Terminologie :
cesta je posloupnost (v0, . . . , vk), kde k ∈ N0, v0, . . . , vk ∈ V, (v0, v1), . . . , (vk−1, vk) ∈ E,
cesta je prostá, jsou-li v0, . . . , vk po dvou různá,
smyčka je cesta (v, v),
kružnice je cesta (v0, . . ., vk, v0), kde k ∈ N, v0, . . . , vk po dvou různá.
K danému G = (V, E), v tomto okamžiku ne nutně acyklickému, sestrojíme (bipartitní
neorientovaný) graf G′
= ( V ∪ V ′
, E′
), kde V ′
= { v′
| v ∈ V } je disjunktní kopie množiny
V a F′
= { {v, w′
} | (v, w) ∈ F } pro F ⊆ E.
a) Množina F′
je párování v G′
právě když souvislé komponenty grafu (V, F) jsou tvaru :
....................................................................
b) Pro acyklický G je F′
je párování v G′
právě když množina souvislých komponent
grafu (V, F) tvoří
....................................................................
c) Pro množinu P cest v G nechť P◦
značí množinu všech hran na cestách z P. Nechť P
je pokrytí a |P| = k. Pak |P◦′
| = ........................
d) Tedy problém hledání minimálního pokrytí v acyklickém grafu je převeden na problém
hledání
........................................................... v G′
.
e) Tímto je dán Algoritmus 1. Odhadněte jeho složitost.
....................................................................
f) Ukažte, že to nemusí fungovat pro graf, který není acyklický.
g) Níže je dán graf G a pro vaše pohodlí i G′
, vše v několika kopiích. V G zvolte pokrytí
P s ”malým” počtem cest. Vyznačte množinu P′
a např. pomocí alternace volných cest ji
doplňte na optimální. Dokažte optimalitu.
Algoritmus 2 : Acyklický graf G topologicky uspořádáme. Cesty z P tvoříme takto : opakovaně
z nejlevějšího nepoužitého vrcholu postupujeme vpravo nejmenšími možnými kroky
po nepoužitých vrcholech.
h) Odhadněte složitost Algoritmu 2.
3
i) Namalujte výsledek po použití Algoritmu 2 na náš G. Přitom topologické uspořádání
je 1 < 2 < . . . .
43
6
7
8 9
12
15
11
14 1613
10 1721 5
43
6
7
8 9
12
15
11
14 1613
10 1721 5
2’
4’
6’
10’
11’
12’
13’
2
3
6
8
5
10
11
12
13
16
14
15
14’
15’
16’
17’
7
3’
5’
7’
17
9 9’
8’
4
1 1’
2’
4’
6’
10’
11’
12’
13’
2
3
6
8
5
10
11
12
13
16
14
15
14’
15’
16’
17’
7
3’
5’
7’
17
9 9’
8’
4
1 1’
4
2. V ohodnoceném neorientovaném grafu G = (V, E, w) zadaným obrázkem nalezněte
minimální kostru Primovým algoritmem. Je-li v některém kroku více možností, řiďte se
abecedou.
4
1
7 1
2
8
4
5
34
15 7
2
8
1
3
4 3
8
57
5
2
3
3
4
1
78
4
2 3
a
d
e i
n p
m
k l o
g
c
j
q r
f
b
h
4
1
7 1
2
8
4
5
34
15 7
2
8
1
3
4 3
8
57
5
2
3
3
4
1
78
4
2 3
a
d
e i
n p
m
k l o
g
c
j
q r
f
b
h
5
GRAFOVÉ ALGORITMY
2006/7 - 3. termín
1. Minimální doplnění na silně souvislý graf
Je dán orientovaný graf G = (V, E). Množina hran F ⊆ V × V je jeho doplněním, je-li
graf (V, E ∪ F) silně souvislý. Úkolem je najít doplnění minimální kardinality.
Pro v ∈ V označíme [v] silně souvislou komponentu obsahující vrchol v. Definujeme
faktorový graf GSCC
= (V SCC
, ESCC
), kde
V SCC
= { [v] | v ∈ V }, ESCC
= { ([u], [v]) | (u, v) ∈ E, [u] = [v] }
Zvolme zobrazení α přiřazující každé komponentě reprezentanta, neboli α : V SCC
→ V
splňující [α([v])] = [v].
a) Nechť F je minimální doplnění grafu G. Pak pro lib. (u, v) ∈ F je [u] = ...... a pro
různá (u, v), (u′
, v′
) ∈ F je ([u], [v]) = ........ Je tedy { ([u], [v]) | (u, v) ∈ F } doplněním grafu
GSCC
mohutnosti ...................... .
b) Naopak, je-li H doplnění grafu GSCC
bez smyček, je
............................................................ doplněním grafu G stejné mohut-
nosti.
Tedy obecný problém je převeden na problém hledání minimálního doplnění acyklického
grafu. Vrchol bez výstupních hran označíme stok, vrchol bez vstupních hran zdroj. Vrchol,
který je zároveň stok i zdroj nazveme izolovaný. Nechť v částech c) – j) je G acyklický
bez izolovaných vrcholů, |V | = n ≥ 2, |E| = m, s množinou zdrojů S a množinou stoků T,
|S| = s ≥ 1, |T| = t ≥ 1.
c) Lze předpokládat, že s ≤ t, jinak bychom graf G nahradili
..............................................................
Níže bude podán algoritmus, který najde r ≤ s, označí prvky množiny S symboly
v1, . . ., vs a prvky množiny T symboly w1, . . . , wt tak, aby platilo :
(i) pro každé i = 1, . . ., r existuje cesta z vi do wi,
(ii) pro každé i = r + 1, . . ., s existuje j ∈ {1, . . . , r} a cesta z vi do wj,
(iii) pro každé j = r + 1, . . . , t existuje i ∈ {1, . . ., r} a cesta z vi do wj.
Nechť S = {a1, . . . , as}, T = {b1, . . . , bt}.
Algoritmus 1 :
1. Pro i = 1, . . ., s vedeme z ai cestu. Vrcholy na ní označujeme symbolem i. Jsou dvě
možnosti :
a) narazíme na vrchol již označený; ten nepřeznačujeme a zvyšujeme i.
b) skončíme ve vrcholu bj ∈ T; pak prohlásíme (ai, bj) za nový pár a zvýšíme i.
2. Nyní si všímáme neoznačených prvků z T. Postupně z každého takového, řekněme bk,
vedeme zpětnou cestu a neoznačeným vrcholům dáváme značku 0. Jsou tři možnosti :
a) narazíme na vrchol se značkou i ≥ 1 a ai je v nějakém páru; bereme další neoznačený
prvek z T,
b) narazíme na vrchol se značkou i ≥ 1 a ai není v žádném páru; pak
(otázka d) ) ....................................................................
c) narazíme na vrchol se značkou 0; bereme další neoznačený prvek z T.
6
3. Vzniklé páry nechť jsou (v1, w1), . . ., (vr, wr), zbývající prvky z S resp. T označíme
symboly vr+1, . . ., vs resp. symboly wr+1, . . . , wt libovolně.
e) Složitost algoritmu je .........................................., neboť každé hrany si vší-
máme
....................................... a ..........................................
f) K čemu bylo dobré předpokládat acykličnost ? ..........................
Algoritmus 2 :
Klademe
F = { (w1, v2), . . . , (wr−1, vr), (wr, ws+1), (ws+1, ws+2), . . . , (wt−1, wt), (wt, v1)
jen (wr,v1) pro s=t
,
(wr+1, vr+1), . . . , (ws, vs) } .
Uvažme uzavřenou cestu Q v (V, E ∪ F) :
Q = (v1, . . . , w1
z párování
, v2, . . . , w2
z párování
, . . . , vr, . . . , wr
z párování
, ws+1, . . . , wt
nic pro s=t
, v1) .
g) Vše demonstrujte na následujícím grafu. Uveďte všechny páry, připište označení v1, . . ., w1, . . .
a přikreslete hrany z F. Kvůli jednoznačnosti dáváme přednost vrcholům, které jsou dříve v
uspořádání
a < · · · < d < 1 < 2 < · · · < 17 < p < · · · < u .
4
3
6
7
8 9
1
2 5 10 17
11
13 14 15 16
12
a
p
r s t u
b c d
q
4
3
6
7
8 9
1
2 5 10 17
11
13 14 15 16
12
a
p
r s t u
b c d
q
Ukážeme, že (V, E ∪ F) je silně souvislý :
Skutečně, lib. u ∈ V mimo Q lze na Q napojit : v G existuje cesta z u do nějakého
wj. Je-li j ∈ {1, . . . , r, s + 1, . . ., t} jsme hotovi. V opačném případě použijeme novou hranu
(wj, vj) a podmínku (ii).
h) Dále pro lib. takové u vede z Q do u cesta :
...................................................................
...................................................................
i) Máme |F| = ...........................................
7
j) Ukažte, že naše doplnění je minimální
...................................................................
...................................................................
k) Graf složený z p izolovaných vrcholů má minimální doplnění z ................... hran;
jak vypadá ? .........................
l) Konečně, nechť acyklický graf má p izolovaných vrcholů, s ≥ 1 zdrojů a t ≥ s stoků. Takový
graf má minimální doplnění z ................... hran; jak vypadá ? .........................
2. Grafy G a H jsou zadány obrázky níže. O každém z nich rozhodněte, zda je bipartitní
a své rozhodnutí dokažte. Najděte rovněž jejich maximální párování a dokažte, že Vámi
nalezená párování jsou maximální.
e
f
g h
j
nl m
b ca
d
k
i
a
b
e
i
j
m
p
q r
w
y z
n
d
g
l
h
c
o
u vs t
x
f
k
8