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

График Габриэля из 100 случайных точек
Точки и соседи Габриэля, так как находится за пределами их диаметра круга.
Наличие точки внутри круга предотвращает точки и от того, чтобы быть соседями Габриэля.

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

Перколяция

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

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

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

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

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

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

  • Бертен, Этьен; Биллиот, Жан-Мишель; Друйе, Реми (2002), "Перколяция континуума в графе Габриэля", Достижения в прикладной теории вероятностей, 34 (4): 689–701, Дои:10.1239 / aap / 1037990948, МИСТЕР  1938937.
  • Бозе, Просенджит; Деврой, Люк; Эванс, Уильям; Киркпатрик, Дэвид (2006), «О покрываемости графов Габриэля и β-скелетов», Журнал SIAM по дискретной математике, 20 (2): 412–427, CiteSeerX  10.1.1.46.4728, Дои:10.1137 / S0895480197318088, МИСТЕР  2257270.
  • Габриэль, Куно Рубен; Сокал, Роберт Реувен (1969), «Новый статистический подход к анализу географических вариаций», Систематическая биология, Общество систематических биологов, 18 (3): 259–278, Дои:10.2307/2412323, JSTOR  2412323.
  • Матула, Дэвид В .; Сокал, Роберт Реувен (1980), «Свойства графов Габриэля, относящиеся к исследованию географических вариаций и кластеризации точек на плоскости», Геогр. Анальный., 12 (3): 205–222, Дои:10.1111 / j.1538-4632.1980.tb00031.x.
  • Норренброк, Кристоф (2014), Порог перколяции на плоских евклидовых графах Габриэля, arXiv:1406.0663, Bibcode:2014arXiv1406.0663N.