Жемчужина Эйлера - Дэвид С. Ричесон

по теории графов считают внешнюю область гранью. Если рассматривать граф как остров, то эта неограниченная грань будет морем, протянувшимся в бесконечность во всех направлениях. И хотя называть эту неограниченную область гранью довольно странно, часто полезнее включать ее в число граней, чем исключать. Один из способов обрести душевный покой в этом вопросе — рассматривать граф как остров не в бескрайнем море, а на глобусе (рис. 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 и для исходного графа.

У этой формулы есть интересное следствие: в любом представлении планарного графа с E ребрами и V вершинами количество граней одинаково. Иными словами, если десять человек нарисуют планарный граф, поставив точки там, где пожелают, и проведя ребра, так чтобы они не пересекались, то у всех графов будет одно и то же число граней (F = 1 + E — V, если не считать неограниченной грани). Например, на рис. 13.5 показан граф с четырьмя вершинами и шестью ребрами и два его планарных представления с тремя гранями каждое.

Рис. 13.5. Два разных планарных представления одного графа будут иметь одно и то же число граней

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

В полном графе с n вершинами, обозначаемом Kn, n вершин, и каждая пара вершин соединена ровно одним ребром. Это самый большой возможный граф с n вершинами, не имеющий ни петель, ни параллельных ребер. Графы K1… K5 показаны на рис. 13.6. Удалив петли из графа домино (рис. 11.11), мы получили бы граф K7.

Рис. 13.6. Полные графы K1, K2, K3, K4 и K5

С полным графом тесно связан полный двудольный граф. Он обладает тем свойством, что множество вершин можно разделить на два подмножества U и V, так что никакие две вершины, принадлежащие U, и никакие две вершины, принадлежащие V, не соединены ребром, а каждая вершина из U соединена с каждой вершиной из V ровно одним ребром. Если U содержит m вершин, а V— n вершин, то соответствующий полный двудольный граф обозначается Km,n. Графы K3,2 и K3,3 показаны на рис. 13.7. Типичный пример полного двудольного графа, который приводится в любом начальном учебнике по теории графов, — граф ресурсоснабжающих компаний. Множество U состоит из компаний (газовой, водопроводной, электрической и т. д.), а множество V — из клиентов. Поскольку каждый клиент должен получать ресурсы каждого вида, то получающийся граф полный двудольный.

Рис. 13.7. Полные двудольные графы K3,2 и K3,3

Мы хотели бы знать, какие из полных и полных двудольных графов планарные. Легко показать, что графы K1, K2, K3, K4, Km,1 и Km,2 планарные. Например, на рис. 13.8 мы видим, что K4 и K3,2 планарные. Оказывается, что все остальные графы интересующего нас вида непланарные. Воспользуемся формулой Эйлера, чтобы доказать, что K5 и K3,3 непланарные.

Рис. 13.8. K4 и K3,2 — планарные графы

Чтобы доказать, что K5 непланарный, мы воспользуемся техникой доказательства от противного. Предположим, что утверждение, которое мы хотим доказать, неверно (т. е. что граф K5 планарный), и покажем, что это приводит к логическому противоречию. Тогда можно будет заключить, что K5 непланарный. Г. Х. Харди писал: «Метод доказательства reductio ad absurdum, столь любимый Евклидом, — один из самых лучших инструментов математика. Это гораздо более “хитроумный” гамбит, чем любой шахматный гамбит: шахматист