počet hran v grafu incidentních s daným vrcholem From Wikipedia, the free encyclopedia
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ý.
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.
U orientovaného grafu se rozlišuje tzv. vstupní a výstupní stupeň vrcholu:
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 |
Tvrzení: V neorientovaném grafu G = (V, E) platí
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
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“.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.