Граф Ґабріеля у математиці та обчислювальній геометрії — це граф, що складається з множини точок в евклідовому просторі та виражає поняття їх близькості. Формально, це граф з набором вершин в якому будь-які точки та суміжні, якщо вони не тотожні, тобто , і замкнуте коло з відрізком у якості діаметра не містить інших елементів множини . Граф Ґабріеля природним чином узагальнюється до багатовимірних просторів, при цьому порожні кола заміняються порожніми замкнутими кулями. Граф названо за іменем Рубена Ґабріеля[en] який описав цей тип графу в спільній з Робертом Сокалом[en] статті 1969 року[1].

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

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

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

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

Примітки ред.

  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.