Stupeň vrcholu
Z Wikipedie, otevřené encyklopedie
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
- orientovaný graf - zde rozlišujeme tzv. vstupní a výstupní stupeň vrcholu:
- vstupní stupeň
- výstupní stupeň
- vstupní stupeň
[editovat] Princip sudosti
Tvrzení: V neorientovaném grafu G = (V, E) platí 
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 
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“.
[editovat] Podívejte se také na
- Seznam grafových pojmů na anglické wiki
- Skóre grafu
