Drsná matematika III -- 11. přednáška
Toky v sítích a hry
Masarykova univerzita
Fakulta informatiky
9. 12. 2008
Obsah přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Kde je dobré číst?
Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní
matematiky, Univerzita Karlova v Praze, Karolinum, Praha,
2000, 377 s.
Petr Hliněný, Teorie grafů, studijní materiály,
http://www.fi.muni.cz/~hlineny/Vyuka/GT/
Bill Cherowitzo, Applied Graph Therory, Lecture Notes,
http://www-
math.cudenver.edu/~wcherowi/courses/m4408/m4408f.html
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Další skupina aplikací jazyka teorie grafů se týká přesunu nějakého
měřitelného materiálu v pevně zadané síti. Vrcholy v orientovaném
grafu představují body, mezi kterými lze podél hran přenášet
předem známá množství, která jsou zadána formou ohodnocení
hran. Některé vybrané vrcholy představují zdroj sítě), jiné výstup
ze sítě. Podle analogie potrubní sítě pro přenos kapaliny říkáme
výstupním vrcholům stok sítě). Síť je tedy pro nás orientovaný
graf s ohodnocenými hranami a vybranými vrcholy, kterým říkáme
zdroje a stoky.
Je zřejmé, že se můžeme bez újmy na obecnosti omezit na
orientované grafy s jedním zdrojem a jedním stokem. V obecném
případě totiž vždy můžeme přidat jeden stok a jeden zdroj navíc a
spojit je vhodně orientovanými hranami s všemi zadanými zdroji a
stoky tak, že ohodnocení přidaných hran bude zároveň zadávat
maximální kapacity jednotlivých zdrojů a stoků. Situace je
naznačena na obrázku, kde černými vrcholy nalevo jsou zobrazeny
všechny zadané zdroje, zatímco černé vrcholy napravo jsou všechny
zadané stoky. Nalevo je jeden přidaný (virtuální) zdroj jako bílý
vrchol a napravo jeden stok. Označení hran není v obrázku
uvedeno.
Definition
Síť je orientovaný graf G = (V , E) s vybraným jedním vrcholem z
nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok,
spolu s nezáporným ohodnocením hran w : E  R. Tokem v síti
S = (V , E, z, s, w) rozumíme ohodnocení hran f : E  R takové,
že součet hodnot u vstupních hran u každého vrcholu v, kromě
zdroje a stoku, je stejný jako součet u výstupních hran z téhož
vrcholu, tj.
eIN(v)
f (e) =
eOUT(v)
f (e).
Velikost toku f je dána celkovou balancí hodnot u zdroje
.
Definition
Síť je orientovaný graf G = (V , E) s vybraným jedním vrcholem z
nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok,
spolu s nezáporným ohodnocením hran w : E  R. Tokem v síti
S = (V , E, z, s, w) rozumíme ohodnocení hran f : E  R takové,
že součet hodnot u vstupních hran u každého vrcholu v, kromě
zdroje a stoku, je stejný jako součet u výstupních hran z téhož
vrcholu, tj.
eIN(v)
f (e) =
eOUT(v)
f (e).
Velikost toku f je dána celkovou balancí hodnot u zdroje
.
Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst
jako hodnotu
|f | =
eIN(s)
f (e) -
eOUT(v)
f (e).
Na obrázku máme nakreslenu jednoduchou síť se zvýrazněným
bílým zdrojem a černým stokem. Součtem maximálních kapacit
hran vstupujících do stoku vidíme, že maximální možný tok v této
síti je 5.
4
0011
0011
0
0
1
1
0
0
1
1
0011
0011
00110011
0011
2
3
2
5
3
3
2
2
1
3
2 1
2
0
0
1
1
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Naší úlohou bude pro zadanou síť na grafu G určit maximální
možný tok.
Definition
Řezem v síti S = (V , E, z, s, w) rozumíme takovou množinu hran
C  E, že po jejím odebrání nebude v grafu G = (V , E \ C) žádná
cesta z z do s. Číslo
|C| =
eC
w(e)
nazýváme velikost řezu C.
Evidentně platí, že nikdy nemůžeme najít větší tok, než je hodnota
kteréhokoliv z řezů. Na dalším obrázku máme zobrazen tok sítí s
hodnotou 5 a čárkovanými lomenými čarami jsou naznačeny řezy o
hodnotách 12, 8 a 5.
2/3
0011
0011
0011 0011
0011
0011
0
0
1
1
0
0
1
1
0011
2/2
1/3
1/2
0/2
1/2 1/1
0/2
1/3
2/2
2/4
1/3
2/5
1/1
0
0
1
1
Sestavíme funkční algoritmus, který pomocí postupných konstrukcí
vhodných cest najde řez s minimální možnou hodnotou a zároveň
najde tok, který tuto hodnotu realizuje. Tím dokážeme následující
větu:
Theorem
Maximální velikost toku v dané síti S = (V , E, z, s, w) je rovna
minimální velikosti řezu v této síti.
Myšlenka algoritmu ­ prohledáváme cesty mezi uzly grafu a
snažíme se je ,,nasytit co největším tokem. Zavedeme si za títo
účelem terminologii. O neorientované cestě v síti
S = (V , E, z, s, w) z vrcholu v do vrcholu w řekneme, že je
nenasycená, jestliže pro všechny hrany této cesty orientované ve
směru z v do w platí f (e) < w(e) a f (e) > 0 pro hrany
orientované opačně. Za rezervu kapacity hrany e pak označujeme
číslo w(e) - f (e) pro případ hrany orientované ve směru z v do w
a číslo f (e) při orientaci opačné. Pro zvolenou cestu bereme za
rezervu kapacity minimální rezervu kapacity z jejích hran.
Fordův-Fullkersonův algoritmus
Vstupem je síť S = (V , E, z, s, w) a výstupem maximální možný
tok f : E  R.
Iniciace: zadáme f (e) = 0 pro všechny hrany e  E a
prohledáváním do šířky z vrcholu z najdeme množinu vrcholů
U  V , do kterých existuje nenasycená cesta;.
Hlavní cyklus: Dokud s  U opakujeme
zvolíme nenasycenou cestu P ze zdroje z do s a zvětšíme tok f
u všech hran této cesty o její minimální rezervu
obnovíme U.
na výstup dáme maximální tok f a minimální řez C tvořený
všemi hranami vycházejícími z U a končícími v doplňku V \ U.
Důkaz správnosti algoritmu
Jak jsme viděli, velikost každého toku je nejvýše rovna hodnotě
kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení
algoritmu jsme vygenerovali řez i tok se stejnou hodnotou.
Algoritmus se zastaví při prvním případu, kdy neexistuje
nenasycená cesta ze zdroje z do stoku s. To znamená, že U
neobsahuje s a pro všechny hrany e z U do zbytku je f (e) = w(e),
jinak bychom museli koncový vrchol e přidat k U.
Důkaz správnosti algoritmu
Jak jsme viděli, velikost každého toku je nejvýše rovna hodnotě
kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení
algoritmu jsme vygenerovali řez i tok se stejnou hodnotou.
Algoritmus se zastaví při prvním případu, kdy neexistuje
nenasycená cesta ze zdroje z do stoku s. To znamená, že U
neobsahuje s a pro všechny hrany e z U do zbytku je f (e) = w(e),
jinak bychom museli koncový vrchol e přidat k U.
Zároveň ze stejného důvodu všechny hrany e, které začínají v
komplementu V \ U a končí v U musí mít tok f (e) = 0.
Pro velikost toku celé sítě jistě platí
|f | =
hrany z U do V \ U
f (e) hrany
z V \ U do U
f (e).
Tento výraz je ovšem v okamžiku zastavení roven
hrany z U do V \ U
f (e) =
hrany z U do V \ U
w(e) = |C|,
což jsme chtěli dokázat.
Pro velikost toku celé sítě jistě platí
|f | =
hrany z U do V \ U
f (e) hrany
z V \ U do U
f (e).
Tento výraz je ovšem v okamžiku zastavení roven
hrany z U do V \ U
f (e) =
hrany z U do V \ U
w(e) = |C|,
což jsme chtěli dokázat.
Zbývá ovšem ukázat, že algoritmus skutečně zastaví.
Pro velikost toku celé sítě jistě platí
|f | =
hrany z U do V \ U
f (e) hrany
z V \ U do U
f (e).
Tento výraz je ovšem v okamžiku zastavení roven
hrany z U do V \ U
f (e) =
hrany z U do V \ U
w(e) = |C|,
což jsme chtěli dokázat.
Zbývá ovšem ukázat, že algoritmus skutečně zastaví.
Všimněme si, že pro celočíslené hodnoty ohodnocení hran získáme
také celočíselný tok.
0/3
0011
0011
0011 0011
0011
0011
0
0
1
1
0
0
1
1
0011
0/2
0/2
0/2 1/1
0/2
0/3
0/2
2/4
0/3
1/5
0/1
2/3
2/2
0011
0/3
0011
0011
0011 0011
0011
0011
0
0
1
1
0011
0
0
1
1
0/2
0/2
2/2 1/1
0/2
2/3
2/2
2/4
0/3
3/5
0/1
2/3
2/2
0011
Chod algoritmu je ilustrován na obrázku. Vlevo jsou vybaveny dvě
nejkratší nenasycené cesty ze zdroje do stoku (horní má dvě hrany,
spodní tři). Jsou vyznačeny červeně. Napravo je pak nasycena další
cesta v pořadí a je vyznačena modře. Je nyní zjevné, že nemůže
existovat další nenasycená cesta ze zdroje do stoku. Proto
algoritmus v tomto okamžiku skončí.
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Můžeme požadovat dodržení maximální kapacity průtoku přes
jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale
také minimální toky přes jednotlivé hrany či vrcholy.
Můžeme požadovat dodržení maximální kapacity průtoku přes
jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale
také minimální toky přes jednotlivé hrany či vrcholy.
Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a
dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme
právě jednou hranou s příslušnou kapacitou.
Můžeme požadovat dodržení maximální kapacity průtoku přes
jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale
také minimální toky přes jednotlivé hrany či vrcholy.
Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a
dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme
právě jednou hranou s příslušnou kapacitou.
Omezení minimálními průtoky lze zahrnout do iniciace našeho
algoritmu. Je ovšem zapotřebí otestovat, jestli takový tok vůbec
existuje.
Můžeme požadovat dodržení maximální kapacity průtoku přes
jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale
také minimální toky přes jednotlivé hrany či vrcholy.
Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a
dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme
právě jednou hranou s příslušnou kapacitou.
Omezení minimálními průtoky lze zahrnout do iniciace našeho
algoritmu. Je ovšem zapotřebí otestovat, jestli takový tok vůbec
existuje.
V literatuře lze najít řadu dalších nuancí, nebudeme se jim zde
věnovat.
Hezkým využitím toků v sítí je řešení úlohy bipartitního párování.
Úlohou je v bipartitním grafu najít maximální podmnožinu hran
takovou, aby žádné dvě hrany nesdílely vrchol.
Jde o abstraktní variantu docela obvyklé úlohy ­ třeba spárování
kluků a holek k tanci v tanečních, kdybychom měli předem známé
možnosti, ze kterých vybíráme.
Tento problém docela snadno převedeme na hledání maximálního
toku. Přidáme si uměle navíc ke grafu zdroj, který propojíme
hranami jdoucími do všech vrcholů v jedné skupině v bipartitním
grafu, zatímco ze všech vrcholů ve druhé skupině vedeme hranu do
přidanéhoho stoku. Všechny hrany opatříme maximální kapacitou 1
a hledáme maximální tok. Za páry pak bereme hrany s nenulovým
tokem.
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
,,Nim . Na stole leží hromádka n sirek. Dva hráči střídavě odebírají
jednu až pět sirek. Kdo nemá co vzít, prohrál.
,,Nim . Na stole leží hromádka n sirek. Dva hráči střídavě odebírají
jednu až pět sirek. Kdo nemá co vzít, prohrál.
Existuje za nějakého hráče vyhrávající strategie?
Kombinatorické hry
.
Hra dvou hráčů.
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Pro každou pozici a každého hráče je popsána množina
přípustných tahů, tj. množina pozic, do kterých se může hra
jedním tahem dostat.
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Pro každou pozici a každého hráče je popsána množina
přípustných tahů, tj. množina pozic, do kterých se může hra
jedním tahem dostat.
Hráči se střídají na tahu.
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Pro každou pozici a každého hráče je popsána množina
přípustných tahů, tj. množina pozic, do kterých se může hra
jedním tahem dostat.
Hráči se střídají na tahu.
Hra končí v okamžiku, kdy hráč na tahu nemůže táhnout
(nemá k dispozici žádný přípustný tah). Hra podle normálních
pravidel končí prohrou zmíněného hráče. Pokud ten, kdo
nemůže táhnout vyhrává, hovoříme o hře ,,na žebráka .
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Pro každou pozici a každého hráče je popsána množina
přípustných tahů, tj. množina pozic, do kterých se může hra
jedním tahem dostat.
Hráči se střídají na tahu.
Hra končí v okamžiku, kdy hráč na tahu nemůže táhnout
(nemá k dispozici žádný přípustný tah). Hra podle normálních
pravidel končí prohrou zmíněného hráče. Pokud ten, kdo
nemůže táhnout vyhrává, hovoříme o hře ,,na žebráka .
Hra končí po konečném počtu tahů.
Kombinatorické hry
.
Hra dvou hráčů.
Existuje množina (většinou konečná) všech možných pozic ve
hře.
Pro každou pozici a každého hráče je popsána množina
přípustných tahů, tj. množina pozic, do kterých se může hra
jedním tahem dostat.
Hráči se střídají na tahu.
Hra končí v okamžiku, kdy hráč na tahu nemůže táhnout
(nemá k dispozici žádný přípustný tah). Hra podle normálních
pravidel končí prohrou zmíněného hráče. Pokud ten, kdo
nemůže táhnout vyhrává, hovoříme o hře ,,na žebráka .
Hra končí po konečném počtu tahů.
Hru nazýváme nestrannou, pokud množina přípustných tahů v
dané pozici nezávisí na tom, který hráč je na tahu. V opačném
případě hovoříme o partizánské hře.
Graf nestranné hry
Je orientovaný graf, jehož uzly jsou tvořeny všemi různými
pozicemi, hrany odpovídají přípustným tahům.
Graf nestranné hry
Je orientovaný graf, jehož uzly jsou tvořeny všemi různými
pozicemi, hrany odpovídají přípustným tahům.
Graf kombinatorické nestranné hry je acyklický.
Graf nestranné hry
Je orientovaný graf, jehož uzly jsou tvořeny všemi různými
pozicemi, hrany odpovídají přípustným tahům.
Graf kombinatorické nestranné hry je acyklický.
P a N pozice hry.
Plán přednášky
Literatura
Toky v sítích
Problém maximálního toku v síti
Další aplikace
Hry
Sprague­Grundyho teorie
Nechť hra je representována acyklickým orientovaným grafem
(V , H). Spragueova-Grundyova funkce je funkce g : V  N0,
kterou definujeme následovně:
g(v) = 0 pro všechny listy
Nechť hra je representována acyklickým orientovaným grafem
(V , H). Spragueova-Grundyova funkce je funkce g : V  N0,
kterou definujeme následovně:
g(v) = 0 pro všechny listy
pro v  V takový, že jsou ohodnoceni všichni jeho následníci
definujeme
g(v) = min{a  N0|neexistuje hrana (v, w), kde g(w) = a}
Nechť hra je representována acyklickým orientovaným grafem
(V , H). Spragueova-Grundyova funkce je funkce g : V  N0,
kterou definujeme následovně:
g(v) = 0 pro všechny listy
pro v  V takový, že jsou ohodnoceni všichni jeho následníci
definujeme
g(v) = min{a  N0|neexistuje hrana (v, w), kde g(w) = a}
Theorem
Pozice hry odpovídající uzlu v v grafu hry je P právě když
g(v) = 0.
Součtem her representovaných grafy G1 = (V1, H1) a
G2 = (V2, H2) rozumíme hru s grafem G = (V , H),
kde V = V1 × V2,
a H = {(v1v2, w1v2)|(v1, w1)  H1}  {(v1v2, v2w2)|(v2, w2)  H2}.
Součtem her representovaných grafy G1 = (V1, H1) a
G2 = (V2, H2) rozumíme hru s grafem G = (V , H),
kde V = V1 × V2,
a H = {(v1v2, w1v2)|(v1, w1)  H1}  {(v1v2, v2w2)|(v2, w2)  H2}.
Theorem
Pro orientované acyklické grafy G1 = (V1, E1), G2 = (V2, E2) a
G = (V , E) = G1 + G2 a jejich Spragueovy­Grundyovy funkce g1,
g2 a g platí:
g(v1v2) = g(v1)  g(v2)
Theorem
Každá nestranná hra je ekvivalentní zobecněné Nim hře.