Граф Габриэля 100 случайных точекТочки и являются габриэлевыми соседями, так как лежит вне окружности с диаметром, представленным ребром .Наличие точки внутри окружности мешает точкам и быть габриэлевыми соседями.
Граф Габриэлямножества точек двумерного пространства выражает понятие близости этих точек. Формально, это граф с вершинами , в котором любые точки и смежны, когда они различны, то есть , и замкнутый круг с отрезком в качестве диаметра не содержит других элементов множества .
Графы Габриэля естественным образом обобщаются на более высокие размерности, где пустые диски заменяются пустыми замкнутыми шарами.
Названы в честь Рубена Габриэля[англ.], который ввёл их в совместной статье с Робертом Сокалом[англ.] в 1969.
Существование конечного порога перколяции[англ.] узлов для графов Габриэля доказали Бертен, Биллиот и Друилхет[1], а более точные значения как для порога узлов, так и порога рёбер (связей) дал Норренброк[2].
Граф является частным случаем бета-скелета Подобно бета-скелетам и, в отличие от триангуляции Делоне, данный граф не является геометрическим стягивающим деревом[англ.] — для некоторых множеств точек расстояния в графе Габриэля могут быть много больше евклидовых расстояний между точками[4].
Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Continuum percolation in the Gabriel graph // Advances in Applied Probability. — 2002. — Т. 34, вып. 4. — С. 689–701. — doi:10.1239/aap/1037990948.