Граф ближайших соседей

Граф ближайших соседей (Nearest neighbor graph) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует дуга из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P).

Во многих обсуждениях направление рёбер игнорируется и граф ближайших соседей определяется как обычный (неориентированный) граф. Однако отношение ближайшего соседства не является симметричным, т. е. если q является ближайшим соседом p, то p не обязательно будет ближайшим соседом q.