Меню Главная Случайная статья Настройки Граф Габриэля Материал из https://ru.wikipedia.org Граф Габриэля множества ${\displaystyle S}$ точек двумерного пространства выражает понятие близости этих точек. Формально, это граф ${\displaystyle G}$ с вершинами ${\displaystyle S}$, в котором любые точки ${\displaystyle p\in S}$ и ${\displaystyle q\in S}$ смежны, когда они различны, то есть ${\displaystyle p\neq q}$, и замкнутый круг с отрезком ${\displaystyle {\overline {pq}}}$ в качестве диаметра не содержит других элементов множества ${\displaystyle S}$. Графы Габриэля естественным образом обобщаются на более высокие размерности, где пустые диски заменяются пустыми замкнутыми шарами. Названы в честь Рубена Габриэля[англ.], который ввёл их в совместной статье с Робертом Сокалом[англ.] в 1969. Содержание 1 Протекание 2 Связанные геометрические графы 3 Примечания 4 Литература Протекание Существование конечного порога перколяции[англ.] узлов для графов Габриэля доказали Бертен, Биллиот и Друилхет[1], а более точные значения как для порога узлов, так и порога рёбер (связей) дал Норренброк[2]. Связанные геометрические графы Граф Габриэля является подграфом триангуляции Делоне. Он может быть найден за линейное время, если триангуляция Делоне задана[3]. Граф Габриэля содержит в качестве подграфов евклидово минимальное остовное дерево, граф относительных окрестностей и граф ближайших соседей. Граф является частным случаем бета-скелета Подобно бета-скелетам и, в отличие от триангуляции Делоне, данный граф не является геометрическим стягивающим деревом[англ.] — для некоторых множеств точек расстояния в графе Габриэля могут быть много больше евклидовых расстояний между точками[4]. Примечания Bertin, Billiot, Drouilhet, 2002. Norrenbrock, 2014. Matula, Sokal, 1980. Bose, Devroye, Evans, Kirkpatrick, 2006. Литература Etienne Bertin, Jean-Michel Billiot, Rmy Drouilhet. Continuum percolation in the Gabriel graph // Advances in Applied Probability. — 2002. — Т. 34, вып. 4. — С. 689–701. — doi:10.1239/aap/1037990948. Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. On the spanning ratio of Gabriel graphs and -skeletons // SIAM Journal on Discrete Mathematics. — 2006. — Т. 20, вып. 2. — С. 412–427. — doi:10.1137/S0895480197318088. Kuno Ruben Gabriel, Robert Reuven Sokal. A new statistical approach to geographic variation analysis // Systematic Biology. — Society of Systematic Biologists, 1969. — Т. 18, вып. 3. — С. 259–278. — doi:10.2307/2412323. — . David W. Matula, Robert Reuven Sokal. Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane // Geogr. Anal.. — 1980. — Т. 12, вып. 3. — С. 205–222. — doi:10.1111/j.1538-4632.1980.tb00031.x. Christoph Norrenbrock. Percolation threshold on planar Euclidean Gabriel Graphs. — 2014. — . — arXiv:1406.0663.