This HTML5 document contains 16 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n6http://www.kgraph.org/
n12http://
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n4http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n8http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Legközelebbi_szomszéd-gráf
rdfs:label
Legközelebbi szomszéd-gráf
dct:subject
n8:Geometriai_gráfok
dbo:wikiPageID
1592193
dbo:wikiPageRevisionID
23795085
dbo:wikiPageExternalLink
n6: n12:www.kgraph.org
prop-hu:wikiPageUsesTemplate
n4:Reflist n4:Wayback n4:Fordítás
prop-hu:date
20210123200644
prop-hu:url
n6:
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.
prov:wasDerivedFrom
wikipedia-hu:Legközelebbi_szomszéd-gráf?oldid=23795085&ns=0
dbo:wikiPageLength
6372
foaf:isPrimaryTopicOf
wikipedia-hu:Legközelebbi_szomszéd-gráf
Subject Item
wikipedia-hu:Legközelebbi_szomszéd-gráf
foaf:primaryTopic
dbpedia-hu:Legközelebbi_szomszéd-gráf