WikiSort.ru - Не сортированное

Граф Габриэля множества ${\displaystyle S}$ точек двумерного пространства выражает понятие близости этих точек. Формально, это граф ${\displaystyle G}$ с вершинами ${\displaystyle S}$ , в котором любые точки ${\displaystyle p\in S}$ и ${\displaystyle q\in S}$ смежны, когда они различны, то есть, ${\displaystyle p\neq q}$ , и замкнутый круг с отрезком ${\displaystyle {\overline {pq}}}$ в качестве диаметра не содержит других элементов множества ${\displaystyle S}$ .

Графы Габриэля естественным образом обобщаются на более высокие размерности, где пустые диски заменяются пустыми замкнутыми шарами. Названы в честь Рубена Габриэля^[en], который ввёл их в совместной статье с Робертом Сокалом^[en] в 1969.

Протекание

Сущестование конечного порога перколяции^[en] узлов для графов Габриэля доказали Бертен, Биллиот и Друилхет^[1], а более точные значения как для порога узлов, так и порога рёбер (связей) дал Норренброк^[2].

Связанные геометрические графы

• Граф Габриэля является подграфом триангуляции Делоне. Он может быть найден за линейное время если триангуляция Делоне задана^[3].

• Граф Габриэля содержит в качестве подграфов евклидово минимальное остовное дерево, граф относительных окрестностей^[en] и граф ближайших соседей.

• Граф является частным случаем бета-скелета^[en]. Подобно бета-скелетам и в отличие от триангуляции Делоне данный граф не является геометрическим стягивающим деревом^[en] — для некоторых множеств точек расстояния в графе Габриэля могут быть много больше евклидовых расстояний между точками^[4].

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.