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

Очки

a

и

b

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

c

находится вне окружности их диаметра.

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

c

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

a

и

b

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

В математике и вычислительной граф Габриэля множества геометрии $S$ количества точек на евклидовой плоскости выражает одно понятие близости или близости этих точек. Формально это график $G$ с набором вершин $S$ в котором любые две различные точки $p\in S$ и $q\in S$ соседствуют именно тогда, когда закрытый диск, имеющий $pq$ поскольку диаметр не содержит других точек. Другой способ выразить тот же критерий смежности состоит в том, что $p$ и $q$ должны быть двумя заданными точками, ближайшими к их средней точке , при этом ни одна другая заданная точка не находится так близко. Графы Габриэля естественным образом обобщаются на более высокие измерения, при этом пустые диски заменяются пустыми закрытыми шарами . Графики Габриэля названы в честь К. Рубена Габриэля , который представил их в статье с Робертом Р. Сокалем в 1969 году. ^[1]

перколяция

Для графов Габриэля бесконечных случайных наборов точек порог перколяции конечных узлов дает долю точек, необходимую для поддержки связности: если задано случайное подмножество с меньшим количеством вершин, чем порог, оставшийся граф почти наверняка будет иметь только конечные связные компоненты, в то время как если размер случайного подмножества больше порога, то оставшийся граф почти наверняка будет иметь бесконечную компоненту (а также конечные компоненты). Существование этого порога было доказано Бертеном, Биллиотом и Друиле (2002) . ^[2] а более точные значения порогов сайта и связи были даны Норренброком. ^[3]

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

Граф Габриэля является подграфом Делоне триангуляции . Его можно найти за линейное время , если задана триангуляция Делоне. ^[4]

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

Это экземпляр бета-скелета . Как и бета-скелеты и в отличие от триангуляции Делоне, это не геометрический гаечный ключ : для некоторых наборов точек расстояния внутри графика Габриэля могут быть намного больше, чем евклидовы расстояния между точками. ^[5]

Ссылки

^ Габриэль, К. Рубен ; Сокал, Роберт Р. (1969), «Новый статистический подход к анализу географических вариаций», Systematic Biology , 18 (3): 259–278, doi : 10.2307/2412323 , JSTOR 2412323
^ Бертен, Этьен; Биллио, Жан-Мишель; Друиле, Реми (2002), «Просачивание континуума в графе Габриэля», «Достижения в области прикладной теории вероятностей » , 34 (4): 689–701, doi : 10.1239/aap/1037990948 , MR 1938937 , S2CID 121288601
^ Норренброк, Кристоф (май 2016 г.), «Порог перколяции на плоских евклидовых графах Габриэля», European Physical Journal B , 89 (5): 111, arXiv : 1406.0663 , Bibcode : 2016EPJB...89..111N , doi : 10.1140/epjb /e2016-60728-0 , S2CID 254114033
^ Матула, Дэвид В .; Сокал, Роберт Р. (1980), «Свойства графиков Габриэля, имеющие отношение к исследованию географических вариаций и группировке точек на плоскости», Geographical Analysis , 12 (3): 205–222, doi : 10.1111/j.1538-4632.1980. tb00031.x
^ Бозе, Просенджит ; Деврой, Люк ; Эванс, Уильям; Киркпатрик, Дэвид (2006), «О соотношении охвата графов Габриэля и β-скелетов», SIAM Journal on Discrete Mathematics , 20 (2): 412–427, CiteSeerX 10.1.1.46.4728 , doi : 10.1137/S0895480197318088 , MR 2257270

[gabsok-1] Габриэль, К. Рубен ; Сокал, Роберт Р. (1969), «Новый статистический подход к анализу географических вариаций», Systematic Biology , 18 (3): 259–278, doi : 10.2307/2412323 , JSTOR 2412323

[bbd-2] Бертен, Этьен; Биллио, Жан-Мишель; Друиле, Реми (2002), «Просачивание континуума в графе Габриэля», «Достижения в области прикладной теории вероятностей » , 34 (4): 689–701, doi : 10.1239/aap/1037990948 , MR 1938937 , S2CID 121288601

[nor-3] Норренброк, Кристоф (май 2016 г.), «Порог перколяции на плоских евклидовых графах Габриэля», European Physical Journal B , 89 (5): 111, arXiv : 1406.0663 , Bibcode : 2016EPJB...89..111N , doi : 10.1140/epjb /e2016-60728-0 , S2CID 254114033

[matsok-4] Матула, Дэвид В .; Сокал, Роберт Р. (1980), «Свойства графиков Габриэля, имеющие отношение к исследованию географических вариаций и группировке точек на плоскости», Geographical Analysis , 12 (3): 205–222, doi : 10.1111/j.1538-4632.1980. tb00031.x

[bdek-5] Бозе, Просенджит ; Деврой, Люк ; Эванс, Уильям; Киркпатрик, Дэвид (2006), «О соотношении охвата графов Габриэля и β-скелетов», SIAM Journal on Discrete Mathematics , 20 (2): 412–427, CiteSeerX 10.1.1.46.4728 , doi : 10.1137/S0895480197318088 , MR 2257270

[1]

[2]

[3]

[4]

[5]