| dbo:abstract
|
- 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 ) 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 n(d + 1)/(d + 2) 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 (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, és a megoldásában egyaránt. A az NNG-beli utak követésével talál meg nagy sebességgel. Az NNG-k a vizsgálati területébe is tartoznak. (hu)
- 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 ) 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 n(d + 1)/(d + 2) 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 (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, és a megoldásában egyaránt. A az NNG-beli utak követésével talál meg nagy sebességgel. Az NNG-k a vizsgálati területébe is tartoznak. (hu)
|
