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