Граф Ґабріеля у математиці та обчислювальній геометрії — це граф, що складається з множини точок в евклідовому просторі та виражає поняття їх близькості. Формально, це граф з набором вершин в якому будь-які точки та суміжні, якщо вони не тотожні, тобто , і замкнуте коло з відрізком як діаметр, не містить інших елементів множини . Граф Ґабріеля природним чином узагальнюється до багатовимірних просторів, при цьому порожні кола заміняються порожніми замкнутими кулями. Граф названо за іменем який описав цей тип графу в спільній з статті 1969 року.
Для графу Ґабріеля доведено існування граничного порогу перколяції (захоплення окремих вузлів графу та утворення нескінченної сукупності) та обраховано точні значення для порогового рівня перколяції окремих вузлів та зв'язків (ребер).
Пов'язані геометричні графи Граф Ґабріеля це підграф тріангуляції Делоне. Він може бути побудований за лінійний час, якщо тріангуляцію Делоне задано. Граф Габріеля містить як підграфи евклідове мінімальне кістякове дерево, граф відносних околів і граф найближчих сусідів. Граф є частковим випадком бета-кістяка. Подібно до бета-кістяків і на відміну від тріангуляції Делоне, цей граф не є геометричним стягувальним деревом — для деяких множин точок відстані в графі Габріеля можуть бути значно більшими від евклідових відстаней між точками.
Примітки