GRAFOVÉ ALGORITMY
2007/8 - 1. termín
1. Artikulace a bloky
Uvažujeme neorientované grafy. Artikulace je takový vrchol, že po jeho odstranění
(včetně hran s ním incidentních) se zvětší počet souvislých komponent. Blok je (vzhledem k
inluzi) maximální množina vrcholů vzhledem k následující vlastnosti : je alespoň dvouprvková
a příslušný indukovaný podgraf je souvislý a nemá artikulaci.
Níže máte uvedeny dva algoritmy. První je varianta DFS, druhý by měl počítat artikulace
a bloky souvislého grafu.
Komentář k proměnným :
G = (V, E) je neorientovaný graf, s ∈ V ,
nr(v) je pořadí objevení vrcholu v,
p(v) je předchůdce vrcholu v,
u(e) je příznak objevení hrany e, přitom píšeme e = uv = vu pro e = {u, v},
S je zásobník,
C je množina všech artikulací,
L je funkce low,
k je počet bloků,
B1, . . . , Bk jsou bloky.
Přitom L(v) je definováno jako :
min{ nr(v), min{ nr(u) | ∃ w ∈ V a v−w−cesta ze stromových hran a zpětná hrana wu } }
Na dvě místa do druhého algoritmu doplňte přiřazení/podmínku týkající se funkce L.
Dále doplňte :
Vrchol v = s je artikulace právě když ............(v termínech L).
Vrchol s je artikulace právě když ............ .
Průběh části výpočtu druhého algoritmu na níže uvedený graf uveďte do připravené
tabulky. Pokud máme někde více možností, řídíme se abecedou. Přitom :
krok = vypořádání se s novou hranou nebo návrat po stromové hraně,
typ kroku : t = objevení stromové hrany,
b = objevení zpětné hrany,
n = návrat po stromové hraně.
Uveďte stav zásobníku S a proměnné L po každém kroku. Váš první krok : jeden krok
před prvním návratem. Váš poslední krok : druhá stromová z s.
Po skončení výpočtu :
C = ...................................
k = ...................................
B1 = .................................
B2 = .................................
...................................
Do diagramu též pro každý vrchol v uveďte nr(v)/L(v).
s
b
a
c
d
e
f
g
h
i
j
k
l
s
b
a
c
d
e
f
g
h
i
j
k
l
s
b
a
c
d
e
f
g
h
i
j
k
l
s
b
a
c
d
e
f
g
h
i
j
k
l
s
b
a
c
d
e
f
g
h
i
j
k
l
s
b
a
c
d
e
f
g
h
i
j
k
l
První algoritmus na souvislém grafu má složitost O(|E|), neboť kromě inicializace pracujeme
s každou hranou v každém směru právě jednou a vždy provedeme konstantní počet
kroků. Ja je to pro druhý algoritmus ?
...................
Dokažte, že druhý algoritmus správně počítá bloky (alespoň pro případ p(v) je artikulace,
p(v) = s).
...................
2
2. Párování
Grafy G a H spolu s jejich párováními jsou zadány obrázky níže. O každém z nich
rozhodněte, zda je bipartitní a své rozhodnutí dokažte.
Zjistěte zda daná párování jsou maximální. Pro oba grafy najděte jejich maximální párování
a dokažte maximalitu.
Můžete např. použít alternaci volných cest s tím, že když z daného vrcholu taková cesta
neexistuje, nemusíme ho dále uvažovat.
3
GRAFOVÉ ALGORITMY
2007/8 - 2. termín
1. Druhá nejlepší minimální kostra
Nechť G = (V, E) je souvislý neorientovaný graf, nechť w : E → R je na různých hranách
různá. Již víme, že existuje jediná minimální kostra (stručně MST). Kostra T je SBMST,
jestliže má mezi všemi kostrami druhé nejmenší ohodnocení (takových koster může být více).
a) Nechť T je MST a T′
je SBMST. Dokažte, že existují hrany (u, v) ∈ T a (x, y) ∈ T
tak, že T′
= (T \ {(u, v)}) ∪ {(x, y)}.
Důkaz : Uvědomte si, že libovolná kostra má |V | − 1 hran.
1. Nechť T′
\ T = {(x, y)}. Pak T \ T′
= .........................
a platí ...............................
2. Nechť |T′
\ T| ≥ 2. Pak i |T \ T′
| ≥ 2. Nechť (u, v) je minimální váhy z T \ T′
. Pak
T′
∪ {(u, v)} má cyklus c a na něm existuje hrana (x, y) ∈
.......................................................
Sporem dokážeme, že w(x, y) > w(u, v). V T ∪ {(x, y)} máme cyklus c′
. Ten obsahuje
(u′
, v′
) ∈
................................................................
Nyní T′′
= (T \ {(u′
, v′
)}) ∪ {(x, y)} je kostra a tedy w(u′
, v′
) < ..................
Celkem
...........................................
a to je spor s volbou
............................................
Konečně položme T′′′
= (T′
\ {(x, y)}) ∪ {(u, v)}. Pak w(T′′′
) < ...................
Přitom T′′′
= T, neboť
...............................................
A už konečný máme spor, neboť
...............................................
b) Následující algoritmus pro kostru T ⊆ E počítá, pro všechna u, v ∈ V , maximálně
ohodnocenou hranu na (jediné) u-v-cestě v T.
BFS-Fill-Max(T, w)
1 for each vertex u ∈ V
2 do for each vertex v ∈ V
3 do {
4 max[u, v] ← nil
5 }
6 Q ← ∅
7 Enqueue(Q, u)
8 while Q = ∅
9 do {
10 x ← Dequeue(Q)
11 for each v ∈ Adj[x]
12 do {
13 if max[u, v] = nil and .....
14 then if x = u or .....
15 then max[u, v] ← (x, v)
16 else max[u, v] ← max[u, x]
17 Enqueue(Q, v)
18 }
19 }
20 return max
b1) Doplňte dvě chybějící formulky.
b2) Odhadněte složitost (při důkazu se můžete odvolat na BFS).
b3) Aplikujte algoritmus na následující strom. Seznamy sousedů jsou podle abecedy. Pro
u = a uveďte postupně všechny změny proměnných Q, x, v, max společně s číslem řádku, kde
k tomu došlo.
000
000
000
111
111
111
000
000
000
111
111
111
000
000
000
111
111
111
000
000
000
111
111
111
00
00
00
11
11
11
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
00000000000000000000000000000001111111111111111111111111111111
00000000000000001111111111111111
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a di
e
fb
h c g
3
6
0
72
541
000
000
000
111
111
111
000
000
000
111
111
111
00
00
00
11
11
11
00
00
00
11
11
11
000
000
000
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
00
00
00
00
11
11
11
11
000000000000000000000000000000111111111111111111111111111111
00000000000000001111111111111111
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a di
e
fb
h c g
3
6
0
72
541
000
000
000
111
111
111
000
000
000
111
111
111
000
000
000
111
111
111
000
000
000
111
111
111
00
00
00
11
11
11
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
111
111
111
00000000000000000000000000000001111111111111111111111111111111
00000000000000001111111111111111
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a di
e
fb
h c g
3
6
0
72
541
000
000
000
111
111
111
000
000
000
111
111
111
00
00
00
11
11
11
00
00
00
11
11
11
000
000
000
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
000
000
000
000
111
111
111
111
00
00
00
11
11
11
000000000000000000000000000000111111111111111111111111111111
00000000000000001111111111111111
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a di
e
fb
h c g
3
6
0
72
541
2
c) Je dána MST T a matice (max[u, v])u,v∈V . Jak spočítáte nějakou SBMST T′
?
Nalezneme (x, y) ∈ T minimalizující
............................................................
a položíme
T′
= .......................................................
Důkaz korektnosti :
Podle bodu a) existují
.............................................................
tak, že
T′
= .............................................................
přitom
w(T′
) = w(T)− ..................................................
Pro dané (x, y) je (u, v) minimalizující w(T′
) právě
..................................................................
3
2. Silně souvislé komponenty
V městě Autokarově řešili problém s dopravou. Silnice jsou tu úzké a nestačí pro obousměrný
provoz. Bylo potřeba z každé silnice udělat jednosměrku. Řešení strážníka Hlavičky
vidíte na přiloženém plánku. Jediná obousměrná cesta je trajektová linka mezi body 5 a
14. Vaším úkolem je pomocí vhodného algoritmu spočítat silně souvislé komponenty takto
vzniklého grafu (a navrhnout minimální počet a umístění autovrakovišť, které potřebuje
Autokarov po změnách strážníka Hlavičky :) ).
3 42
1
5
6 7 8
11109
12 13 14
most
trajekt
3 42
1
5
6 7 8
11109
12 13 14
most
trajekt
3 42
1
5
6 7 8
11109
12 13 14
most
trajekt
3 42
1
5
6 7 8
11109
12 13 14
most
trajekt
4
GRAFOVÉ ALGORITMY
2007/8 - 3. termín
1. st-očíslování
Je dán neorientovaný graf G = (V, E) s n ≥ 2 vrcholy, který je 2-souvislý (t.j. je souvislý
a po odstranění libovolného vrcholu se spolu s ním incidentními hranami zůstavá souvislý).
Máme najít bijekci STN : V → {1, . . . , n}, píšeme v = vi pro STN(v) = i, tak, aby :
(i) {v1, vn} ∈ E,
(ii) pro každé j ∈ {2, 3, . . ., n − 1} existují i, k ∈ {1, . . . , n} tak, že i < j < k a
{vi, vj}, {vj, vk} ∈ E.
Předpokládáme, že již proběhl průzkum do hloubky. Čas objevení (1, 2, . . .) vrcholu v
nechť je DFN(v), jeho otec je FATH(v).
Hodnota funkce LOW(u) je definováno jako :
min{ DFN(u), min{ DFN(w) | ∃ x ∈ V a u−x−cesta ze stromových hran a zpětná (x, w) } } .
Dále předpokládáme, že máme napočítanou i funkci LOW spolu s příslušnými cestami.
Pro v ∈ V se cesta PATH(v) určuje takto :
Případ 1. Existuje nová zpětná hrana (v, w). Prohlásíme ji za starou a položíme PATH(v) =
(v, w).
Případ 2. Existuje nová stromová hrana (v, u). Nechť (u = u0, u1, . . . , uk, w) je cesta
dávající LOW(u) = DFN(w). Proč je u = w ?
.................................................................
Položíme PATH(v) = (v, u0, u1, . . . , uk, w) a všechny vrcholy a hrany na ní prohlásíme za
staré.
Případ 3. Existuje nová zpětná hrana (u, v). Nechť (u = u0, u1, . . . , uk, w) je cesta nahoru
po stromových hranách do prvního starého w. Položíme PATH(v) = (v, u0, u1, . . ., uk, w) a
všechny vrcholy a hrany na ní prohlášíme za staré.
Případ 4. Všechny hrany incidentní s v jsou staré. Položíme PATH(v) = ∅.
ST-Number(G)
1 begin
2 mark s, t and (s, t) “old” and all the other vertices and edges “new”;
3 push down t and s into stack S in this order;
4 {s is over t}
5 COUNT ← 1;
6 pop up the top entry v from S;
7 while v = t
8 do begin
9 if PATH(v) = ∅
10 then begin
11 STN(v) ← COUNT;
12 COUNT ← COUNT + 1
13 end
14 else begin
15 let PATH(v) = (v, u1, u2, · · · , uk, w);
16 push down the vertices uk, uk−1, . . . , u1, v into S in this order
17 {v is a top entry of S}
18 end
19 fi;
20 pop up the top entry v from S
21 end;
22 STN(t) ← COUNT
23 end.
Algoritmus demonstrujte na níže uvedených diagramech. Zastavujeme se vždy na ř. 19.
Nad diagram uveďte případ (1 až 4), podle něhož se našla cesta. “Old” vrcholy a hrany
vyznačte modře, nalezenou (orientovanou) cestu červeně. Pod diagram uveďte stav zásobníku
S a změny proměnné STN od posledního kroku. Začínáme s modře vyznačenými a, c, {a, c}
a zásobníkem c, a (odshora).
00
0000
11
1111
00
0000
11
1111
0000
00
1111
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
00
00
0
00
00
0
0
0
00
0
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
1
1
11
1
1
1
11
1
1
1
11
1
1
1
11
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
0000000
00000000000000
0000000
0000000
0000000
00000000000000
0000000
0000000
0000000
0000000
1111111
11111111111111
1111111
1111111
1111111
11111111111111
1111111
1111111
1111111
1111111
g
f
d
a
e
c
00
0000
11
1111
00
0000
11
1111
0000
00
1111
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
00
00
0
00
00
0
0
0
00
0
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
1
1
11
1
1
1
11
1
1
1
11
1
1
1
11
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
000000
000000000000
000000
000000
000000
000000000000
000000
000000
000000
000000
111111
111111111111
111111
111111
111111
111111111111
111111
111111
111111
111111
g
f
d
a
e
c
00
0000
11
1111
00
0000
11
1111
0000
00
1111
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
00
00
0
00
00
0
0
0
00
0
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
1
1
11
1
1
1
11
1
1
1
11
1
1
1
11
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
0000000
00000000000000
0000000
0000000
0000000
00000000000000
0000000
0000000
0000000
0000000
1111111
11111111111111
1111111
1111111
1111111
11111111111111
1111111
1111111
1111111
1111111
g
f
d
a
e
c
00
0000
11
1111
00
0000
11
1111
0000
00
1111
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
00
00
0
00
00
0
0
0
00
0
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
1
1
11
1
1
1
11
1
1
1
11
1
1
1
11
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
000000
000000000000
000000
000000
000000
000000000000
000000
000000
000000
000000
111111
111111111111
111111
111111
111111
111111111111
111111
111111
111111
111111
g
f
d
a
e
c
2
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
0
00
0
0
0
00
0
0
0
00
0
0
0
0
00
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
1
1
11
1
1
1
11
1
1
1
1
11
1
1
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
0000000
0000000
00000000000000
0000000
0000000
0000000
00000000000000
0000000
0000000
0000000
0000000
1111111
1111111
11111111111111
1111111
1111111
1111111
11111111111111
1111111
1111111
1111111
1111111
g
f
d
a
e
c
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
0
00
0
0
0
00
0
0
0
00
0
0
0
0
00
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
1
1
11
1
1
1
11
1
1
1
1
11
1
1
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
000000
000000
000000000000
000000
000000
000000
000000000000
000000
000000
000000
000000
111111
111111
111111111111
111111
111111
111111
111111111111
111111
111111
111111
111111
g
f
d
a
e
c
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
0
00
0
0
0
00
0
0
0
00
0
0
0
0
00
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
1
1
11
1
1
1
11
1
1
1
1
11
1
1
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
0000000
0000000
00000000000000
0000000
0000000
0000000
00000000000000
0000000
0000000
0000000
0000000
1111111
1111111
11111111111111
1111111
1111111
1111111
11111111111111
1111111
1111111
1111111
1111111
g
f
d
a
e
c
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
00
00
00
11
11
11
0
0
00
0
0
0
00
0
0
0
00
0
0
0
0
00
0
0
00
0
0
0
00
0
00
0
0
0
00
0
00
0
0
0
00
0
1
1
11
1
1
1
11
1
1
1
1
11
1
1
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
1
11
1
11
1
1
000000
000000
000000000000
000000
000000
000000
000000000000
000000
000000
000000
000000
111111
111111
111111111111
111111
111111
111111
111111111111
111111
111111
111111
111111
g
f
d
a
e
c
00
00
00
11
11
11
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
0
00
00
0
00
00
0
00
0
00
0
00
00
0
000
0
000
0
000
0
000
0
000
0
0
00
0
0
1
11
11
1
11
11
1
11
1
11
1
11
11
1
111
1
111
1
111
1
111
1
111
1
11
1
1
1
0000000
00000000000000
00000000000000
0000000
00000000000000
00000000000000
0000000
0000000
1111111
11111111111111
1111111
11111111111111
11111111111111
1111111
11111111111111
1111111
g
f
d
a
e
c
00
00
00
11
11
11
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
0
00
00
0
00
00
0
00
0
00
0
00
00
0
000
0
000
0
000
0
000
0
000
0
0
00
0
0
1
11
11
1
11
11
1
11
1
11
1
11
11
1
111
1
111
1
111
1
111
1
111
1
11
1
1
1
000000
000000000000
000000000000
000000
000000000000
000000000000
000000
000000
111111
111111111111
111111
111111111111
111111111111
111111
111111111111
111111
g
f
d
a
e
c
00
00
00
11
11
11
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
0
00
00
0
00
00
0
00
0
00
0
00
00
0
000
0
000
0
000
0
000
0
000
0
0
00
0
0
1
11
11
1
11
11
1
11
1
11
1
11
11
1
111
1
111
1
111
1
111
1
111
1
11
1
1
1
0000000
00000000000000
00000000000000
0000000
00000000000000
00000000000000
0000000
0000000
1111111
11111111111111
1111111
11111111111111
11111111111111
1111111
11111111111111
1111111
g
f
d
a
e
c
00
00
00
11
11
11
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
0
00
00
0
00
00
0
00
0
00
0
00
00
0
000
0
000
0
000
0
000
0
000
0
0
00
0
0
1
11
11
1
11
11
1
11
1
11
1
11
11
1
111
1
111
1
111
1
111
1
111
1
11
1
1
1
000000
000000000000
000000000000
000000
000000000000
000000000000
000000
000000
111111
111111111111
111111
111111111111
111111111111
111111
111111111111
111111
g
f
d
a
e
c
Dostali jste skutečně st-očíslování ? Ke každému i připište vi a namalujte všechny hrany
množiny E. (Druhý diagram máme pro ty co pokazí první.)
00
0000
11
1111
0
00
1
11
0
00
1
11
0
00
1
11
00
0000
11
1111
00
0000
11
1111
1 2 3 654
00
0000
11
1111
00
0000
11
1111
00
0000
11
1111
0
00
1
11
0
00
1
11
00
0000
11
1111
1 2 3 654
3
Korektnost :
Proč nastane některý z případů 1 - 4 ?
................................
Libovolný v je označen jako starý a definitivně odstraněn z S pouze v případě, že všechny
hrany s ním incidentní jsou staré.
G je 2-souvislý a proto je lib. v dosažitelné z s
................................
a tedy každý vrchol se dostane do S a je prohlášen za starý předtím, než je t odstraněn.
Zřejmě STN(s) = 1, STN(t) = n a {s, t} ∈ E.
Vrchol u = s, t jde poprve do S jako vnitřní vrchol nějaké cesty (v, u1, . . . , ui = u, . . . , w).
Přitom w je starý, neboť
................................
a w je stále v S, neboť jsme objevili novou hranu, která
................................
V zásobníku je tedy v jistém okamžiku u nad w a pod v.
Konečně si uvědomíme, že je-li někdy x nad y, je STN ............
Proč ?
................................
Jaká je složitost našeho algoritmu ? Zdůvodněte.
................................
4
2. Obchodní cestující.
Obchodní cestující Kliment Stíhačka má zítra ráno v plánu několik obchodních jednání
po České i Slovenské republice. Bydlí v Českých Budějovicích a má navštívit Brno, Cheb,
Liberec, Nitru a Žilinu, v libovolném pořadí. Chtěl by mít služební cestu co nejkratší, ale
vybrat takovou je (NP-)těžké a na to do rána nemá čas. Můžete mu však pomoci následujícím
2-aproximativním algoritmem.
Uvažujme úplný neorientovaný graf s vrcholy tvořenými výše jmenovanými městy a váhami
hran danými vzdáleností měst v kilometrech:
Brno Č. B. Cheb Liberec Nitra
Žilina 203 381 550 379 142
Nitra 174 339 541 406
Liberec 235 236 246
Cheb 374 230
Č. B. 182
1. Najděte nejlacinější kostru T tohoto grafu.
2. Zdvojte v T každou hranu a nakreslete takto vznilký obrazec jedním tahem tak, abyste
začali i skončili ve vrcholu České Budějovice.
3. Vypište vrcholy v pořadí, v jakém jste je poprvé potkali při kreslení. To bude plán
cesty pro Klimenta.
Ve druhém kroce máte možnost volby, jak obrazec nakreslíte. Proveďte kroky 2 a 3 pro
jinou volbu nakreslení než poprvé. Určete, která z výsledných cest je kratší.
Bodování:
Nalezení minimální kosty: 12 bodů maximálně.
Vypsání cest: 7+7 bodů maximálně.
Určení kratší z nich: 4 bodů.
Cheb
Liberec
České Budějovice
Brno
Nitra
Žilina
5