3622
правки
Изменения
Нет описания правки
{{Определение
|id=def1
|definition='''Триангуляция графа''' (англ. ''triangulation'') {{---}} представление [[Укладка графа на плоскости#defplanar | планарного графа]] на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).
}}
{{Определение
|id=def2
|definition='''Разделяющий треугольник''' (англ. ''separating triangle'') {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.
}}
|proof=
Докажем теорему для плоской триангуляции графа <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:Fary2.png|250px|Рисунок 2]]
Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин <tex>v</tex> и <tex>w</tex> может быть только два общих соседа <tex>p</tex> и <tex>q</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: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>.
}}
==Смотри См. также==
* [[Теорема Понтрягина-Куратовского]]
* [[Укладка графа на плоскости]]
==СсылкиИсточники информации==
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
