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 (, ). 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  .
 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 (; ; ). A lokálisan körgráfok éleinek száma akár  is lehet .
 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.

Fordítás

Kapcsolódó szócikkek
 Markov-takaró
 Moore-szomszédság
 Neumann-szomszédság

Jegyzetek
.
.
.
.
.
 .
.

Gráfelméleti objektumok
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ó, csúccsal éséllel rendelkező gráfban azös számú csúcs szomszédos azéscsúcsokkal , de nem szomszédos aés 6 csúccsal . Azös csúcs szomszédsága azcsúcsokból és azé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 ( , ) . 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 \ . 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 arendű 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 ( ; ; ) . A lokálisan körgráfok éleinek száma akár is lehet \ . 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 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 Kapcsolódó szócikkek Markov-takaró Moore-szomszédság Neumann-szomszédság Jegyzetek . . . . . \ . . Gráfelméleti objektumok