Граф Габріеля
Граф Ґабріеля у математиці та обчислювальній геометрії — це граф, що складається з множини точок в евклідовому просторі та виражає поняття їх близькості. Формально, це граф з набором вершин в якому будь-які точки та суміжні, якщо вони не тотожні, тобто , і замкнуте коло з відрізком у якості діаметра не містить інших елементів множини . Граф Ґабріеля природним чином узагальнюється до багатовимірних просторів, при цьому порожні кола заміняються порожніми замкнутими кулями. Граф названо за іменем Рубена Ґабріеля[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.
