Изменения

Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936 года, 1936ом году и Иштваном Фари (István Fáry) в 1948ом году и Штейном в 1951ом году. Иногда ее называют теоремой Фари-Вагнера.

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

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

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

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

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

Возьмем E <tex>\varepsilon</tex> равным минимуму из всех расстояний от вершины <tex>s </tex> до инцидентных ей вершин и до отрезков, проходящих мимо нее . Картинка 4.2Тогда получим, что все соседи t вершины s находятся снаружи C_E(s) и только ребра G', пересекающие R_E(t), являются инцидентными s. Картинка 4.1

[[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>. <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> с другой стороны. Картинка 5 [[File:Fary6.png|250px|Рисунок 6]] Удалим <tex>s </tex> и инцидентные ей ребра, нарисуем прямые ребра <tex>G</tex>, инцидентные <tex>v </tex> и <tex>w</tex>. Картинка 6 [[File:Fary7.png|250px|Рисунок 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> достигнута. Теперь мы можем удалить триангуляцию графадобавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.