Изменения

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

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

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

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

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

Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>|V|</tex>. Предположим, что графы с числом вершин, меньшим <tex>V</tex>, мы можем нарисовать требуемым образом.

База: индукции, когда <tex>|V|=3</tex> {{---}} тривиально, выполняется тривиальным образом. Переход: Предположим, что графы с любым числом вершин меньше <tex>|V | \geqslant 4</tex> , мы можем нарисовать требуемым образом. Рассмотрим ребро <tex>vw</tex>, [[Матрица инцидентности графа#definc | инцидентное]] внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в <tex>G</tex> графе нет разделяющих треугольников, то <tex>vw</tex> {{---}} возьмём любое. Иначе <tex>vw</tex> {{---}} ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в <tex>G</tex>. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.

Если Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <tex>vw</tex> не в разделяющем треугольнике <tex>pv</tex> и <tex>qw</tex> {{---}} любые общие соседи может быть только два общих соседа <tex>vp</tex> и <tex>wq</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> {{---}} по часовой стрелке.

Мы получили граф <tex>G'</tex>, с меньшим числом вершин равно равным <tex>V - 1</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>t</tex> вершины <tex>s</tex> находятся снаружи <tex>C_{\varepsilon}(s)</tex> и только ребра <tex>G'</tex>, пересекающие инцидентные <tex>s</tex>, могут пересекать <tex>R_{\varepsilon}(t)</tex>, являются инцидентными <tex>s</tex>.

Проведем линию <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>.

Теперь мы можем удалить триангуляцию графадобавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.

==СсылкиСм. также==* [[Теорема Понтрягина-Куратовского]] * [[Укладка графа на плоскости]] ==Источники информации==