2.2 Okolí a stupeň vrcholu

1 Úvod 2 Grafy 2.1 Grafy 2.2 Okolí a stupeň vrcholu 2.3 Sled, cesta a kružnice v grafu 2.4 Souvislost a izomorfismus 2.5 Reprezentace grafu 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 11 Dynamické programování Index Literatura

Definice 2.13 (Okolí vrcholu)

Nechť $G = (V,E)$ je graf a $v \in V$ jeho vrchol.

$N_G(v)$ značíme množinu všech sousedů vrcholu $v$ v grafu $G$

$N_G(v)$ nazýváme (otevřené) okolí vrcholu $v$ v grafu $G$

$N_G(v) \cup \{v\}$ nazýváme uzavřené okolí vrcholu $v$ v grafu $G$

Definice 2.14 (Stupeň vrcholu)

Nechť $G = (V,E)$ je graf a $v \in V$ jeho vrchol.

$\text{deg}_G(v)$ nazýváme stupněm vrcholu $v$ v grafu $G$ a značí počet hran obsahující vrchol $v$

Poznámka 2.1

Pro stupeň vrcholu $v$ pak platí, že $\text{deg}_G(v) = |N_G(v)|$

Definice 2.15 (Regulární graf)

Graf je $r$-regulární, pokud stupeň každého jeho vrcholu je $r$

Graf je regulární, pokud je $r$-regulární pro nějaké $r$

Definice 2.16 (Izolovaný vrchol)

Vrchol stupně 0 nazveme izolovaný (nemá žádné sousedy)

Lemma 2.1 (Princip sudosti)

Pro každý graf $G = (V,E)$ platí

\begin{equation*} \sum_{v \in V} \text{deg}_G(v) = 2|E| \end{equation*}

Zobrazit důkaz

Posčítáme-li stupně všech vrcholů, započítáme každou hranu přesně dvakrát, což dává součet $2|E|$

\begin{align*} \sum_{v \in V} \text{deg}_G(v) &= \sum_{v \in V} |N_G(v)| = \sum_{v \in V} |\{u \in V \mid \{u,v\} \in E\}|\\ & \href{Místo počítání sousedících vrcholů spočítáme "sousedící hrany"}{\class{mathpopup bg-info-subtle}{=}} \sum_{v \in V} |\{e \in E \mid v \in e \}| \href{Uďeláme si čárku za každou hranu, která obsahuje vrchol $v$}{\class{mathpopup bg-info-subtle}{=}} \sum_{v \in V} \sum_{e \in E \mid v \in e} 1\\ & \href{Prohodím sumy, tedy za každou hranu si započítám oba vrcholy v ní}{\class{mathpopup bg-info-subtle}{=}} \sum_{e \in E} \sum_{v \in e} 1 = \sum_{e \in E} 2 = 2|E|\end{align*}

$\square$

Důsledek 2.1 (Důsledek principu sudosti)

Z principu sudosti plynou následující tvrzení:

V každém grafu je počet vrcholů lichého stupně sudý
Každý regulární graf lichého stupně musí mít sudý počet vrcholů