Stupeň vrcholu

V teorii grafů se pojmem stupeň vrcholu (někdy též valence vrcholu) označuje počet hran, které do daného vrcholu zasahují. Stupeň vrcholu u se značí deg(u). Přesnější definice závisí na tom, zda je graf orientovaný nebo neorientovaný.

Neorientovaný graf

Neorientovaný graf s 6 vrcholy označenými jejich stupněm

$deg(u)=\left|\{e\in {\mathit {E}}\mid u\in e\;\}\right|$

U neorientovaného grafu je stupeň vrcholu počet hran, které do daného vrcholu zasahují. Koncové body smyčky tvoří tentýž vrchol, proto se tato hrana počítá dvakrát.

Orientovaný graf

Orientovaný graf s 4 vrcholy a 5 hranami

U orientovaného grafu se rozlišuje tzv. vstupní a výstupní stupeň vrcholu:

• vstupní stupeň

$deg^{+}(u)=\left|\{e\in {\mathit {E}}\mid \exists v\in {\mathit {V}}\;:e=(v,u)\;\}\right|$

• výstupní stupeň

$deg^{-}(u)=\left|\{e\in {\mathit {E}}\mid \exists v\in {\mathit {V}}\;:e=(u,v)\;\}\right|$

U orientovaného grafu jsou hrany orientované, proto se vstupující hrana a vystupující hrany počítají zvlášť. Celkový stupeň uzlu je pak roven součtu vstupujících a vystupujících hran.

Stupně vrcholů z obrázku vpravo:

Vrchol	vstupní stupeň	výstupní stupeň
1	0	2
2	2	0
3	2	2
4	1	1

Princip sudosti

Tvrzení: V neorientovaném grafu G = (V, E) platí $\sum _{v\in {\mathit {V}}}deg(v)=2\left|E\right|$

Důkaz: Je to pouze vyjádření faktu, že každou hranu započítáváme dvakrát - jednou ve vrcholu, kde začíná, podruhé ve vrcholu, kde končí.

Poznámka: Pro orientované grafy změníme levou stranu rovnosti v tvrzení na $\sum _{v\in {\mathit {V}}}\left(deg^{+}(v)+deg^{-}(v)\right)$

Důsledek: Počet vrcholů s lichým stupněm je sudé číslo. Neboli „počet lidí, kteří si na večírku potřásli ruce s lichým počtem účastníků, je sudé číslo“.

Související články

• Seznam grafových pojmů na anglické wiki
• Skóre grafu