Stupeň vrcholu
Prerekvizita: [L0.1] Co je graf — orientovaná vs. neorientovaná hrana.
Hrany kolem vrcholu
Pro vrchol $v$ orientovaného grafu $G$ definujeme (značení dle kurzu, budeš ho potkávat u toků i řezů):
- $\delta^+(v)$ — množina hran vycházejících (leaving) z $v$,
- $\delta^-(v)$ — množina hran vstupujících (entering) do $v$,
- $\delta(v)$ — množina všech hran incidentních s $v$ (tj. $\delta^+(v) \cup \delta^-(v)$),
- $\Gamma(v)$ — množina sousedů (neighbors) vrcholu $v$.
Velikosti těchto množin jsou stupně: $|\delta^+(v)|$ je výstupní stupeň (out-degree), $|\delta^-(v)|$ je vstupní stupeň (in-degree) a $|\delta(v)|$ je stupeň vrcholu (degree). V neorientovaném grafu směr není, takže existuje jen $\delta(v)$ a stupeň $|\delta(v)|$.
Zkus sám: spočítej z obrázku $|\delta^+(b)|$, $|\delta^-(b)|$ a $\Gamma(b)$.
Z $b$ vycházejí hrany do $c$ a do $d$, takže $|\delta^+(b)| = 2$. Do $b$ vstupuje jen hrana z $a$, takže $|\delta^-(b)| = 1$. Sousedé jsou všechny vrcholy spojené hranou bez ohledu na směr: $\Gamma(b) = \{a, c, d\}$.
Součet stupňů (handshake lemma)
Teď klíčové pozorování. Sečti stupně všech vrcholů v libovolném grafu.
Zkus sám: čemu se rovná $\sum_{v \in V(G)} |\delta(v)|$? (Nápověda: kolikrát se v součtu „započítá“ jedna hrana?)
Každá hrana má přesně dva krajní vrcholy, takže se v součtu objeví přesně dvakrát — jednou za každý konec. Proto $$\sum_{v \in V(G)} |\delta(v)| = 2\,|E(G)|.$$ Součet stupňů je tedy vždy sudé číslo.
Zkus sám: co z toho plyne pro počet vrcholů s lichým stupněm?
Rozděl součet na vrcholy sudého a lichého stupně: $\underbrace{\sum_{\text{sudé}}}_{\text{sudé číslo}} + \sum_{\text{liché}} = 2|E|$ (sudé). Součet přes liché stupně tedy musí být sudý — a součet lichých čísel je sudý, jen když jich je sudý počet. Závěr: počet vrcholů lichého stupně je sudý. (Tohle využije Christofidesův algoritmus v K3: vrcholů lichého stupně v kostře je sudě, takže se dají spárovat.)
K čemu nám to bude: balance vrcholu
U digrafů budeme často porovnávat $|\delta^+(v)|$ a $|\delta^-(v)|$ — případně součty toků na těchto hranách:
- Toky (K4): zachování toku ve vrcholu = „co přiteče po $\delta^-(v)$, to odteče po $\delta^+(v)$“.
- Eulerovský tah (K3, Christofides): existence souvisí se sudostí stupňů, v digrafu s rovností $|\delta^+(v)| = |\delta^-(v)|$.
Téhle rovnosti/nerovnosti budeme říkat balance vrcholu. Zatím stačí umět stupně spočítat.
Key takeaways — L0.2- $\delta^+(v)$ = hrany z $v$ ven (out-degree $|\delta^+(v)|$); $\delta^-(v)$ = hrany do $v$ (in-degree $|\delta^-(v)|$); $\delta(v)$ = všechny incidentní hrany.
- Handshake lemma: $\sum_{v \in V(G)} |\delta(v)| = 2|E(G)|$ — každá hrana se počítá dvakrát.
- Důsledek: počet vrcholů lichého stupně je vždy sudý.
- Porovnání $|\delta^+(v)|$ vs. $|\delta^-(v)|$ („balance“) je základ zachování toku (K4) a podmínek pro Eulerovský tah (K3).
“Notice: $\sum_{v \in V(G)} |\delta(v)| = 2\,|E(G)|$. The number of nodes with an odd degree is even.” Prove both statements for an arbitrary undirected graph $G$.
a) Co je v zadání?
Dvě tvrzení ze slidu 54: (1) součet stupňů všech vrcholů je dvojnásobek počtu hran, (2) vrcholů s lichým stupněm je sudý počet. Máš je dokázat pro libovolný neorientovaný graf.
b) Co k tomu budeme potřebovat?
- [L0.1] Co je graf — hrana má dva krajní vrcholy.
- Tato lekce — definice $\delta(v)$ a stupně.
c) Jak nad úlohou uvažovat?
Pro (1): nepočítej po vrcholech, počítej po hranách — kolika členům součtu přispěje jedna hrana? Pro (2): rozděl $V$ na vrcholy sudého a lichého stupně a využij paritu výsledku z (1).
d) Úplné řešení
(1) Dvojí počítání (double counting) dvojic (vrchol, incidentní hrana): každá hrana $e = \{v,w\}$ je incidentní s přesně dvěma vrcholy, takže přispívá hodnotou 1 do $|\delta(v)|$ a hodnotou 1 do $|\delta(w)|$ — celkem 2 do součtu. Sečteno přes všechny hrany: $$\sum_{v \in V(G)} |\delta(v)| = \sum_{e \in E(G)} 2 = 2\,|E(G)|.$$
(2) Označ $S$ vrcholy sudého stupně a $L$ vrcholy lichého stupně. Pak $$\underbrace{\sum_{v \in S} |\delta(v)|}_{\text{sudé}} + \sum_{v \in L} |\delta(v)| = 2|E(G)| \;\;(\text{sudé}).$$ Součet $\sum_{v \in L} |\delta(v)|$ je tedy sudý. Je to ale součet $|L|$ lichých čísel — a ten je sudý právě tehdy, když je $|L|$ sudé. Tedy počet vrcholů lichého stupně je sudý. $\blacksquare$
For the digraph drawn above (nodes $a,b,c,d,e$), determine $|\delta^+(v)|$ and $|\delta^-(v)|$ for every node $v$, and verify that $\sum_v |\delta^+(v)| = \sum_v |\delta^-(v)| = |E(G)|$.
a) Co je v zadání?
U digrafu z obrázku výše vypiš out-degree a in-degree všech pěti vrcholů a ověř, že oba součty dají počet hran.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice $\delta^+(v)$, $\delta^-(v)$.
c) Jak nad úlohou uvažovat?
Projdi hranu po hraně: každá orientovaná hrana přidá přesně 1 do out-degree svého počátku a přesně 1 do in-degree svého konce. Proč z toho rovnost součtů plyne okamžitě?
d) Úplné řešení
Hrany grafu: $(a,b), (b,c), (b,d), (d,a), (c,e), (e,d)$, tedy $|E| = 6$.
| $v$ | $a$ | $b$ | $c$ | $d$ | $e$ | Σ |
|---|---|---|---|---|---|---|
| $|\delta^+(v)|$ | 1 | 2 | 1 | 1 | 1 | 6 |
| $|\delta^-(v)|$ | 1 | 1 | 1 | 2 | 1 | 6 |
Oba součty = 6 = $|E(G)|$, protože každá hrana má právě jeden počátek (přispěje 1× do součtu out-degree) a právě jeden konec (1× do součtu in-degree).