Граф Габриэля

Граф Габриэля (Gabriel graph) множества [math]\displaystyle{ S }[/math] точек двумерного пространства выражает понятие близости этих точек. Формально, это --- граф [math]\displaystyle{ G }[/math] с множеством вершин [math]\displaystyle{ S }[/math], в котором любые две различные точки [math]\displaystyle{ p, q \in S }[/math] смежны, если замкнутый круг с отрезком [math]\displaystyle{ \overline{pq} }[/math] в качестве диаметра не содержит других элементов множества [math]\displaystyle{ S }[/math].

Графы Габриэля естественным образом обобщаются на пространства более высоких размерностей заменой кругов на шары. Названы в честь К.Р.Габриэля (K.R. Gabriel), который их ввёл в 1969.

Граф Габриэля является подграфом триангуляции Делоне и может быть найден за линейное время, если триангуляция Делоне задана. Он содержит в качестве подграфов евклидово минимальное остовное дерево, граф относительных окрестностей и граф ближайших соседей.