Directed Chinese Postman jako MCF
V [L4.10] jsme listonoše slíbili jako třetí „rukopis“ MCF (po max flow a nejkratší cestě) — dnes ten slib splníme. Je to formulační úloha: u zkoušky se nechce běh algoritmu, ale přesný převod na MCF a věta o tom, jak se z toku poskládá trasa. Obě ingredience už znáš: pětici $(G, l, u, c, b)$ z [L4.10] a Eulerovský tah z [L3.8c].
Úloha: projet každou ulici (zadání 1:1)
Leaving from their post office, a postal carrier needs to pass every street in the given direction, delivering and collecting letters, and then returning to the post office. The carrier would like to cover this route by traveling the minimum possible distance.
Formally, given a directed graph $G = (V, E)$, where each edge $(i, j)$ has an associated nonnegative length $c_{ij}$, we wish to find an edge progression of minimum length that starts at some node (the post office), visits each arc of the graph at least once, and returns to the starting node.
Klíčové slovo je edge progression (sled hran): hledáme uzavřený sled — posloupnost na sebe navazujících orientovaných hran, která se vrátí do startu. Vrcholy i hrany se ve sledu smějí opakovat (na rozdíl od cesty) — pošťák klidně projde křižovatkou pětkrát, jen ho každý metr navíc stojí čas.
Zkus sám: „projdi všechno a vrať se s minimální délkou“ — to zní skoro jako TSP [L3.4]. V čem se pošťák od obchodního cestujícího liší a proč je ten rozdíl tak zásadní?
TSP chce navštívit každý vrchol (právě jednou — Hamiltonovský okruh [L3.3]), pošťák chce projet každou hranu (aspoň jednou — Eulerovský motiv [L3.8c]). A ten rozdíl je propastný: TSP je silně NP-těžký [L3.5], kdežto směrovaný pošťák se převede na MCF a vyřeší polynomiálně. Stejná rétorika zadání, opačný svět složitosti — pamatuj si: vrcholy = Hamilton = těžké, hrany = Euler = lehké.
Zkus sám: kdy má pošťák úplné štěstí — kdy existuje trasa, která projede každou ulici právě jednou (nic se neopakuje)?
Přesně tehdy, když je graf eulerovský digraf: v každém vrcholu se počet výstupních hran rovná počtu vstupních, $|\delta^+(v)| = |\delta^-(v)|$. Je to směrovaná obdoba podmínky „všechny stupně sudé“ z [L3.8c]: kolikrát do křižovatky vjedeš, tolikrát z ní musíš vyjet — a každý vjezd i výjezd spotřebuje jednu dosud neprojetou hranu. Slide 30 to říká doslova (viz box níže). Jakmile je někde $\delta^+ \ne \delta^-$, některé ulice se musí jet vícekrát — a otázka zní, které a kolikrát, aby délka navíc byla minimální. Přesně tohle za nás rozhodne MCF.
Formulace jako minimum cost flow
Zkus sám: navrhni pětici $(G, l, u, c, b)$ z [L4.10] sám. Nápověda: co znamená proměnná $f(e)$? Proč úloha nemá žádný zdroj ani spotřebič? A jak vynutíš „každou ulici aspoň jednou“?
Nech graf $G$ i ceny tak, jak jsou, a čti $f(e)$ jako počet průjezdů hranou $e$. ① Trasa je uzavřená — do každé křižovatky pošťák tolikrát vjede, kolikrát vyjede — takže platí čistý Kirchhoff [L4.1] bez bilancí: $b(v) = 0$ pro všechny vrcholy, je to cirkulace. ② „Každou ulici aspoň jednou“ = dolní mez $l(e) = 1$; shora nic neomezuje, $u(e) = \infty$. ③ Cena $c(e)$ = délka ulice, minimalizujeme $\sum_e c(e) f(e)$ = celkovou ujetou vzdálenost. Žádná konstrukce pomocných uzlů — síť je město samo.
The Chinese Postman Problem (A postman has to deliver the mail within his district given by strongly connected directed graph. To do this, he must start at the post office, go along each street at least once, and finally return to the post office. The problem is to find a postman's tour of minimum length.) can be reduced to the Min-Cost Flow:
- Set $b(v) = 0 \ \forall v \in V$.
- Set $l(e) = 1$, $u(e) = \infty$ and $c(e)$ is weight of edge $\forall e \in E$.
There is a closed postman's tour using each edge exactly once (i.e., Eulerian walk which is a closed walk containing every edge) iff every vertex has equal indegree and outdegree (i.e. Eulerian digraph).
Zapsáno jako model (vzorové řešení zkoušky používá $x_{ij}$ = number of times arc $(i,j)$ is traversed):
$$\min \sum_{(i,j) \in E} c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_{(v,j) \in E} x_{vj} - \sum_{(i,v) \in E} x_{iv} = 0 \;\; \forall v \in V, \qquad 1 \le x_{ij} \le \infty, \;\; x_{ij} \in \mathbb{Z}.$$
Celočíselnost přitom dostaneš zadarmo: meze i bilance jsou celočíselné, takže existuje celočíselné optimum (Integral Flow Theorem, citovali jsme ho v [L4.5]) — a cycle canceling [L4.11] ho najde sám, protože startuje z celočíselného toku a augmentuje o celá $\gamma$. „Počet průjezdů“ tedy vyjde jako pořádné celé číslo, ne $1{,}5$ průjezdu.
Kudy tečou duplikace: nevyvážené vrcholy
Zkus sám: substituuj $y(e) = f(e) - 1 \ge 0$ („kolikrát navíc hranu jedu“) a dosaď do Kirchhoffa $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = 0$. Jaká bilanční rovnice vyjde pro $y$ — a co říká o vrcholech s $\delta^+ \ne \delta^-$?
Dosazení $f = 1 + y$ dá $\sum_{\delta^+(v)} y - \sum_{\delta^-(v)} y = |\delta^-(v)| - |\delta^+(v)|$. Duplikační tok $y$ je tedy obyčejný MCF s bilancemi $b_y(v) = |\delta^-(v)| - |\delta^+(v)|$ (rozepsání je naše — slidy uvádějí jen cirkulační tvar, oba modely jsou ale ekvivalentní): vrchol s přebytkem vstupů ($\delta^- > \delta^+$) je zdrojem duplikací — pošťák tam vjede vícekrát, než má kudy vyjet, takže nějaký výjezd musí zopakovat; vrchol s přebytkem výstupů je spotřebičem — musí se do něj vracet. Vyvážené vrcholy mají $b_y = 0$ a duplikace jimi jen protékají. MCF pak pošle duplikace z přebytkových do deficitních vrcholů po nejlevnějších cestách — to je celé kouzlo.
To je přesně intuice „vyvážení stupňů“: úloha se ptá, jak nejlevněji dorovnat $\delta^+ = \delta^-$ všude — a dorovnání se kupuje opakovanými průjezdy existujících ulic.
Příklad od začátku do konce
Zkouškové zadání žádný konkrétní graf nedává (je formulační) — následující čtyřvrcholová instance je naše vlastní, abychom celý řetěz audit stupňů → MCF → Eulerovský tah viděli na číslech:
Zkus sám: udělej audit stupňů. Které vrcholy jsou nevyvážené, kdo je zdroj a kdo spotřebič duplikací — a kudy duplikace poteče?
$P$: $\delta^+ = 1$, $\delta^- = 1$ ✓; $B$: $1 = 1$ ✓. $A$: $\delta^- = 2$ (z $P$ a z $C$), ale $\delta^+ = 1$ → přebytek vstupů, $b_y(A) = +1$, zdroj duplikace. $C$: $\delta^+ = 2$, $\delta^- = 1$ → $b_y(C) = -1$, spotřebič. Jedna jednotka duplikací musí téct z $A$ do $C$; jediná (a tedy nejlevnější) cesta je $A \to B \to C$ za $1 + 2 = 3$. Výsledek: $f(A{\to}B) = f(B{\to}C) = 2$, jinde $f = 1$, cena $\sum c \cdot f = 7 + 3 = 10$.
Zkus sám: z $C$ vede do $A$ hrana $C \to A$ za 1 — proč se pošťák nemůže z $C$ prostě „vrátit“ po hraně $B \to C$ zpátky do $B$, když už tam jednou jel?
Protože hrana $B \to C$ je orientovaná — projet se dá jen po směru (zadání: „pass every street in the given direction“). V tom je celé „directed“: opakované průjezdy se smí kupovat jen u existujících šipek, couvat nelze. (A pozor na záměnu: hrana $C \to A$ pošťákovi s duplikací nepomůže — ta teče z $A$ do $C$, v protisměru k ní.) Proto duplikace musí objet $A \to B \to C$, i když „vzdušnou čarou“ proti šipce by to bylo kratší.
Celý řetěz krok za krokem:
Z toku na trasu: Eulerovský tah v multigrafu
Druhá půlka zkouškové otázky zní „describe how to obtain the minimum-length edge progression from the minimum-cost flow“. Vzorové řešení (banka #25, 1:1):
After solving, construct a directed multigraph containing $x_{ij}$ copies of every arc $(i, j)$. Since flow conservation gives $\text{outdegree}(v) = \text{indegree}(v)$ for all $v$, the multigraph is balanced. If the original graph is strongly connected, the multigraph has an Eulerian closed walk. This Eulerian walk is the required postman route.
There is no source or sink, because the route must be closed.
Tah pak sestavíš Hierholzerovým skládáním okruhů, které znáš z [L3.8c] — jen místo „sudé stupně“ hlídáš $\delta^+ = \delta^-$ (což ti Kirchhoff zaručil za odměnu zadarmo). Délka tahu = projde každou kopii hrany právě jednou = $\sum_e c(e) f(e)$ = cena toku, takže trasa je opravdu minimální.
Nebezpečné polopravdy1) Bez $l(e) = 1$ se to rozpadne: s $l = 0$ je nejlevnější cirkulace nulový tok za 0 — pošťák zůstane doma. „Aspoň jednou“ kóduje právě dolní mez. 2) Žádný zdroj a spotřebič: $b(v) = 0$ všude — trasa je uzavřená. Kdo přidá $s$ a $t$, modeluje jinou úlohu (otevřenou trasu). 3) $f(e)$ není 0/1: je to počet průjezdů, proto $u(e) = \infty$; duplikace = $f(e) - 1$. Neplést s párovacími sítěmi z [L4.12], kde kapacita 1 byla podstatná. 4) Potřebuješ silnou souvislost (slide ji předpokládá: „district given by strongly connected directed graph“) — jinak se z některé ulice nelze vrátit a přípustná cirkulace s $l = 1$ vůbec neexistuje. 5) Tohle je směrovaná verze. Neorientovaný čínský pošťák je jiná úloha (řeší se párováním vrcholů lichého stupně) a tahle redukce se na ni 1:1 použít nedá — u zkoušky si v zadání všimni „in the given direction“.
Key takeaways — L4.13- Directed Chinese postman: uzavřený sled (edge progression) minimální délky, který projede každou orientovanou hranu ≥1×. Bez opakování to jde právě tehdy, když je graf eulerovský digraf: $|\delta^+(v)| = |\delta^-(v)|$ všude (směrovaná obdoba [L3.8c]).
- Redukce na MCF (slide 30): $b(v) = 0$ pro všechny vrcholy (cirkulace, žádný zdroj/spotřebič), $l(e) = 1$, $u(e) = \infty$, $c(e)$ = délka; $f(e)$ = počet průjezdů hranou. Celočíselnost zadarmo (Integral Flow Theorem [L4.5]).
- Substituce $y = f - 1$: duplikace jsou MCF s bilancemi $b_y(v) = |\delta^-(v)| - |\delta^+(v)|$ — nevyvážené vrcholy jsou zdroje (přebytek vstupů) a spotřebiče (přebytek výstupů) duplikací; MCF je propojí nejlevnějšími cestami.
- Z toku na trasu: multigraf s $f(e)$ kopiemi hran je díky Kirchhoffovi vyvážený; je-li $G$ silně souvislý, existuje v něm uzavřený Eulerovský tah [L3.8c] = hledaná trasa o délce $\sum_e c(e) f(e)$.
- Hrany = Euler = polynomiální (MCF + cycle canceling [L4.11]); vrcholy = Hamilton/TSP = NP-těžké [L3.5].
Leaving from their post office, a postal carrier needs to pass every street in the given direction, delivering and collecting letters, and then returning to the post office. The carrier would like to cover this route by traveling the minimum possible distance.
Formally, given a directed graph $G = (V, E)$, where each edge $(i, j)$ has an associated nonnegative length $c_{ij}$, we wish to find an edge progression of minimum length that starts at some node (the post office), visits each arc of the graph at least once, and returns to the starting node. Formulate as a minimum cost flow problem and describe how to obtain the minimum-length edge progression from the minimum-cost flow.
a) Co je v zadání?
Dvě explicitní odevzdávky: ① formulace — zapsat pošťáka jako MCF (proměnné, účelová funkce, Kirchhoff, meze, bilance); ② rekonstrukce — slovně popsat, jak se z optimálního toku dostane trasa. Žádný konkrétní graf, žádný výpočet — je to „papírová“ formulační úloha.
b) Co k tomu budeme potřebovat?
- Tato lekce — celá (takeaways).
- [L4.10] Minimum Cost Flow + reziduální graf s cenami — pětice $(G, l, u, c, b)$ a LP tvar.
- [L3.8c] Eulerovský tah a zdvojení hran — proč vyváženost ⟹ uzavřený tah.
- [L4.11] Cycle canceling — kdyby padla doplňující otázka „a jak ten MCF vyřešíš?“.
c) Jak nad úlohou uvažovat?
Začni významem proměnné: $x_{ij}$ = kolikrát hranou projedu. Pak tři rozhodnutí, každé s jednou větou zdůvodnění: uzavřená trasa ⟹ čistý Kirchhoff a $b \equiv 0$ (žádný zdroj/spotřebič); „aspoň jednou“ ⟹ $l = 1$; nic neomezuje shora ⟹ $u = \infty$. U rekonstrukce nezapomeň na obě podmínky existence tahu: vyváženost (dá Kirchhoff) a silnou souvislost (předpoklad zadání) — a na větu, proč je délka tahu rovna ceně toku.
d) Úplné řešení (dle vzorového řešení banky #25)
① Model (minimum-cost circulation). Proměnná $x_{ij} \in \mathbb{Z}$ = počet průjezdů hranou $(i,j)$:
$$\min \sum_{(i,j)\in E} c_{ij} x_{ij}$$
za podmínek zachování toku v každém vrcholu a dolních mezí:
$$\sum_{(v,j)\in E} x_{vj} - \sum_{(i,v)\in E} x_{iv} = 0 \quad \forall v \in V, \qquad 1 \le x_{ij} \le \infty.$$
Je to minimum cost flow (cirkulace) s $b(v) = 0$ pro všechna $v$, $l(e) = 1$, $u(e) = \infty$ a cenami $c$. Zdroj ani spotřebič neexistují, protože trasa musí být uzavřená. Meze a bilance jsou celočíselné ⟹ existuje celočíselné optimum ([L4.5]).
② Rekonstrukce trasy. Z optimálního toku postav orientovaný multigraf s $x_{ij}$ kopiemi každé hrany $(i, j)$. Kirchhoff dává $\text{outdegree}(v) = \text{indegree}(v)$ pro všechna $v$, multigraf je tedy vyvážený; je-li původní graf silně souvislý, má multigraf uzavřený Eulerovský tah ([L3.8c], směrovaná verze). Tento Eulerovský tah je hledaná trasa pošťáka: projede každou kopii hrany právě jednou, tedy každou hranu $(i,j)$ právě $x_{ij} \ge 1$ krát, a jeho délka je $\sum c_{ij} x_{ij}$ = cena toku ⟹ minimální.
The figure shows the street network of a district as a directed graph $G$; the label of each arc is its length. The postman starts at node 1 (the post office), must traverse every arc at least once in its direction, and return to node 1.
(i) Decide whether the postman can cover the district without traversing any arc twice. (ii) Formulate the problem as a minimum cost flow problem. (iii) Find the optimal flow and the minimum route length. (iv) Write down one minimum-length postman route.
a) Co je v zadání?
Konkrétní město na 6 křižovatkách a 9 jednosměrkách. Postupně: rozhodnout existenci tahu bez opakování (i), zformulovat MCF (ii), najít optimum (iii) a vypsat trasu (iv) — přesně řetěz z lekce.
b) Co k tomu budeme potřebovat?
- Tato lekce — audit stupňů, formulace, rekonstrukce (takeaways).
- [L4.10] — pětice MCF.
- [L3.8c] — skládání Eulerovského tahu.
c) Jak nad úlohou uvažovat?
(i) je čistý audit: spočítej $\delta^+$ a $\delta^-$ každého vrcholu. (iii) nemusíš řešit cycle cancelingem od nuly — najdi nevyvážené vrcholy a uvědom si, že duplikace = jednotka toku ze zdroje duplikací do spotřebiče po nejlevnější cestě; tady se nabízejí dvě konkurenční cesty, porovnej je. (iv) slep tah Hierholzerem: jeď okruh, a kdykoli projíždíš vrcholem s nevyčerpanými kopiemi, vlož boční okruh.
d) Úplné řešení (vlastní — přiznáno)
(i) Ne. Audit stupňů: vrchol 1 má $\delta^+ = 2$ (hrany do 2, 3), ale $\delta^- = 3$ (z 4, 5, 6); vrchol 4 má $\delta^+ = 3$ (do 1, 5, 6), ale $\delta^- = 2$ (z 2, 3). Vrcholy 2, 3, 5, 6 jsou vyvážené ($1 = 1$). Graf není eulerovský digraf ⟹ bez opakování to nejde.
(ii) $f(e)$ = počet průjezdů hranou $e$; minimalizuj $\sum_e c(e) f(e)$ při Kirchhoffovi $\sum_{\delta^+(v)} f - \sum_{\delta^-(v)} f = 0$ $\forall v$ a mezích $1 \le f(e) \le \infty$, $f(e) \in \mathbb{Z}$ — tedy MCF s $b \equiv 0$, $l = 1$, $u = \infty$.
(iii) Duplikace $y = f - 1$: bilance $b_y(v) = |\delta^-| - |\delta^+|$ dávají $b_y(1) = +1$ (zdroj), $b_y(4) = -1$ (spotřebič), jinde 0. Jedna jednotka z 1 do 4: cesta $1 \to 2 \to 4$ stojí $1 + 1 = 2$, cesta $1 \to 3 \to 4$ stojí $3 + 2 = 5$ ⟹ MCF vybere levnější. Optimum: $f(1{\to}2) = f(2{\to}4) = 2$, ostatních sedm hran $f = 1$. Délka $= \sum_e c(e) + 2 = 14 + 2 = \mathbf{16}$. (Kontrola optimality: v $G_f$ jsou zpětné hrany $2 \to 1$ za $-1$ a $4 \to 2$ za $-1$; každý cyklus s nimi má cenu $\ge 0$ — např. $1 \to 3 \to 4 \to 2 \to 1$ stojí $3 + 2 - 1 - 1 = +3$ — žádný záporný cyklus, tok je optimální [L4.11].)
(iv) Multigraf = graf + druhé kopie hran $1 \to 2$ a $2 \to 4$; všechny vrcholy vyvážené (1 i 4 mají $\delta^+ = \delta^- = 3$). Jeden Eulerovský tah z pošty:
$$1 \to 2 \to 4 \to 5 \to 1 \to 3 \to 4 \to 6 \to 1 \to 2 \to 4 \to 1$$
s délkou $1 + 1 + 1 + 1 + 3 + 2 + 2 + 1 + 1 + 1 + 2 = 16$. Každá šipka projeta aspoň jednou ($1{\to}2$ a $2{\to}4$ přesně dvakrát), start i cíl v uzlu 1. ✓