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 [skrýt] 1 Neorientovaný graf 2 Orientovaný graf 3 Princip sudosti 4 Související články 5 Externí odkazy

Neorientovaný graf

$deg(u)=|\{e\in \mathit{E}\mid u\in e\}|$

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

U orientovaného grafu se rozlišuje tzv. vstupní a výstupní stupeň vrcholu:

• vstupní stupeň

$de{g}^{+}(u)=|\{e\in \mathit{E}\mid \mathrm{\exists }v\in \mathit{V}:e=(v,u)\}|$

• výstupní stupeň

$de{g}^{-}(u)=|\{e\in \mathit{E}\mid \mathrm{\exists }v\in \mathit{V}:e=(u,v)\}|$

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}}(de{g}^{+}(v)+de{g}^{-}(v))$

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

• Skóre grafu

Externí odkazy

• Seznam grafových pojmů na anglické Wikipedii (anglicky)

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii