A matematika, azon belül a gráfelmélet területén n darab valamely metrikus térbeli P objektumhoz (pl. pontok halmazához a síkban euklideszi távolsággal) tartozó legközelebbi szomszéd-gráf (nearest neighbor graph, NNG) olyan irányított gráf, melynek csúcshalmazában P minden eleméhez egy-egy csúcs tartozik, és p-ből q csúcsba pontosan akkor mutat irányított él, ha q a p legközelebbi szomszédja (azaz a p és q távolsága nem nagyobb, mint p és a P-beli bármely más objektum távolsága).
Sok esetben az élek irányítottságától eltekintenek, és az NNG-t irányítatlan gráfként definiálják. A legközelebbi szomszéd-reláció azonban nem szimmetrikus, tehát definícióban szereplő p nem feltétlenül q legközelebbi szomszédja.
Ha egy cikkben szükséges, hogy az objektumok legközelebbi szomszédja egyértelmű legyen, a P halmaz elemeit megszámozzák és döntetlen esetén pl. a legmagasabb indexű elemet tekintik a legközelebbi szomszédnak.
A k-legközelebbi szomszéd-gráf (k-NNG) olyan gráf, melyben p-ből q-ba akkor húzódik él, ha a p és q közötti távolság a p és a többi P-beli objektum közötti távolságok között a k-adik legkisebb távolságok között van. Az NNG a k-NNG speciális esete, méghozzá ez az 1-NNG. A k-NNG-kre egyfajta szeparációs tétel vonatkozik: O(k1/dn1 − 1/d) csúcs eltávolításával két, egyenként legfeljebb csúcsból álló részgráffá particionálhatók.
Egy másik speciális eset az (n − 1)-NNG. Ez a gráf a legtávolabbi szomszéd-gráf (farthest neighbor graph, FNG).
Az algoritmusok elméleti tárgyalása során az egyszerűség kedvéért gyakran az objektumok általános helyzetét feltételezik, tehát hogy a legközelebbi (k-legközelebbi) szomszéd minden objektum esetében egyedi. Az algoritmusok implementációjánál fontos odafigyelni arra, hogy az egyediség nem minden esetben áll fenn.
A síkban, vagy akár sokdimenziós terekben elhelyezkedő pontok legközelebbi szomszéd-gráfjait több helyen alkalmazzák: adattömörítésben, mozgástervezésben és a létesítmény-elhelyezési probléma megoldásában egyaránt. A statisztikai analízis legközelebbi szomszéd-láncalgoritmusa az NNG-beli utak követésével talál meg hierarchikus klasztereket nagy sebességgel. Az NNG-k a számítási geometria vizsgálati területébe is tartoznak.
Ponthalmazok NNG-i
Egydimenziós eset
Az egy egyenesen elhelyezkedő ponthalmaz esetén egy pont legközelebbi szomszédja a tőle balra és/vagy jobbra elhelyezkedő pont. Ebből adódóan az NNG vagy egy útgráf, vagy diszjunkt útgráfokból álló erdő, és rendezés segítségével O(n log n) idő alatt előállítható. Ez a becslés egyes számítási modellekben aszimptotikusan optimális, mivel a megszerkesztett NNG megadja a választ a listaelem-egyediség problémára: elegendő annak vizsgálata, hogy az NNG tartalmaz-e nulla hosszúságú élt.
Magasabb dimenziók A továbbiakban feltételezzük, hogy az NNG-k irányított gráfok, és a legközelebbi szomszédok egyértelműen meghatározhatók. A következőket állíthatjuk:
Egy NNG bármely irányított útjának élhosszai monoton csökkenőek. Egy NNG-ben csak 2 hosszúságú körök lehetségesek és minden, legalább két csúcsból álló gyengén összefüggő komponensben pontosan egy 2-kör található. Síkbeli pontok NNG-je síkbarajzolható gráf, mely csúcsainak fokszáma legfeljebb 6 lehet. Általános helyzetű pontok esetén a maximális fokszám csak 5. Egy sík vagy magasabb dimenziójú tér pontjainak NNG-je (itt irányítatlan gráfként kezelve és a többszörös legközelebbi szomszédokat is megengedve) a pontok Delaunay-háromszögelésének, Gabriel-gráfjának és a fél-Yao-gráfjának is részgráfja. Ha a pontok általános helyzetűek vagy ha a szomszédok egyediségét is megköveteljük, az NNG egy erdő, az euklideszi minimális feszítőfa részgráfja.
Fordítás
Jegyzetek
További információk C++ library for efficient nearest-neighbor graph construction
Kategória:Geometriai gráfok