Габриэль граф - Gabriel graph

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

Точки

{ displaystyle a}

и

{ displaystyle b}

соседи Габриэля, так как

{ displaystyle c}

находится за пределами их диаметра круга.

Наличие точки

{ displaystyle c}

внутри круга предотвращает точки

{ displaystyle a}

и

{ displaystyle b}

от того, чтобы быть соседями Габриэля.

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

Перколяция

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

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

Граф Габриэля - это подграф из Триангуляция Делоне. Его можно найти в линейное время если дана триангуляция Делоне (Матула и Сокал 1980 ).

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

Это пример бета-скелет. Подобно бета-скелетам и в отличие от триангуляции Делоне, это не геометрический гаечный ключ: для некоторых наборов точек расстояния в графе Габриэля могут быть намного больше, чем евклидовы расстояния между точками (Bose et al. 2006 г. ).

Габриэль граф - Gabriel graph

Перколяция

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

Рекомендации