Záporné váhy ano, záporné cykly ne
Prerekvizity: [L0.3] Cesta, sled, tah, cyklus (rozdíl cesta vs. sled je tady klíčový), [L0.1] Co je graf. Otevíráme kapitolu K2 — slot 2 zkoušky (nejkratší cesty, 7 bodů, padá v ~90 % termínů). A přesně otázka této lekce — „proč vadí záporné cykly?“ — je doložená otázka z ústní zkoušky. Než se v dalších lekcích pustíme do algoritmů, musíme vědět, kdy má úloha vůbec smysl.
Úloha nejkratší cesty (Shortest Path)
Definice ze slidů (kurz ji uvádí anglicky — nech si ji projít hlavou v obou jazycích):
Shortest Path. Instance: Digraph $G$, weights $c : E(G) \to \mathbb{R}$, nodes $s, t \in V(G)$. Goal: Find the shortest $s$–$t$ path $P$, i.e. one of minimum weight $c(E(P))$, or decide that $t$ is unreachable from $s$.
Česky: v orientovaném grafu s ohodnocením hran $c$ hledáme nejkratší cestu (shortest path) z $s$ do $t$ — cestu s nejmenším součtem vah hran. Délka cesty $P$ je $c(E(P)) = \sum_{e \in E(P)} c(e)$ a vzdálenost $l(s,t)$ je délka nejkratší $s$–$t$ cesty. Příbuzné varianty: z $s$ do všech vrcholů (shortest path tree — SPT, strom nejkratších cest), ze všech do $t$ (stačí otočit hrany), a mezi všemi dvojicemi (all pairs shortest path). Varianta $s \to t$ se podle slidů často řeší algoritmy pro SPT (případně all-pairs) — asymptoticky rychlejší algoritmus jen pro jednu dvojici není znám; výpočet lze ukončit při dosažení $t$.
Zkus sám: všimni si v definici oboru vah — $c : E(G) \to \mathbb{R}$, tedy i záporné. K čemu by záporná váha hrany byla dobrá?
Dvě typické situace:
- Nejdelší cesta (longest path): podle slidů se převádí na nejkratší otočením znaménka vah — hledáme minimum místo maxima. Z kladných zisků se tak stanou záporné „náklady“. (Tahle transformace se nám bude hodit u investičních úloh v DAG.)
- Smíšené náklady a zisky: hrana může reálně vydělávat (dotovaný úsek, zisk z obchodu po cestě) — váha je pak záporná přirozeně.
Proto chceme teorii, která záporné váhy unese. Otázka lekce: kde přesně je hranice, za kterou se úloha rozbije?
Co přesně rozbije záporný cyklus
Vzpomeň si na rozdíl z [L0.3]: cesta (path) nesmí opakovat vrcholy, sled (edge progression) smí cokoliv. Teď si vezmi graf, ve kterém je cyklus se záporným součtem vah.
Zkus sám: sled z $s$ do $t$ projde okolo záporného cyklu. Co se stane s jeho délkou, když cyklus oběhne ještě jednou navíc? A kolikrát to může opakovat?
Každý oběh přičte záporné číslo — sled se zkrátí. A opakovat to může donekonečna: délka sledu klesá k $-\infty$, takže nejkratší sled neexistuje. U cesty tenhle trik nejde — oběh cyklu by zopakoval vrchol, což cesta zakazuje.
Pro cestu je situace pořád zdravá. V konečném grafu je jen konečně mnoho cest z $s$ do $t$ (žádná nesmí opakovat vrcholy, takže má nejvýš $|V|-1$ hran) — a minimum konečné množiny vždy existuje. Slidy to formulují jako větu:
Pokud v grafu existuje cesta z $s$ do $t$, pak existuje i nejkratší cesta z $s$ do $t$. Pozor: pro sled to neplatí — v grafu se záporným cyklem najdeme vždy ještě kratší sled, který cyklus oběhne znovu.
Zkus sám: nejkratší cesta tedy existuje vždy (když je $t$ dosažitelný). Tak proč je záporný cyklus vůbec problém?
Problém není existence, ale nalezení. Rychlost algoritmů pro nejkratší cesty stojí podle slidů na tom, že se nestarají o opakování vrcholů — nerozlišují cestu od sledu. To si můžou dovolit jen tehdy, když nejkratší sled „automaticky“ odpovídá nejkratší cestě. Záporný cyklus tuhle ekvivalenci zničí (nejkratší sled neexistuje) — a najednou je potřeba opakování vrcholů hlídat explicitně, což dělá úlohu NP-těžkou — pojem jsme zavedli u ILP v [L0.7] Co je ILP a LP relaxace (žádný polynomiální algoritmus není znám).
- Pokud graf neobsahuje cyklus záporné ani nulové váhy, pak každý nejkratší sled z $s$ do $t$ je nejkratší cestou z $s$ do $t$.
- Pokud graf neobsahuje cyklus záporné váhy, pak každý nejkratší sled z $s$ do $t$ obsahuje nejkratší cestu z $s$ do $t$ a má stejnou délku (případné nulové cykly navíc lze vystřihnout).
Tohle je celá pointa názvu lekce: záporné váhy ano — dokud nevytvoří záporný cyklus, smí algoritmus klidně počítat se sledy a výsledek bude nejkratší cesta. Záporné cykly ne — s nimi se úloha mění z polynomiální na NP-těžkou. (Které algoritmy zvládnou záporné hrany a které ne, rozebereme u Dijkstry [L2.4] a Bellman-Forda [L2.12]; Bellman-Ford navíc umí záporný cyklus aspoň detekovat.)
Zkus sám (otázka přímo ze slidu 11): co naopak nesmí obsahovat graf, když nás zajímá nejdelší cesta?
Kladné cykly. Nejdelší cesta = nejkratší cesta po otočení znamének vah — a záporný cyklus v otočeném grafu je přesně kladný cyklus v původním. Sled by na kladném cyklu nabíral délku do $+\infty$. Proto např. „maximalizace zisku“ na grafu s kladným ziskovým cyklem je stejně těžká úloha (vrátí se nám to v [L2.17] Nejdelší cesta: kdy je těžká a kdy snadná).
Trojúhelníková nerovnost — a jak ji záporný cyklus poruší
Bez záporných cyklů se vzdálenosti chovají „geometricky slušně“. Slide 10:
Pokud graf neobsahuje cyklus záporné váhy, pak pro všechny trojice vrcholů $i, j, k$ platí $l(i,j) \le l(i,k) + l(k,j)$.
Důsledek (značíme $c(i,j)$ váhu hrany z $i$ do $j$): $\;l(i,j) \le c(i,j)$, $\;l(i,j) \le l(i,k) + c(k,j)$, $\;l(i,j) \le c(i,k) + l(k,j)$.
Intuice: cesta přes mezizastávku $k$ je jedna z možností, jak se dostat z $i$ do $j$ — nemůže být lepší než optimum… pokud ovšem slepením dvou nejkratších cest zase vznikne cesta (nebo aspoň sled, který umíme zkrátit na cestu stejné délky). A přesně to záporný cyklus pokazí. Slide 11 to ukazuje na tomhle grafu:
Zkus sám: spočítej v obrázku $l(i,j)$, $l(i,k)$ a $l(k,j)$ (délky nejkratších cest) a dosaď do trojúhelníkové nerovnosti. Co vyjde?
$l(i,j) = \min\{5,\; 6 + (-2)\} = 4$ (cesta $i{\to}k{\to}j$), $\;l(i,k) = \min\{6,\; 5 + (-1)\} = 4$ (cesta $i{\to}j{\to}k$), $\;l(k,j) = -2$. Dosazení:
$$\begin{aligned} l(i,j) &\le l(i,k) + l(k,j) \\ 6 - 2 &\le (5 - 1) + (-2) \\ 4 &\le 2 \quad \ldots \text{ spor!} \end{aligned}$$Proč věta selhala? Graf obsahuje záporný cyklus $j \to k \to j$ s váhou $(-1) + (-2) = -3$. Slepením nejkratší cesty $i \to j \to k$ a hrany $k \to j$ vznikne sled, který tenhle záporný cyklus obsahuje — a sled se zkrátit na stejně dlouhou cestu nedá. Trojúhelníková nerovnost (a s ní celá výstavba algoritmů v dalších lekcích) tedy předpokládá graf bez záporných cyklů.
Neorientované grafy: jen nezáporné váhy
Celou dobu mluvíme o digrafech. Neorientovaný graf se na orientovaný převádí standardně: každá neorientovaná hrana $\{v, w\}$ se nahradí dvojicí orientovaných hran $(v,w)$ a $(w,v)$ se stejnou váhou.
Zkus sám: co tenhle převod udělá s neorientovanou hranou váhy $-3$?
Vzniknou hrany $(v,w)$ a $(w,v)$, obě s váhou $-3$ — a ty spolu tvoří cyklus $v \to w \to v$ s váhou $-6$. Jediná záporná neorientovaná hrana = záporný cyklus. Proto se u neorientovaných grafů uvažují jen instance s nezápornými váhami.
Pozor: nezaměňuj „záporná hrana“ a „záporný cyklus“- V orientovaném grafu záporná hrana sama o sobě nevadí — úloha je v pořádku, dokud žádný cyklus nemá záporný součet. (Jen ne každý algoritmus ji zvládne — to rozlišíme u Dijkstry [L2.4] vs. Bellman-Forda [L2.12].)
- V neorientovaném grafu je každá záporná hrana po převodu rovnou záporný 2-cyklus — tam je „záporná hrana“ a „záporný cyklus“ totéž.
- „Nejkratší cesta neexistuje“ je u záporného cyklu nepřesné: neexistuje nejkratší sled ($\to -\infty$); nejkratší cesta existuje, ale je NP-těžké ji najít.
Proč zrovna NP-těžké?
Tvrzení „se záporným cyklem je hledání nejkratší cesty NP-těžké“ má na slidu 12 elegantní zdůvodnění — redukci z existence Hamiltonovské kružnice (cyklus navštěvující každý vrchol právě jednou):
Pro zvídavé: jak z grafu $G$ vyrobit instanci nejkratší cesty, která „pozná“ Hamiltonovskou kružnici?
Konstrukce ze slidu 12: vezmi $G$ a všem hranám dej váhu $-1$ (graf $G'$). Zvol libovolný vrchol $v$ a vytvoř jeho duplikát $v'$ včetně hran. Přidej zdroj $s$, cíl $t$ a hrany $(s, v)$ a $(v', t)$ s váhou $0$. Pak nejkratší cesta z $s$ do $t$ v $G'$ má délku $-|V(G)|$ právě tehdy, když v $G$ existuje Hamiltonovská kružnice: cesta dlouhá $-|V(G)|$ musí použít $|V(G)|$ hran váhy $-1$ bez opakování vrcholů — tedy obejít všechny vrcholy a vrátit se „do $v$“ (přes duplikát $v'$). A protože každý cyklus v $G$ se v $G'$ stal záporným cyklem, umí takové grafy řešit jen algoritmus, který zvládá záporné cykly — kdyby byl polynomiální, řešil by polynomiálně i NP-těžkou Hamiltonovskou kružnici.
Tady nám stačí závěr; důkazové techniky tohohle typu (redukce) si budeš procvičovat v kapitole K3 — TSP verzi téhle redukce provedeme celou v [L3.5]. Souhrnnou zkouškovou úlohu na záporné cykly potkáš ve FOTO vyvrcholení [L2.18].
Key takeaways — L2.1- Záporné váhy hran jsou OK, dokud netvoří záporný cyklus: pak nejkratší sled neexistuje (délka $\to -\infty$) a najít nejkratší cestu je NP-těžké (redukce z Hamiltonovské kružnice).
- Hledáme cestu (bez opakování vrcholů), ne sled [L0.3]; existuje-li nějaká $s$–$t$ cesta, nejkratší cesta existuje vždy.
- Bez záporných cyklů nejkratší sled obsahuje nejkratší cestu stejné délky — proto smí algoritmy ignorovat opakování vrcholů a být rychlé.
- Bez záporných cyklů platí trojúhelníková nerovnost $l(i,j) \le l(i,k) + l(k,j)$; záporný cyklus ji rozbije.
- Neorientovaná záporná hrana = záporný 2-cyklus po převodu na digraf → u neorientovaných grafů jen nezáporné váhy.
- U nejdelší cesty vadí symetricky kladné cykly (otočení znamének vah).
Consider a digraph with nodes $i$, $j$, $k$ and edges: $(i,j)$ with weight $5$, $(i,k)$ with weight $6$, $(j,k)$ with weight $-1$, and $(k,j)$ with weight $-2$. Recall the theorem: if the graph does not contain a cycle of negative weight, then distances between all triplets of nodes satisfy $l(i,j) \le l(i,k) + l(k,j)$. Compute the distances $l(i,j)$, $l(i,k)$, $l(k,j)$, check the triangle inequality, and explain the result.
a) Co je v zadání?
Konkrétní digraf o třech vrcholech a čtyřech hranách (je to přesně graf z obrázku výše). Máme spočítat tři vzdálenosti — délky nejkratších cest —, dosadit je do trojúhelníkové nerovnosti a vysvětlit, co se děje.
b) Co k tomu budeme potřebovat?
- [L0.3] Cesta, sled, tah, cyklus — vzdálenost je délka nejkratší cesty.
- Tato lekce — trojúhelníková nerovnost a její předpoklad „bez záporných cyklů“.
c) Jak nad úlohou uvažovat?
Graf je maličký — vzdálenosti spočítej výčtem všech cest (mezi každou dvojicí jsou nejvýš dvě). Pak se ptej: je splněn předpoklad věty? Projdi všechny cykly v grafu a sečti jejich váhy. Nakonec si rozmysli, co přesně vznikne slepením dvou nejkratších cest, jejichž délky v nerovnosti sčítáš.
d) Úplné řešení
Vzdálenosti (cesty nesmí opakovat vrcholy, takže kandidátů je málo):
- $l(i,j) = \min\{\,c(i,j),\; c(i,k) + c(k,j)\,\} = \min\{5,\; 6 - 2\} = 4$ — nejkratší cesta $i \to k \to j$.
- $l(i,k) = \min\{\,c(i,k),\; c(i,j) + c(j,k)\,\} = \min\{6,\; 5 - 1\} = 4$ — nejkratší cesta $i \to j \to k$.
- $l(k,j) = c(k,j) = -2$ — jediná $k$–$j$ cesta je přímá hrana.
Trojúhelníková nerovnost:
$$\begin{aligned} l(i,j) &\le l(i,k) + l(k,j) \\ 6-2 &\le (5-1) + (-2) \\ 4 &\le 2 \quad \ldots \text{ spor (nerovnost neplatí)} \end{aligned}$$Vysvětlení: věta tady nic neslibuje, protože její předpoklad je porušen — graf obsahuje záporný cyklus $j \to k \to j$ s váhou $(-1) + (-2) = -3$. Mechanismus selhání: důkaz nerovnosti stojí na slepení nejkratší $i$–$k$ cesty a nejkratší $k$–$j$ cesty do jednoho objektu. Tady ale $i$–$k$ cesta prochází vrcholem $j$, takže slepením vznikne sled $i \to j \to k \to j$, který obsahuje právě ten záporný cyklus — a nedá se zkrátit na cestu stejné délky. Přesně tohle je obecný důvod, proč všechny věty a algoritmy kapitoly K2 předpokládají graf bez záporných cyklů.
When we transform an undirected graph to a directed graph, every undirected edge connecting $v$ and $w$ is transformed to two edges $(v,w)$ and $(w,v)$. Explain why this transformation of a negative undirected edge results in a negative cycle, and why we therefore consider only instances with nonnegative weights when working with undirected graphs.
a) Co je v zadání?
Vysvětlovací otázka (typické téma na ústní): proč standardní převod neorientovaného grafu na digraf nesnese záporné hrany.
b) Co k tomu budeme potřebovat?
- Tato lekce — převod neorientované hrany na dvojici protisměrných hran; co způsobí záporný cyklus.
- [L0.3] Cesta, sled, tah, cyklus — definice cyklu.
c) Jak nad úlohou uvažovat?
Nakresli si jednu neorientovanou hranu $\{v,w\}$ s váhou $c < 0$ a proveď převod. Jaký nejmenší cyklus v digrafu vznikl a jakou má váhu? Pak použij hlavní poznatek lekce: co záporný cyklus dělá s nejkratším sledem a se složitostí úlohy.
d) Úplné řešení
Neorientovaná hrana $\{v,w\}$ s váhou $c$ se převede na hrany $(v,w)$ a $(w,v)$, obě s váhou $c$. Ty spolu tvoří cyklus $v \to w \to v$ o váze $2c$. Je-li $c < 0$, je $2c < 0$ — vznikl záporný cyklus, a to z jediné záporné hrany, bez ohledu na zbytek grafu.
Důsledky (z této lekce): v digrafu se záporným cyklem neexistuje nejkratší sled (oběhy $v \to w \to v$ srážejí délku k $-\infty$), takže algoritmy postavené na ztotožnění „nejkratší sled = nejkratší cesta“ nelze použít, a hledání nejkratší cesty je v takové třídě instancí NP-těžké. Proto se po převodu na digraf uvažují u neorientovaných grafů jen instance s nezápornými váhami — tam žádný záporný cyklus vzniknout nemůže a celý aparát kapitoly K2 funguje.