Vertex (teorie grafů)

V teorii grafů je vrchol základní jednotkou, která tvoří grafy — neorientovaný graf se skládá z mnoha vrcholů a mnoha hran (neuspořádaných dvojic vrcholů), zatímco orientovaný graf sestává z mnoha vrcholů a mnoha oblouků (uspořádaných dvojic vrcholů). Na výkresech znázorňujících graf je vrchol obvykle označen kruhem se štítkem, hranou čárou a obloukem šipkou spojující vrcholy.

Z hlediska teorie grafů jsou vrcholy považovány za bezpříznakové nedělitelné objekty, i když mohou představovat určitou strukturu v závislosti na problému, ze kterého graf pochází. Například sémantická síť  je graf, ve kterém vrcholy představují koncept třídy objektů.

Dva vrcholy, které tvoří hranu, se nazývají koncové vrcholy hrany a o hraně se říká, že je incidentní s vrcholy. O vrcholu w se říká, že sousedí s jiným vrcholem v , pokud graf obsahuje hranu ( v , w ). Okolí vrcholu v je vygenerovaný podgraf tvořený všemi vrcholy sousedícími s v .

Typy vrcholů

Stupeň vrcholu v grafu je počet hran, které k němu dopadají. Vrchol se nazývá izolovaný , pokud je jeho stupeň nula. To znamená, že je to vrchol, který není koncem žádné hrany. Vrchol se nazývá list (nebo visící ), pokud má stupeň jedna. Orientovaný graf rozlišuje mezi out-degree (počet odchozích oblouků) a in-degree (počet příchozích hran). Zdroj se nazývá vrchol s nulovým stupněm a vrchol s nulovým stupněm se nazývá sink .

Pant je vrchol, jehož odstranění vede ke zvětšení připojených složek grafu. Vrcholový oddělovač je množina vrcholů, jejichž odstranění vede ke zvětšení spojených složek grafu. Vrcholový k-souvislý graf  je takový, ve kterém odstraněním méně než k vrcholů zůstane graf vždy připojen. Nezávislá množina je množina vrcholů, z nichž žádné dva nesousedí, a vrcholový kryt je množina vrcholů, která obsahuje alespoň jeden koncový vrchol libovolné hrany grafu. Vektorový prostor vrcholů grafu je vektorový prostor, jehož základem jsou vektory odpovídající vrcholům grafu (nad polem čísel {0, 1}) [1] [2] .

O grafu se říká , že je vertex-tranzitivní , pokud má symetrie, které přenášejí jakýkoli vrchol do jakéhokoli jiného vrcholu. V kontextu výčtu grafů a izomorfismu grafu je důležité rozlišovat mezi označenými vrcholy a neoznačenými vrcholy . Označený vrchol je další informace spojená s vrcholem, která jej odlišuje od ostatních označených vrcholů. Dva grafy lze považovat za izomorfní pouze tehdy, pokud izomorfismus přebírá vrcholy k vrcholům se stejnými štítky. Neoznačené vrcholy pak mohou být přeloženy do jiných vrcholů pouze na základě sousedství a bez použití dalších informací.

Vrcholy grafu jsou podobné vrcholům polytopu , ale nejsou stejné - kostra tvoří graf, jehož vrcholy jsou vrcholy polytopu, ale vrcholy polytopu mají další struktura (geometrické umístění), která je v teorii grafů ignorována. Vrcholový obrazec mnohostěnu je podobný okolí vrcholu grafu.

Viz také

Poznámky

  1. ↑ M. Svámí, K. Tulasimaran. Grafy, sítě a algoritmy. - Moskva: Mir, 1984. - S. 62-76. kapitola 4
  2. ↑ Reinhard Distel. Teorie grafů. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - S. 35.

Odkazy

  Přejděte na položku Wikidata  Slovníky a encyklopedie