57
правок
Изменения
Нет описания правки
{{Определение
|id=def1
|definition='''Триангуляция графа''' {{---}} представление [[Укладка графов#defplanar | планарного графа ]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
}}
Мы получили граф <tex>G'</tex>, с меньшим числом вершин равным <tex>V - 1</tex>, то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных <tex>s</tex>).
Для любого <tex>\varepsilon > 0</tex> обозначим <tex>C_{\varepsilon}(s)</tex> {{---}} круг радиуса <tex>\varepsilon</tex>, с вершиной <tex>s</tex> в центре.
Для каждого соседа <tex>t</tex> вершины <tex>s</tex> в графе <tex>G'</tex> обозначим <tex>R_{\varepsilon}(t)</tex> область, содержащую множество объединение всех окрытых отрезков от , проведённых из <tex>t</tex> до каждой точки из в <tex>C_{\varepsilon}(s)</tex>.
Возьмем <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s</tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.
