V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!

Stupeň vrcholu

Z Multimediaexpo.cz

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

Neorientovaný graf

Neorientovaný graf s 6 vrcholy označenými jejich stupněm
\(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.

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

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

Související články

Externí odkazy


Citováno z „http://www1fdc.multimediaexpo.cz/mmecz/index.php/Stupe%C5%88_vrcholu“