Stupeň vrcholu

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 14. 8. 2022, 14:53

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

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

Skóre grafu

Externí odkazy

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

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

@@ Řádka 4: / Řádka 4: @@
 [[Soubor:UndirectedDegrees (Loop).png|240px|thumb|Neorientovaný graf s 6 vrcholy označenými jejich stupněm]]
-:<big>\(deg(u) = \left | \{e\in\mathit{E} \mid u\in e\;\}\right |</math>
+:<big>\(deg(u) = \left | \{e\in\mathit{E} \mid u\in e\;\}\right |\)</big>
 U neorientovaného grafu je stupeň vrcholu počet hran, které do daného vrcholu zasahují. Koncové body [[Hrana (graf)|smyčky]] tvoří tentýž vrchol, proto se tato hrana počítá dvakrát.
@@ Řádka 13: / Řádka 13: @@
 U orientovaného grafu se rozlišuje tzv. ''vstupní'' a ''výstupní'' stupeň vrcholu:
 * vstupní stupeň
-:<big>\(deg^+(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (v, u)\;\}\right |</math>
+:<big>\(deg^+(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (v, u)\;\}\right |\)</big>
 * výstupní stupeň
-:<big>\(deg^-(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (u, v)\;\}\right |</math>
+:<big>\(deg^-(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (u, v)\;\}\right |\)</big>
 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.
@@ Řádka 34: / Řádka 34: @@
 == Princip sudosti ==
-''Tvrzení'': V neorientovaném grafu ''G = (V, E)'' platí <big>\(\sum_{v\in\mathit{V}}deg(v) = 2\left |E\right |</math>
+''Tvrzení'': V neorientovaném grafu ''G = (V, E)'' platí <big>\(\sum_{v\in\mathit{V}}deg(v) = 2\left |E\right |\)</big>
 ''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 <big>\(\sum_{v\in\mathit{V}}\left (deg^+(v) + deg^-(v)\right )</math>
+''Poznámka'': Pro orientované grafy změníme levou stranu rovnosti v tvrzení na <big>\(\sum_{v\in\mathit{V}}\left (deg^+(v) + deg^-(v)\right )\)</big>
 ''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“.