Csúcs (gráfelmélet)

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.

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 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

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

Fordítá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

Gallo, Giorgio (1988). „Shortest path algorithms”. Annals of Operations Research 13 (1), 1–79. o. DOI:10.1007/BF02288320.
Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
Chartrand, Gary. Introductory graph theory. New York: Dover (1985. november 4.). ISBN 0-486-24775-9
Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press (1986. november 4.). ISBN 0-19-853916-9
Harary, Frank. Graph theory. Reading, Mass.: Addison-Wesley Publishing (1969. november 4.). ISBN 0-201-41033-8
Graphical enumeration. New York, Academic Press (1973. november 4.). ISBN 0-12-324245-2

További információk

Weisstein, Eric W.: Graph Vertex (angol nyelven). Wolfram MathWorld