GRAFOVÉ ALGORITMY
2004/2005 - 1. termín
1. Tranzitivní obal.
Konečná uspořádaná množina P = (P, ≤) je zadána pomocí relace pokrývání ≺. Výpočet
relace ≤ algoritmem Floyd – Warshall vezme čas ............
Simonův algoritmus.
Nechť n = |P|, c = |≺|, o = |≤|. Nechť množina P je reprezentována seznamem odpovídajícímu
nějakému topologickému uspořádání grafu (P, ≺). Nechť ord [x] = i značí, že x ∈ P
je zde i-tým prvkem. Pro každé x ∈ P máme vypočítat seznam F[x] reprezentující množinu
f(x) = { y ∈ P | x ≤ y }.
Nechť U[x] je seznam reprezentující množinu u(x) = { y ∈ P | x ≺ y }. Nechť množina
P je sjednocením po dvou disjunktních řetězců C1, . . . , Ck, nechť C[x] = j značí, že x ∈ Cj.
První položku seznamu S značíme first S.
Doplňte následující algoritmus. Dokažte jeho korektnost a odhadněte jeho složitost vzhledem
k parametrům n, k, c, o.
1 invertujeme seznam P, nechť vznikne seznam S
2 for x ∈ S, j = 1, . . . , k do G[j, x] ←− ∅ endfor
3 for x ∈ S do
4 for y ∈ U[x] do
5 for j = 1, . . ., k do
6 if ..................................... .......................................... then
7 G[j, x] ←− G[j, y]
8 endif
9 endfor
10 endfor
11 push(x, G[C[x], x])
12 endfor
13 for x ∈ S do F[x] ←− ∅ endfor
14 for x ∈ S do
15 for j = 1, . . ., k do
16 F[x] ←− G[j, x] ∪ F[x]
17 endfor
18 endfor
Nechť g(j, x) je jistá podmnožina množiny Cj reprezentovaná seznamem G[j, x].
Na připravených diagramech uveďte stav množin g(j, x) v okamžicích l. 10 a l. 12.
Máme C1 = {1, 2, 5, 8}, C2 = {3, 7}, C3 = {4, 6} a topologické uspořádání množiny P
je (1, 2, . . ., 8).
x
xx
x x
x x
x x x
x x x
y
y
y
y
y
y
y y y
x
y
y
x
x xx
y
xx
1
2 3 4
5 6 7
8
I když se vám nepodaří “trefit” podmínku z l. 6, můžete dostat body za odhad složitosti.
Předpokládejte, že její ověření vezme konstantní čas.
2
2. Toky v sítích
Na síti z obrázku se zdrojem 0 a cílem 11 najděte maximální tok. Podejte důkaz jeho
maximálnosti.
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2
9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2
9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2
9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2
9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2
9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2 9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
1
2
3
6
7
8
10
11
6
8
14
6
2
5
3
7
1
8
2 9
12
2
6
9
2
9
1
7
4
6
3
8
0 9
5
4
11
8
4
3
GRAFOVÉ ALGORITMY
2004/2005 - 2. termín
1. Rozklad uspořádané množiny na řetězce.
Konečná uspořádaná množina P = (P, ≤) je zadána pomocí relace pokrývání ≺. Nechť U[x]
je seznam reprezentující množinu u(x) = { y ∈ P | x ≺ y }. Nechť n = |P|, c = |≺|. Nechť
množina P je reprezentována seznamem odpovídajícím nějakému topologickému uspořádání
grafu (P, ≺).
Pro x ∈ P máme spočítat C[x] ∈ {1, . . ., k} dávající rozklad množiny P na neprázdné
řetězce Cj = { x ∈ P | C[x] = j }, j ∈ {1, . . ., k}.
Pro x ∈ P je význam Z[x] ∈ {0, 1} “nezařazeno”/“zařazeno”. Nechť množina l “kandidátů”
je reprezentována seznamem L.
První položku seznamu S značíme first S. Neprázdný seznam S ochuzený o první položku
značíme rest S.
Doplňte následující algoritmus.
1 j ←− 1
2 for x ∈ P do Z[x] ←− 0 endfor
3 for x ∈ P do
4 if Z[x] = 0 then
5 C[x] ←− j
6 Z[x] ←− 1
7 L ←− U[x]
8 while L = ∅ do
9 y ←− first L
10 if Z[y] = 0 do
11
12
13
13’
14 else
15
16 endif
17 endwhile
18 j ←− j + 1
19 endif
20 endfor
Na připravených diagramech uveďte každou změnu množiny l společně s číslem řádku,
na němž ke změně došlo. Topologické uspořádání množiny P je (1, 2, . . ., 8). Seznamy U[x]
respektují toto uspořádání.
4
1
4
5
32
8
76
Dokažte jeho korektnost. Důkaz může vypadat např. takto :
1. Každé Cj je neprázdný řetězec :
2. j=1,...,k Cj = P :
3. Pro j = j′
je .......................
Bedlivě odhadněte složitost vašeho algoritmu vzhledem k parametrům n, c. Odhadněte
též c pomocí n a uveďte složitost algoritmu vzhledem k n. I když se vám nepodaří “trefit”
příkazy z l. ...., můžete dostat body za odhad složitosti. Předpokládejte, že každý z těchto
příkazů vezme konstantní čas.
Konečně poznamenejte, co by se stalo, kdyby množina P nebyla topologicky uspořádaná.
5
2. Párování.
a) Ukažte, že níže uvedený graf G = ({1, . . ., 20}, ...) není bipartitní.
b) Najděte v našem grafu maximální párování.
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
000000
111111
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000
00
1111
11
0000111100001111
00000000000000001111111111111111
00000000000000001111111111111111
000
00000
0
111
111111
000
00000
0
111
11111
1
000
00000
00000
0000
0000
00000
000
000
1111
11111
11111
1111
1111
11111
111
11
000
00000
00000
0000
0000
00000
000
000
1111
11111
11111
1111
1111
11111
111
11
000
00000
0
111
111111
000
00000
0
111
11111
1
000000000000
00000000000000000000
0000
111111111111
111111111111111111111111
000000000000
00000000000000000000
111111111111
11111111111111111111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000000
0000000000000000000000000
00000
111111111111111
1111111111111111111111111
11111 000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000
00000000000000000000
111111111111
11111111111111111111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
00000111110000011111
0000000000000000011111111111111111
0000000000000000011111111111111111
0000011111 0000011111
00
00
000
0
11
11
111
1
000
0000
00
111
1111
11
0000
0000
000000
0000
000000
0000
0000
0000
0000
0000
000000
00
000000
00
00
111111
1111
111111
111111
1111
1111
1111
1111
1111
1111
111111
11
111111
11
00
00
000
00
000
00
00
00
00
00
000
0
000
0
0
111
11
111
111
11
11
11
11
11
11
111
1
111
1
00
00
000
0
11
11
111
1
000
0000
00
111
1111
11
0000000000
0000000000
000000000000000
00000
1111111111
1111111111
111111111111111
11111
0000000000
0000000000
000000000000000
00000
1111111111
1111111111
111111111111111
11111
000000000000000
00000000000000000000
0000000000
111111111111111
11111111111111111111
1111111111
000000000000000
00000000000000000000
0000000000
111111111111111
11111111111111111111
1111111111
000000000000
0000000000000000
00000000
111111111111
1111111111111111
11111111 0000000000
0000000000
000000000000000
0000000000
1111111111
111111111111111
1111111111
1111111111
0000000000
0000000000
000000000000000
0000000000
1111111111
111111111111111
1111111111
1111111111
0000000000
0000000000
000000000000000
0000000000
1111111111
1111111111
111111111111111
1111111111
0000111100001111
00000000000000001111111111111111
00000000000000001111111111111111
000
00000
0
111
111111
000
00000
0
111
11111
1
000
00000
00000
0000
0000
00000
000
000
1111
11111
11111
1111
1111
11111
111
11
000
00000
00000
0000
0000
00000
000
000
1111
11111
11111
1111
1111
11111
111
11
000
00000
0
111
111111
000
00000
0
111
11111
1
000000000000
00000000000000000000
0000
111111111111
111111111111111111111111
000000000000
00000000000000000000
111111111111
11111111111111111111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000000
0000000000000000000000000
00000
111111111111111
1111111111111111111111111
11111 000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
000000000000
00000000000000000000
111111111111
11111111111111111111
000000000000
00000000000000000000
0000
111111111111
11111111111111111111
1111
0000111100001111
00000000000000001111111111111111
00000000000000001111111111111111
00001111 00001111
00
00
000
0
11
11
111
1
000
0000
00
111
1111
11
00
00
000
00
000
00
00
00
00
00
000
0
000
0
0
111
11
111
111
11
11
11
11
11
11
111
1
111
1
00
00
000
00
000
00
00
00
00
00
000
0
000
0
0
111
11
111
111
11
11
11
11
11
11
111
1
111
1
00
00
000
0
11
11
111
1
000
0000
00
111
1111
11
00000000
00000000
000000000000
0000
11111111
11111111
111111111111
1111
00000000
00000000
000000000000
0000
11111111
11111111
111111111111
1111
000000000000
0000000000000000
00000000
111111111111
1111111111111111
11111111
000000000000
0000000000000000
00000000
111111111111
1111111111111111
11111111
000000000000000
00000000000000000000
0000000000
111111111111111
11111111111111111111
1111111111 00000000
00000000
000000000000
00000000
11111111
111111111111
11111111
11111111
00000000
00000000
000000000000
00000000
11111111
111111111111
11111111
11111111
00000000
00000000
000000000000
00000000
11111111
11111111
111111111111
11111111
4 5
6
8
9
11
13 14
16 17 20
10
1
19
18
3
2
12 15
7
6
GRAFOVÉ ALGORITMY
2004/2005 - 3. termín
1. Výpočet relace pokrývání.
Konečná uspořádaná množina P = (P, ≤) je zadána pomocí matice určující relaci ≤ (pro
x, y ∈ P v konstantním čase zjistíme zda x ≤ y či nikoliv). Sama množina P je reprezentována
seznamem odpovídajícímu nějakému topologickému uspořádání grafu (P, ≤).
Úkolem je spočítat seznamy U[x], x ∈ P, reprezentující množiny
u(x) = { y ∈ P | x ≺ y } .
První položku seznamu S značíme first S. Neprázdný seznam S ochuzený o první položku
značíme rest S. Doplňte následující algoritmus.
1 Q ←− P
2 for a ∈ P
3 Q ←− rest Q
4 S ←− ∅
5 for x ∈ Q do
6 if a ≤ x then
7 T ←− S
8 while T = ∅ and first T.............. do
9 ......................................
10 endwhile
11 if T = ∅ then push (x, S) endif
12 endif
13 endfor
14 U[a] ←− S
15 endfor
Konkrétní případ : Matice relace ≤ je níže (na pozici (x, y) je 1 právě když x ≤ y).
Topologické uspořádání je (1, 2, . . ., 8).
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1
2 0 1 0 0 1 1 0 1
3 0 0 1 0 1 0 1 1
4 0 0 0 1 0 1 1 1
5 0 0 0 0 1 0 0 1
6 0 0 0 0 0 1 0 1
7 0 0 0 0 0 0 1 1
8 0 0 0 0 0 0 0 1
Do připravené tabulky uveďte všechny změny proměnných x, S, T v části výpočtu, kde
a = 1.
7
řádek x S T
Dokažte jeho korektnost. Důkaz může vypadat např. takto :
1. Do seznamu S se může dostat jen prvek pokrývající prvek a.
8
2. Libovolný prvek zařazovaný do S pokrývá a.
Nechť n = |P|, c = |≤|. Odhadněte složitost našeho algoritmu. I když se vám nepodaří
trefit” formule/příkazy z l. ...., můžete dostat body za odhad složitosti. Předpokládejte, že
každý z těchto příkazů vezme konstantní čas.
2. Cirkulace
Nechť V = {1, . . . , n} a nechť G = (V, E) je orientovaný graf s ohodnocením hran
c : E → R. V konkrétním příkladě uvedeném níže najděte maximální cirkulaci. Například
můžete použít algoritmus:
Především každá cirkulace x určuje pomocný graf Gx = (V, Ex) s ohodnocením hran wx:
(i, j) ∈ Ex ⇐⇒ ( (i, j) ∈ E & xij < cij nebo to neplatí a (j, i) ∈ E & xji > 0 ) .
Hrany prvního typu ohodnotíme −1 a hrany druhého typu 1.
1. Začínáme s nulovou cirkulací.
2. while v (Gx, wx) existuje záporná kružnice
do vybereme některou a zvětšíme podél ní cirkulaci.
Abyste se ve výpočtech vyznali, doporučuji např. cirkulace modře, hrany pomocného grafu
s ohodnocením -1 zeleně, ty s ohodnocením 1 červeně, další barvu můžete použít pro záporné
kružnice.
Hodnocení: nalezení maximální cirkulace 10 b. Důkaz maximality (např. pomocí některého
algoritmu pro hledání záporných kružnic) dalších 10 b.
9
2
4
4
7
3
1
2
2
4
4 3
2
4 4
42
4
2 2
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
2
4
4
7
3
1
2
2
4
4 3
2
4 4
42
4
2 2
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
2
4
4
7
3
1
2
2
4
4 3
2
4 4
42
4
2 2
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10
1 2
3
4
5
6
7
8 9
10