Szomszédság (gráfelmélet)

A gráfelméletben a v csúcs szomszédos csúcsa az a csúcs , amely a v -hez egy éllel kapcsolódik . Egy v csúcs szomszédsága a G gráfban a G gráf generált részgráfja , amely a v - hez konjugált összes csúcsból és két ilyen csúcsot összekötő összes élből áll. Például az ábrán egy 6 csúcsú és 7 éles gráf látható. Az 5. csúcs szomszédos az 1., 2. és 4. csúcsokkal, de nem szomszédos a 3. és 6. csúcsokkal. Az 5. csúcs szomszédsága egy gráf, amelynek három csúcsa 1, 2 és 4, valamint egy él összeköti az 1. és 2. csúcsot.

Egy környéket gyakran jelölnek N G ( v ) vagy (ha tudod, melyik gráfról van szó) N ( v ). Ugyanez a szomszédsági jelölés használható a szomszédos csúcsok halmazára való hivatkozásra, nem pedig a megfelelő generált részgráfra. A fent leírt szomszédság nem tartalmazza magát a v - t, és erre a szomszédságra úgy hivatkozunk, mint a v nyitott szomszédságára . Meghatározhat egy olyan környéket, amely tartalmazza a v . Ebben az esetben a környéket zártnak nevezzük, és N G [ v ] -ként jelöljük . Hacsak nincs kifejezetten megadva, a környéket nyitottnak kell tekinteni.

A szomszédságlistán és szomszédsági mátrixon keresztül számítógépes algoritmusokban gráfok ábrázolására használhatók a környékek . A szomszédságokat a gráf klaszterezési együtthatója is használja, amely a szomszédságainak átlagos sűrűségét méri. Ezenkívül a gráfok számos fontos osztálya meghatározható a szomszédságainak tulajdonságaival vagy a szomszédságok kölcsönös szimmetriájával.

Egy izolált csúcsnak nincsenek szomszédos csúcsai. Egy csúcs foka megegyezik a szomszédos csúcsok számával. Egy speciális eset egy csúcsot ugyanahhoz a csúcshoz kötõ hurok . Ha létezik ilyen él, akkor a csúcs a saját szomszédságához tartozik.

Egy gráf helyi tulajdonságai

Ha egy G gráf minden csúcsának szomszédsága izomorf valamely H gráfhoz , akkor G -ről azt mondjuk, hogy lokálisan H gráf , és ha G minden csúcsának vannak olyan környékei, amelyek valamelyik F gráfcsaládhoz tartoznak , akkor G -t lokálisan gráfnak mondjuk. F [1] [2] . Például az ábrán látható oktaéder gráfban minden csúcsnak van egy négy csúcsból álló ciklusával izomorf szomszédság , tehát az oktaéder lokálisan C 4 .

Például:

Bármely teljes K n gráf lokálisan K n-1 gráf . Az egyetlen lokálisan teljes gráf a teljes gráfok diszjunkt uniója.
A T ( rs , r ) Turan-gráf lokálisan ekvivalens T -vel (( r -1) s , r -1). Vagyis bármely Turan gráf lokálisan Turan gráf.
Bármely síkbeli gráf lokálisan külső síkbeli . Azonban nem minden lokálisan kívüli gráf síkbeli.
Egy gráf akkor és csak akkor háromszög nélküli gráf , ha lokálisan független .
Bármely k - kromatikus gráf lokálisan ( k -1) - kromatikus. Minden lokálisan k -kromatikus gráfnak van kromatikus száma [3] . $O({\sqrt {kn)))$
Ha egy F gráfcsalád a generált részgráfok felvételének művelete alatt zárt, akkor F-beli bármely gráf lokálisan is F . Például bármely akkordgráf lokálisan akkord, minden tökéletes gráf lokálisan tökéletes, minden összehasonlíthatósági gráf összehasonlíthatósági gráf.
Egy gráf lokálisan ciklikus, ha minden szomszédság ciklus . Például az oktaéder gráf az egyetlen lokálisan C 4 gráf, az ikozaéder gráf az egyetlen lokálisan C 5 gráf, és a 13. rendű Paley gráf lokálisan C 6 . A K 4 -től eltérő lokálisan ciklikus gráfok pontosan a Whitney-háromszögelés alapjául szolgáló gráfok , amelyek úgy ágyazzák be a gráfokat egy felületbe, hogy a beágyazás lapjai megfeleljenek a gráf klikkjeinek [4] [5] [6] . A lokálisan ciklikus gráfok akár élek is lehetnek [7] . ${\displaystyle n^{2-o(1)))$
A karmok nélküli grafikonok lokálisan háromszögmentesek . Azaz minden csúcsra a csúcsszomszédsági gráf komplementere nem tartalmaz háromszögeket. Egy gráf, amely lokálisan egy H gráf, akkor és csak akkor nem tartalmaz karmokat, ha H függetlenségi száma legfeljebb kettő. Például egy szabályos ikozaéder gráfja nem tartalmaz karmokat, mert lokálisan C 5 , a C 5 függetlenségi szám pedig kettő.

