EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 8 минут
#формула эйлера#планарный граф#плоский граф#теория графов#грани графа
Формула Эйлера для планарных графов

Формула Эйлера для планарных графов связывает три числа: количество вершин VV, рёбер EE и граней FF. Для связного графа, нарисованного на плоскости без пересечений рёбер, всегда получается V−E+F=2V-E+F=2. Удивительно, что равенство не зависит от формы рисунка: изогнутые рёбра и неравные области ничего в нём не меняют. Важно лишь правильно считать грани и не забывать внешнюю область. Попробуйте добавить диагонали в калькуляторе: каждое новое ребро делит одну грань на две, а значение выражения остаётся прежним.

Планарный и плоский граф: в чём разница

Планарный граф допускает изображение на плоскости, в котором рёбра пересекаются только в общих вершинах. Плоский граф - конкретный рисунок с такой укладкой. Один и тот же планарный граф можно нарисовать и с пересечениями, и без них; для подсчёта граней по формуле нужна именно укладка без посторонних пересечений. Точка пересечения на неудачном рисунке сама по себе не становится вершиной исходного графа.

Грань плоского графа - связная область плоскости, которая остаётся после удаления рисунка графа. Одна из граней неограниченная: это область снаружи. Её считают вместе с ограниченными. Например, простой треугольник ограничивает одну внутреннюю область, но граней у него две. Три вершины, три ребра и две грани дают 3−3+2=23-3+2=2.

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

Слово «грань» здесь обозначает область плоскости, а не обязательно многоугольник. Граница может проходить по одному ребру дважды: такое случается с мостом, удаление которого разбивает связный граф на две компоненты. У дерева вообще нет ограниченных граней, но есть одна внешняя. Эти случаи тоже входят в теорему.

Как применять формулу и считать внешнюю грань

Пусть связный плоский граф имеет четыре вершины по углам квадрата и одну диагональ. У квадрата четыре стороны и одна диагональ, значит, E=5E=5. Диагональ делит внутреннюю область на два треугольника; снаружи находится ещё одна грань. Поэтому V=4V=4, E=5E=5, F=3F=3, и проверка даёт

V−E+F=4−5+3=2.V-E+F=4-5+3=2.

Квадрат с диагональю: четыре вершины, пять рёбер и три грани с учётом внешней
Квадрат с диагональю: четыре вершины, пять рёбер и три грани с учётом внешней

Если известны вершины и рёбра связного плоского графа, выразим число граней: F=E−V+2F=E-V+2. Например, при V=8V=8 и E=12E=12 получаем F=12−8+2=6F=12-8+2=6. Это число включает внешнюю грань; ограниченных граней в таком рисунке пять. Напротив, если граней шесть и вершин восемь, то рёбер E=V+F−2=12E=V+F-2=12.

Вычисление предполагает, что граф действительно связен и уже уложен без пересечений. Одна лишь тройка чисел не доказывает существование конкретного рисунка и не определяет, какие вершины соединены. У разных графов могут совпадать все три счётчика.

Почему равенство верно: удаляем рёбра циклов

Начнём с дерева - связного графа без циклов. У дерева с VV вершинами ровно V−1V-1 ребро, а грань только одна, внешняя. Получаем V−(V−1)+1=2V-(V-1)+1=2. Это базовый случай, в том числе для единственной изолированной вершины: 1−0+1=21-0+1=2.

Теперь возьмём произвольный связный плоский граф с циклом. Удалим одно ребро этого цикла, сохранив его концы. Связность не исчезнет: между концами остаётся путь по другим рёбрам цикла. Ребро разделяло две грани, и после удаления они сливаются в одну. Значит, EE и FF одновременно уменьшаются на единицу, а V−E+FV-E+F не меняется.

Повторяя операцию, в конечном графе удалим все циклы и получим дерево. На каждом шаге выражение сохранялось, а для дерева оно равно двум. Следовательно, и для исходного графа оно равно двум. Важно удалять именно ребро цикла: удаление моста разъединяет граф и не сливает две разные грани. Подробная формулировка и индукционное доказательство приведены в учебнике по комбинаторике.

Эта идея работает и в обратную сторону. Добавим ребро внутри одной грани между уже существующими вершинами так, чтобы оно не пересекало другие рёбра. Грань разделится на две: EE и FF вырастут на единицу. Именно это происходит с каждой диагональю из одной вершины в калькуляторе. При nn вершинах и kk таких диагоналях V=nV=n, E=n+kE=n+k, F=k+2F=k+2.

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

Есть и другая операция: поставим новую вершину прямо на существующем ребре. Старое ребро теперь заменено двумя, то есть число вершин и число рёбер увеличилось на единицу. Новая грань не возникла, а разность числа вершин и рёбер осталась прежней. Такой приём называют подразбиением ребра. Он помогает понять, почему формула не зависит от того, сколько промежуточных точек отмечено вдоль пути, если учитывать их и в числе вершин, и в числе рёбер.

