Hamiltonovská kružnice a NP-úplnost
Velké důkazy téhle kapitoly o TSP — neexistence r-aproximace [L3.6] i faktory double-tree [L3.9] a Christofidese [L3.10] — stojí na jednom základním kameni: na problému Hamiltonovské kružnice. Dnes ten kámen položíme: přesná definice (EN 1:1 ze slidů, u zkoušky ji budeš citovat), co znamená „rozhodovací problém“ a „NP-úplný“, a proč nám právě HC poslouží jako zdroj těžkosti pro TSP. Žádný velký důkaz dnes — jen přesné pojmy, bez kterých by ses v důkazech [L3.5]/[L3.6] ztratil(a).
Okruh přes všechna města — formálně
Obchodní cestující chce objet všechna města a vrátit se domů, žádné město nenavštívit dvakrát. Pojmy na to už máš z [L0.3] Cesta, sled, tah, cyklus.
Zkus sám: vyber správný pojem z [L0.3] a zformuluj „okruh přes všechna města, každé právě jednou“ jako vlastnost grafu.
Hledáme kružnici (uzavřenou cestu — vrcholy se neopakují, začátek = konec), která navíc obsahuje všechny vrcholy grafu. Sled by směl města opakovat, tah by hlídal jen hrany — „každé město právě jednou“ říká přesně kružnice. Kružnici přes všechny vrcholy se říká Hamiltonovská.
Existence of Hamiltonian Circuit (HC, Hamiltonovská kružnice)
- Instance: Undirected graph $G$.
- Goal: Decide if Hamiltonian circuit (circuit visiting every node exactly once) exists in graph $G$.
Slide dodává: „The directed version of this problem is: (Hamiltonian cycle) for a directed graph“ — terminologie kurzu: circuit neorientovaně, cycle orientovaně [L0.3].
Jméno nese po Williamu Rowanu Hamiltonovi: jeho Icosian game (Hamilton's puzzle) byla hra „najdi okružní cestu po hranách dvanáctistěnu“ — slide 14 ji ukazuje jako rovinný graf (pohled dovnitř dvanáctistěnu jednou z jeho dvanácti stěn). Jako všechna platónská tělesa dvanáctistěn Hamiltonovskou kružnici má. Vyzkoušej si hledání na menším grafu:
Na trojbokém hranolu se to povedlo. Jenže HC je rozhodovací problém — a zajímavá je hlavně situace, kdy odpověď zní NE:
Zkus sám: dokaž, že „motýlek“ nahoře žádnou Hamiltonovskou kružnici nemá. (Nápověda: kolikrát by kružnice musela projít vrcholem $c$?)
Vrchol $c$ je artikulace: po jeho odebrání se graf rozpadne na dvě komponenty $\{a,b\}$ a $\{d,e\}$. Kružnice navštěvující všechny vrcholy by musela z levé komponenty do pravé a zase zpátky — a každý přechod mezi nimi vede přes $c$. Kružnice by tedy prošla vrcholem $c$ aspoň dvakrát, což definice kružnice zakazuje (každý vrchol právě jednou). HC neexistuje. $\blacksquare$
Všimni si, že tohle byl regulérní malý důkaz. U malých grafů NE-odpověď často zdůvodníš strukturou (artikulace, vrchol stupně 1…) — za chvíli uvidíš, že obecně je to mnohem horší.
Rozhodovací problém: odpověď je jen ANO/NE
HC se ptá „existuje?“ — odpověď je jediný bit, žádná cílová funkce. S rozhodovacími úlohami ses už potkal(a) u 2-Partition: rozhodovací ILP s cílem $\min 0$ [L0.8], [L1.1]. Slide 13 uvádí HC pod titulkem „Related Decision Problem“ — je to rozhodovací příbuzný optimalizačního TSP („najdi nejlevnější Hamiltonovskou kružnici v úplném grafu $K_n$“), který formálně zavedeme v [L3.4]. Tahle dvojice (rozhodovací HC ↔ optimalizační TSP) je přesně to, co budou důkazy [L3.5]/[L3.6] spřahovat.
Co vlastně dělá TSP (a HC) těžkým?
První podezřelý: kandidátů je příliš mnoho.
Zkus sám: kolik různých Hamiltonovských kružnic má úplný graf $K_n$? Spočítej to pro 4 města.
Kružnici zapíšeš jako pořadí měst. Start si můžeš zafixovat (kružnice je „kruhová“, nezáleží, kde ji začneš číst) — zbylá města zpermutuješ $(n-1)!$ způsoby — a každou kružnici jsi započítal(a) dvakrát (po směru a proti směru). Celkem $\tfrac{1}{2}(n-1)!$ — pro $n = 4$ jsou to $3$ kružnice (slide 16). Pro $n = 20$ už $\approx 6 \cdot 10^{16}$: hrubá síla nemá šanci.
Zkus sám: je tedy „exponenciálně mnoho kandidátů“ ta pravá příčina těžkosti? Porovnej s minimální kostrou na týchž 4 městech.
NE — a slide 16 to ukazuje krásným kontrastem: na 4 městech existují jen $\tfrac{1}{2}(n-1)! = 3$ Hamiltonovské kružnice, ale $n^{n-2} = 16$ koster (Cayleyho formule). Koster je víc než kružnic (a pro velká $n$ dramaticky: $n^{n-2}$ roste rychleji než $\tfrac{1}{2}(n-1)!$), přesto minimální kostru najde hladový algoritmus v polynomiálním čase [L0.5] Minimální kostra (MST). Velikost prostoru kandidátů těžkost nevysvětluje — záleží na struktuře problému. Slide 16 (EN 1:1): „What makes the TSP so hard? This question stimulates the study of NP-completeness.“
Třída NP: ANO-odpověď se dá rychle ověřit
Zkus sám: tvrdím, že konkrétní graf o 1000 vrcholech MÁ Hamiltonovskou kružnici. Najít ji neumíš. Co bych ti musel předat, abys mé tvrzení dokázal(a) zkontrolovat za pár vteřin?
Stačí, když ti předám tu kružnici samotnou — třeba jako pořadí vrcholů $v_1, v_2, \ldots, v_n$. Ty pak jen ověříš: (1) je v seznamu každý vrchol grafu právě jednou, (2) každá dvojice po sobě jdoucích vrcholů je spojena hranou, (3) hranou je spojen i poslední vrchol s prvním. To je pár průchodů seznamem — polynomiální čas, hledat nic nemusíš. Takovému „důkazu k předání“ se říká certifikát (certificate).
Přesně tenhle argument je na slidu 13 (EN 1:1): „HC belongs to NP problems. For each yes-instance $G$ we take any Hamiltonian circuit of $G$ as a certificate. To check whether a given edge set is in fact a Hamiltonian circuit of a given graph is obviously possible in polynomial time.“ Ověření certifikátu si přehraj krok za krokem:
- P — rozhodovací problémy řešitelné v polynomiálním čase (např. „existuje v grafu kostra?“, „existuje cesta $s \to t$?“).
- NP — rozhodovací problémy, u nichž lze ANO-odpověď ověřit v polynomiálním čase pomocí certifikátu. Hledat řešení může být těžké; zkontrolovat předložené řešení je snadné. Platí P ⊆ NP (kdo umí řešit, umí i ověřovat).
- NP-úplný (NP-complete) — problém, který (1) sám leží v NP a (2) je v NP nejtěžší: každý problém z NP se na něj dá polynomiálně převést. Polynomiální algoritmus pro jediný NP-úplný problém by znamenal $P = NP$.
- NP-těžký (NP-hard) — aspoň tak těžký jako NP-úplné problémy, ale nemusí sám ležet v NP; typicky optimalizační úlohy (ILP [L0.7], TSP) — výsledek optimalizace není ANO/NE, takže o „certifikátu ANO-odpovědi“ nemá smysl mluvit.
(Slidy kurzu tyto pojmy předpokládají a nedefinují — slovníček je vlastní shrnutí standardních definic v rozsahu, který K3 potřebuje. Slide 13 z něj používá přesně dvě věci: HC ∈ NP přes certifikát a „HC je NP-complete problem“.)
Zkus sám: funguje certifikát i obráceně — umíš mi krátkým „důkazem k předání“ doložit, že graf Hamiltonovskou kružnici NEMÁ?
Obecně ne — a v té asymetrii je celé kouzlo třídy NP. U motýlka výše jsme NE-odpověď zdůvodnili artikulací, jenže to byl šťastný speciální případ. Pro obecný graf žádný polynomiálně ověřitelný certifikát NE-odpovědi není znám: „dokladovat“ neexistenci znamená v principu vyloučit všech $\tfrac{1}{2}(n-1)!$ kandidátů. Definice NP mluví jen o ANO-instancích — zapamatuj si to, u zkoušky je to oblíbený chyták.
K čemu nám HC bude: zdroj těžkosti pro redukce
NP-úplnost HC není pro nás muzejní fakt — je to nástroj. Když chceme dokázat, že nějaký nový problém $X$ je těžký, nebudeme NP-úplnost budovat od nuly: vezmeme problém, o němž se to už ví (HC), a ukážeme polynomiální převod (redukci): z libovolné instance HC vyrobíme v polynomiálním čase instanci problému $X$ tak, aby odpovědi/výsledky korespondovaly. Kdyby pak $X$ šel řešit polynomiálně, šel by polynomiálně i HC — a bylo by $P = NP$.
Zkus sám (předkrm na [L3.5]): graf $G$ má $n$ vrcholů a chceš rozhodnout HC. Umíš z $G$ vyrobit instanci TSP — úplný graf $K_n$ s cenami hran — tak, aby hodnota optima prozradila, jestli HC v $G$ existuje?
Nápad ze slidu 18: vrcholy nech, graf zúplni a hrany oceň 1 (hrana byla v $G$), resp. 2 (hrana v $G$ nebyla). Okruh přes všechna města má $n$ hran, takže stojí $n$ právě tehdy, když použil samé jedničky — tedy samé hrany původního grafu — tedy právě tehdy, když $G$ má Hamiltonovskou kružnici. Optimum $= n$ ⟺ HC existuje. Celý důkaz (včetně toho, proč z vah $\{1,2\}$ plyne silná NP-těžkost) provedeme v [L3.5]; zostřená varianta s vahami $2 + (r-1)n$ pak v [L3.6] zabije i r-aproximace.
S redukcemi z Hamiltonovských problémů ses ostatně už dvakrát potkal(a) v K2: nejkratší cesta se záporným cyklem „pozná“ Hamiltonovskou kružnici [L2.1] a nejdelší cesta s jednotkovými vahami „pozná“ Hamiltonovskou cestu [L2.17]. Teď už víš, jak se ten argument jmenuje a odkud se těžkost bere.
Pozor: nebezpečné polopravdy o NP- „NP znamená ne-polynomiální.“ NE — NP je „nedeterministicky polynomiální“ ≈ ANO-odpověď ověřitelná polynomiálně certifikátem. Celé P leží uvnitř NP.
- „NP-úplný = prakticky neřešitelný.“ NE — slidy 3–12 ukazují optimálně vyřešené TSP instance až s 24 978 městy (Švédsko 2004). NP-úplnost říká jen: polynomiální algoritmus pro všechny instance není znám (a nejspíš neexistuje). Chytré exponenciální metody (B&B [L0.7], ILP modely [L3.4]) konkrétní instance zvládají.
- Směr redukce: těžkost $X$ dokazuješ převodem ZNÁMÉHO těžkého problému NA $X$ (HC → TSP): „kdybys uměl $X$, uměl bys HC“. Převod opačným směrem (TSP → HC) o těžkosti TSP neříká nic.
- „Certifikát funguje pro obě odpovědi.“ NE — definice NP mluví jen o ANO-instancích; krátký doklad NEexistence HC obecně neznáme.
Key takeaways — L3.3- HC (Existence of Hamiltonian Circuit): Instance = undirected graph $G$; Goal = decide if Hamiltonian circuit (circuit visiting every node exactly once) exists. Orientovaná verze se jmenuje Hamiltonian cycle. HC je NP-úplný.
- HC ∈ NP přes certifikát: u ANO-instance předlož kružnici (pořadí vrcholů) — kontrola „každý vrchol právě jednou + po sobě jdoucí dvojice jsou hrany + uzavření“ je polynomiální. Pro NE-odpověď krátký certifikát obecně neznáme.
- Počet kandidátů těžkost nevysvětluje: $\tfrac{1}{2}(n-1)!$ kružnic vs. $n^{n-2}$ koster (na 4 městech 3 vs. 16) — koster je víc, a MST je přesto polynomiální [L0.5].
- Z HC budeme redukovat na TSP: ceny 1/2 dají silnou NP-těžkost [L3.5], ceny $2+(r-1)n$ neexistenci r-aproximace [L3.6]. Redukce vede vždy ze známého těžkého problému na nový.
Existence of Hamiltonian Circuit (HC). Instance: Undirected graph $G$. Goal: Decide if Hamiltonian circuit (circuit visiting every node exactly once) exists in graph $G$.
Show that HC belongs to NP problems: propose a certificate for a yes-instance and explain why it can be checked in polynomial time.
a) Co je v zadání?
Teoretická mini-úloha: nemáš HC řešit, jen doložit příslušnost do NP — tedy říct, co je certifikát ANO-instance a popsat polynomiální kontrolu. Přesně tahle věta se hodí i jako první krok u ústní otázky na NP-těžkost TSP.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice HC, pojem certifikátu a třídy NP.
- [L0.3] Cesta, sled, tah, cyklus — co přesně je kružnice.
c) Jak nad úlohou uvažovat?
Odpověz na tři otázky: CO předám (datová struktura certifikátu), JAK to zkontroluji (seznam testů — nezapomeň žádný!), PROČ je kontrola polynomiální (odhad počtu operací). Pozor na nejčastější opomenutí: kontrola, že posloupnost je uzavřená (poslední–první je taky hrana) a že obsahuje všechny vrcholy, každý právě jednou.
d) Úplné řešení
Certifikát. Pro ANO-instanci $G$ vezmeme libovolnou její Hamiltonovskou kružnici, zapsanou jako posloupnost vrcholů $v_1, v_2, \ldots, v_n$ (slide 13: „we take any Hamiltonian circuit of $G$ as a certificate“; ekvivalentně lze předat množinu hran kružnice).
Kontrola. Ověříme:
- posloupnost má délku $n = |V(G)|$ a každý vrchol grafu v ní je právě jednou (jeden průchod + pole příznaků, $O(n)$);
- pro každé $i = 1, \ldots, n-1$ je $\{v_i, v_{i+1}\} \in E(G)$ a navíc $\{v_n, v_1\} \in E(G)$ — uzavření kružnice ($n$ dotazů na hranu; s maticí sousednosti $O(1)$ na dotaz, tedy $O(n)$, se seznamy sousedů $O(n + m)$ celkem).
Projde-li obojí, předložená posloupnost je kružnice procházející každým vrcholem právě jednou — Hamiltonovská kružnice, a odpověď ANO je doložena. Kontrola běží v čase $O(n + m)$, tj. polynomiálně ve velikosti vstupu. Certifikát má velikost $O(n)$, tedy také polynomiální. Proto HC ∈ NP. $\blacksquare$
Pozn.: tím je hotová „snadná půlka“ NP-úplnosti. Druhá půlka (každý problém z NP se na HC polynomiálně převede) se v kurzu nedokazuje — bereme ji jako známý fakt (slide 13: „NP-complete problem“) a stavíme na ní redukce v [L3.5]/[L3.6].
For each of the two graphs below decide whether a Hamiltonian circuit exists. If YES, provide a certificate; if NO, prove it.
Graph A: $V = \{1,2,3,4,5,6\}$, $E = \{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,1\},\{1,4\},\{2,5\}\}$.
Graph B: $V = \{u_1, u_2, w_1, w_2, w_3\}$, $E = \{\{u_i, w_j\} : i \in \{1,2\},\ j \in \{1,2,3\}\}$ (every $u$ is connected to every $w$, no other edges).
a) Co je v zadání?
Dva malé grafy; u každého rozhodni HC. U ANO se chce certifikát (pořadí vrcholů), u NE důkaz — přesně dvojice dovedností z této lekce. Graf B je bipartitní (dvoubarevný): hrany vedou jen mezi skupinou $u$ a skupinou $w$.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice HC, certifikát, důkazy NEexistence na malých grafech.
- [L0.3] — kružnice; [L0.2] Stupeň vrcholu — počítání hran u vrcholu.
c) Jak nad úlohou uvažovat?
Graf A: 6 vrcholů na kružnici 1–2–…–6 plus dvě „příčky“ — zkus nejdřív obvodovou kružnici. Graf B: sleduj, jak se na libovolné kružnici střídají skupiny $u$ a $w$ (jiné hrany než $u$–$w$ nejsou). Co to říká o počtech vrcholů z obou skupin na uzavřené kružnici?
d) Úplné řešení
Graf A: ANO. Certifikát: $1, 2, 3, 4, 5, 6$ (a zpět do $1$). Kontrola: všech 6 vrcholů právě jednou; dvojice $\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,6\}$ i uzavírací $\{6,1\}$ jsou v $E$. Příčky $\{1,4\}, \{2,5\}$ vůbec nepotřebujeme — certifikát nemusí použít všechny hrany grafu, jen doložit kružnici.
Graf B: NE. Všechny hrany vedou mezi skupinami $\{u_1,u_2\}$ a $\{w_1,w_2,w_3\}$, takže každá kružnice vrcholy obou skupin striktně střídá: $u, w, u, w, \ldots$ Uzavřená střídavá kružnice obsahuje stejný počet vrcholů z obou skupin. Hamiltonovská kružnice by ale musela obsahovat $2$ vrcholy $u$ a $3$ vrcholy $w$ — to se střídáním nejde dohromady ($2 \neq 3$). HC neexistuje. $\blacksquare$
Alternativně přes stupně: kružnice používá u každého vrcholu přesně 2 hrany; oba vrcholy $u_1, u_2$ by dohromady poskytly 4 „konektory“, jenže tři vrcholy $w$ potřebují $3 \cdot 2 = 6$ hran a všechny vedou do $u$ — spor $6 \neq 4$ [L0.2].
Obecné poučení (hodí se k ústní): bipartitní graf s nestejně velkými partitami nemá HC; graf s artikulací (motýlek z výkladu) nemá HC. Krátké NE-důkazy existují jen díky speciální struktuře — pro obecný graf je nemáme.