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