Формула Эйлера для планарных графов

Формула Эйлера для планарных графов связывает три числа: количество вершин , рёбер и граней . Для связного графа, нарисованного на плоскости без пересечений рёбер, всегда получается . Удивительно, что равенство не зависит от формы рисунка: изогнутые рёбра и неравные области ничего в нём не меняют. Важно лишь правильно считать грани и не забывать внешнюю область. Попробуйте добавить диагонали в калькуляторе: каждое новое ребро делит одну грань на две, а значение выражения остаётся прежним.
Планарный и плоский граф: в чём разница
Планарный граф допускает изображение на плоскости, в котором рёбра пересекаются только в общих вершинах. Плоский граф - конкретный рисунок с такой укладкой. Один и тот же планарный граф можно нарисовать и с пересечениями, и без них; для подсчёта граней по формуле нужна именно укладка без посторонних пересечений. Точка пересечения на неудачном рисунке сама по себе не становится вершиной исходного графа.
Грань плоского графа - связная область плоскости, которая остаётся после удаления рисунка графа. Одна из граней неограниченная: это область снаружи. Её считают вместе с ограниченными. Например, простой треугольник ограничивает одну внутреннюю область, но граней у него две. Три вершины, три ребра и две грани дают .
Слово «грань» здесь обозначает область плоскости, а не обязательно многоугольник. Граница может проходить по одному ребру дважды: такое случается с мостом, удаление которого разбивает связный граф на две компоненты. У дерева вообще нет ограниченных граней, но есть одна внешняя. Эти случаи тоже входят в теорему.
Как применять формулу и считать внешнюю грань
Пусть связный плоский граф имеет четыре вершины по углам квадрата и одну диагональ. У квадрата четыре стороны и одна диагональ, значит, . Диагональ делит внутреннюю область на два треугольника; снаружи находится ещё одна грань. Поэтому , , , и проверка даёт

