Stupeň vrcholu

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

== Neorientovaný graf ==
[[Soubor:UndirectedDegrees (Loop).png|240px|thumb|Neorientovaný graf s 6 vrcholy označenými jejich stupněm]]

:<math>deg(u) = \left | \{e\in\mathit{E} \mid u\in e\;\}\right |</math>

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

== Orientovaný graf ==
[[Soubor:Directed graph.png|thumb|240px|Orientovaný graf s 4 vrcholy a 5 hranami]]

U orientovaného grafu se rozlišuje tzv. ''vstupní'' a ''výstupní'' stupeň vrcholu:
* vstupní stupeň
:<math>deg^+(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (v, u)\;\}\right |</math>
* výstupní stupeň
:<math>deg^-(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (u, v)\;\}\right |</math>

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:
{| class="wikitable"
|-
! 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í <math>\sum_{v\in\mathit{V}}deg(v) = 2\left |E\right |</math>

''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 <math>\sum_{v\in\mathit{V}}\left (deg^+(v) + deg^-(v)\right )</math>

''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 ==
* [[Skóre grafu]]

== Externí odkazy ==
* [https://en.wikipedia.org/wiki/Glossary_of_graph_theory Seznam grafových pojmů na anglické Wikipedii (anglicky)]


{{Článek z Wikipedie}}
[[Kategorie:Grafové pojmy]]