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

A matematika, azon belül a gráfelmélet területén egy gráf v csúcsával szomszédos csúcs olyan csúcs, mellyel v-t él köti össze. A G gráfbeli v csúcs szomszédsága (neighbourhood) megegyezik a v-vel szomszédos csúcsok feszített részgráfjával. Például az ábrán látható, 6 csúccsal és 7 éllel rendelkező gráfban az 5-ös számú csúcs szomszédos az 1, 2 és 4 csúcsokkal, de nem szomszédos a 3 és 6 csúccsal. Az 5-ös csúcs szomszédsága az 1, 2, 4 csúcsokból és az 1 és 2 csúcs közötti élből álló gráf.

Egy hat csúcsot és hét élet tartalmazó gráf

A szomszédság jelölése lehet N_G(v) vagy – amikor egyértelmű, melyik gráfról van szó – N(v). Ugyanez jelentheti csak a szomszédos csúcsok halmazát (tehát nem a feszített részgráfjukat). A fenti szomszédságfogalom, amit pontosabban v nyílt szomszédságának nevezhetünk, magát a v csúcsot nem foglalja magába; definiálható a v csúcsot is tartalmazó zárt szomszédság, melynek jelölése N_G[v]. Ha nem specifikált, hogy zárt vagy nyílt szomszédságról van szó, akkor általában a nyílt szomszédságra gondolunk.

Számítógépes algoritmusokban lehetséges a gráfok reprezentációja a csúcsok szomszédságain keresztül, szomszédsági listával vagy szomszédsági mátrixszal. A gráf klaszterezettségi együtthatója kiszámítása is a szomszédságokon keresztül történik – ez a szomszédságok átlagos sűrűségével egyezik meg. Számos fontos gráfosztály definiálható a szomszédságok tulajdonságai, vagy a szomszédságok között fellépő szimmetriaviszonyok alapján.

Egy izolált csúcsnak nincsenek szomszédai. Egy csúcs fokszáma megegyezik a szomszédos csúcsok számával. Speciális eset a hurokél: ha az ilyen élet megengedjük, a csúcs a saját (nyitott) szomszédságának része.

Gráfok lokális tulajdonságai

Az oktaédergráfban bármely csúcs szomszédsága egy 4-kör.

Ha G minden csúcsának szomszédsága izomorf a H gráffal, a G lokálisan H, és ha G minden csúcsának szomszédsága az F gráfcsaládba tartozik, akkor G lokálisan F (Hell 1978, Sedlacek 1983). Például az ábrán látható oktaédergráf minden csúcsának szomszédsága izomorf a négy csúcsú körrel, ezért az oktaéder lokálisan C₄.

További példák:

• Bármely K_n teljes gráf lokálisan K_n−1. A lokálisan teljes gráfok közé kizárólag teljes gráfok diszjunkt uniója tartozik.
• A T(rs,r) Turán-gráf lokálisan T((r−1)s,r−1). Általánosabban: minden Turán-gráf lokálisan Turán.
• Minden síkgráf lokálisan külsíkgráf. Az viszont nem igaz, hogy minden lokálisan outerplanáris gráf síkgráf lenne.
• Egy gráf akkor és csak akkor háromszögmentes, ha lokálisan független.
• Minden k-kromatikus gráf lokálisan (k−1)-kromatikus. Minden lokálisan k-kromatikus gráf száma $O({\sqrt {kn}})$ (Wigderson 1983).
• Ha F a gráfminorképzésre nézve zárt gráfcsalád, akkor minden F-beli gráf lokálisan is F. Például minden húrgráf lokálisan húrgráf; minden perfekt gráf lokálisan perfekt; minden összehasonlíthatósági gráf lokálisan összehasonlíthatósági.
• Egy gráf lokálisan kör-, ha minden szomszédsága körgráf. Például az oktaéder az egyetlen lokálisan C₄ gráf, az ikozaéder az egyetlen lokálisan C₅ gráf, és a 13 rendű Paley-gráf lokálisan C₆. A K₄ kivételével a lokálisan körgráfok éppen a Whitney-háromszögelések alapgráfjai, azaz gráfok egy felületbe való olyan beágyazásai, melyben a beágyazás tartományai éppen a gráf klikkjei (Hartsfeld & Ringel 1991; Larrión, Neumann-Lara & Pizaña 2002; Malnič & Mohar 1992). A lokálisan körgráfok éleinek száma akár $n^{2-o(1)}$ is lehet (Seress & Szabó 1995).
• A karommentes gráfok azok a gráfok, melyek lokálisan ko-háromszögmentesek; tehát minden csúcs szomszédságának komplementer gráfja háromszögmentes. Egy lokálisan H gráf pontosan akkor karommentes, ha H függetlenségi száma legfeljebb kettő; például a szabályos ikozaéder karommentes, mivel lokálisan C₅ és a C₅ függetlenségi száma 2.

Halmaz szomszédsága

Egy A csúcshalmazt tekintve az A szomszédsága a csúcsok szomszédságainak uniója, tehát azon csúcsok halmaza, melyek legalább egy A-beli elemmel szomszédosak.

Egy gráf A csúcshalmaza akkor modul, ha minden A-beli csúcs ugyanazokkal az A-n kívüli szomszédokkal rendelkezik. Bármely gráf rendelkezik egyedi rekurzív modulfelbontással, ami a gráfból lineáris időben előállítható; a moduláris felbontási algoritmusokat alkalmazzák más algoritmusokban, például az összehasonlíthatósági gráfok felismerése során.

Fordítás

• Ez a szócikk részben vagy egészben a Neighbourhood (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.

Kapcsolódó szócikkek

• Markov-takaró
• Moore-szomszédság
• Neumann-szomszédság

Jegyzetek

• Hartsfeld, Nora & Ringel, Gerhard (1991), "Clean triangulations", Combinatorica 11 (2): 145–155, DOI 10.1007/BF01206358.
• Hell, Pavol (1978), "Graphs with given neighborhoods I", Problems Combinatories et theorie des graphes, vol. 260, Colloque internationaux C.N.R.S., pp. 219–223.
• Larrión, F.; Neumann-Lara, V. & Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics 258: 123–135, doi:10.1016/S0012-365X(02)00266-2, <http://xamanek.izt.uam.mx/map/papers/cuello10_DM.ps>.
• Malnič, Aleksander & Mohar, Bojan (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B 56 (2): 147–164, DOI 10.1016/0095-8956(92)90015-P.
• Sedlacek, J. (1983), "On local properties of finite graphs", Graph Theory, Lagów, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 242–247, ISBN 978-3-540-12687-4, DOI 10.1007/BFb0071634.
• Seress, Ákos & Szabó, Tibor (1995), "Dense graphs with cycle neighborhoods", Journal of Combinatorial Theory, Series B 63 (2): 281–293, doi:10.1006/jctb.1995.1020, <http://www.inf.ethz.ch/personal/szabo/PS/kornyezetek.ps>. Hozzáférés ideje: 2017-01-06 Archiválva 2005. augusztus 30-i dátummal a Wayback Machine-ben.
• Wigderson, Avi (1983), "Improving the performance guarantee for approximate graph coloring", Journal of the ACM 30 (4): 729–735, DOI 10.1145/2157.2158.