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

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Nový článek)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Stupeň vrcholu|700}}
+
V [[Teorie grafů|teorii grafů]] se pojmem '''stupeň vrcholu''' (někdy též ''valence'' vrcholu) označuje počet [[hrana grafu|hran]], které do daného [[vrchol grafu|vrcholu]] zasahují. Stupeň vrcholu ''u'' se značí ''deg(u)''. Přesnější definice závisí na tom, zda je graf [[Orientovaný graf|orientovaný]] nebo neorientovaný.
 +
== Neorientovaný graf ==
 +
[[Soubor:UndirectedDegrees (Loop).png|240px|thumb|Neorientovaný graf s 6 vrcholy označenými jejich stupněm]]
 +
 +
:<math>deg(u) = \left | \{e\in\mathit{E} \mid u\in e\;\}\right |</math>
 +
 +
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.
 +
 +
== Orientovaný graf ==
 +
[[Soubor:Directed graph.png|thumb|240px|Orientovaný graf s 4 vrcholy a 5 hranami]]
 +
 +
U orientovaného grafu se rozlišuje tzv. ''vstupní'' a ''výstupní'' stupeň vrcholu:
 +
* vstupní stupeň
 +
:<math>deg^+(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (v, u)\;\}\right |</math>
 +
* výstupní stupeň
 +
:<math>deg^-(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (u, v)\;\}\right |</math>
 +
 +
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:
 +
{| class="wikitable"
 +
|-
 +
! 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í <math>\sum_{v\in\mathit{V}}deg(v) = 2\left |E\right |</math>
 +
 +
''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 <math>\sum_{v\in\mathit{V}}\left (deg^+(v) + deg^-(v)\right )</math>
 +
 +
''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 ==
 +
* [https://en.wikipedia.org/wiki/Glossary_of_graph_theory Seznam grafových pojmů na anglické Wikipedii (anglicky)]
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Grafové pojmy]]
[[Kategorie:Grafové pojmy]]

Verze z 8. 10. 2015, 13:15

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
<math>deg(u) = \left | \{e\in\mathit{E} \mid u\in e\;\}\right |</math>

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ň
<math>deg^+(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (v, u)\;\}\right |</math>
  • výstupní stupeň
<math>deg^-(u) = \left | \{e\in\mathit{E} \mid \exists v\in\mathit{V}\;:e = (u, v)\;\}\right |</math>

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í <math>\sum_{v\in\mathit{V}}deg(v) = 2\left |E\right |</math>

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 <math>\sum_{v\in\mathit{V}}\left (deg^+(v) + deg^-(v)\right )</math>

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“