Граф ближайших соседей
Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P)Шаблон:Sfn.
Во многих обсуждениях направление рёбер игнорируется и ГБС определяется как обычный (неориентированный) граф. Однако отношение ближайшего соседства не является симметричным, т.е. если q является ближайшим соседом p, то p не обязательно будет ближайшим соседом q.
В некоторых обсуждениях, чтобы сделать выбор ближайшего соседа единственным, множество P индексируется и когда происходит выбор ближайшего объекта, выбирается объект с наибольшим индексомШаблон:Sfn.
Граф k-ближайших соседей (k-ГБС) — это граф, в котором две вершины p и q связаны ребром, если расстояние между p и q находится среди k наименьших расстояний от p до других объектов в P. ГБС является частным случаем k-ГБС, а именно, это 1-ГБС. k-ГБС удовлетворяют условиям теоремы о планарном разбиении — их можно разбить на два подграфа с максимум вершинами путём удаления ) точекШаблон:Sfn.
Другой частный случай — (n − 1)-ГБС. Этот граф называется графом дальних соседей (ГДС).
В теоретических обсуждениях алгоритмов часто предполагается некий вид общего положения, а именно, что для каждого объекта ближайший (k-ближайший) сосед единственен. При имплементации алгоритмов необходимо учитывать, что это условие не всегда выполняется.
ГДС как для точек на плоскости, так и для точек в многомерных пространствах, находят приложения, например, в сжатии данных, для Шаблон:Не переведено 5 и размещения объектов. В статистическом анализе Шаблон:Не переведено 5, основанный на путях в этом графе, может быть использовано для быстрого поиска иерархических кластеризаций. Графы ближайших соседей являются также предметом вычислительной геометрии.
Графы ближайших соседей для множеств точек
Одномерный случай
Для множества точек на плоскости ближайшим соседом точки является левый или правый (или оба) сосед, если они отсортированы вдоль прямой. Таким образом, ГБС является путём или лесом нескольких путей и может быть построен за время O(n log n) путём сортировки. Эта оценка является Шаблон:Не переведено 5 для некоторых моделей вычислений, поскольку построенный ГБС даёт ответ задачи Шаблон:Не переведено 5 — достаточно проверить, нет ли в полученном ГБС ребра нулевой длины.
Более высокие размерности
Если нет явного указания, предполагается, что графы ближайших соседей являются ориентированными графами с единственным образом определённым соседями, как описано во введении.
- Вдоль любого ориентированного пути в ГБС длины рёбер не увеличиваютсяШаблон:Sfn.
- Возможны циклы лишь длины 2 в ГБС и каждая слабо связная компонента ГДС с 2 и более вершинами имеет в точности один 2-циклШаблон:Sfn.
- Для точек плоскости ГБС является планарным графом со степенями вершин, не превосходящими 6. Если точки находятся в общем положении, степень вершин не превосходит 5Шаблон:Sfn.
- ГБС (рассматриваемый как неориентированный граф с разрешением нескольких ближайших соседей) множества точек плоскости или любого пространства более высокой размерности является подграфом триангуляции Делоне, графа Габриэля и Шаблон:Не переведено 5Шаблон:Sfn. Если точки находятся в общей позиции или если наложено условие единственности ближайшего соседа, ГБС является лесом, подграфом Шаблон:Не переведено 5.