Santa Claus — 2022-11-10 01:22 (56 days ago) — edit — reply
1. Protipříklad: viz obrázek. Nejkrátší zlepšení je v první iteraci cesta délky tři přes "střed" diamantu, ale toto zablokuje jakýkoliv další tok. Maximální tok má ale velikost 2 (po obvodu diamantu).
2.
a. Ne nutně nejkratší cesta.
i) Orákulum poradí i kapacitu.
Každý tok můžeme rozložit dva podtoky: jeden ve tvaru cesty a druhý, který využívá o jednu hranu méně, a sice následovně:
Pro hranu s nejmenším průtokem nalezneme na toku cestu ze zdroje do stoku, na kterém hrana leží. (Nalezneme cestu do počátku hrany ze zdroje a pak také z konce hrany do stoku).
Původní tok můžeme rozdělit podtok, který je tato cesta s velikostí toku rovnému původní velikosti toku na dané hraně - to můžeme udělat, protože původní hrana měla nejmenší průtok, průtoky ostatních hran tedy nebudou vyšší než jejich průtoky v původním toku, tudíž nepřekročí kapacitu. Druhý tok vznikne odečtením průtoků na prvním podtoku od původního toku. Žádná hrana nebude mít záporný průtok - odečetli jsme nejvýše minimum průtoků. Kirchhoffovy zákonu zůstanou evidentně zachovány.
Takto můžeme tok na konečném počtu hran rozložit na konečný počet podtoků ve tvaru cest a nulový tok. (Induktivně, pokud není tok ve tvaru cesty, ubereme hranu, má konečný počet hran, takže dříve nebo později se zastavíme (nejpozději když zbyde jediná hrana - přímo ze zdroje do stoku))
Toto nám poskytuje jednotlivé instrukce orákula
ii) Vždy pošleme plnou kapacitu
TBD
b. Nejkratší cesta
Neplatí, pro protipříklad viz stejný obrázek jako u 1. Orákulum poradí cestu, která nám síť ihned zablokuje.
3.
Hrany s celočíselnou kapacitou omezenou konstantou lze rozdělit na multihrany s jednotkovou kapacitou. Každou hranu rozdělíme maximálně na konstantně nových hran, celkový počet hran tedy bude stále $O(m)$.
Pak máme multigraf s jednotkovými hranami. Hledání toku na multigrafu je stejné jako na jednoduchém grafu.
Navíc na grafu s jednotkovými hranami rychleji nalezneme blokující tok, použijeme úpravu na toky s jednotkovými kapacitami (z přednášky/poznámek [M. Mareše]):
> Pokud síť neobsahuje cykly délky 2 (dvojice navzájem opačných hran), všechny rezervy jsou jen 0 nebo 1. Pokud obsahuje, mohou rezervy být i dvojky, a proto síť upravíme tak, že ke každé hraně přidáme hranu opačnou s nulovou
kapacitou a rezervu proti směru toku přiřkneme jí.
(Maximálně jich ale přidáme m.)
> Při hledání blokujícího toku tedy budou mít všechny hrany na nalezené cestě stejnou, totiž jednotkovou, rezervu, takže vždy z grafu odstraníme celou cestu.
Když máme m hran, počet zlepšení po cestách délky l bude maximálně m/l. Proto
složitost hledání blokujícího toku bude $m/l · O(l) = O(m)$.Tedy pro jednotkové
kapacity dostáváme složitost O(nm).
4. Vytvoříme následující graf:
Začneme vytvořením zdroje. Poslanci budou reprezentováni vrcholy. Do každého z nich hrana ze zdroje o kapacitě jedna. Kluby budou reprezentovány vrcholy. Do každého klubu povede hrana s kapacitou 1 z poslance, pokud je poslanec členem. Ze všech klubů povedou hrany s kapacitou dva do spotřebiče.
Úlohu pak lze převést na hledání toku, který využije kapacity hran vedoucích do stoku naplno. Stačí tedy nalézt maximální tok, žádný maximální tok nebude větší (řez podle všech hran vedoucích do stoku).
Správnost je patrná z konstrukce: žádný poslanec nebude kumulovat funkce: může z něj vést maximálně jedna využítá hrana. Jak víme, algoritmus zachová celočíselné ohodnocení. Pokud budou všechny hrany do stoku naplněny, do každého klubu vedou právě dvě naplněné hrany.
Podmínkou existence řešení je existence takového toku, pokud neexistuje, existuje minimální řez s menší kapacitou přes hrany mezi poslanci a kluby (případně i poslanci a zdrojem). Pokud takový tok existuje, máme řešení.