Toky v sítích
Otázky k zamyšlení?
► Proč při Fordově-Fulkersonově metodě hledáme cesty
v reziduálni síti? Nestačilo by nám hledat cesty v původní síti (s vynecháním plně nasycených hran)?
Toky v sítích
Otázky k zamyšlení?
► Proč při Fordově-Fulkersonově metodě hledáme cesty
v reziduálni síti? Nestačilo by nám hledat cesty v původní síti (s vynecháním plně nasycených hran)?
► Potřebujeme reziduálni síť pro Edmondsův-Karpův algoritmus (hledání hranově nejkratší cesty)?
Toky v sítích
Otázky k zamyšlení?
► Proč při Fordově-Fulkersonově metodě hledáme cesty
v reziduálni síti? Nestačilo by nám hledat cesty v původní síti (s vynecháním plně nasycených hran)?
► Potřebujeme reziduálni síť pro Edmondsův-Karpův algoritmus (hledání hranově nejkratší cesty)?
► Potřebujeme reziduálni síť pro algoritmus nejširších cest?
Toky v sítích - aplikace
Pokrytí cykly
Máme orientovaný graf G = (\/, E) a chceme najít takovou množinu vrcholově disjunktních cyklů, která pokrývá všechny vrcholy grafu (nebo odpovědět, že takové pokrytí neexistuje).
► Jak převést tento problém na problém toku v síti?
Toky v sítích - aplikace
Pokrytí cykly
Máme orientovaný graf G = (\/, E) a chceme najít takovou množinu vrcholově disjunktních cyklů, která pokrývá všechny vrcholy grafu (nebo odpovědět, že takové pokrytí neexistuje).
► Jak převést tento problém na problém toku v síti?
► Nápověda: Všimněte si, že v každém pokrytí cykly má každý vrchol právě jednu vstupní a právě jednu výstupní hranu.
Toky v sítích - aplikace
Umisťování kamenů na mřížku
Máme čtvercovou mřížku n x n, na níž jsou čtverce označeny buď bílou nebo šedou barvou (ne nutně pravidelně). Zajímá nás, jestli je možno na mřížku umístit kameny tak, že:
1. každý kámen je na bílém čtverci,
2. v každém řádku je právě jeden kámen a
3. v každém sloupci je právě jeden kámen.
Toky v sítích - aplikace
Výběr projektů
Nejmenovaná společnost se má rozhodnout, kterým projektům se bude věnovat. Některé projekty jsou ziskové, jiné jsou ztrátové, nicméně mohou na sobě záviset. Společnost chce samozřejmě maximalizovat svůj zisk.
► Jak formálně definujeme tento problém?
► Jak převedeme tento problém na problém toků?
Toky v sítích - aplikace
Eliminace týmů v baseballu
Máme baseballové týmy v lize, někdy v průběhu sezóny, a zajímá nás, zda má náš oblíbený tým ještě šanci vyhrát ligu nebo jestli už byl matematicky eliminován. Příklad takové situace je níže:
Team	Won-Lost	Left	NY	BAL	BOS	TOR	DET
New York	75-59	28		3	8	7	3
Baltimore	71-63	28	3		2	7	4
Boston	69-66	27	8	2		0	0
Toronto	63-72	27	7	7	0		0
Detroit	49-86	27	3	4	0	0	
► Má Detroit šanci vyhrát ligu?
Toky v sítích - aplikace
Eliminace týmů v baseballu
Máme baseballové týmy v lize, někdy v průběhu sezóny, a zajímá nás, zda má náš oblíbený tým ještě šanci vyhrát ligu nebo jestli už byl matematicky eliminován. Příklad takové situace je níže:
Team	Won-Lost	Left	NY	BAL	BOS	TOR	DET
New York	75-59	28		3	8	7	3
Baltimore	71-63	28	3		2	7	4
Boston	69-66	27	8	2		0	0
Toronto	63-72	27	7	7	0		0
Detroit	49-86	27	3	4	0	0	
► Má Detroit šanci vyhrát ligu?
► Jak můžeme tento problém vyřešit pomocí toků?
Toky v sítích - aplikace
Plánování letecké dopravy
Máme seznam leteckých linek (místo a čas odletu, místo a čas příletu) a zajímá nás, zda můžeme všechny tyto linky obsloužit s použitím daného počtu letadel. Letadla mohou potřebovat nějaký čas na letišti pro údržbu, ale také mohou přelétávat mezi letišti. Od těchto informací abstrahujeme a předpokládáme místo toho, že máme informaci, které linky jsou dosažitelné z jiných linek. (Linka y je dosažitelná z linky x, pokud je možné, aby jedno letadlo letělo nejdříve linku x a potom linku y.) Příklad:
1. Boston (6.00)     Washington DC (7.00)
2. Philadelphia (7.00)     Pittsburgh (8.00)
3. Washington DC (8.00)     Los Angeles (11.00)
4. Philadelphia (11.00)     San Francisco (14.00)
5. San Francisco (14.15) —>> Seattle (15.15)
6. Las Vegas (17.00)     Seattle (18.00)
► Jak zformulujeme tento problém pomocí toků nebo některých jejich variant?
Toky v sítích - aplikace
Zaokrouhlování matice
Máme matici n x m, která obsahuje nezáporná reálná čísla. Chceme zaokrouhlit všechna čísla v matici (nahradit je buď horní nebo dolní celou částí) tak, aby součty řádků a sloupců zůstaly stejné.
1,2   3,4   2,4\       /l   4 2\ 3,9   4,0   2,1   ^   4   4 2 7,9   1,6   0,5/      \8   1 1/
► Jak tento problém převedeme na problém toků?
Toky v sítích - aplikace
Zaokrouhlování matice
Máme matici n x m, která obsahuje nezáporná reálná čísla. Chceme zaokrouhlit všechna čísla v matici (nahradit je buď horní nebo dolní celou částí) tak, aby součty řádků a sloupců zůstaly stejné.
1,2   3,4   2,4\       /l   4 2\ 3,9   4,0   2,1   ^   4   4 2 7,9   1,6   0,5/      \8   1 1/
► Jak tento problém převedeme na problém toků?
► V reálných aplikacích (prezentace dat) nemusí být součty řádků a sloupců celočíselné. Jak bychom řešili obecnější problém, kde je cílem zaokrouhlit matici tak, aby i součty řádků a sloupců byly zaokrouhlené?