Теорема Фари — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
Строка 64: Строка 64:
 
==Ссылки==
 
==Ссылки==
 
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
 
* [[wikipedia:Fáry's_theorem | Wikipedia {{---}} Fáry's theorem ]]
* [[wikipedia:ru:Теорема_Фари | Википедия {{---}} Теорема Фари ]]
 
 
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
 
* [http://arxiv.org/abs/cs/0505047 Доказательство теоремы Фари]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Версия 16:26, 18 ноября 2013

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


Определение:
Триангуляция графа — представление планарного графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).


Определение:
Разделяющий треугольник — цикл длины [math]3[/math] в графе [math]G[/math], внутри и снаружи которого находятся вершины графа.


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

Рисунок 1


Теорема (Фари):
Любой планарный граф имеет плоское представление, в котором все ребра представлены в виде отрезков прямых.
Доказательство:
[math]\triangleright[/math]

Докажем теорему для плоской триангуляции графа [math]G[/math]. Ее можно достичь, добавив в [math]G[/math] необходимое количество ребер. Применим индукцию по числу вершин [math]V[/math].

База индукции, когда [math]V=3[/math], выполняется тривиальным образом. Предположим, что графы с любым числом вершин [math]V \geqslant 4[/math], мы можем нарисовать требуемым образом. Рассмотрим ребро [math]vw[/math], инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда [math]vw[/math] — граница двух граней [math]vwp[/math] и [math]vwq[/math].

Рисунок 2

Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин [math]v[/math] и [math]w[/math] может быть только два общих соседа [math]p[/math] и [math]q[/math], причём [math]p[/math] и [math]q[/math] не соединены ребром. Пусть [math](vp, vw, vq, vx_1, vx_2 ... vx_k)[/math] и [math](wq, wv, wp, wy_1, wy_2 ... wy_m)[/math] — обход по часовой стрелке ребер, исходящих соостветсвенно из [math]v[/math] и [math]w[/math]. Пусть [math]G'[/math] — граф, полученный из [math]G[/math] стягиванием ребра [math]vw[/math] в вершину [math]s[/math]. Заменим пары параллельных ребер [math]vq[/math] и [math]wq[/math] на [math]sq[/math] и [math]vp, wp[/math] на [math]sp[/math]. Получим вершину [math]s[/math], из которой исходят ребра [math](sp, sy_1, sy_2 ... sy_m, sq, sx_1, sx_2 ... sx_k)[/math] — по часовой стрелке.

Рисунок 3

Мы получили граф [math]G'[/math], с меньшим числом вершин равным [math]V - 1[/math], то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных [math]s[/math]). Для любого [math]\varepsilon \gt 0[/math] обозначим [math]C_{\varepsilon}(s)[/math] — круг радиуса [math]\varepsilon[/math], с вершиной [math]s[/math] в центре. Для каждого соседа [math]t[/math] вершины [math]s[/math] в графе [math]G'[/math] обозначим [math]R_{\varepsilon}(t)[/math] область, содержащую множество всех окрытых отрезков от [math]t[/math] до каждой точки из [math]C_{\varepsilon}(s)[/math].

Возьмем [math]\varepsilon[/math] равным минимуму из всех расстояний от вершины [math]s[/math] до инцидентных ей вершин и до отрезков, проходящих мимо нее.

Рисунок 4

Тогда получим, что все соседи [math]t[/math] вершины [math]s[/math] находятся снаружи [math]C_{\varepsilon}(s)[/math] и только ребра [math]G'[/math], пересекающие [math]R_{\varepsilon}(t)[/math], являются инцидентными [math]s[/math].

Рисунок 5

Проведем линию [math]L[/math] через вершину [math]s[/math] так, чтобы вершина [math]p[/math] лежала с одной ее стороны, а [math]q[/math] — с другой (иначе [math]L[/math] наложится на ребра [math]sp[/math] и [math]sq[/math]) и никакое из ребер [math]\{sx_i : 1 \lt i \lt k\}[/math] и [math]\{sy_i : 1 \lt i \lt m\}[/math] не лежало на [math]L[/math]. Ребра [math]sq[/math] и [math]sq[/math] разбивают [math]C_{\varepsilon}(s)[/math] на две дуги: первая пересекает ребра [math]\{sx_i : 1 \lt i \lt k\}[/math], а вторая — ребра [math]\{sy_i : 1 \lt i \lt m\}[/math]. [math]L[/math] пересекает [math]C_{\varepsilon}(s)[/math] в двух точках. Расположим [math]v[/math] и [math]w[/math] в этих точках: [math]v[/math] на дуге, пересекающей [math]\{sx_i : 1 \lt i \lt k\}[/math], а [math]w[/math] с другой стороны.

Рисунок 6

Удалим [math]s[/math] и инцидентные ей ребра, нарисуем прямые ребра [math]G[/math], инцидентные [math]v[/math] и [math]w[/math].

Рисунок 7

Получим, что [math]vw[/math] лежит на [math]L[/math]. Так как [math]p[/math] и [math]q[/math] лежат с разных сторон [math]L[/math], ребра, инцидентные [math]v[/math] и [math]w[/math], не пересекаются. По выбору [math]\varepsilon[/math], ребра, инцидентные [math]v[/math] и [math]w[/math], не пересекают и другие ребра [math]G[/math]. Таким образом желаемая укладка графа [math]G[/math] достигнута.

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

Ссылки