Граф найбли́жчих сусі́дів (ГНС) для множини P, що складається з n об'єктів у метричному просторі (наприклад, для множини точок на площині з евклідовою метрикою) — орієнтований граф, вершинами якого є елементи множини P, в якому існує орієнтоване оебро з p в q, якщо q є найближчим сусідом p (тобто відстань від p до q не більша, ніж від p до будь-якого іншого об'єкта з P)[1].
У багатьох обговореннях напрямок ребер нехтують та ГНС визначають як звичайний (неорієнтований) граф. Проте відношення найближчого сусідства не є симетричним, тобто, якщо q є найближчим сусідом p, то p не обов'язково є найближчим сусідом q.
У деяких обговореннях, щоб зробити вибір найближчого сусіда єдиним, множину P індексують і коли відбувається вибір найближчого об'єкта, вибирають об'єкт із найбільшим індексом[2].
Граф k-найближчих сусідів (k-ГНС) — це граф, у якому дві вершини p і q пов'язані ребром, якщо відстань між p і q належить до k найменших відстаней від p до інших об'єктів у P. ГНС є окремим випадком k-ГНС, а саме, це 1-ГНС. k-ГНС задовольняють умовам теореми про планарне розбиття — їх можна розбити на два підграфи з максимум вершинами, видаливши ) точок[3].
Інший окремий випадок — (n − 1)-ГНС. Цей граф називається графом далеких сусідів (ГДС).
У теоретичних обговореннях алгоритмів часто передбачається певний вид загального положення, а саме, що для кожного об'єкта найближчий (k-найближчий) сусід єдиний. При імплементації алгоритмів слід ураховувати, що ця умова не завжди виконується.
Для множини точок на прямій найближчим сусідом точки є лівий або правий (або обидва) сусіди, якщо вони відсортовані вздовж прямої. Таким чином, ГНС є шляхом або лісом декількох шляхів і його можна побудувати за часO(n log n) шляхом сортування. Ця оцінка є асимптотично оптимальною[en] для деяких моделей обчислень, оскільки побудований ГНС дає відповідь для задачі унікальності елементів[en] — достатньо перевірити, чи немає в отриманому ГНС ребра нульової довжини.
Вищі розмірності
Якщо немає явної вказівки, передбачається, що графи найближчих сусідів є орієнтованими графами з єдиним способом визначеними сусідами, як описано у вступі.
Уздовж будь-якого орієнтованого шляху ГНС довжини ребер не збільшуються[2].
У ГНС можливі цикли лише довжини 2 і кожна слабко зв'язна компонента ГДС із 2 і більше вершинами має рівно один 2-цикл[2].
Gary L. Miller, Shang-Hua Teng, William Thurston, Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs // J. ACM. — 1997. — Т. 44, вип. 1 (18 жовтня). — С. 1–29. — DOI:10.1145/256292.256294.