01 Okolí, stupně
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Okolí a stupeň
- Nechť $G=(V,E)$ je graf a $v \in V$ jeho vrchol
- Platí, že stupeň se rovná počtu vrcholů v okolí, $\deg_{G(v)}= |N_G(v)|$
# Vstupní stupeň
- Kolik hran tam vchází
- Značíme $\deg^+$
- Vrcholům se stupněm 0 se říká zdroje
# Výstupní stupeň
- Kolik hran vychází
- Značíme $\deg^-$
- Vrcholům se stupněm 0 se říká stoky
# Regulární graf
- Graf je $r$-regulární, pokud stupeň každého jeho vrcholu je $r$ (například 2-regulární, 3-regulární …)
- Graf je regulární, pokud je $r$-regulární pro nějaké $r$
# Izolovaný vrchol
- Vrchol stupně 0, tedy
- Nemá žádné sousedy
# Princip sudosti
- Pro každý graf $G=(V,E)$ platí: $$ \large{\sum_{v \in V} \deg_{G(v)} = 2|E|} $$
- tj. součet všech stupňů se rovná 2× počet hran
- 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|$
Důsledky
- 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ů.