Sok szomszéd

Egy A csúcshalmaz esetén az A szomszédsága a csúcsok környezeteinek uniója, tehát tartalmazza az összes olyan csúcsot, amely A legalább egy tagjához konjugált .

Egy gráf A csúcshalmazát modulnak nevezzük, ha A minden csúcsának ugyanaz a szomszédsághalmaza az A -n kívül . Minden gráfnak van egy egyedi rekurzív modularizációja, az úgynevezett modularizáció , amely a gráfból lineáris időben felépíthető . A moduláris felbontó algoritmust más gráfalgoritmusokra is alkalmazzák, beleértve az összehasonlíthatósági gráffelismerést .

Lásd még

Moore környéken
Von Neumann környéken
Csúcsfigura , hasonló fogalom a poliéderek geometriájában.

Irodalom

Nora Hartsfeld, Gerhard Ringel. Tiszta háromszögelések // Combinatorica . - 1991. - 1. évf. 11, sz. 2. - P. 145-155. - doi : 10.1007/BF01206358 .
Pavol Hell. . Grafikonok adott környékekkel I // Problemes Combinatoires et Théorie des Graphes. - Párizs: Éditions du Centre national de la recherche scientifique, 1978. - xiv + 443 p. – (Colloques internationaux CNRS, 260. köt.). — ISBN 2222020700 . - P. 219-223.
F. Larrión, V. Neumann-Lara, M. A. Pizaña. Whitney-háromszögelések, lokális kerület és iterált klikk gráfok // Diszkrét matematika . - 2002. - 20. évf. 258. - P. 123-135. - doi : 10.1016/S0012-365X(02)00266-2 .
Aleksander Malnic, Bojan Mohar. Felületek lokálisan ciklikus háromszögleteinek generálása // Journal of Combinatorial Theory, B sorozat . - 1992. - 1. évf. 56. sz. 2. - P. 147-164. - doi : 10.1016/0095-8956(92)90015-P .
J. Sedlacek. . A véges gráfok lokális tulajdonságairól // Graph Theory, Lagow. - Springer-Verlag, 1983. - (Matematikai előadásjegyzetek, 1018. köt.). - ISBN 978-3-540-12687-4 . - doi : 10.1007/BFb0071634 . - P. 242-247.
Seress Ákos, Szabó Tibor. Sűrű gráfok cikluskörnyezetekkel // Journal of Combinatorial Theory, B sorozat . - 1995. - 1. évf. 63. sz. 2. - P. 281-293. - doi : 10.1006/jctb.1995.1020 . Az eredetiből archiválva : 2005. augusztus 30.
Avi Wigderson. A hozzávetőleges grafikonszínezés teljesítménygaranciájának javítása // Journal of the ACM . - 1983. - 1. évf. 30, sz. 4. - P. 729-735. - doi : 10.1145/2157.2158 .