Ekvivalence definic stromu [NICE]
Z [L0.4] Strom, kostra, les, DAG znáš definici: tree (strom) = souvislý graf bez kružnice, a jako fakty jsme tam přijali „strom má $n-1$ hran“ a „mezi každou dvojicí vrcholů vede právě jedna cesta“. Dnes všechny tyhle tváře stromu dokážeme — je to méně častá, ale férová otázka k ústní (na slidech 61–62 je plný důkaz). Bonus: dva fakty z důkazu („hrana na kružnici jde smazat bez ztráty souvislosti“, „hrana uvnitř komponenty uzavře kružnici“) jsi už mlčky používal u MST i u [L3.9] double-tree.
Sedm tváří stromu (slide 61)
Let $G$ be an undirected graph with $n$ nodes, then the following statements are equivalent:
- (a) $G$ is a tree.
- (b) $G$ has $n - 1$ edges and no circuit.
- (c) $G$ has $n - 1$ edges and is connected.
- (d) $G$ is connected and while removing any edge it will not be connected anymore.
- (e) $G$ is a minimal graph which has $\delta(X) \ne \emptyset$ for all $\emptyset \ne X \subset V(G)$
- (f) $G$ is circuit-free and the addition of any edge creates a circuit.
- (g) $G$ contains a unique path between any pair of vertices.
Většinu tvrzení přečteš rovnou: (d) říká „minimálně souvislý“ (každá hrana je nepostradatelná), (f) říká „maximálně acyklický“ (žádná hrana se už nevejde). Jediný nový zápis je $\delta(X)$ v (e): zobecnění okolí vrcholu $\delta(v)$ z [L0.2] na množinu vrcholů — řez (cut) $$\delta(X) = \{\,\{u,v\} \in E(G) : u \in X,\ v \notin X\,\}$$ = hrany s právě jedním koncem v $X$.
Zkus sám: přečti (e) „lidsky“. Co znamená „$\delta(X) \ne \emptyset$ pro každou neprázdnou vlastní $X \subset V(G)$“ — a co k tomu přidává slovo „minimal“?
„Každý řez je neprázdný“ je jen jiný způsob, jak říct souvislost: kdyby pro nějakou $X$ bylo $\delta(X) = \emptyset$, nevede z $X$ ven žádná hrana a vrcholy v $X$ se s těmi venku nikdy nepropojí. A naopak: je-li graf nesouvislý, vezmi za $X$ jednu komponentu — její řez je prázdný. Slovo minimal pak říká, že po smazání kterékoli hrany už tahle vlastnost neplatí. Takže (e) je vlastně (d) převlečené do jazyka řezů.
Prohlédni si všech sedm tváří na jednom stromě ($n = 6$):
Pozor na polopravdu: „$n-1$ hran = strom“
V (b) i (c) má počet hran $n-1$ vždy parťáka (bez kružnice / souvislost). Není to zbytečná opatrnost?
Zkus sám: najdi graf s $n = 6$ vrcholy a $m = 5 = n-1$ hranami, který NENÍ strom.
Trojúhelník + oddělená cesta: $\{A,B,C\}$ spojené do kružnice (3 hrany) a vedle cesta $D$–$E$–$F$ (2 hrany). Celkem $m = 5 = n - 1$, ale graf je nesouvislý a zároveň obsahuje kružnici. „Hrana navíc“ promrhaná na kružnici přesně odpovídá „chybějící hraně“ mezi komponentami.
Nebezpečná polopravda„Graf s $n-1$ hranami je strom“ — NE. Počet hran $n-1$ dělá strom až ve dvojici s jednou další vlastností: + bez kružnice = (b), nebo + souvislost = (c). Samotné $n-1$ hran připouští „kružnice tady, díra jinde“ (viz obrázek). U ústní na tohle zdůvodnění dojde.
Strategie důkazu: kruh místo 42 šipek
Zkus sám: ekvivalence 7 tvrzení znamená 7·6 = 42 implikací „cokoli ⇒ cokoli“. Kolik jich opravdu musíme dokázat ručně?
Stačí 7 — uzavřený kruh $(a) \Rightarrow (g) \Rightarrow (e) \Rightarrow (d) \Rightarrow (f) \Rightarrow (b) \Rightarrow (c) \Rightarrow (a)$. Z libovolného tvrzení se pak do libovolného jiného „dojede po kruhu“ řetězením implikací. Přesně takhle je postavený slide 62.
Plán: nejdřív si pořídíme počítadlo $n = m + p$ (pohání tři implikace), pak kruh objedeme.
Motor důkazu: les má $n = m + p$
Slide 62 se dvakrát odvolává na fakt (znáš ho jako poznatek z [L0.4], teď ho dokážeme): „for a forest with $n$ nodes, $m$ edges and $p$ connected components $n = m + p$. (The proof is a trivial induction on $m$)“ (1:1).
Zkus sám: báze indukce $m = 0$. Kolik komponent má les bez hran?
Každý vrchol je sám svojí komponentou: $p = n$, tedy $n = 0 + n$. ✓
Zkus sám: indukční krok — do lesa přidám hranu $\{u,v\}$ tak, aby výsledek byl pořád les. Proč musí $u$ a $v$ ležet v různých komponentách? A co to udělá s $p$?
Kdyby $u, v$ ležely v téže komponentě, existuje mezi nimi cesta $P$ a $P + \{u,v\}$ uzavře kružnici — výsledek by nebyl les. Takže hrana lesa vždy spojuje dvě různé komponenty a slije je v jednu: $m$ vzroste o 1, $p$ klesne o 1, součet $m + p$ se nezmění. Z báze $m + p = n$ to platí pořád.
Důsledek pro náš protipříklad výše: les s $m = n - 1$ hranami má $p = n - m = 1$ komponentu, tedy je souvislý. Trojúhelník + cesta se z toho vykroutil jen tím, že není les.
$(a) \Rightarrow (g)$: dvě cesty = kružnice
Slide 62 (1:1): „(a) $\Rightarrow$ (g): follows from the fact that the union of two distinct paths with the same endpoints contains a circuit.“ Rozbalíme:
Zkus sám: strom je souvislý — aspoň jedna cesta mezi $u$ a $v$ tedy existuje. Proč nemůžou existovat dvě různé?
Sporem: nechť $P_1 \ne P_2$ jsou dvě různé cesty z $u$ do $v$. Jdi po obou současně od $u$: v nějakém vrcholu $r$ se poprvé rozvětví (existuje, jinak by byly stejné) a protože obě končí ve $v$, v nějakém prvním vrcholu $s$ se zase potkají. Úsek $P_1[r,s]$ + úsek $P_2[s,r]$ je uzavřený a vnitřně disjunktní — kružnice. Strom ale kružnici nemá (definice (a) z [L0.4]) → spor. Cesta je tedy právě jedna: (g).
$(g) \Rightarrow (e) \Rightarrow (d)$: jazyk řezů
Slide 62 tu důkaz nerozepisuje: „(g) $\Rightarrow$ (e) $\Rightarrow$ (d): see [1] page 17 Proposition 2.3.“ (odkaz na učebnici Korte–Vygen). Náčrt níže je vlastní doplněk (přiznáno) — pro ústní bohatě stačí.
$(g) \Rightarrow (e)$: Jednoznačné cesty ⟹ souvislost ⟹ každý řez neprázdný (cesta z $u \in X$ do $v \notin X$ musí někde řez překročit) — to je vlastnost z (e). Zbývá minimalita:
Zkus sám: smažu libovolnou hranu $e = \{u,v\}$. Najdi množinu $X$, jejíž řez se tím vyprázdní. (Nápověda: hrana $e$ je sama o sobě cesta z $u$ do $v$…)
Hrana $e$ je cesta $u$–$v$; podle (g) je to jediná cesta mezi $u$ a $v$. V $G - e$ už tedy žádná $u$–$v$ cesta není. Vezmi $X$ = {vrcholy dosažitelné z $u$ v $G - e$}: platí $u \in X$, $v \notin X$ a žádná hrana $G - e$ z $X$ nevede ven (jinak by se dalo dosáhnout dál), takže $\delta_{G-e}(X) = \emptyset$. Žádná hrana se nedá postrádat → $G$ je minimální: (e).
$(e) \Rightarrow (d)$: už víme (try v sekci 1), že „všechny řezy neprázdné“ ⟺ souvislost. (e) tedy říká: $G$ je souvislý a po smazání kterékoli hrany souvislost padne — což je doslova (d).
$(d) \Rightarrow (f)$: „trivial“ — rozepsáno
Slide 62 (1:1): „(d) $\Rightarrow$ (f): trivial.“ (f) má dvě půlky — zkus obě:
Zkus sám: proč graf splňující (d) nemůže obsahovat kružnici?
Kdyby obsahoval kružnici $C$, smaž libovolnou její hranu $e \in C$: každá cesta, která $e$ používala, se vyhne po zbytku kružnice („objížďka“) — graf zůstane souvislý. To popírá (d) („while removing any edge it will not be connected anymore“). Takže kružnice není.
Zkus sám: proč přidání libovolné nové hrany $\{u,v\}$ kružnici vytvoří?
(d) garantuje souvislost, takže mezi $u$ a $v$ už nějaká cesta $P$ vede. $P + \{u,v\}$ je kružnice. Obě půlky (f) platí. ✓
Všimni si: objížďkový argument („hrana na kružnici jde smazat bez ztráty souvislosti“) za chvíli pohání i mašinu v $(c) \Rightarrow (a)$ — a znáš ho z důkazu, že MST je strom ([L0.5], [L3.8b]).
$(f) \Rightarrow (b) \Rightarrow (c)$: počítadlo poprvé
Slide 62 (1:1): „(f) $\Rightarrow$ (b) $\Rightarrow$ (c): follows from the fact that for a forest with $n$ nodes, $m$ edges and $p$ connected components $n = m + p$.“
Zkus sám ($(f) \Rightarrow (b)$): $G$ je bez kružnice a každá přidaná hrana kružnici vytvoří. Proč musí být $G$ souvislý? A kolik má pak hran?
Sporem: kdyby měl $G$ aspoň dvě komponenty, přidej hranu $\{u,v\}$ mezi nimi. Kružnice přes novou hranu by potřebovala jinou cestu $u$–$v$ — ta ale mezi komponentami neexistuje. Nová hrana tedy kružnici nevytvoří → spor s (f). Takže $p = 1$ a počítadlo dá $n = m + 1$, tj. $m = n - 1$. Spolu s „circuit-free“ je to přesně (b).
Zkus sám ($(b) \Rightarrow (c)$): $G$ má $n-1$ hran a žádnou kružnici. Dopočítej souvislost.
Bez kružnice = les → platí $n = m + p = (n-1) + p$, tedy $p = 1$: souvislý. Spolu s $m = n-1$ je to (c). ✓
$(c) \Rightarrow (a)$: mašina na ničení kružnic
Poslední šipka uzavírá kruh. Slide 62 (1:1): „(c) $\Rightarrow$ (a): $G$ is connected with $n - 1$. As long as there are any circuits in $G$, we destroy them by deleting any edge of the circuit. Suppose we have deleted $k$ circuits, the resulting graph $G'$ is a tree (contains no circuit and is connected) and has $m = n - 1 - k$ edges. So $n = m + p = n - 1 - k + 1$, implying $k = 0$.“
Zkus sám: proč mašina nikdy neztratí souvislost? A proč z $k = 0$ plyne, že $G$ je strom?
Maže se vždy hrana ležící na kružnici — objížďkový argument ze sekce $(d) \Rightarrow (f)$ říká, že souvislost přežije. Výsledek $G'$ je souvislý a bez kružnice = strom, a podle počítadla má $n - 1$ hran. Začínali jsme ale s $n-1$ hranami a každé zničení kružnice jednu hranu stálo: $n - 1 - k = n - 1 \Rightarrow k = 0$. Mašina tedy neměla co ničit — $G$ byl bez kružnice už na začátku, a protože je souvislý, je to strom: (a). Kruh je uzavřen. ∎
Mašina v akci (schválně na grafu s $m = n + 1$ hranami, ať je co ničit — poslední krok říká, proč s $m = n-1$ nezničí nic):
Key takeaways — L3.13- Sedm ekvivalentních charakterizací stromu (slide 61): strom ⟺ $n-1$ hran + bez kružnice ⟺ $n-1$ hran + souvislý ⟺ minimálně souvislý ⟺ minimální graf s $\delta(X) \ne \emptyset$ pro každý řez ⟺ maximálně acyklický ⟺ právě jedna cesta mezi každou dvojicí vrcholů.
- Důkaz = kruh 7 implikací $(a) \Rightarrow (g) \Rightarrow (e) \Rightarrow (d) \Rightarrow (f) \Rightarrow (b) \Rightarrow (c) \Rightarrow (a)$ — ekvivalenci netřeba dokazovat po dvojicích (slide 62).
- Motor: les s $n$ vrcholy, $m$ hranami a $p$ komponentami má $n = m + p$ (indukce dle $m$: hrana lesa vždy slije dvě komponenty).
- Dva opakovaně použité fakty: hrana na kružnici jde smazat bez ztráty souvislosti (objížďka); hrana uvnitř komponenty kružnici uzavře.
- Polopravda: „$n-1$ hran ⇒ strom“ neplatí (trojúhelník + cesta) — vždy je nutný parťák: souvislost, nebo acykličnost.
Let $G$ be an undirected graph with $n$ nodes, then the following statements are equivalent:
(a) $G$ is a tree. (b) $G$ has $n - 1$ edges and no circuit. (c) $G$ has $n - 1$ edges and is connected. (d) $G$ is connected and while removing any edge it will not be connected anymore. (e) $G$ is a minimal graph which has $\delta(X) \ne \emptyset$ for all $\emptyset \ne X \subset V(G)$. (f) $G$ is circuit-free and the addition of any edge creates a circuit. (g) $G$ contains a unique path between any pair of vertices.
(Vlastní pokyn k procvičení — přiznáno:) Prove that the statements are equivalent.
a) Co je v zadání?
Věta ze slidu 61: sedm tvrzení o neorientovaném grafu, která jsou všechna ekvivalentní (každé z nich může sloužit jako definice stromu). Úkol: dokázat ekvivalenci — tj. zorganizovat implikace tak, aby se z každého tvrzení dalo dojít ke každému.
b) Co k tomu budeme potřebovat?
- [L0.4] Strom, kostra, les, DAG — definice strom/les, fakt $n = m + p$,
- [L0.3] Sled, tah, cesta, kružnice — co je circuit/cesta,
- [L0.2] Okolí vrcholu — značení $\delta$, zde zobecněné na řez $\delta(X)$,
- tato lekce — kruh implikací a počítadlo $n = m+p$.
c) Jak nad úlohou uvažovat?
Nedokazuj 42 dvojic — postav uzavřený kruh $(a) \Rightarrow (g) \Rightarrow (e) \Rightarrow (d) \Rightarrow (f) \Rightarrow (b) \Rightarrow (c) \Rightarrow (a)$. Dopředu si připrav lemma $n = m + p$ pro lesy (indukce dle $m$) — pohání šipky $(f) \Rightarrow (b) \Rightarrow (c)$ i $(c) \Rightarrow (a)$. Dvě malá kopací kolečka: „dvě různé cesty se stejnými konci ⟹ kružnice“ a „hrana na kružnici jde smazat bez ztráty souvislosti“.
d) Úplné řešení
Lemma (slide 62, 1:1): for a forest with $n$ nodes, $m$ edges and $p$ connected components $n = m + p$. (The proof is a trivial induction on $m$.) — Indukce: $m=0$ dává $p=n$; přidávaná hrana lesa musí spojovat dvě různé komponenty (jinak by s cestou mezi svými konci uzavřela kružnici), takže $m \mathbin{+}{=} 1$, $p \mathbin{-}{=} 1$ a součet $m+p$ se zachovává.
$(a) \Rightarrow (g)$ (slide 62: „follows from the fact that the union of two distinct paths with the same endpoints contains a circuit“): Souvislost dává aspoň jednu cestu mezi každou dvojicí. Kdyby $P_1 \ne P_2$ vedly obě z $u$ do $v$, úsek mezi prvním rozvětvením $r$ a prvním opětovným setkáním $s$ tvoří kružnici — spor s acykličností stromu. Cesta je právě jedna.
$(g) \Rightarrow (e) \Rightarrow (d)$ (slide 62 odkazuje na [1] page 17 Proposition 2.3; náčrt vlastní — přiznáno): Z (g) plyne souvislost, a souvislost ⟺ $\delta(X) \ne \emptyset$ pro každou $\emptyset \ne X \subset V$ (cesta z $X$ ven musí řez překročit; obráceně prázdný řez = odříznutá množina). Minimalita: hrana $e=\{u,v\}$ je podle (g) jedinou $u$–$v$ cestou, takže v $G-e$ má množina vrcholů dosažitelných z $u$ prázdný řez → žádnou hranu nelze postrádat: (e). A (e) přeloženo z jazyka řezů: $G$ souvislý a $G - e$ nesouvislý pro každé $e$ — doslova (d).
$(d) \Rightarrow (f)$ (slide 62: „trivial“): Kružnice by dovolila smazat svou hranu bez ztráty souvislosti (objížďka po zbytku kružnice) — spor s (d); a přidání $\{u,v\}$ k existující $u$–$v$ cestě (souvislost) kružnici uzavře.
$(f) \Rightarrow (b) \Rightarrow (c)$ (slide 62: přes lemma): Z (f): kdyby $G$ měl dvě komponenty, hrana mezi nimi by žádnou kružnici nevytvořila (chybí druhá cesta) — spor; tedy $p=1$ a lemma dá $m = n-1$: to je (b). Z (b): les s $m = n-1$ má $p = n - m = 1$, tedy souvislý: (c).
$(c) \Rightarrow (a)$ (slide 62, 1:1): „$G$ is connected with $n-1$. As long as there are any circuits in $G$, we destroy them by deleting any edge of the circuit. Suppose we have deleted $k$ circuits, the resulting graph $G'$ is a tree (contains no circuit and is connected) and has $m = n - 1 - k$ edges. So $n = m + p = n - 1 - k + 1$, implying $k = 0$.“ — Mazání hrany kružnice souvislost zachová (objížďka), výsledek je souvislý a bez kružnice = strom, podle lemmatu má $n-1$ hran; protože jsme začali s $n-1$ hranami a každé smazání jednu stálo, je $k=0$: $G$ kružnici nikdy neměl a je to strom. Kruh je uzavřen, všech 7 tvrzení je ekvivalentních. ∎
Let $G$ be an undirected graph with $12$ nodes and $8$ edges. (i) Assume $G$ contains no circuit. How many connected components does $G$ have? (ii) Can a graph with $12$ nodes and $8$ edges be connected? (iii) A connected graph $H$ has $12$ nodes and $11$ edges. Prove that $H$ is a tree.
a) Co je v zadání?
Tři rychlé otázky na vztah mezi počtem vrcholů, hran a komponent: (i) spočítat komponenty lesa, (ii) rozhodnout, zda málo hran dovolí souvislost, (iii) aplikovat implikaci $(c) \Rightarrow (a)$.
b) Co k tomu budeme potřebovat?
- tato lekce — lemma $n = m + p$ a implikace $(c) \Rightarrow (a)$,
- [L0.4] — definice les/strom/komponenta.
c) Jak nad úlohou uvažovat?
(i) Bez kružnice = les → dosaď do počítadla. (ii) Kolik hran souvislost minimálně potřebuje? Vyjdi z toho, že souvislý graf obsahuje kostru. (iii) Tohle je přesně premisa (c) — stačí citovat kruh, nebo zopakovat mašinu na ničení kružnic.
d) Úplné řešení
(i) Les: $n = m + p \Rightarrow p = 12 - 8 = 4$ komponenty.
(ii) Ne. Souvislý graf na $n$ vrcholech obsahuje kostru ([L0.4]), tedy aspoň $n - 1 = 11$ hran; $8 < 11$. (Alternativně: mašina z $(c)\Rightarrow(a)$ by z něj smazáním $k \ge 0$ hran udělala strom s $8 - k \le 8 < 11$ hranami — spor s lemmatem.)
(iii) $H$ je souvislý a má $n - 1 = 11$ hran → splňuje (c). Podle ekvivalence ze slidu 61 (implikace $(c) \Rightarrow (a)$, slide 62) je $H$ strom. Rozepsáno: ničíme-li kružnice mazáním jejich hran, souvislost se zachová a výsledný strom má podle lemmatu $11$ hran — takže jsme nesmazali nic ($k=0$) a $H$ byl bez kružnice od začátku. ∎