|
V [[teorieTeorie grafů|teorii grafů]] se pojmem '''stupeň vrcholu''' (někdy též ''valence'' vrcholu) označuje počet [[grafGraf (teorie grafů)#Základní pojmy|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ýOrientovaný graf|orientovaný]] nebo neorientovaný.
==Neorientovaný graf==
[[Image:6n-graf.svg|250px|thumb|Graf s 6 vrcholy a 7 hranami]]
*:<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éhohodaného vrcholu zasahují. KaždáKoncové smyčkabody se[[Hrana počítá(graf)|smyčky]] dvakrát.tvoří Jetentýž tovrchol, proto, žese každátato hrana mápočítá dva koncové bodydvakrát.
Následující tabulka udává stupeň vrcholů z obrázku vpravo:
Vrcholy na obrázku vpravo má následující stupeň.
{| class="wikitable"
|-
[[Image:Directed graph.svg|thumb|Orientovaný graf s 4 vrcholy a 5 hranami]]
*orientovanýU graforientovaného -grafu zdese rozlišujemerozliš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 každá hrana dva rozdílné konce -se vstupující hrana a vystupující hrany. Každý konec se počítápočítají zvlášť. StupeňCelkový stupeň uzlu je roveňpak roven součtu vstupujících a vystupuícíchvystupujících hran.
HodnotyStupně vrcholů z obrázku vpravo:
{| class="wikitable"
|-
|}
== 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ů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==
== Podívejte se také na ==
*[[:en:Glossary of graph theory|Seznam grafových pojmů]] na anglické wiki
*[[Skóre grafu]]
| 