Если граф состоит из нескольких компонент

Если граф не связен, число справа меняется. Для плоского графа с CC компонентами связности, включая изолированные вершины, верно

V−E+F=1+C.V-E+F=1+C.

Смысл поправки легко увидеть на двух отдельных треугольниках. У них шесть вершин и шесть рёбер. Внутренних граней две, а внешняя область общая для обоих треугольников, поэтому всего граней три: 6−6+3=3=1+26-6+3=3=1+2. Не нужно приписывать каждому треугольнику собственную внешнюю грань при подсчёте граней всего рисунка.

Обоснование можно свести к связному случаю: соединяем разные компоненты C−1C-1 новыми рёбрами через грани без пересечений. Каждое такое ребро соединяет компоненты и не создаёт новую грань. После добавления получаем связный граф с теми же VV и FF, но с E+C−1E+C-1 рёбрами. Формула для него даёт V−(E+C−1)+F=2V-(E+C-1)+F=2, откуда следует V−E+F=1+CV-E+F=1+C. Для C=1C=1 возвращается привычная двойка.

Многогранники и треугольные разбиения

Поверхность выпуклого многогранника можно представить на сфере, а затем перенести на плоскость: одна из его граней становится внешней областью рисунка. Так формула для графа связана с классическим равенством для многогранников. У куба восемь вершин, двенадцать рёбер и шесть граней: 8−12+6=28-12+6=2. В плоском изображении одна из шести граней соответствует внешней области, а не исчезает.

Формула полезна и при разбиении области на треугольники. Если внутри многоугольника провести непересекающиеся диагонали, каждая новая диагональ увеличивает число внутренних областей на одну. Для выпуклого nn-угольника полный набор из одной вершины содержит n−3n-3 диагонали и создаёт n−2n-2 внутренних треугольника. Внешняя грань даёт ещё одну, поэтому всего F=n−1F=n-1, а E=2n−3E=2n-3. Подстановка снова даёт n−(2n−3)+(n−1)=2n-(2n-3)+(n-1)=2. Применение подсчёта к точкам и треугольникам разобрано в статье о триангуляции Делоне.

Что формула говорит о планарности

Для простого связного плоского графа с V≥3V\geq3 каждую границу грани можно обойти по рёбрам, причём её длина не меньше трёх. При подсчёте длин границ каждое ребро учитывается дважды, даже если оно мост: тогда оно встречается дважды на границе одной грани. Поэтому 3F≤2E3F\leq2E. Подставляя F=E−V+2F=E-V+2, получаем необходимую оценку E≤3V−6E\leq3V-6.

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

Частые ошибки

  • Не считать внешнюю область. У цикла есть внутренняя и внешняя грани, даже если на странице виден только один многоугольник.
  • Считать пересечение рёбер вершиной. Вершинами являются заданные точки графа; для формулы нужен рисунок без посторонних пересечений.
  • Применять двойку к несвязному графу. При CC компонентах справа стоит 1+C1+C, а изолированные вершины тоже учитываются.
  • Считать, что выполнение оценки доказывает планарность. Неравенство E≤3V−6E\leq3V-6 необходимо при указанных условиях, но недостаточно.
  • Удалять мост в доказательстве как ребро цикла. Мост разъединяет граф; доказательство использует ребро, концы которого остаются связаны другим путём.

FAQ

Считаются ли петли и кратные рёбра?

Да. Формула V−E+F=2V-E+F=2 верна и для связного плоского мультиграфа с петлями и кратными рёбрами. Но оценка E≤3V−6E\leq3V-6 выше требует простого графа: петли и кратные рёбра нарушают условие о длине границ граней.

Сколько граней у дерева?

Ровно одна: внешняя. Дерево не содержит цикла и потому не ограничивает отдельную область плоскости. Для дерева E=V−1E=V-1, так что формула подтверждает F=1F=1.

Меняется ли число граней при другой укладке?

Для одного и того же связного планарного графа число граней в любой плоской укладке равно E−V+2E-V+2. Форма и границы отдельных граней могут измениться, но общее количество останется прежним.

Коротко

Для связного плоского графа V−E+F=2V-E+F=2, где внешняя область входит в число граней. Доказательство сводит граф к дереву удалением рёбер циклов: каждое такое удаление уменьшает и число рёбер, и число граней на единицу. Для CC компонент формула принимает вид V−E+F=1+CV-E+F=1+C; само равенство не является критерием планарности произвольного рисунка.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Задача о трёх колодцах: доказательство через теорию графов

Задача о трёх колодцах: доказательство через теорию графов

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

11 июня 202610 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

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

8 ноября 20268 минут
Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

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

8 ноября 20268 минут
Дерево: свойства и число рёбер

Дерево: свойства и число рёбер

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

8 ноября 20268 минут
Эйлерова характеристика поверхности: формулы и примеры

Эйлерова характеристика поверхности: формулы и примеры

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

8 ноября 20268 минут
Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

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

8 ноября 20269 минут