Если известны вершины и рёбра связного плоского графа, выразим число граней: . Например, при и получаем . Это число включает внешнюю грань; ограниченных граней в таком рисунке пять. Напротив, если граней шесть и вершин восемь, то рёбер .
Вычисление предполагает, что граф действительно связен и уже уложен без пересечений. Одна лишь тройка чисел не доказывает существование конкретного рисунка и не определяет, какие вершины соединены. У разных графов могут совпадать все три счётчика.
Почему равенство верно: удаляем рёбра циклов
Начнём с дерева - связного графа без циклов. У дерева с вершинами ровно ребро, а грань только одна, внешняя. Получаем . Это базовый случай, в том числе для единственной изолированной вершины: .
Теперь возьмём произвольный связный плоский граф с циклом. Удалим одно ребро этого цикла, сохранив его концы. Связность не исчезнет: между концами остаётся путь по другим рёбрам цикла. Ребро разделяло две грани, и после удаления они сливаются в одну. Значит, и одновременно уменьшаются на единицу, а не меняется.
Повторяя операцию, в конечном графе удалим все циклы и получим дерево. На каждом шаге выражение сохранялось, а для дерева оно равно двум. Следовательно, и для исходного графа оно равно двум. Важно удалять именно ребро цикла: удаление моста разъединяет граф и не сливает две разные грани. Подробная формулировка и индукционное доказательство приведены в учебнике по комбинаторике.
Эта идея работает и в обратную сторону. Добавим ребро внутри одной грани между уже существующими вершинами так, чтобы оно не пересекало другие рёбра. Грань разделится на две: и вырастут на единицу. Именно это происходит с каждой диагональю из одной вершины в калькуляторе. При вершинах и таких диагоналях , , .
Рассмотрим обратную операцию на конкретных числах. Начнём с квадрата: четыре вершины, четыре ребра и две грани. Добавление диагонали не создаёт вершину, поскольку оба её конца уже принадлежат графу. Получается пять рёбер и три грани. Если затем удалить именно эту диагональ, две внутренние области вновь соединятся. Вычитание одного ребра компенсируется уменьшением числа граней, поэтому проверка работает в обе стороны.
Есть и другая операция: поставим новую вершину прямо на существующем ребре. Старое ребро теперь заменено двумя, то есть число вершин и число рёбер увеличилось на единицу. Новая грань не возникла, а разность числа вершин и рёбер осталась прежней. Такой приём называют подразбиением ребра. Он помогает понять, почему формула не зависит от того, сколько промежуточных точек отмечено вдоль пути, если учитывать их и в числе вершин, и в числе рёбер.
Если граф состоит из нескольких компонент
Если граф не связен, число справа меняется. Для плоского графа с компонентами связности, включая изолированные вершины, верно
Смысл поправки легко увидеть на двух отдельных треугольниках. У них шесть вершин и шесть рёбер. Внутренних граней две, а внешняя область общая для обоих треугольников, поэтому всего граней три: . Не нужно приписывать каждому треугольнику собственную внешнюю грань при подсчёте граней всего рисунка.
Обоснование можно свести к связному случаю: соединяем разные компоненты новыми рёбрами через грани без пересечений. Каждое такое ребро соединяет компоненты и не создаёт новую грань. После добавления получаем связный граф с теми же и , но с рёбрами. Формула для него даёт , откуда следует . Для возвращается привычная двойка.
Многогранники и треугольные разбиения
Поверхность выпуклого многогранника можно представить на сфере, а затем перенести на плоскость: одна из его граней становится внешней областью рисунка. Так формула для графа связана с классическим равенством для многогранников. У куба восемь вершин, двенадцать рёбер и шесть граней: . В плоском изображении одна из шести граней соответствует внешней области, а не исчезает.
Формула полезна и при разбиении области на треугольники. Если внутри многоугольника провести непересекающиеся диагонали, каждая новая диагональ увеличивает число внутренних областей на одну. Для выпуклого -угольника полный набор из одной вершины содержит диагонали и создаёт внутренних треугольника. Внешняя грань даёт ещё одну, поэтому всего , а . Подстановка снова даёт . Применение подсчёта к точкам и треугольникам разобрано в статье о триангуляции Делоне.
Что формула говорит о планарности
Для простого связного плоского графа с каждую границу грани можно обойти по рёбрам, причём её длина не меньше трёх. При подсчёте длин границ каждое ребро учитывается дважды, даже если оно мост: тогда оно встречается дважды на границе одной грани. Поэтому . Подставляя , получаем необходимую оценку .
Если простой связный граф нарушает эту оценку, плоской укладки у него нет. Но выполнение неравенства ещё не гарантирует планарности: оно учитывает только количество вершин и рёбер, а не их устройство. Структурный критерий рассматривается в статье о теореме Понтрягина-Куратовского, а отдельный пример применения к двудольному графу - в задаче о трёх колодцах. Связность, которая нужна для выбора версии формулы, можно проверить с помощью обхода графа в глубину.
Частые ошибки
- Не считать внешнюю область. У цикла есть внутренняя и внешняя грани, даже если на странице виден только один многоугольник.
- Считать пересечение рёбер вершиной. Вершинами являются заданные точки графа; для формулы нужен рисунок без посторонних пересечений.
- Применять двойку к несвязному графу. При компонентах справа стоит , а изолированные вершины тоже учитываются.
- Считать, что выполнение оценки доказывает планарность. Неравенство необходимо при указанных условиях, но недостаточно.
- Удалять мост в доказательстве как ребро цикла. Мост разъединяет граф; доказательство использует ребро, концы которого остаются связаны другим путём.
FAQ
Считаются ли петли и кратные рёбра?
Да. Формула верна и для связного плоского мультиграфа с петлями и кратными рёбрами. Но оценка выше требует простого графа: петли и кратные рёбра нарушают условие о длине границ граней.
Сколько граней у дерева?
Ровно одна: внешняя. Дерево не содержит цикла и потому не ограничивает отдельную область плоскости. Для дерева , так что формула подтверждает .
Меняется ли число граней при другой укладке?
Для одного и того же связного планарного графа число граней в любой плоской укладке равно . Форма и границы отдельных граней могут измениться, но общее количество останется прежним.
Коротко
Для связного плоского графа , где внешняя область входит в число граней. Доказательство сводит граф к дереву удалением рёбер циклов: каждое такое удаление уменьшает и число рёбер, и число граней на единицу. Для компонент формула принимает вид ; само равенство не является критерием планарности произвольного рисунка.
Читайте также

Задача о трёх колодцах: доказательство через теорию графов
Разбираем задачу о трёх колодцах: почему три дома нельзя соединить с тремя колодцами без пересечения дорожек, как она сводится к графу K3,3 и что доказывает формула Эйлера для плоских графов.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

Алгоритм Хирхольцера: как найти эйлеров путь
Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

Дерево: свойства и число рёбер
Как связаны вершины и рёбра дерева, почему их числа отличаются на единицу и какие признаки помогают отличить дерево от произвольного графа. Примеры и доказательство.

Эйлерова характеристика поверхности: формулы и примеры
Эйлерова характеристика поверхности: как считать вершины, рёбра и грани, находить характеристику по роду и границе и проверять ответ на примерах сферы и тора.

Максимальный поток: алгоритм Форда-Фалкерсона
Максимальный поток алгоритмом Форда-Фалкерсона: разбираем остаточную сеть, обратные рёбра и дополняющие пути на примере, а результат проверяем разрезом.