Граф Габріеля

Граф Ґабріеля у математиці та обчислювальній геометрії — це граф, що складається з множини точок $S$ в евклідовому просторі та виражає поняття їх близькості. Формально, це граф $G$ з набором вершин $S$ в якому будь-які точки $p\in S$ та $q\in S$ суміжні, якщо вони не тотожні, тобто $p\neq q$ , і замкнуте коло з відрізком ${\overline {pq}}$ у якості діаметра не містить інших елементів множини $S$ . Граф Ґабріеля природним чином узагальнюється до багатовимірних просторів, при цьому порожні кола заміняються порожніми замкнутими кулями. Граф названо за іменем Рубена Ґабріеля^[en] який описав цей тип графу в спільній з Робертом Сокалом^[en] статті 1969 року^[1].

Для графу Ґабріеля доведено існування граничного порогу перколяції (захоплення окремих вузлів графу та утворення нескінченної сукупності)^[2] та обраховано точні значення для порогового рівня перколяції окремих вузлів та зв'язків (ребер)^[3].

Пов'язані геометричні графи

Граф Ґабріеля це підграф тріангуляції Делоне. Він може бути побудований за лінійний час, якщо тріангуляцію Делоне задано^[4].

Граф Габріеля містить як підграфи евклідове мінімальне кістякове дерево, граф відносних околів і граф найближчих сусідів.
Граф є частковим випадком бета-кістяка. Подібно до бета-кістяків і на відміну від тріангуляції Делоне, цей граф не є геометричним стягувальним деревом — для деяких множин точок відстані в графі Габріеля можуть бути значно більшими від евклідових відстаней між точками^[5].

Примітки

↑ Gabriel, K. Ruben; Sokal, Robert R. (1969-09-XX). A New Statistical Approach to Geographic Variation Analysis. Systematic Zoology. Т. 18, № 3. с. 259. doi:10.2307/2412323. Архів оригіналу за 10 листопада 2021. Процитовано 13 квітня 2021.
↑ Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002-12-XX). Continuum percolation in the Gabriel graph. Advances in Applied Probability (англ.). Т. 34, № 4. с. 689—701. doi:10.1239/aap/1037990948. ISSN 0001-8678. Процитовано 13 квітня 2021.
↑ Norrenbrock, Christoph (1 червня 2014). Percolation threshold on planar Euclidean Gabriel Graphs. arXiv e-prints. Т. 1406. с. arXiv:1406.0663. Процитовано 13 квітня 2021.
↑ Matula, David W.; Sokal, Robert R. (3 вересня 2010). Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane. Geographical Analysis (англ.). Т. 12, № 3. с. 205—222. doi:10.1111/j.1538-4632.1980.tb00031.x. Процитовано 13 квітня 2021.
↑ Bose, Devroye, Evans, Kirkpatrick, 2006.

[1] Gabriel, K. Ruben; Sokal, Robert R. (1969-09-XX). A New Statistical Approach to Geographic Variation Analysis. Systematic Zoology. Т. 18, № 3. с. 259. doi:10.2307/2412323. Архів оригіналу за 10 листопада 2021. Процитовано 13 квітня 2021.

[2] Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002-12-XX). Continuum percolation in the Gabriel graph. Advances in Applied Probability (англ.). Т. 34, № 4. с. 689—701. doi:10.1239/aap/1037990948. ISSN 0001-8678. Процитовано 13 квітня 2021.

[3] Norrenbrock, Christoph (1 червня 2014). Percolation threshold on planar Euclidean Gabriel Graphs. arXiv e-prints. Т. 1406. с. arXiv:1406.0663. Процитовано 13 квітня 2021.

[4] Matula, David W.; Sokal, Robert R. (3 вересня 2010). Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane. Geographical Analysis (англ.). Т. 12, № 3. с. 205—222. doi:10.1111/j.1538-4632.1980.tb00031.x. Процитовано 13 квітня 2021.

[FOOTNOTEBose,_Devroye,_Evans,_Kirkpatrick2006-5] Bose, Devroye, Evans, Kirkpatrick, 2006.

[1]

[2]

[3]

[4]

[5]