Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




14.09.2021


13.09.2021


12.09.2021


11.09.2021


10.09.2021





Яндекс.Метрика

Граф Габриэля

04.03.2021

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

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

Протекание

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

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

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