Жемчужина Эйлера

Глава 13 Планарные графы, математические планшеты и брюссельская капуста

В большинстве наук одно поколение разрушает созданное предыдущим и отменяет установленное ранее. Только в математике каждое поколение добавляет новый этаж к прежней конструкции.

— Герман Ганкель

¹⁰³

В предыдущей главе мы видели, какую остроумную технику применил Коши для доказательства формулы Эйлера. Он взял многогранник, удалил одну грань и спроецировал все, что осталось, на плоскость этой грани. Затем он доказал, что для получившегося многоугольника имеет место формула V — E + F = 1, а значит, для исходного многогранника — формула V — E + F = 2. Связь с теорией графов бросается в глаза. На первый взгляд кажется, что было бы тривиально обобщить формулу Эйлера на графы, которые не являются проекциями многогранников и имеют криволинейные ребра.

Но трудность обобщения формулы Эйлера состоит в том, что это проходит не для всех графов. Подсчитать вершины и ребра просто — это те элементы, из которых граф и состоит, но вот граней у графа может и не быть. Даже в том случае, когда граф нарисован на бумаге, ребра необязательно разбивают область на грани. Например, ребро PR в левом графе на рис. 13.1 пересекает ребро QS, поэтому не может быть границей никакой грани. Однако этот граф можно нарисовать по-другому (как в правой части), так что пересечений не будет, и тогда область разбивается на грани. Граф, который можно нарисовать, так что ребра не пересекаются, называется планарным.

В многограннике грань — это область, ограниченная многоугольником. Для графов определение не такое строгое. Грань может быть ограничена одним ребром, как петля из P в P на рис. 13.1. Или двумя ребрами, как в случае пары ребер, соединяющих вершины Q и R. (Два ребра между одной и той же парой вершин называются параллельными.) Возможно даже, что ребро заходит внутрь грани, как ребро между S и T.

Рис. 13.1. Два представления одного и того же графа

Многие специалисты по теории графов считают внешнюю область гранью. Если рассматривать граф как остров, то эта неограниченная грань будет морем, протянувшимся в бесконечность во всех направлениях. И хотя называть эту неограниченную область гранью довольно странно, часто полезнее включать ее в число граней, чем исключать. Один из способов обрести душевный покой в этом вопросе — рассматривать граф как остров не в бескрайнем море, а на глобусе (рис. 13.2). Тогда неограниченная грань оказывается конечной.

Рис. 13.2. Расположение планарного графа на сфере

Итак, мы имеем следующее обобщение формулы Эйлера для планарных графов.

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

Для связного планарного графа с V вершинами, E ребрами и F гранями имеет место соотношение V — E + F = 2.

Если не считать неограниченную область гранью, то формула Эйлера принимает вид V — E + F = 1. У графа на рис. 13.1 пять вершин, семь ребер и четыре грани, 5–7 + 4 = 2, как и должно быть.

В качестве элементарного примера рассмотрим дерево. Деревом называется связный граф без циклов (см. рис. 13.3). Поскольку в дереве нет циклов, не ограничена всего одна грань, поэтому формула Эйлера дает V — E + 1 = 2, или V = E + 1. Иными словами, число вершин дерева на единицу больше числа ребер. В дереве на рис. 13.3 имеется 19 вершин и 18 ребер.

Рис. 13.3. Дерево

Существует много доказательств формулы Эйлера для графов. Мы приведем короткое, в котором, как и Коши, будем удалять ребра по одному. Но при этом будем осторожны, чтобы не повторить его ошибки.

Начнем с произвольного связного планарного графа. Выберем любое ребро. Это ребро либо соединяет две разные вершины, либо является петлей, которая начинается и заканчивается в одной и той же вершине. Предположим, что оно соединяет две вершины. Тогда будем стягивать ребро, пока оно не исчезнет полностью и два его конца не сольются в один. Это можно сделать так, что результирующий граф останется планарным (см. стягивание ребер a, c и d на рис. 13.4). Такая процедура уменьшает количество ребер и вершин на единицу, а число граней оставляет тем же самым. Поэтому величина V — E + F не изменяется. Теперь предположим, что ребро является петлей. В этом случае просто удалим ребро из графа (см. удаление ребер b и e на рис. 13.4). При этом число ребер и граней уменьшается на единицу, а число вершин остается неизменным. Поэтому величина V — E + F не изменяется.

Рис. 13.4. Сведение планарного графа к одной вершине путем удаления ребер a, b, c, d и, наконец, e

Продолжим процесс удаления ребер, пока не останется единственная вершина. В этот момент мы имеем одну вершину, ни одного ребра и одну грань (внешняя область). Поэтому V — E + F = 2. Поскольку величина V — E + F не изменялась на протяжении всего процесса, то V — E + F = 2 и для исходного графа.