Теорема Фари

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

Определение:

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

Определение:

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

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

Теорема (Фари):

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

Доказательство:

[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]. Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин [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] — по часовой стрелке. Мы получили граф [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] до инцидентных ей вершин и до отрезков, проходящих мимо нее. Тогда получим, что все соседи [math]t[/math] вершины [math]s[/math] находятся снаружи [math]C_{\varepsilon}(s)[/math] и только ребра [math]G'[/math], пересекающие [math]R_{\varepsilon}(t)[/math], являются инцидентными [math]s[/math]. Проведем линию [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] с другой стороны. Удалим [math]s[/math] и инцидентные ей ребра, нарисуем прямые ребра [math]G[/math], инцидентные [math]v[/math] и [math]w[/math]. Получим, что [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]

Ссылки

• Wikipedia — Fáry's theorem
• Википедия — Теорема Фари
• Доказательство теоремы Фари