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ý.

Obsah

1 Neorientovaný graf
2 Orientovaný graf
3 Princip sudosti
4 Související články

[editovat] Neorientovaný graf

Graf s 6 vrcholy a 7 hranami

$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.

Následující tabulka udává stupeň vrcholů z obrázku vpravo:

Vrchol	Stupeň
1	2
2	3
3	2
4	3
5	3
6	1

[editovat] 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

[editovat] 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“.

[editovat] Související články

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

Kategorie: Grafové pojmy

Stupeň vrcholu v jiných jazycích: English, Español, עברית, Magyar, Српски / Srpski, ไทย, Tiếng Việt

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Stupe%C5%88_vrcholu“
Stránka byla naposledy upravena v Stránka byla naposledy editována 18. 6. 2008 v 03:11.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).