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

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

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

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

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

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

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