3622
правки
Изменения
Нет описания правки
Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936 года, 1936ом году и Иштваном Фари (István Fáry) в 1948ом году и Штейном в 1951ом году. Иногда ее называют теоремой Фари-Вагнера.
{{Определение
|id=def1
|definition='''Триангуляция графа — ''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
}}
{{Определение
|id=def1def2|definition='''Разделяющий треугольник — ''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3 </tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
}}
Разделяющий треугольник представлен на рисунке 1изображён ниже. [[FileОтносительно него существует три вида вершин:Fary1внешние, внутренние и лежащие на самом треугольнике.png|thumb|500px|Рисунок 1]]
[[File:Fary1.png|250px|Рисунок 1]]
{{Теорема
|about=Фари
|statement= Любой планарный граф имеет плоское представление на плоскости, в котором все его ребра будут прямымипредставлены в виде отрезков прямых.
|proof=
[[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>. Возьмем <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> достигнута. Теперь мы можем удалить триангуляцию графадобавленные нами ребра, оставив в графе лишь исходные (уже прямые) ребра.
}}
==См. также==
* [[Теорема Понтрягина-Куратовского]]
* [[Укладка графа на плоскости]]
==Источники информации==
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]