57
правок
Изменения
Нет описания правки
|proof=
Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G </tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>V</tex>. Предположим, что графы с числом вершин, меньшим <tex>V</tex>, мы можем нарисовать требуемым образом.
База: <tex>V=3</tex> {{---}} тривиально.
Переход: <tex>V \geqslant 4</tex>
Рассмотрим ребро <tex>vw</tex>. Если в <tex>G</tex> нет разделяющих треугольников, то <tex>vw</tex> – {{---}} любое. Иначе <tex>vw</tex> – {{---}} ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в <tex>G</tex>. Тогда <tex>vw</tex> – {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.
[[File:Fary2.png|250px|Рисунок 2]]
Если <tex>vw</tex> не в разделяющем треугольнике <tex>p</tex> и <tex>q</tex> – {{---}} любые общие соседи <tex>v</tex> и <tex>w</tex>.
Пусть <tex>(vp, vw, vq, vx_1, vx_2 ... vx_k)</tex> и <tex>(wq, wv, wp, wy_1, wy_2 ... wy_m)</tex> – обход по часовой стрелке ребер, исходящих соостветсвенно из <tex>v</tex> и <tex>w</tex>.
Пусть <tex>G'</tex> – {{---}} планарная триангуляция, полученная из G стягиванием ребра <tex>vw</tex> в вершину <tex>s</tex>. Заменим пары параллельных ребер <tex>vq</tex> и <tex>wq</tex> на <tex>sq</tex> и <tex>vp, wp</tex> на <tex>sp</tex>. Получим вершину <tex>s</tex>, из которой исходят ребра <tex>(sp, sy_1, sy_2 ... sy_m, sq, sx_1, sx_2 ... sx_k)</tex> {{---}} по часовой стрелке.
[[File:Fary3.png|250px|Рисунок 3]]
Мы получили граф <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>.
[[File:Fary4.png|250px|Рисунок 5]]
Проведем линию <tex>L</tex> через вершину <tex>s</tex> так, чтобы вершина <tex>p</tex> лежала с одной ее стороны, а <tex>q</tex> — {{---}} с другой (иначе <tex>L</tex> наложится на ребра <tex>sp</tex> и <tex>sq</tex>) и никакое из ребер <tex>\{sx_i : 1 < i < k\}</tex> и <tex>\{sy_i : 1 < i < m\}</tex> не лежало на <tex>L</tex>.
Ребра <tex>sq</tex> и <tex>sq</tex> разбивают <tex>C_{\varepsilon}(s)</tex> на две дуги: первая пересекает ребра <tex>\{sx_i : 1 < i < k\}</tex>, а вторая {{---}} ребра <tex>\{sy_i : 1 < i < m\}</tex>.
<tex>L</tex> пересекает <tex>C_{\varepsilon}(s)</tex> в двух точках. Расположим <tex>v</tex> и <tex>w</tex> в этих точках: <tex>v</tex> на дуге, пересекающей <tex>\{sx_i : 1 < i < k\}</tex>, а <tex>w</tex> с другой стороны.
