GRAFOVÉ ALGORITMY
2008/9 - 1. termín
1. Barvení hran
Dáme kopii algoritmu s očíslovanými řádky a použitých pojmů, něco k tomu asi dodám, asi nebudu nic vynechávat. Úkoly:
1. update mis v RECOLOR v čase O(d) : přidáme řádky xxa,... , kde bude uvedeno
u vrcholů ... bude mis nejmenší uvedená první nepoužitá barva,
u vrcholů . . . položíme . . . ,
u ostatních vrcholů hodnotu mis necháme.
2. Korektnost dokážeme indukcí vzhledem k parametru____
... = 0 : ....
indukční krok : . . .
3. Jakou větu dostáváme jako důsledek korektnosti algoritmu ? Chromatické číslo grafu Gje...
4. V jakém čase umíme implementovat RECOLOR ?
(Pomoc s datovými strukturami a linky mezi nimi).
Celková složitost je tedy ....................
5. Aplikujte algoritmus na graf a : b,c,d,e
b : a,c,e
c : a,b,d
d : a,c,e
e : a,b,d
Pořadí barev : červená, modrá, zelená, žlutá, hnědá Postupujte přísně podle abecedy. Připravím obrázky.
1 Toky
V následující síti najdete maximální tok z s do t a podejte důkaz maximality:
1
2
GRAFOVÉ ALGORITMY
2008/9 - 2. termín 1. Syntaktické kvaziuspořádání
Nechť (M, •) je monoid a nechť P C M je množina. Definujme kvaziuspořádání < na množině M vztahem
u < v -<==- ( V p, q G M ) ( pvq G P == puq G P ) .
Nechť C je nějaká množina generátorů monoidu (M, •). Uvažujme orientovaný graf G = (V, E), kde
V = M x M, E = { ((uc,vc), (u, v)) | (u, v) G V, c G C }U{ ((cu,cv), (u, v)) | (u, v) G V, c G C} .
Uvažme, že u < v -<=>- existuje (x, y)-(u, v)—cesta v G taková, že x G P, x G P. Ohodnoťme vrcholy grafu G takto
u     ,     í 0    pro u G P, v G P /(u,v) = \l jinak.
Nechť M je konečná množina, |M| = n, |C| = c. Nabízí se algoritmus pro výpočet relace <. Ze všech vrcholů
spustíme DFS. U všech navštívených vrcholů stanovíme
Jaká je složitost Vašeho algoritmu ?
Šlo by sekvenčně realizovat spustení DFS z několika vrcholů současně ? Jaké by se musely v DFS provést modifikace. Jak by to dopadlo se složitostí ?
Demonstrujte algoritmus pro
M = {1, a, b}, 1 neutrální , a, b levé nulové , C = {a, b}, P = {a} .
2 Párování
Doplňte do následujícího grafu 2 hrany tak, aby maximální párování pokrylo 18 vrcholu. Dokažte, že Vami nalezene parovaní je ve Vami doplnenem grafu maximalní. (18 bodu)
ProC pridaní žádných dvou hran nestaCilo, aby graf mel perfektní parovaní? (4
body)
Doplnte tretí hranu a najdete perfetkní parovaní. (8 bodu)
3
GRAFOVÉ ALGORITMY
2008/9 - 3. termín
1. Barvení vrcholů planárního grafu
Result 1. Pro planární graf s n > 3 je m < 3n — 6. Result 2. Každá planarní graf ma vrchol stupne < 5.
Result 3. Graf je planarní prave když nema podgraf izomorfní se "subdivision" of K5 nebo
Doplňte konstruktivní dukaž následující vety.
Veta. Každí planarní graf lže vrcholove obarvit nejvíse peti barvami.
Duíkaž. Provedeme ho indukcí vžhleme k n. Pokud n <......je tvržení žrejme.
Necht' tedy n > .....       a predpokladejme, že tvržení platí pro všechny grafy s menším
poctem vrcholu.
Case 1. Necht' existuje vrchol v stupne < 4. Podle indukčního predpokladu lže graf G \ v obarvit nejvíse 5 barvami. Jak obarvíme vrchol v ?
Case 2. Necht' vsechny vrcholy mají stupen............................. Podle................
existuje vrchol stupne...............Vybereme takoví vrchol v.
Podle................existují jeho sousedi x, y, kterí..........................................
V G \ v žtotožneme vrcholy x, y. Vžnikne graf G', ktery je opet planírní, nebot'
Podle indukcního predpokladu lže G' obarvit nejvyse 5 barvami. Jak obarvíme G \ v ?
Jak obarvíme G ?
Složitost. Zrejme vsechny operace krome odstranovaní vrcholu a jejich žtotožnovaní vežmou celkem ...................................
Odstranení vrcholu v stupne d(v) vežme O(d(v)).
Ponevadž J2v&v d(v) < ........................................podle...................................
vežmou vsechna odstraňovaní celkem.................................
O složitosti tedy rožhodují žtotožnení. Vrcholy x, y žtotožníme v case O(d(x) + d(y)). Proto je celkovía sloňžitost algoritmu ..................................
Príklad. Demonstrujte algoritmus na nasledujícím príklade. Aby byl prubeh vípoctu naprosto jednožnaňcníy je
1. Poňradí barev je ňcervenía, modría, želenaí, ňžlutía, hnňedía.
2. Poradí vrcholu je podle abecedy, i napr. vrchol {a, x} mí prednost pred vrcholem b.
3   Soustava rovnic
V následující soustavě rovnic vystupuje 8 proměnných xi,..., x8. Vaším úkolem je soustavu vyresit s pomocí grafovúch algoritmu takto:
Soustavě je prirazen orientovaný graf G s vrcholy v1,..., v8 a hranami definovanými: pro vsechna i, j G {1,..., 8} graf G obsahuje hranu (vj, v j), prúve když v soustave rovnic je rúdek tvaru x j := Exp, kde Exp je výraz obsahující promennou xj.
Ukol císlo 1 (15 bodu): spocítejte a popiste graf GSCC silne souvislúch komponent grafu G.
Ukol císlo 2 (10 bodu): usporadejte silne souvisle komponenty (tedy vrcholy grafu GSCC) topologicky.
Ukol císlo 3 (5 bodu): uvažujte postupne silne souvisle komponenty v topo-logickem usporadaní (zacínate komponentou, do níž nevedou žúdne hrany). Omezte se na podsoustavu rovnic danou vrcholy zpracovavane komponenty. Podsoustavu vyreste. Postupne takto vyreste celou soustavu rovnic. Kolik ma soustava realnych resení? Jaka to jsou?
xi := xi + 2x8 - 4
x2 := 3x7 — x4 — x2
x3 := 3x5 + 4x4 + x2 +2
x5   := 3x28
x6 := x3 — xi + x4
x7 := x2 + 3
x8 := x5 + x8 — 3
5