„Csúcs (gráfelmélet)” változatai közötti eltérés
[ellenőrzött változat] | [ellenőrzött változat] |
Syp (vitalap | szerkesztései) Átirányítás ide: Gráfelméleti fogalomtár#Alapfogalmak |
Syp (vitalap | szerkesztései) Átirányítás megszüntetve. Eredeti cél: Gráfelméleti fogalomtár#Alapfogalmak Címke: Megszüntetett átirányítás |
||
1. sor: | 1. sor: | ||
[[Image:6n-graf.svg|thumb|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''' vagy '''pont''' (''vertex'' vagy ''node'') a [[gráf]]okat alkotó alapelemek közé tartozik: egy [[irányítatlan gráf]] csúcsok és [[él (gráfelmélet)|é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ág (gráfelmélet)|szomszédsága]] a gráf ''v''-vel szomszédos csúcsok alkotta [[feszített részgráf]]ja. |
|||
==Csúcstípusok== |
|||
Egy csúcs 𝛿(v)-vel jelölt [[fokszám (gráfelmélet)|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 𝛿<sup> -</sup>(v)-vel jelölt kifokát (a kimenő élek számát) és a 𝛿<sup>+</sup>(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 [[klikk (gráfelmélet)|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 [[összefüggő komponens (gráfelmélet)|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 összefüggő gráf|''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úcstér|csúcstere]] olyan vektortér, melynek bázisvektorai a gráf csúcsainak felelnek meg. |
|||
Egy gráf akkor [[Csúcstranzitív gráf|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áfizomorfizmus]]ok 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ág (gráfelmélet)|szomszédsági]] viszonyok alapján cserélhető fel bármely más csúccsal. |
|||
A gráfok csúcsai a [[csúcs (geometria)|poliéderek csúcsainak]] analógiájának tekinthetők: egy poliéder ([[politóp]]) [[n-váz|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== |
|||
* [[Él (gráfelmélet)]] |
|||
* [[Gráfelmélet]] |
|||
⚫ | |||
==Fordítás== |
|||
* {{fordítás|en|Vertex (graph theory)|oldid=806809670|n=a|4=angol}} |
|||
==Jegyzetek== |
|||
{{reflist|2}} |
|||
* {{cite journal |
|||
| last = Gallo |
|||
| first = Giorgio |
|||
| last2 = Pallotino |
|||
| first2 = Stefano |
|||
| title = Shortest path algorithms |
|||
| journal = Annals of Operations Research |
|||
| volume = 13 |
|||
| issue = 1 |
|||
| pages = 1–79 <!-- the inline reference refers to page 4 --> |
|||
| year = 1988 |
|||
| doi = 10.1007/BF02288320 |
|||
| ref=harv |
|||
}} |
|||
* [[Claude Berge|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) |
|||
* {{Cite book | last=Chartrand | first=Gary | authorlink=Gary Chartrand | title=Introductory graph theory | date=1985 | publisher=Dover | location=New York | isbn=0-486-24775-9 | pages=}} |
|||
* {{Cite book |author1=Biggs, Norman |author2=Lloyd, E. H. |author3=Wilson, Robin J. | title=Graph theory, 1736-1936 | date=1986 | publisher=Clarendon Press | location=Oxford [Oxfordshire] | isbn=0-19-853916-9 | pages=}} |
|||
* {{Cite book | last=Harary | first=Frank | authorlink=Frank Harary | title=Graph theory | date=1969 | publisher=Addison-Wesley Publishing | location=Reading, Mass. | isbn=0-201-41033-8 | pages=}} |
|||
* {{Cite book |author1=Harary, Frank |author2=Palmer, Edgar M. | title=Graphical enumeration | date=1973 | publisher=New York, Academic Press | location= | isbn=0-12-324245-2 | pages=}} |
|||
==További információk== |
|||
*{{mathworld | title = Graph Vertex | urlname = GraphVertex}} |
|||
[[Kategória:Gráfelmélet]] |
A lap 2018. december 7., 21:01-kori változata
A matematika, azon belül a gráfelmélet területén a csúcs, csomópont 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
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. június 25.). ISBN 0-486-24775-9
- Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press (1986. június 25.). ISBN 0-19-853916-9
- Harary, Frank. Graph theory. Reading, Mass.: Addison-Wesley Publishing (1969. június 25.). ISBN 0-201-41033-8
- Graphical enumeration. New York, Academic Press (1973. június 25.). ISBN 0-12-324245-2
További információk
- Weisstein, Eric W.: Graph Vertex (angol nyelven). Wolfram MathWorld