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 250px|náhled|Neorientovaný graf s 6 vrcholy označenými jejich stupněm
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 náhled|Orientovaný graf s 4 vrcholy a 5 hranami
U orientovaného grafu se rozlišuje tzv. vstupní a výstupní stupeň vrcholu: vstupní stupeň
výstupní stupeň
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í
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“.
Související články Seznam grafových pojmů na anglické wiki Skóre grafu
Kategorie:Grafové pojmy