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

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

Граф Габриэля 100 случайных точек

Точки $a$$a$ и $b$$b$ являются габриэлевыми соседями, так как $c$$c$ лежит вне окружности с диаметром, представленным ребром $ab$$ab$.

Наличие точки $c$$c$ внутри окружности мешает точкам $a$$a$ и $b$$b$ быть габриэлевыми соседями.

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

ПротеканиеПравить

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

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

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

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

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