Габриэль граф

График Габриэля из 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) .

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

Граф Габриэль является подграф из триангуляции Делоне . Его можно найти за линейное время, если дана триангуляция Делоне ( Matula & Sokal 1980 ).

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

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

Ссылки [ править ]

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