Eulerovský tah a zdvojení hran (sudý stupeň)
Třetí, poslední stavební kámen aproximací metrického TSP. Z [L3.8a] Metrický TSP + trojúhelníková nerovnost + shortcutting umíme z laciného uzavřeného sledu vyrobit Hamiltonovský okruh bez zdražení; z [L3.8b] MST jako dolní mez máme měřítko $\mathrm{OPT} \ge c(E(T))$. Chybí jediné: odkud ten laciný uzavřený sled vzít. Dnes ho vyrobíme — z kostry, zdvojením hran a Eulerovým slavným kritériem sudých stupňů.
Poslední chybějící díl skládačky
Shortcutting [L3.8a] chce na vstupu uzavřený sled přes všechny vrcholy a důkaz faktoru bude chtít, aby jeho cena šla svázat s $c(E(T))$ — tedy ideálně sled, který používá jen hrany kostry (každou nejvýš párkrát). Nejlevnější představitelný cíl: projít každou hranu právě jednou.
Sled, který žádnou hranu neopakuje, má jméno z [L0.3] Cesta, sled, tah, cyklus: tah (trail). Slide 24 mu říká Eulerian walk (Eulerovský tah) $L$, s vysvětlivkou EN 1:1: „the Eulerian walk L (i.e., a closed walk containing every edge)“ — uzavřený sled obsahující každou hranu (a protože je to tah, každou právě jednou).
Zkus sám: vezmi MST z [L3.8b] (obrázek níže) a pokus se v něm najít uzavřený tah obsahující všechny 4 hrany. Kde to ztroskotá?
Na listech. Jakmile vejdeš třeba do $C$ (jedinou hranou $B$–$C$), nemáš kudy ven — jediná hrana $C$ je už použitá a tah hrany opakovat nesmí. A i kdybys v listu začal, na konci se tam nemáš jak vrátit. Strom na $\ge 2$ vrcholech má vždy listy (stupeň 1), takže kostra sama Eulerovský tah nikdy nemá. Něco s ní budeme muset udělat — a klíčem je, jak hned uvidíš, právě ten stupeň 1, tedy lichý stupeň.
Nutná podmínka: každý vrchol sudého stupně
Překážka z listů je speciální případ obecného jevu. Představ si, že uzavřený Eulerovský tah existuje, a sleduj libovolný vrchol $v$.
Zkus sám: kolik hran u $v$ „spotřebuje“ jedna návštěva (průchod) vrcholu $v$? Co z toho plyne pro stupeň $|\delta(v)|$ z [L0.2] Stupeň vrcholu?
Přesně dvě: jednou hranou tah do $v$ vejde, jinou vyjde (hrany se v tahu neopakují, takže jsou různé). Tah tedy hrany u $v$ spáruje do dvojic (příchod, odchod). Protože Eulerovský tah projde každou hranu u $v$, je $|\delta(v)|$ = 2 × (počet návštěv) — sudé číslo. U startu = cíle je to stejné: úvodní odchod se spáruje se závěrečným příchodem (tah je uzavřený). Sudý stupeň všech vrcholů je tedy nutná podmínka. List se stupněm 1 ji porušuje — proto strom ztroskotal.
… a sudost i stačí (v souvislém grafu)
Slide 24 rovnou konstatuje obě implikace najednou (Observation, EN 1:1):
„the doubling of edges in $T$ ensures even degree of all vertices in the multigraph, which is a sufficient and necessary condition for existence of Eulerian walk.“
Tedy: sudý stupeň všech vrcholů je nutná i postačující podmínka existence Eulerovského tahu. (Mlčky se předpokládá souvislost — zdvojená kostra je souvislá vždy; viz danger box níže.)
Nutnost jsme si právě dokázali. Proč sudost stačí, slidy nedokazují — náčrt argumentu (vlastní doplněk) si ale zkus sestavit sám, je to hezké a u ústní se hodí:
Zkus sám: vyraž z libovolného vrcholu $s$ a choď dál vždy nějakou dosud nepoužitou hranou. Proč se nemůžeš zaseknout nikde jinde než zpátky v $s$?
Spočítej parity. Stojíš-li ve vrcholu $v \ne s$, pak jsi u něj zatím spotřeboval lichý počet hran: každá dřívější návštěva 2 (příchod + odchod) a teď navíc 1 příchod. Jenže $|\delta(v)|$ je sudé — takže aspoň jedna hrana u $v$ je pořád volná a můžeš odejít. Zaseknout se lze jedině v $s$ (tam je spotřeba sudá a může dojít na nulu volných) — tvá procházka tedy vždy skončí jako uzavřený tah.
Pokud po něm zbyly nepoužité hrany: díky souvislosti se některá dotýká vrcholu $w$ na už nalezeném tahu (a zbylé hrany mají u každého vrcholu opět sudé počty — odečetli jsme dvojice). Spusť stejnou procházku z $w$ po zbylých hranách → druhý uzavřený tah, který do prvního v $w$ vpleteš (projdeš první tah do $w$, objedeš druhý, dokončíš první). Opakuj, dokud hrany nedojdou — vznikne Eulerovský tah celého grafu. (Tomuhle postupu se říká Hierholzerův algoritmus a běží v polynomiálním čase — Euler je na rozdíl od Hamiltona [L3.3] snadný.)
Zdvojení hran: jak kostře vyrobit sudé stupně
Zpátky ke kostře $T$. Má listy, tedy liché stupně — Eulerovský tah nemá. Potřebujeme ji nejjednodušeji opravit.
Zkus sám: jak z kostry vyrobit graf, kde má každý vrchol sudý stupeň — bez přidávání vrcholů a tak, aby cena nových hran šla vyjádřit přes $c(E(T))$?
Zdvoj každou hranu. Stupeň každého vrcholu se přesně zdvojnásobí: $2 \cdot |\delta(v)|$ je sudé vždy, ať byl původní stupeň jakýkoliv — žádné rozbory případů. Souvislost zůstane (hran jen přibylo) a cena nového grafu je přesně $2\,c(E(T))$. Vznikne ovšem multigraf — graf, kde mezi dvěma vrcholy smí vést víc hran; dvě kopie téže hrany jsou dvě různé hrany a tah projde každou kopii právě jednou.
Přesně to je krok 2 double-tree algoritmu (slide 24, EN 1:1): „By doubling every edge in $T$ we get multigraph in which we find the Eulerian walk $L$ (i.e., a closed walk containing every edge);“ A cenu zachycuje bod 3 důkazu na slidu 25 (EN 1:1) — třetí a poslední nerovnost (vlastně rovnost) budoucího řetízku:
„$2 c(E(T)) = c(E(L))$ holds due to the creation of $L$ by doubling edges in $T$“
Žádná magie: $L$ projde každou hranu multigrafu právě jednou a multigraf = každá hrana $T$ dvakrát, takže $c(E(L)) = 2\,c(E(T))$.
Celé si to přehraj na zdvojené MST z [L3.8b] (tatáž metrická $K_5$, $c(E(T)) = 7$):
K čemu to bude: tři kameny jsou pohromadě
Stepper skončil pointou: Eulerovský tah zdvojené MST je přesně ten sled $W$, na kterém v [L3.8a] běžel shortcutting ($14 \to$ okruh ceny 12). Nic z toho nebyla náhoda — byl to dopředu rozložený double-tree algoritmus. V [L3.9] už jen slepíme řetízek (slide 25):
$$2\, \mathrm{OPT}(K_n, c) \;\stackrel{2.}{\ge}\; 2\, c(E(T)) \;\stackrel{3.}{=}\; c(E(L)) \;\stackrel{1.}{\ge}\; c(E(H)),$$kde bod 1 je shortcutting [L3.8a], bod 2 dolní mez [L3.8b] a bod 3 dnešní zdvojení. Christofides [L3.10] pak zahraje stejnou partii chytřeji: nezdvojí všechno, ale opraví jen vrcholy, kde sudost chybí — vrcholů lichého stupně je v každém grafu sudý počet [L0.2], takže se dají spárovat levným perfektním párováním (slide 26: „The merging of $T$ and $M$ ensures even degree of all vertices in the multigraph and thus existence of Eulerian walk.“). A Eulerovský tah potkáš i mimo TSP — u směrovaného čínského pošťáka [L4.13] se hrany doplňují podle bilance $|\delta^+| = |\delta^-|$.
Pozor: nebezpečné polopravdy- „Eulerovský tah ≈ Hamiltonovský okruh.“ NE — Euler projde každou HRANU právě jednou (vrcholy se smí opakovat), Hamilton každý VRCHOL právě jednou [L3.3]. A složitost je opačný svět: Euler se pozná v polynomiálním čase (zkontroluj sudosti), Hamilton je NP-úplný. Eulerovský tah není přípustné řešení TSP — okruh z něj teprve vyrobí shortcutting [L3.8a].
- „Sudé stupně stačí vždy.“ Bez souvislosti ne — dvě disjunktní kružnice mají všechny stupně sudé, ale jeden tah je neprojde. Slide 24 souvislost nezmiňuje, protože zdvojená kostra je souvislá automaticky (vlastní upřesnění, přiznáno). Přesně: ekvivalence platí pro souvislé multigrafy (resp. ty, kde všechny hrany leží v jedné komponentě).
- Uzavřený vs. otevřený tah: dnešní věta je o uzavřeném tahu (start = cíl) — ten chce TSP. Otevřený Eulerovský tah existuje ⟺ právě 2 vrcholy mají lichý stupeň (vlastní doplněk, slidy ho nepotřebují). Slavné königsberské mosty žádný Eulerovský tah nemají právě proto, že tam mají lichý stupeň čtyři vrcholy.
- „Zdvojení je zadarmo.“ NE — platíš celou kostru podruhé: $c(E(L)) = 2\,c(E(T))$. Právě tahle dvojka je celý faktor 2 double-tree algoritmu; Christofides [L3.10] ji srazí na $\tfrac{3}{2}$ tím, že místo druhé kostry přidá jen párování s cenou $\le \mathrm{OPT}/2$.
Key takeaways — L3.8c- Eulerovský tah = uzavřený tah [L0.3] obsahující každou hranu právě jednou; v souvislém (multi)grafu existuje ⟺ každý vrchol má sudý stupeň [L0.2] (slide 24: „sufficient and necessary condition“). Nutnost: každá návštěva vrcholu spáruje 2 hrany; postačitelnost: procházka se zasekne jen ve startu + vplétání (Hierholzer, polynomiální).
- Zdvojení všech hran kostry zdvojnásobí každý stupeň → všechny sudé → Eulerovský multigraf; cena tahu $c(E(L)) = 2\,c(E(T))$ (slide 25, bod 3).
- Eulerovský tah pak shortcutting [L3.8a] převede na Hamiltonovský okruh bez zdražení — s dolní mezí [L3.8b] jsou tím pohromadě všechny tři kameny řetízku $2\,\mathrm{OPT} \ge 2\,c(E(T)) = c(E(L)) \ge c(E(H))$ pro [L3.9].
- Euler ≠ Hamilton: hrany × vrcholy, polynomiální × NP-úplné [L3.3].
- Christofides [L3.10] nezdvojuje vše — liché vrcholy (vždy sudý počet [L0.2]) opraví perfektním párováním.
Step 2 of the double-tree algorithm states: „By doubling every edge in $T$ we get multigraph in which we find the Eulerian walk $L$ (i.e., a closed walk containing every edge);“ The slide observes: „the doubling of edges in $T$ ensures even degree of all vertices in the multigraph, which is a sufficient and necessary condition for existence of Eulerian walk.“ Step 3 of the proof states: „$2 c(E(T)) = c(E(L))$ holds due to the creation of $L$ by doubling edges in $T$“.
Study questions (own): (i) Prove that even degree of every vertex is a necessary condition for the existence of a closed Eulerian walk. (ii) Sketch why, in a connected multigraph, even degrees are also sufficient. (iii) Explain why doubling every edge of a spanning tree makes all degrees even, and derive the equality $c(E(L)) = 2\,c(E(T))$.
a) Co je v zadání?
Důkazová mini-úloha: obhájit Observation ze slidu 24 — obě implikace ekvivalence „Eulerovský tah ⟺ sudé stupně“ — a zdůvodnit krok zdvojení včetně ceny. U zkoušky je to bod 3 důkazů faktorů 2 i 3/2 (a věta, na kterou se oba algoritmy odvolávají v kroku „find the Eulerian walk“).
b) Co k tomu budeme potřebovat?
- Tato lekce — párovací argument, náčrt Hierholzera, zdvojení.
- [L0.2] Stupeň vrcholu — definice $|\delta(v)|$, parita.
- [L0.3] Cesta, sled, tah, cyklus — tah = sled bez opakování hran.
- [L0.4] — kostra je souvislá (souvislost zdvojeného multigrafu).
c) Jak nad úlohou uvažovat?
(i) Sleduj jeden vrchol a počítej hrany, které tah u něj spotřebuje za jednu návštěvu; nezapomeň na start = cíl. (ii) „Choď po nepoužitých hranách“ — kde jediné se můžeš zaseknout a proč (parita spotřeby)? Co se zbylými hranami? (iii) Co udělá zdvojení se stupněm $|\delta(v)|$? A kolikrát Eulerovský tah multigrafu zaplatí každou hranu původní kostry?
d) Úplné řešení (vlastní rozepsání; postačitelnost = náčrt Hierholzera)
(i) Nutnost. Nechť uzavřený Eulerovský tah existuje a $v$ je libovolný vrchol. Každý průchod tahu vrcholem $v$ použije právě dvě hrany u $v$: jednu pro příchod, jinou pro odchod (tah hrany neopakuje). U startovního vrcholu se úvodní odchod páruje se závěrečným příchodem (tah je uzavřený). Hrany u $v$ se tedy rozpadnou na disjunktní dvojice — a protože Eulerovský tah obsahuje každou hranu, je $|\delta(v)| = 2 \cdot (\text{počet návštěv } v)$, tedy sudé. $\blacksquare$
(ii) Postačitelnost (náčrt). Vyjdi z libovolného vrcholu $s$ a opakovaně pokračuj libovolnou nepoužitou hranou. Ve vrcholu $v \ne s$ je počet dosud použitých hran u $v$ lichý (dvojice za dřívější návštěvy + aktuální příchod), ale $|\delta(v)|$ je sudé → existuje nepoužitá hrana → lze pokračovat. Procházka se tedy zastaví jedině v $s$, čímž vznikne uzavřený tah $C_1$. Zbývají-li nepoužité hrany, mají u každého vrcholu opět sudé počty (odebrali jsme dvojice) a díky souvislosti se některá dotýká vrcholu $w \in C_1$; stejným postupem z $w$ vznikne uzavřený tah $C_2$, který do $C_1$ v $w$ vpleteme (projdi $C_1$ do $w$, objeď $C_2$, dokonči $C_1$). Konečně mnoha opakováními vznikne uzavřený tah obsahující všechny hrany — Eulerovský. (Hierholzerův algoritmus, polynomiální.) $\blacksquare$
(iii) Zdvojení a cena. Zdvojením má vrchol $v$ v multigrafu stupeň $2\,|\delta_T(v)|$ — sudý bez ohledu na paritu původního stupně (listy kostry přestanou překážet). Multigraf je souvislý (vznikl z kostry přidáváním hran [L0.4]), takže podle (ii) Eulerovský tah $L$ existuje. Jeho hrany jsou přesně hrany multigrafu, každá právě jednou — a multigraf obsahuje každou hranu $e \in E(T)$ dvakrát, takže $c(E(L)) = \sum_{e \in E(T)} 2\,c(e) = 2\,c(E(T))$, přesně jak tvrdí slide 25, bod 3. $\blacksquare$
Consider the metric TSP instance on nodes $\{A, B, C, D, E\}$ from lessons [L3.8a] and [L3.8b], and its minimum spanning tree $T = \{\{B,C\}, \{A,B\}, \{A,E\}, \{B,D\}\}$ with $c(E(T)) = 7$ (costs: $c(B,C){=}1$, $c(A,B){=}2$, $c(A,E){=}2$, $c(B,D){=}2$).
(a) Double every edge of $T$ and list the degrees of all vertices in the resulting multigraph. Why does an Eulerian walk exist? (b) Starting at $A$, find an Eulerian walk $L$ and compute $c(E(L))$; verify $c(E(L)) = 2\,c(E(T))$. (c) Shortcut $L$ into a Hamiltonian circuit $H$ (lesson [L3.8a]) and compare $c(E(H))$ with $c(E(L))$.
a) Co je v zadání?
Početní procvičení celé dnešní konstrukce: zdvojit kostru, ověřit sudosti, najít Eulerovský tah, spočítat jeho cenu a shortcuttingem ho dorazit na okruh. Je to ručně provedený double-tree algoritmus — v [L3.9] k němu už jen doplníme důkaz faktoru.
b) Co k tomu budeme potřebovat?
- Tato lekce — sudé stupně ⟺ Eulerovský tah, zdvojení, $c(E(L)) = 2\,c(E(T))$.
- [L3.8a] T02 — shortcutting (posloupnost prvních návštěv).
- [L3.8b] T02 — odkud se vzala MST a její cena 7.
c) Jak nad úlohou uvažovat?
(a) Stupeň v multigrafu = 2 × stupeň v $T$; spočítej stupně v $T$ ($B$ je střed, $C, D, E$ listy). (b) Drž se pravidla „zaseknout se smíš jen ve startu“: z listů se vracej druhou kopií hrany. (c) Zapisuj posloupnost vrcholů tahu a škrtej opakované — zbytek je okruh.
d) Úplné řešení (vlastní)
(a) Stupně v $T$: $|\delta(A)| = 2$ ($B, E$), $|\delta(B)| = 3$ ($A, C, D$), $|\delta(C)| = |\delta(D)| = |\delta(E)| = 1$ (listy). Po zdvojení: $A$: 4, $B$: 6, $C$: 2, $D$: 2, $E$: 2 — všechny sudé; multigraf je navíc souvislý (zdvojená kostra). Podle dnešní věty (slide 24 Observation) Eulerovský tah existuje.
(b) Např. $L: A \to B \to C \to B \to D \to B \to A \to E \to A$ (z listů $C$, $D$, $E$ vždy zpět druhou kopií; obě kopie $A$–$B$ použity v opačných směrech). Každá z 8 hran multigrafu právě jednou, start = cíl ✓. Cena: $2 + 1 + 1 + 2 + 2 + 2 + 2 + 2 = \mathbf{14} = 2 \cdot 7 = 2\,c(E(T))$ ✓ (slide 25, bod 3 — tah platí každou hranu kostry přesně dvakrát).
(c) Posloupnost prvních návštěv v $L = A,B,C,B,D,B,A,E,A$: vrcholy $B$ (druhý a třetí výskyt) a $A$ (prostřední výskyt) přeskočíme → $H = A, B, C, D, E, A$. Cena $c(E(H)) = 2 + 1 + 2 + 5 + 2 = \mathbf{12} \le 14 = c(E(L))$ — shortcutting díky trojúhelníkové nerovnosti nezdražil [L3.8a] (je to přesně tamní běh). Mimochodem se sendvičem z [L3.8b] T02: $7 \le \mathrm{OPT} \le 12$ a $12 \le 2 \cdot 7 = 14$ — faktor 2, který v [L3.9] dokážeme obecně, tu sedí.