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.
A szomszédság jelölése lehet NG(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 NG[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
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 (Sablon:Harvnb, Sablon:Harvnb). 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 C4.
További példák:
- Bármely Kn teljes gráf lokálisan Kn−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 Sablon:Harv.
- 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 C4 gráf, az ikozaéder az egyetlen lokálisan C5 gráf, és a 13 rendű Paley-gráf lokálisan C6. A K4 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 (Sablon:Harvnb; Sablon:Harvnb; Sablon:Harvnb). A lokálisan körgráfok éleinek száma akár is lehet Sablon:Harv.
- 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 C5 és a C5 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.