A legközelebbi szomszédok grafikonja

A legközelebbi szomszéd gráf ( GBC ) egy metrikus térben lévő n objektumból álló P halmazhoz (például egy euklideszi metrikával rendelkező sík ponthalmazához ) egy irányított gráf, amelynek csúcsai a P halmaz elemei , amelynek p -től q -ig van egy irányított éle , ha q a p legközelebbi szomszédja (azaz a p -től a q -ig mért távolság nem nagyobb, mint a p -től a P -ből származó bármely más objektumig ) [1] .

Sok vitában az élek irányát figyelmen kívül hagyják, és a GBS-t közönséges (iránytalan) gráfként határozzák meg . A legközelebbi szomszéd kapcsolat azonban nem szimmetrikus , azaz. ha q p legközelebbi szomszédja , akkor p nem feltétlenül q legközelebbi szomszédja .

Egyes vitákban a legközelebbi szomszéd választásának egyedivé tétele érdekében a P halmazt indexeljük, és amikor a legközelebbi objektumot választjuk, a legmagasabb indexű objektumot választjuk [2] .

A k -legközelebbi szomszéd gráf ( k -GBN ) egy olyan gráf, amelyben két p és q csúcsot egy él köt össze, ha p és q távolsága a p -től a P -ben lévő többi objektumtól való k legkisebb távolság közé tartozik . A GBS a k -GBS speciális esete, vagyis 1-GBS. k -GBS teljesíti a síkbeli felosztási tétel feltételeit - ) pontok eltávolításával két részgráfra oszthatók, maximum csúcsokkal [3] .

Egy másik speciális eset az ( n  − 1)-GBS. Ezt a gráfot távoli szomszéd gráfnak (FDN) nevezik .

Az algoritmusok elméleti tárgyalása során gyakran feltételeznek valamilyen általános álláspontot , nevezetesen, hogy minden objektum esetében a legközelebbi (k-közelebbi) szomszéd egyedi. Az algoritmusok implementálásakor figyelembe kell venni, hogy ez a feltétel nem mindig teljesül.

A GDS mind a síkban lévő pontok, mind a többdimenziós terek pontjai számára alkalmazásokat találhat, például az adattömörítésben , a mozgástervezésben és az objektumok elhelyezésében . A statisztikai elemzésben a gráf útvonalain alapuló legközelebbi szomszéd lánc algoritmus használható a hierarchikus klaszterezések gyors megtalálására . A legközelebbi szomszéd gráfok szintén a számítási geometria tárgyát képezik .

Ponthalmazok legközelebbi szomszédos grafikonjai

Egydimenziós tok

Egy síkban lévő ponthalmaz esetén a pont legközelebbi szomszédja a bal vagy a jobb (vagy mindkettő) szomszédja, ha egyenes vonal mentén vannak rendezve. Így a GBS több ösvényből álló ösvény vagy erdő , és rendezéssel O ( n log n ) idő alatt megépíthető . Ez a becslés aszimptotikusan optimális egyes számítási modelleknél , mivel a megszerkesztett GBS választ ad az elemegyediségi problémára – elegendő ellenőrizni, hogy a kapott GBS tartalmaz-e nulla hosszúságú élt.

Magasabb méretek

Hacsak nincs kifejezetten kijelentve, a legközelebbi szomszéd gráfokról azt feltételezzük, hogy irányított gráfok egyedileg meghatározott szomszédokkal, a bevezetőben leírtak szerint.

  1. A GBS bármely orientált útvonala mentén az élek hossza nem nő [2] .
  2. GBS-ben csak 2 hosszúságú ciklusok lehetségesek, és minden gyengén kapcsolt, 2 vagy több csúcsot tartalmazó GDS-komponensnek pontosan egy 2-ciklusa van [2] .
  3. Síkpontok esetén a GBS egy sík gráf , amelynek csúcsfoka nem haladja meg a 6-ot. Ha a pontok általános helyzetben vannak , a csúcs foka nem haladja meg az 5-öt [2] .
  4. A GBS (amelyet irányítatlan gráfnak tekintünk több legközelebbi szomszéd felbontással) egy síkban vagy bármely magasabb dimenziójú térben lévő ponthalmaznak egy Delaunay-háromszögelés , egy Gabriel-gráf és egy félig Y-gráf részgráfja [ 4] . Ha a pontok közös helyzetben vannak, vagy ha egyedi legközelebbi szomszéd feltételt szabunk meg, akkor a GBS egy erdő , az euklideszi minimum feszítőfa részgráfja .

Jegyzetek

  1. ↑ Preparata, Sheimos, 1989 .
  2. ↑ 1 2 3 4 Eppstein, Paterson, Yao, 1997 , p. 263–282.
  3. ↑ Miller, Teng, Thurston, Vavasis, 1997 .
  4. ↑ Rahmati, King, Whitesides, 2013 , p. 137–144.

Irodalom

Linkek