VYVRCHOLENÍ: Teorie záporných cyklů / 5 výroků [FOTO]
Slot 2 nemusí být vždy počítací — místo modelovací úlohy se objevuje i čistá teorie nejkratších cest. Dochovaly se dva formáty: čtyřdílná úloha Handling negative cycles in the graph (zkouška KO 21. 06. 2021, úloha T01 níže — třetí a poslední FOTO checkpoint kapitoly) a úloha „5 výroků“ (dokaž, nebo vyvrať protipříkladem; úloha T02). Dobrá zpráva: žádný nový obsah dnes nepotřebuješ — všechny odpovědi už máš z minulých lekcí. Nová je jen disciplína skládání: poznat, na kterou „páku“ výrok tlačí, a vytáhnout správný argument.
Důkaz, nebo protipříklad?
Zkus sám: výrok tvrdí, že něco platí vždy („always“, „any two vertices“). Co stačí k jeho vyvrácení — a co je potřeba k jeho potvrzení?
Asymetrie je tvůj přítel: k vyvrácení stačí jediný protipříklad, a klidně miniaturní — 3–4 vrcholy bohatě stačí. K potvrzení naopak nestačí žádné množství příkladů: potřebuješ obecný argument pokrývající všechny instance (typicky rozpis ceny cesty, např. $c'(P) = c(P) + h\,|P|$ z [L2.15], nebo odvolání na korektní algoritmus se splněnými vstupními podmínkami). Proto se vyplatí nejdřív chvíli hledat protipříklad — když se ani po systematickém pokusu nenajde, bývá to nápověda, že výrok platí a má krátký důkaz.
Zkus sám: sestav si checklist — jaké „páky“ zkouškové výroky o nejkratších cestách nejčastěji lámou? (Projdi v hlavě lekce K2.)
Pět otázek, které si polož u každého výroku:
- Je nejkratší cesta vůbec definovaná? Záporný cyklus → sled ≠ cesta, úloha NP-těžká [L2.1].
- Splňuje algoritmus vstupní podmínky? Dijkstra chce nezáporné váhy [L2.4], Bellman-Ford „jen“ žádný záporný cyklus [L2.12].
- Mění transformace vah pořadí cest? Posun $+h$ ano ($c'(P) = c(P) + h\,|P|$), násobení $k > 0$ ne [L2.15].
- Nesměšuje výrok cenu a počet hran? To jsou dvě různá kritéria [L2.16].
- Jde o nejdelší cestu? Pak je jedinou hranicí kladný cyklus: bez něj snadná (×(−1)), s ním NP-těžká [L2.17].
- Malý graf: 3–4 vrcholy, dvě konkurenční $s \to t$ cesty — jedna přímá hrana, jedna o více hranách s těsně lepší cenou.
- Silná souvislost (když ji zadání chce): přidej zpáteční hranu $t \to s$ s velkou kladnou váhou — souvislost zajistí a nic nepokazí.
- Kontrola definovanosti: v protipříkladu nesmí omylem vzniknout záporný cyklus (pokud ho tam nechceš), jinak vyvracíš výrok rozbitou instancí [L2.1].
- Dopočítej obě strany: napiš ceny obou cest před úpravou i po ní — protipříklad bez čísel není protipříklad.
Detekce ≠ řešení
Zkus sám: Bellman-Ford umí záporný cyklus detekovat [L2.12]. Plyne z toho, že umí najít nejkratší cestu v grafu, který záporný cyklus obsahuje?
Ne — a přesně tahle záměna je nejčastější chyba celé úlohy. Jsou to dva různé problémy:
- Detekce („je v grafu záporný cyklus?“) je polynomiální: $n-1$ relaxačních průchodů Bellman-Forda a pak jeden kontrolní průchod přes všechny hrany — pokud kdekoliv ještě platí $l(t) > l(v) + c(v,t)$, graf záporný cyklus má (slide 34). Celkem $\mathcal{O}(nm)$.
- Řešení („najdi nejkratší cestu v grafu se záporným cyklem“) je NP-těžké [L2.1]: algoritmy K2 nerozlišují cestu od sledu a nejkratší sled tu neexistuje. Bellman-Ford problém ohlásí — ale nevyřeší.
Ukažme si obojí na jednom silně souvislém grafu $G^\star$ (instance vlastní) se záporným cyklem $a \rightleftarrows b$ o váze $-2 + 1 = -1$:
Detekce v akci — rychlá repríza běhu z [L2.12], tentokrát na $G^\star$ (pořadí hran $(s,a), (a,b), (b,a), (b,t), (t,s)$):
Všimni si bonusu silné souvislosti: z libovolného startu $s$ je dosažitelné všechno, takže trik s pomocným vrcholem $s'$ a nulovými hranami [L2.12] tady není potřeba — to se hodí do odpovědi na první podotázku T01.
Arzenál K2 na jedné stránce
Mapa „téma výroku → hotový argument“. U zkoušky ji budeš mít v hlavě; teď slouží jako rozcestník k úlohám, kde je každý argument vypracovaný:
| Téma výroku / podotázky | Verdikt | Kde je důkaz / protipříklad |
|---|---|---|
| posun všech vah o $+h$ zachová SP | NEPLATÍ — $c'(P) = c(P) + h\,|P|$ | [L2.15] T01 |
| násobení všech vah $k > 0$ zachová SP | PLATÍ — $c'(P) = k \cdot c(P)$, délka $\times k$ | [L2.15] T02 |
| Dijkstra najde SP s nejmenším počtem hran | NEPLATÍ — cena ≠ počet hran | [L2.16] T01 |
| nejmenší počet hran chci doopravdy | všem hranám váhu $1$ → BFS | [L2.16] takeaways |
| nejdelší cesta, kladné váhy, obecný graf | NP-těžká (Hamiltonovská cesta) | [L2.17] T01 |
| nejdelší cesta, všechny váhy záporné | snadná — ×(−1) + Dijkstra | [L2.17] takeaways, T02 |
| detekce záporného cyklu | polynomiální — Bellman-Ford + kontrolní průchod, $\mathcal{O}(nm)$ | [L2.12] |
| SP v grafu se záporným cyklem | NP-těžká | [L2.1] |
Pozor: nebezpečné polopravdy- „Bellman-Ford si se záporným cyklem poradí.“ Poradí si s detekcí — najít nejkratší cestu v grafu se záporným cyklem neumí nikdo polynomiálně (za $P \ne NP$): úloha je NP-těžká [L2.1].
- „Rozdíly vah dvojic hran se posunem $+h$ nezmění, takže se SP zachová.“ Chybný argument z dochované zkouškové odpovědi — o vítězi rozhodují součty podél celých cest a ty rostou o $h \cdot |P|$, tedy podle počtu hran [L2.15].
- Protipříklad mimo zadání. Když zadání říká „strongly connected“, tvůj protipříklad musí být silně souvislý (zpáteční hrana); když vyvracíš zachování SP, musí mít obě instance SP definované. Protipříklad porušující zadání hodnotitel škrtne.
Key takeaways — L2.18- Každý výrok rozhodni důkazem, nebo protipříkladem: vyvrácení = jeden malý graf (3–4 vrcholy, dvě konkurenční cesty, dopočítaná čísla); potvrzení = obecný argument (rozpis ceny cesty, korektní algoritmus se splněnými vstupy).
- Checklist pák: ① definovanost (záporný cyklus? [L2.1]), ② vstupní podmínky algoritmu (Dijkstra [L2.4]), ③ transformace vah ($+h$ vs. $\times k$ [L2.15]), ④ cena ≠ počet hran [L2.16], ⑤ nejdelší cesta = otázka na kladný cyklus [L2.17].
- Detekce ≠ řešení: záporný cyklus se detekuje polynomiálně (Bellman-Ford + kontrolní průchod, $\mathcal{O}(nm)$ [L2.12]), ale nejkratší cesta v grafu se záporným cyklem je NP-těžká.
- Silná souvislost v zadání = bonus (vše dosažitelné, $s'$-trik netřeba) i povinnost (protipříklad ji musí splnit — zpáteční hrana).
- Tohle je FOTO checkpoint: celou čtyřdílnou úlohu T01 napiš na papír a pošli ke kontrole.
FOTO checkpoint
zdroj: zkouška KO_21_06_2021 (historicke_zadani_testu.md ř. 1305–1312, shodně testu_2 ř. 914–921), EN 1:1; dochovaná studentská odpověď je u podotázek 1+4 v zásadě správná, u 2+3 chybná — řešení vlastní s vyznačením rozdílů
Consider having a strongly connected graph $G$, with a set of edges $E$, and with arbitrary edge weights from $\mathbb{Z}$; $c(e)$ denotes the weight of edge $e$. (For the following questions, consider $P \neq NP$.)
- How would you check if $G$ contains a negative cycle in a polynomial time?
- Is finding the shortest path between any two vertices in $G$ always solvable in polynomial time?
- Consider an integer $h$, $h \geq |\min_{e \in E} c(e)|$. Consider graph $G'$, which is identical to $G$, but every edge weight is increased by $h$. Does the shortest path between any two vertices in $G'$ correspond to the shortest path between the same vertices in $G$? If yes, explain why; if no, give a counterexample of graphs $G$ and $G'$.
- Assuming that $c(e) < 0, \forall e \in E(G)$, can you always find the longest path between any two vertices in $G$ in polynomial time? If yes, explain how to do it; if no, briefly describe why it is not possible.
FOTO checkpointTuhle úlohu vyřeš celou NA PAPÍR — všechny čtyři podotázky, od prázdného listu, bez koukání do lekce, orientačně do 15–20 minut (přesný limit zkoušky doložený není, ale při 6 úlohách na test víc mít nebudeš). U podotázky 3 nakresli konkrétní dvojici grafů $G$, $G'$ s čísly a dopočítej obě cesty v obou grafech. Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.
a) Co je v zadání?
Silně souvislý orientovaný graf s libovolnými celočíselnými vahami (i zápornými) a čtyři podotázky: ① jak polynomiálně detekovat záporný cyklus, ② zda je nejkratší cesta vždy polynomiálně řešitelná, ③ zda posun všech vah o $+h$ (zvolené tak, aby váhy vyšly nezáporné) zachová nejkratší cesty, ④ zda při všech záporných vahách umíme polynomiálně nejdelší cestu. Závorka „consider $P \ne NP$“ prozrazuje, že aspoň jedna odpověď bude „ne, je to NP-těžké“.
b) Co k tomu budeme potřebovat?
- [L2.12] Bellman-Ford + detekce záporného cyklu — podotázka 1.
- [L2.1] Záporné váhy ano, záporné cykly ne — podotázka 2 (NP-těžkost se záporným cyklem).
- [L2.15] T01 — podotázka 3 je s ní doslova totožná (hotový protipříklad).
- [L2.17] Nejdelší cesta — podotázka 4 (×(−1) a hranice kladného cyklu); Dijkstra [L2.4].
c) Jak nad úlohou uvažovat?
Každá podotázka je jedna lekce — poznej kterou. ① je čistá reprodukce detekce; využij silnou souvislost (vše je dosažitelné → $s'$-trik netřeba). ② pozor na slovo always: váhy jsou libovolné ze $\mathbb{Z}$, takže graf může obsahovat záporný cyklus — a co pak? ③ neptej se „změní se délky?“, ale „změní se vítěz?“ — rozepiš $c'(P)$ a postav mini protipříklad (nezapomeň: silně souvislý, bez záporného cyklu). ④ aplikuj checklist nejdelší cesty: má graf po ×(−1) záporný cyklus? Dochovaná studentská odpověď je dobrý trenažér: u ② a ③ napsala „yes“ a hodnotitel ji červeně opravoval („What about negative cycles?“) — zkus říct přesně, kde se spletla.
d) Úplné řešení (vlastní; srovnání s dochovanou odpovědí vyznačeno)
① Detekce záporného cyklu — Bellman-Ford + kontrolní průchod, $\mathcal{O}(nm)$. Zvol libovolný startovní vrchol $s$; díky silné souvislosti je z něj dosažitelný celý graf (pomocný vrchol $s'$ s nulovými hranami [L2.12] není potřeba). Proveď $n-1$ průchodů relaxací všech hran. Pak proveď jeden kontrolní průchod: existuje-li hrana $(v,t)$ s $l(t) > l(v) + c(v,t)$, graf obsahuje záporný cyklus; jinak neobsahuje (slide 34). Celkem $\mathcal{O}(nm)$ — polynomiální. (Dochovaná odpověď „run Bellman-Ford $|V|-1$ times, then relax once more; if any distance changes, there is a negative cycle“ je ekvivalentní — hodnotitel ji označil „not incorrect“.)
② NE — ne vždy. Váhy jsou libovolné ze $\mathbb{Z}$, takže $G$ může obsahovat záporný cyklus (silně souvislý graf cykly má; stačí jeden se záporným součtem, např. $a \rightleftarrows b$ v grafu $G^\star$ z lekce). Pak nejkratší sled neexistuje a hledání nejkratší cesty je NP-těžké [L2.1] (redukce z Hamiltonovské kružnice, slide 12) — za předpokladu $P \ne NP$ tedy žádný polynomiální algoritmus neexistuje. Polynomiálně řešitelné to je jen v případě, že $G$ záporný cyklus nemá (Bellman-Ford, $\mathcal{O}(nm)$) — což díky ① umíme poznat. (Dochovaná odpověď „yes, since we are working with finite number of $V$ and $E$“ je chybná — konečnost instance neznamená polynomialitu; hodnotitel ji označil „very confusing“.)
③ NE — protipříklad (tentýž jako v [L2.15] T01). Pro každou cestu platí $c'(P) = c(P) + h \cdot |P|$: příplatek roste s počtem hran, takže se pořadí cest s různým počtem hran může přehodit. Konkrétně $G$: vrcholy $\{s, a, t\}$, hrany $c(s,a) = -2$, $c(a,t) = -2$, $c(s,t) = -3$ a zpáteční hrana $c(t,s) = 10$ (silná souvislost; všechny cykly kladné → nejkratší cesty definované). Minimum vah je $-3$, zvol $h = 3 \ge |{-3}|$.
- V $G$: $c(s{\to}a{\to}t) = -4 \;<\; c(s{\to}t) = -3$ → nejkratší je $s \to a \to t$.
- V $G'$: $c'(s{\to}a{\to}t) = 1 + 1 = 2 \;>\; c'(s{\to}t) = 0$ → nejkratší je přímá hrana $s \to t$.
Nejkratší cesta v $G'$ tedy neodpovídá nejkratší cestě v $G$ (grafy nakreslené pod řešením). $\blacksquare$ (Dochovaná odpověď „yes — rozdíly dvojic hran se nezmění“ je chybná: o vítězi rozhodují součty podél celých cest, viz danger box lekce; hodnotitel připsal „What about negative cycles?“ a skicu trojúhelníkového protipříkladu.)
④ ANO. Vytvoř $G'$ shodný s $G$, ale každou váhu vynásob $(-1)$: z $c(e) < 0$ plyne, že v $G'$ jsou všechny váhy kladné — žádný záporný cyklus, dokonce splněné vstupní podmínky Dijkstry [L2.4]. Nejkratší cesta v $G'$ je nejdelší cestou v $G$ a její délka je $(-1)\times$ délka nalezená v $G'$ [L2.17]. Složitost $\mathcal{O}(n^2)$ (resp. $\mathcal{O}(m + n \log n)$) — polynomiální. (Dochovaná odpověď je správně — hodnotitel ✓.) Pikantní detail k ústní: $G$ sám je samými zápornými vahami prošpikovaný zápornými cykly (silně souvislý graf cykly má a každý je tu záporný), takže nejkratší cesta v $G$ by byla NP-těžká — ale na nejdelší se ptáme „ze správné strany“.
5 výroků a říct zda platí nebo ne. Pokud platí, dokázat, pokud ne, udělat protipříklad. Výroky typu „když zvýšíme cenu hrany v grafu o násobek $k$, délka nejkratší cesty se také zvýší $k$-krát“, „Dijkstrův algoritmus nalezne vždy nejkratší cestu s nejmenším počtem hran“)
Decide whether each of the following statements holds. If it does, prove it; if it does not, give a counterexample.
- If we multiply the cost of every edge in the graph by a constant $k > 0$, the length of the shortest path also increases $k$-times.
- Dijkstra's algorithm always finds the shortest path with the minimum number of edges.
- If we increase the cost of every edge in the graph by the same positive constant $h$, the shortest paths are preserved.
- If all edge weights are negative, the longest path between two vertices can always be found in polynomial time.
- If the graph contains a negative cycle, the Bellman-Ford algorithm can still find the shortest path between two vertices in polynomial time.
a) Co je v zadání?
Formát „dokaž, nebo vyvrať“: u každého výroku verdikt PLATÍ/NEPLATÍ + důkaz, resp. protipříklad. Dochovaly se jen dva ukázkové výroky (1 a 2) — zbylé tři jsou doplněné tak, aby pokryly páky, na které se K2 výroky ptají nejčastěji.
b) Co k tomu budeme potřebovat?
- [L2.15] T02 (násobení $\times k$, vč. druhého čtení „jen jedna hrana“) a [L2.15] T01 (posun $+h$).
- [L2.16] T01 (Dijkstra a počet hran).
- [L2.17] (nejdelší cesta) a [L2.12] + [L2.1] (záporný cyklus: detekce vs. řešení).
c) Jak nad úlohou uvažovat?
Na každý výrok pusť checklist z lekce: definovanost → vstupní podmínky → transformace vah → cena vs. počet hran → kladný cyklus. Výroky 2, 3 a 5 padají na protipříklad/protiargument, výroky 1 a 4 mají krátký důkaz. Nepřepisuj argumenty z minulých lekcí — tady si jen ověř, že je umíš vybrat a stručně podat (na písemce stačí pár řádků + obrázek na výrok).
d) Úplné řešení (vlastní — stručné verdikty s odkazy na vypracované argumenty)
- PLATÍ (pro čtení „všechny hrany“, $k > 0$): množina cest se nemění a $c'(P) = k \cdot c(P)$, kladná konstanta projde přes minimum → $\min_P c'(P) = k \min_P c(P)$, argmin se zachová. Vypracováno vč. mezí platnosti ($k \le 0$) a druhého čtení „jen jedna hrana“ (to NEPLATÍ) v [L2.15] T02.
- NEPLATÍ: Dijkstra minimalizuje součet vah, počet hran do algoritmu nevstupuje. Protipříklad: $s{\to}a{\to}b{\to}t$ za $1+1+1 = 3$ (3 hrany) porazí přímou hranu $s{\to}t$ za $10$ (1 hrana). Vypracováno v [L2.16] T01.
- NEPLATÍ: $c'(P) = c(P) + h \cdot |P|$ — příplatek závisí na počtu hran. Protipříklad = grafy $G$, $G'$ z řešení T01③ výše (s $h = 3$ se vítěz přehodí z $s{\to}a{\to}t$ na $s{\to}t$). Vypracováno v [L2.15] T01.
- PLATÍ: ×(−1) dá všechny váhy kladné → žádný záporný cyklus → Dijkstra [L2.4]; výsledek převeď zpět $\times(-1)$. To je přesně T01④ výše a takeaway [L2.17]. (Pozor na obecnější výrok bez „all weights negative“ — nejdelší cesta s kladným cyklem je NP-těžká, [L2.17] T01.)
- NEPLATÍ: Bellman-Ford záporný cyklus detekuje (kontrolní průchod, $\mathcal{O}(nm)$ [L2.12]), ale nejkratší cestu v takovém grafu nenajde — úloha je NP-těžká [L2.1], takže za $P \ne NP$ to polynomiálně neumí žádný algoritmus. „Umí detekovat“ ≠ „umí vyřešit“.
Poznámka k písemce: přesné EN znění pětice se každý termín liší — formát i páky ale zůstávají. Když výrok nepoznáš, projdi checklist z této lekce; téměř jistě tlačí na jednu z pěti pák.