Граф Габриэля множества точек двумерного пространства выражает понятие близости этих точек. Формально, это граф с вершинами , в котором любые точки и смежны, когда они различны, то есть , и замкнутый круг с отрезком в качестве диаметра не содержит других элементов множества .
Графы Габриэля естественным образом обобщаются на более высокие размерности, где пустые диски заменяются пустыми замкнутыми шарами. Названы в честь , который ввёл их в совместной статье с в 1969.
Протекание Существование конечного узлов для графов Габриэля доказали Бертен, Биллиот и Друилхет, а более точные значения как для порога узлов, так и порога рёбер (связей) дал Норренброк.
Связанные геометрические графы Граф Габриэля является подграфом триангуляции Делоне. Он может быть найден за линейное время, если триангуляция Делоне задана.
Граф Габриэля содержит в качестве подграфов евклидово минимальное остовное дерево, граф относительных окрестностей и граф ближайших соседей.
Граф является частным случаем бета-скелета Подобно бета-скелетам и, в отличие от триангуляции Делоне, данный граф не является геометрическим остовом — для некоторых множеств точек расстояния в графе Габриэля могут быть много больше евклидовых расстояний между точками.
Примечания
Литература
Категория:Планиметрия Категория:Геометрические графы Категория:Графы, имеющие собственные названия