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

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

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

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

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

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

Протекание

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья