Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
В многограннике грань — это область, ограниченная многоугольником. Для графов определение не такое строгое. Грань может быть ограничена одним ребром, как петля из P в P на рис. 13.1. Или двумя ребрами, как в случае пары ребер, соединяющих вершины Q и R. (Два ребра между одной и той же парой вершин называются параллельными.) Возможно даже, что ребро заходит внутрь грани, как ребро между S и T.
Рис. 13.1. Два представления одного и того же графа
Многие специалисты по теории графов считают внешнюю область гранью. Если рассматривать граф как остров, то эта неограниченная грань будет морем, протянувшимся в бесконечность во всех направлениях. И хотя называть эту неограниченную область гранью довольно странно, часто полезнее включать ее в число граней, чем исключать. Один из способов обрести душевный покой в этом вопросе — рассматривать граф как остров не в бескрайнем море, а на глобусе (рис. 13.2). Тогда неограниченная грань оказывается конечной.
Рис. 13.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.