Csúcs (gráfelmélet)
A gráfelméletben a csúcs a gráfokat alkotó alapvető egység – az irányítatlan gráf sok csúcsból és sok élből áll (rendezetlen csúcspárok), míg az irányított gráf sok csúcsból és sok ívből (rendezett csúcspárokból) áll. A gráfot ábrázoló rajzokon a csúcsot általában kör jelöli címkével, az élt egy vonal, az ívet pedig a csúcsokat összekötő nyíl.
Gráfelméleti szempontból a csúcsokat jellemző nélküli oszthatatlan objektumokként kezeljük, bár a gráf eredetétől függően valamilyen struktúrát képviselhetnek. Például a szemantikai hálózat egy gráf, amelyben a csúcsok az objektumok egy osztályának fogalmát képviselik.
Az élt alkotó két csúcsot az él végcsúcsának nevezzük, és az élről azt mondjuk, hogy a csúcsokra esik. Egy w csúcsot szomszédosnak mondunk egy másik v csúcstal, ha a gráf tartalmaz egy élt ( v , w ). A v csúcs szomszédsága egy generált részgráf , amelyet a v -vel szomszédos összes csúcs alkot .
Csúcstípusok
Egy gráf csúcsának foka a rá eső élek száma. Egy csúcsot izoláltnak nevezünk, ha a foka nulla. Vagyis ez egy olyan csúcs, amely egyetlen élnek sem a vége. Egy csúcsot levélnek (vagy függőnek ) nevezünk , ha egy foka van. Az irányított gráf különbséget tesz a kifelé (a kimenő ívek száma) és a befelé (a bejövő élek száma) között. A forrást nulla bemeneti fokozatú csúcsnak, a nulla kilépési fokozatú csúcsot pedig süllyedőnek nevezzük .
A csukló egy olyan csúcs, amelynek eltávolítása a gráf összekapcsolt összetevőinek növekedéséhez vezet. A csúcselválasztó olyan csúcsok halmaza, amelyek eltávolítása a gráf összekapcsolt összetevőinek növekedéséhez vezet. A k-csúccsal összekapcsolt gráf az, amelyben k - nál kevesebb csúcs eltávolításakor a gráf mindig összekapcsolt marad. A független halmaz olyan csúcsok halmaza, amelyek közül nincs kettő szomszédos, a csúcsfedő pedig olyan csúcshalmaz, amely a gráf bármely élének legalább egy végcsúcsát tartalmazza. A gráf csúcsainak vektortere egy olyan vektortér, amelynek alapja a gráf csúcsainak megfelelő vektorok (a {0, 1} számmező felett) [1] [2] .
Egy gráfot csúcstranzitívnak nevezünk , ha olyan szimmetriái vannak, amelyek bármelyik csúcsot bármely másik csúcsba elviszik. A gráffelsorolással és a gráfizomorfizmussal összefüggésben fontos különbséget tenni a címkézett és a címkézetlen csúcsok között . A címkézett csúcs egy csúcshoz társított további információ, amely megkülönbözteti azt a többi címkézett csúcstól. Két gráfot csak akkor tekinthetünk izomorfnak, ha az izomorfizmus csúcsokat visz át az azonos címkével ellátott csúcsokra. A címkézetlen csúcsok ezután csak a szomszédosság alapján és további információk felhasználása nélkül fordíthatók le más csúcsokra.
A gráf csúcsai hasonlóak egy politóp csúcsaihoz , de nem ugyanazok - a politóp váza egy gráfot alkot, amelynek csúcsai a politóp csúcsai, de a politóp csúcsaiban van egy további struktúra (geometriai hely), amelyet a gráfelmélet figyelmen kívül hagy. A poliéder csúcsalakja hasonló a gráfcsúcs környezetéhez.
Lásd még
Jegyzetek
- ↑ M. Swami, K. Tulasimaran. Grafikonok, hálózatok és algoritmusok. - Moszkva: Mir, 1984. - S. 62-76. 4. fejezet
- ↑ Reinhard Distel. Gráfelmélet. - Novoszibirszk: Matematikai Intézet Kiadója, 2002. - 35. o.
Linkek
- Giorgio Gallo, Stefano Pallotino. Legrövidebb út algoritmusai (angol) // Annals of Operations Research. - 1988. - 1. évf. 13 , iss. 1 . - 1-79 . o . - doi : 10.1007/BF02288320 .
- K. Berge Gráfelmélet és alkalmazása. - Moszkva: Külföldi Irodalmi Kiadó, 1962.
- Gary Chartrand. Bevezető gráfelmélet . - New York: Dover, 1985. - ISBN 0-486-24775-9 .
- Norman Biggs, EH Lloyd, Robin J. Wilson. Gráfelmélet, 1736-1936. - Oxford [Oxfordshire]: Clarendon Press, 1986. - ISBN 0-19-853916-9 .
- Frank Harary . gráfelmélet. - Reading, Mass.: Addison-Wesley Publishing, 1969. - ISBN 0-201-41033-8 .
- Frank Harary , Edgar M. Palmer,. Grafikus felsorolás. - New York: Academic Press, 1973. - ISBN 0-12-324245-2 .
- Weisstein, Eric W. Graph Vertex (angol) a Wolfram MathWorld webhelyen .
 Szótárak és enciklopédiák |
|---|