Теорема Фари
Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936ом году и Иштваном Фари (István Fáry) в 1948ом году. Иногда ее называют теоремой Фари-Вагнера.
| Определение: |
| Триангуляция графа — представление планарного графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником). |
| Определение: |
| Разделяющий треугольник — цикл длины в графе , внутри и снаружи которого находятся вершины графа. |
Разделяющий треугольник изображён ниже. Относительно него существует три вида вершин: внешние, внутренние и лежащие на самом треугольнике.
| Теорема (Фари): |
Любой планарный граф имеет плоское представление, в котором все ребра представлены в виде отрезков прямых. |
| Доказательство: |
|
Докажем теорему для плоской триангуляции графа . Ее можно достичь, добавив в необходимое количество ребер. Применим индукцию по числу вершин . База индукции, когда , выполняется тривиальным образом. Предположим, что графы с любым числом вершин , мы можем нарисовать требуемым образом. Рассмотрим ребро , инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда — граница двух граней и .
Так как мы взяли вершины внутри самого глубого разделяющего треугольника, то у вершин и может быть только два общих соседа и , причём и не соединены ребром. Пусть и — обход по часовой стрелке ребер, исходящих соостветсвенно из и . Пусть — граф, полученный из стягиванием ребра в вершину . Заменим пары параллельных ребер и на и на . Получим вершину , из которой исходят ребра — по часовой стрелке.
Мы получили граф , с меньшим числом вершин равным , то есть его можно уложить на плоскости требуемым образом: все ребра прямые (и сохранен обход по часовой стрелке ребер инцидентных ). Для любого обозначим — круг радиуса , с вершиной в центре. Для каждого соседа вершины в графе обозначим объединение всех отрезков, проведённых из в . Возьмем равным минимуму из всех расстояний от вершины до инцидентных ей вершин и до отрезков, проходящих мимо нее.
Тогда получим, что все соседи вершины находятся снаружи и только ребра , пересекающие , являются инцидентными .
Проведем линию через вершину так, чтобы вершина лежала с одной ее стороны, а — с другой (иначе наложится на ребра и ) и никакое из ребер и не лежало на . Ребра и разбивают на две дуги: первая пересекает ребра , а вторая — ребра . пересекает в двух точках. Расположим и в этих точках: на дуге, пересекающей , а с другой стороны.
Удалим и инцидентные ей ребра, нарисуем прямые ребра , инцидентные и .
Получим, что лежит на . Так как и лежат с разных сторон , ребра, инцидентные и , не пересекаются. По выбору , ребра, инцидентные и , не пересекают и другие ребра . Таким образом желаемая укладка графа достигнута. Теперь мы можем удалить триангуляцию графа, оставив в графе лишь исходные (уже прямые) ребра. |
