Strom, kostra, les, DAG
Prerekvizity: [L0.3] Cesta, sled, tah, cyklus (cesta, kružnice), [L0.2] Stupeň vrcholu.
Souvislost
Neorientovaný graf je souvislý (connected), pokud mezi každou dvojicí vrcholů existuje cesta. Maximální souvislé podgrafy jsou komponenty souvislosti (connected components) — každý vrchol leží přesně v jedné. Digraf je souvislý, pokud je souvislý jeho podkladový neorientovaný graf; je silně souvislý (strongly connected), pokud mezi každými $x, y$ vede orientovaná cesta tam i zpět.
Les a strom
- Les (forest) = neorientovaný graf bez kružnice.
- Strom (tree) = les, který je navíc souvislý.
Zkus sám: strom má $n$ vrcholů. Kolik má hran? A co se stane, když jednu hranu přidáš / odebereš?
Strom na $n$ vrcholech má přesně $\boldsymbol{n-1}$ hran. Když libovolnou hranu odebereš, graf se rozpadne (přestane být souvislý). Když libovolnou hranu přidáš, vznikne kružnice. Strom je tedy „přesně na hraně“: minimální souvislý a zároveň maximální acyklický graf.
Slidy (slide 61) dávají sedm ekvivalentních charakterizací stromu. Nejdůležitější pro nás:
- (b) $G$ má $n-1$ hran a žádnou kružnici,
- (c) $G$ má $n-1$ hran a je souvislý,
- (g) mezi každou dvojicí vrcholů vede právě jedna cesta.
Užitečný fakt z důkazu: les s $n$ vrcholy, $m$ hranami a $p$ komponentami splňuje $n = m + p$.
Kostra
Kostra (spanning tree) grafu $G$ = podgraf, který je stromem a obsahuje všechny vrcholy $G$. Každý souvislý graf nějakou kostru má (kružnice postupně trhám odebíráním hran). Pozor: kostra je libovolná — o nejlevnější kostře (MST) až v [L0.5] Minimální kostra (MST).
Zkus sám: kolik hran musíš z grafu s $n$ vrcholy a $m$ hranami odebrat, aby zbyla kostra?
Kostra má $n-1$ hran, takže odebíráš $m - (n-1)$ hran — a každá odebraná musí ležet na nějaké kružnici (jinak bys graf rozpojil).
DAG a topologické uspořádání
Orientovaná obdoba acykličnosti: DAG (directed acyclic graph, orientovaný acyklický graf) = digraf bez orientovaného cyklu. Topologické uspořádání (topological ordering) digrafu je takové seřazení vrcholů do řady, že každá hrana $(u,v)$ jde „zleva doprava“ ($u$ je v pořadí před $v$). Každý DAG má alespoň jedno topologické uspořádání.
Zkus sám: může mít topologické uspořádání digraf, který obsahuje cyklus?
Ne. Na cyklu $v_1 \to v_2 \to \cdots \to v_k \to v_1$ by muselo platit „$v_1$ před $v_2$ před … před $v_k$ před $v_1$“ — tedy $v_1$ před sebou samým, spor. Existence topologického uspořádání je tedy ekvivalentní tomu, že je digraf DAG. Topologické pořadí využijeme např. pro nejkratší cesty v DAGu jedním průchodem (K2) a u precedencí v rozvrhování (K5).
Drobnost navíc ze slidů: out-tree (arborescence, kořenový strom) = digraf s kořenem (root) $x$, ze kterého vede orientovaná cesta do všech vrcholů; do kořene nevstupuje žádná hrana, do každého jiného vrcholu právě jedna. Takhle vypadá např. strom nejkratších cest od zdroje.
Key takeaways — L0.4- Les = neorientovaný graf bez kružnice; strom = souvislý les. Strom na $n$ vrcholech má přesně $n-1$ hran a mezi každou dvojicí vrcholů právě jednu cestu.
- Kostra (spanning tree) = strom obsahující všechny vrcholy grafu — libovolná, nemusí být nejlevnější (to až MST v [L0.5]).
- Les: $n = m + p$ (vrcholy = hrany + komponenty).
- DAG = digraf bez orientovaného cyklu ⟺ má topologické uspořádání (vrcholy na přímce, hrany zleva doprava).
“Let $G$ be an undirected graph with $n$ nodes, then the following statements are equivalent: (a) $G$ is a tree. … (c) $G$ has $n-1$ edges and is connected.” Prove the implication (c) $\Rightarrow$ (a). You may use the fact that for a forest with $n$ nodes, $m$ edges and $p$ connected components $n = m + p$ holds.
a) Co je v zadání?
Máš dokázat: souvislý graf s $n$ vrcholy a $n-1$ hranami je strom (tj. nemá kružnici). Smíš použít vzorec pro les $n = m + p$.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice strom/les, vzorec $n = m + p$.
- [L0.3] Cesta, sled, tah, cyklus — co je kružnice.
c) Jak nad úlohou uvažovat?
Stačí vyloučit kružnice. Zkus „trhat“ kružnice: dokud nějaká existuje, odeber z ní hranu — zůstane graf souvislý? Kolik hran ti zbyde po $k$ odebráních a co na to vzorec $n = m + p$?
d) Úplné řešení
(Důkaz ze slidu 62.) Nechť $G$ je souvislý s $n-1$ hranami. Dokud $G$ obsahuje kružnici, odeberu libovolnou její hranu — odebrání hrany kružnice nezruší souvislost (oba konce hrany zůstanou spojeny zbytkem kružnice). Předpokládejme, že jsem takto odebral $k$ hran (zničil $k$ kružnic). Výsledný graf $G'$ je souvislý a bez kružnice, tedy strom, a má $m = n - 1 - k$ hran.
Strom je les s jednou komponentou ($p = 1$), takže podle vzorce $n = m + p$: $$n = (n - 1 - k) + 1 \;\;\Longrightarrow\;\; k = 0.$$ Žádnou hranu jsem tedy neodebral — $G$ už od začátku žádnou kružnici neměl. $G$ je souvislý a bez kružnice, tedy strom. $\blacksquare$
“A topological ordering of a digraph is a linear ordering of its vertices such that for every directed edge from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering.” Find a topological ordering of the DAG drawn above (edges $(p,q), (p,r), (q,s), (r,s), (r,t), (s,t)$). Is it unique?
a) Co je v zadání?
Pro nakreslený DAG najdi seřazení vrcholů, ve kterém všechny hrany jdou zleva doprava, a rozhodni, jestli je takové seřazení jediné.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice DAG a topologického uspořádání.
- [L0.2] Stupeň vrcholu — in-degree (vrchol bez vstupních hran může jít první).
c) Jak nad úlohou uvažovat?
Který vrchol smí být v pořadí první? (Ten, do kterého nic nevstupuje, tj. $|\delta^-(v)| = 0$.) Vezmi ho, „odeber“ z grafu i s hranami a opakuj. Pro jednoznačnost: je v některém kroku na výběr víc vrcholů s nulovým in-degree?
d) Úplné řešení
In-degree: $|\delta^-(p)| = 0$, takže $p$ první. Po odebrání $p$ mají nulový in-degree $q$ i $r$ — na výběr. Např. pořadí $$p, \; q, \; r, \; s, \; t$$ funguje: všechny hrany $(p,q), (p,r), (q,s), (r,s), (r,t), (s,t)$ jdou zleva doprava. Není jednoznačné: stejně dobře funguje $p, r, q, s, t$ (prohození nezávislých vrcholů $q$ a $r$). Topologické uspořádání je jednoznačné jen tehdy, když je při postupném odebírání v každém kroku právě jeden vrchol s nulovým in-degree (tj. vrcholy jsou zřetězené hranami za sebou do jedné řady) — tady ne.