Cesta, sled, tah, cyklus
Prerekvizita: [L0.1] Co je graf — vrcholy, hrany, orientace.
Procházka grafem
Spousta úloh (nejkratší cesty, TSP, Eulerovský tah) je o „procházení“ grafu. Nejobecnější procházka je sled (v kurzu anglicky edge progression, v běžné literatuře walk): posloupnost $$v_1, e_1, v_2, e_2, \ldots, v_k, e_k, v_{k+1},$$ kde každá $e_i$ je hrana mezi $v_i$ a $v_{i+1}$ (u digrafu hrana $(v_i, v_{i+1})$). Vrcholy i hrany se smí libovolně opakovat. Sled je uzavřený (closed), pokud $v_1 = v_{k+1}$.
Zkus sám: co kdybychom zakázali opakování hran? A co opakování vrcholů — je to silnější, nebo slabší podmínka?
Zákaz opakování hran dává tah; zákaz opakování vrcholů dává cestu. Zákaz opakování vrcholů je silnější: když se neopakuje žádný vrchol, nemůže se opakovat ani hrana (hrana je určena svými konci). Každá cesta je tedy tah a každý tah je sled — naopak to neplatí.
Tah a cesta
- Tah (ve slidech kurzu anglicky walk, v jiné literatuře trail): sled, ve kterém se žádná hrana neobjeví víc než jednou ($e_i \ne e_j$ pro $i \ne j$). Vrcholy se opakovat smí. Klasický příklad: Eulerovský tah projde každou hranu právě jednou (potkáš ho u Christofidese v K3).
- Cesta (path): tah, ve kterém se žádný vrchol neobjeví víc než jednou ($v_i \ne v_j$). Tohle hledáme u nejkratších cest (K2).
Hierarchie: cesta ⊂ tah ⊂ sled.
Pozor na anglickou terminologiiSlidy kurzu používají edge progression = sled a walk = tah (bez opakování hran). Většina učebnic ale používá walk = sled a trail = tah. V písemce čti definici v zadání; česky je to jednoznačné: sled / tah / cesta.
Cyklus (kružnice)
Uzavřená procházka bez opakování vrcholů (kromě začátku = konce) je cyklus. Slidy rozlišují podle orientace: circuit (kružnice) = uzavřený neorientovaný „okruh“ s navzájem různými vrcholy $v_1, \ldots, v_k$; cycle (cyklus) = totéž orientovaně (všechny hrany po směru). Neformálně: cyklus = „uzavřená cesta“.
Zkus sám: proč u nejkratších cest hledáme cestu, a ne jen sled?
Při nezáporných cenách hran se vyplácí vrcholy neopakovat — každé zopakování úsek jen prodraží (nebo nechá stejně drahý), takže nejkratší sled lze vždy zkrátit na cestu. Problém nastane se zápornými cenami: obsahuje-li graf záporný cyklus, sled ho může obíhat donekonečna a „délka“ padá k $-\infty$ — proto se tam musí vynutit cesta a úloha se stává těžkou. Detaily v kapitole K2 (nejkratší cesty).
Key takeaways — L0.3- Sled (edge progression; jinde walk): posloupnost $v_1, e_1, \ldots, e_k, v_{k+1}$ — vrcholy i hrany se smí opakovat.
- Tah (ve slidech walk; jinde trail): sled bez opakování hran.
- Cesta (path): sled bez opakování vrcholů. Hierarchie: cesta ⊂ tah ⊂ sled.
- Cyklus/kružnice (cycle/circuit): uzavřená cesta — $v_1 = v_{k+1}$, jinak se žádný vrchol neopakuje; cycle orientovaně, circuit neorientovaně.
Recall the definitions: “Edge progression (sled) is a sequence $v_1, e_1, v_2, e_2, \ldots, v_k, e_k, v_{k+1}$ such that $e_i = (v_i, v_{i+1}) \in E(G)$ or $e_i = \{v_i, v_{i+1}\} \in E(G)$ for all $i$. Directed (undirected) walk (tah) is directed (undirected) edge progression, where no edge appears more than once, i.e. $e_i \ne e_j$ for all $1 \le i < j \le k$. Directed (undirected) path (cesta) is directed (undirected) walk, where no node appears more than once, i.e. $v_i \ne v_j$ for all $1 \le i < j \le k+1$.”
For the digraph drawn above (edges $(a,b), (b,c), (c,a), (b,d), (d,c), (c,e)$), classify each of the following sequences as an edge progression, a walk, a path, or none of them (state the strongest applicable term):
- $a, b, d, c, e$
- $a, b, c, a, b, d$
- $b, c, a, b, d, c, e$
- $a, b, d, e$
a) Co je v zadání?
Dostaneš digraf a čtyři posloupnosti vrcholů. Pro každou rozhodni, zda je to sled / tah / cesta (uveď nejsilnější platný pojem), nebo vůbec nic (např. když některá hrana v grafu neexistuje).
b) Co k tomu budeme potřebovat?
- Tato lekce — definice sled/tah/cesta a hierarchie cesta ⊂ tah ⊂ sled.
- [L0.1] Co je graf — orientovaná hrana má směr.
c) Jak nad úlohou uvažovat?
Postupuj testem od nejslabšího: (1) Existují všechny použité hrany ve správném směru? Pokud ne, není to ani sled. (2) Opakuje se hrana? Pokud ne, je to tah. (3) Opakuje se vrchol? Pokud ne, je to cesta.
d) Úplné řešení
- $a{\to}b{\to}d{\to}c{\to}e$: hrany $(a,b), (b,d), (d,c), (c,e)$ existují, žádný vrchol se neopakuje → cesta (tedy i tah a sled).
- $a{\to}b{\to}c{\to}a{\to}b{\to}d$: hrany existují, ale hrana $(a,b)$ je použita dvakrát → jen sled (není tah).
- $b{\to}c{\to}a{\to}b{\to}d{\to}c{\to}e$: všechny hrany $(b,c), (c,a), (a,b), (b,d), (d,c), (c,e)$ existují a každá je použita jednou → tah; vrcholy $b$ a $c$ se opakují, takže to není cesta.
- $a{\to}b{\to}d{\to}e$: hrana $(d,e)$ v grafu neexistuje (existuje jen $(d,c)$) → nic, není to ani sled.