Изменения

[[File:Fary1.png|thumb|250px|Рисунок 1]]Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936 года, 1936ом году и Иштваном Фари (István Fáry) в 1948ом году и Штейном в 1951ом году. Иногда ее называют теоремой Фари-Вагнера.

|neat = 1|definition='''Триангуляция графа — ''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа ]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).

|neat = 1|definition='''Разделяющий треугольник — ''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3 </tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.

Разделяющий треугольник представлен изображён ниже. Относительно него существует три вида вершин: внешние, внутренние и лежащие на рисунке 1самом треугольнике.

|statement= Любой планарный граф имеет плоское представление на плоскости, в котором все его ребра будут прямымипредставлены в виде отрезков прямых.

Возьмем E равным минимуму из всех расстояний от вершины s до инцидентных ей Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>|V|</tex>. База индукции, когда <tex>|V|=3</tex>, выполняется тривиальным образом.Предположим, что графы с любым числом вершин меньше <tex>|V| \geqslant 4</tex>, мы можем нарисовать требуемым образом. Рассмотрим ребро <tex>vw</tex>, [[Матрица инцидентности графа#definc | инцидентное]] внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и до отрезков, проходящих мимо нее <tex>vwq</tex>.  [[File:Fary5Fary2.png|thumb|500px250px|Рисунок 42]] Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <tex>v</tex> и <tex>w</tex> может быть только два общих соседа <tex>p</tex> и <tex>q</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> {{---}} граф, полученный из <tex>G</tex> стягиванием ребра <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:Fary4Fary3.png|thumb|500px250px|Рисунок 53]]Тогда получимМы получили граф <tex>G'</tex>, с меньшим числом вершин равным <tex>V - 1</tex>, что то есть его можно уложить на плоскости требуемым образом: все соседи t вершины ребра прямые (и сохранен обход по часовой стрелке ребер, инцидентных <tex>s находятся снаружи C_E</tex>).Для любого <tex>\varepsilon > 0</tex> обозначим <tex>C_{\varepsilon}(s) и только ребра </tex> {{---}} круг радиуса <tex>\varepsilon</tex>, с вершиной <tex>s</tex> в центре. Для каждого соседа <tex>t</tex> вершины <tex>s</tex> в графе <tex>G', пересекающие R_E</tex> обозначим <tex>R_{\varepsilon}(t)</tex> объединение всех отрезков, являются инцидентными проведённых из <tex>t</tex> в <tex>C_{\varepsilon}(s)</tex>.  Возьмем <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s</tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее.

[[File:Fary5.png|250px|Рисунок 4]] Тогда получим, что все соседи <tex>t</tex> вершины <tex>s</tex> находятся снаружи <tex>C_{\varepsilon}(s)</tex> и только ребра <tex>G'</tex>, инцидентные <tex>s</tex>, могут пересекать <tex>R_{\varepsilon}(t)</tex>.  [[File:Fary4.png|250px|Рисунок 5]] Проведем линию <tex>L </tex> через вершину <tex>s </tex> так, чтобы вершина <tex>p лежла </tex> лежала с одной ее стороны, а <tex>q — </tex> {{---}} с другой (такая линия существует, иначе L наложится на ребра рёбра <tex>sp & </tex> и <tex>sq. </tex> накладывались бы друг на друга), и L никакое из ребер <tex>\{sx_i : 1<i<k\} </tex> и <tex>\{sy_i : 1<i<lm\} </tex> не лежало на ней<tex>L</tex>. Ребра <tex>sq & </tex> и <tex>sq </tex> разбивают C_E<tex>C_{\varepsilon}(s) </tex> на две дуги: первая пересекает ребра <tex>\{sx_i : 1<i<k\}</tex>, а вторая — {{---}} ребра <tex>\{sy_i : 1<i<lm\}</tex>. [[File:Fary6.png|thumb|500px|Рисунок 6]]<tex>L </tex> пересекает C_E<tex>C_{\varepsilon}(s) </tex> в двух точках. Расположим <tex>v & </tex> и <tex>w </tex> в этих точках: <tex>v </tex> на дуге, пересекающей <tex>\{sx_i : 1<i<k\}</tex>, а <tex>w </tex> с другой стороны. [[File:Fary6.png|250px|Рисунок 6]] Удалим <tex>s </tex> и инцидентные ей ребра, нарисуем прямые ребра <tex>G</tex>, инцидентные <tex>v </tex> и <tex>w</tex>.  [[File:Fary7.png|thumb|500px250px|Рисунок 7]] Получим, что <tex>vw </tex> лежит на <tex>L</tex>. Так как <tex>p </tex> и <tex>q </tex> лежат с разных сторон <tex>L</tex>, ребра, инцидентные <tex>v </tex> и <tex>w</tex>, не пересекаются. По выбору E<tex>\varepsilon</tex>, ребра, инцидентные <tex>v </tex> и <tex>w</tex>, не пересекают и другие ребра <tex>G</tex>. Таким образом желаемая укладка графа <tex>G </tex> достигнута. Теперь мы можем удалить триангуляцию графадобавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.