Граф Габрієла

Немає цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

Граф Габріеля 100 випадкових точок

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

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

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

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

Примітки

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.
5. Bose, Devroye, Evans, Kirkpatrick, 2006.