Ugrás a tartalomhoz

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

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
Egy hat csúcsot és hét élet tartalmazó gráf

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

[szerkesztés]
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 C4.

További példák:

Halmaz szomszédsága

[szerkesztés]

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

[szerkeszté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

[szerkesztés]

Jegyzetek

[szerkesztés]