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