Ugrás a tartalomhoz

Csúcs (gráfelmélet)

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
Egy 6 csúccsal és 7 éllel rendelkező gráf. A balszélső, 6-os számmal jelölt csúcs a gráf egy „levele” vagy „függő csúcsa”

A matematika, azon belül a gráfelmélet területén a csúcs, csomópont, szögpont vagy pont (vertex vagy node) a gráfokat alkotó alapelemek közé tartozik: egy irányítatlan gráf csúcsok és élek (nem rendezett csúcspárok) halmazából áll, míg egy irányított gráf csúcsok és irányított élek (rendezett csúcspárok) halmazából. A gráf ábrázolásakor a csúcsot általában címkével ellátott körrel, az élt pedig két csúcs közé húzott vonallal vagy nyíllal jelölik.

A gráfelmélet szemszögéből a csúcsok oszthatatlan, tulajdonságokkal nem rendelkező objektumok; természetesen az adott gráfot életre hívó alkalmazási területen rendelkezhet struktúrával, például egy szemantikus háló olyan gráf, melyben a csúcsok fogalmakat vagy objektumosztályokat jelképeznek.

Egy élt alkotó két csúcsot az él végpontjainak nevezzük, az él pedig a csúcsokra illeszkedik. Egy w csúcs akkor szomszédos egy másik v csúccsal, ha a gráf tartalmaz (v,w) élt. Egy v csúcs szomszédsága a gráf v-vel szomszédos csúcsok alkotta feszített részgráfja.

Csúcstípusok

[szerkesztés]

Egy csúcs 𝛿(v)-vel jelölt fokszáma a rá illeszkedő élek számával (azaz a vele szomszédos csúcsok számával) egyezik meg. Egy izolált csúcs olyan csúcs, aminek fokszáma nulla, egy levélcsúcs vagy egyszerűen levél fokszáma pedig egy. Irányított gráfban megkülönböztetjük a csúcs 𝛿 -(v)-vel jelölt kifokát (a kimenő élek számát) és a 𝛿+(v)-vel jelölt befokát (a bejövő élek számát); egy forrás csúcs befoka nulla, míg egy nyelő csúcs kifoka nulla. Egy szimpliciális csúcs szomszédai klikket (teljes részgráfot) alkotnak: bármely két vele szomszédos csúcs egymással is szomszédos. Egy univerzális csúcs a gráf minden más csúcsával szomszédos.

Egy elvágó csúcs eltávolításával a gráf több komponensre esik szét; egy elvágó csúcshalmaz csúcsok olyan gyűjteménye, melyek eltávolításával a gráf több komponensre esik szét. Egy k-szorosan csúcsösszefüggő gráf olyan gráf, mely k-nál kevesebb csúcs eltávolítása után összefüggő marad. Egy független csúcshalmaz csúcsok olyan halmaza, melyek közül semelyik kettő nem szomszédos, egy csúcslefedés pedig csúcsok olyan csúcsok halmaza, mely a gráf minden élének legalább egy végpontját tartalmazza. Egy gráf csúcstere olyan vektortér, melynek bázisvektorai a gráf csúcsainak felelnek meg.

Egy gráf akkor csúcstranzitív, ha vannak bármely csúcsát bármely másik csúcsba átvivő szimmetriái. A gráfok leszámlálása és a gráfizomorfizmusok kontextusában fontos megkülönböztetni a címkézett csúcsokat és címkézetlen csúcsokat. Egy címkézett csúcshoz olyan extra információ társul, ami lehetővé teszi a többi címkézett csúcstól való megkülönböztetését; két gráf csak akkor tekinthető izomorfnak, ha a csúcsaik közötti összerendelés azonos címkéjű csúcsokat rendel össze egymással. Egy címkézetlen csúcs a szomszédsági viszonyok alapján cserélhető fel bármely más csúccsal.

A gráfok csúcsai a poliéderek csúcsainak analógiájának tekinthetők: egy poliéder (politóp) váza gráfot alkot, melynek csúcsai megegyeznek a poliéder csúcsaival, de a poliéder csúcsai további struktúrával rendelkeznek (mértani helyükkel), amivel a gráfelmélet nem foglalkozik.

Kapcsolódó szócikkek

[szerkesztés]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Vertex (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

[szerkesztés]

További információk

[szerkesztés]