Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Также статью Эйлера часто называют зарождением теории графов. Это утверждение не лишено оснований. Хотя Эйлер не чертил графов в своей статье, его абстрактный подход к проблеме напоминает рассуждения, свойственные теории графов. Его применение новой дисциплины — geometriam situs, или топологии, — к задаче и осознание новизны этого метода свидетельствуют об основании нового раздела математики.
Для обсуждения решения нам понадобится несколько определений. Как и в случае многогранников, будем называть степенью вершины количество исходящих из нее ребер. Если в вершине есть петля (ребро, начинающееся и заканчивающееся в ней, как в правом графе на рис. 11.1), то она увеличивает степень на 2. В графе, образованном кёнигсбергскими мостами, имеется три вершины степени 3 и одна вершина степени 5. Граф называется связным, если из любой вершины можно дойти до любой другой, следуя по ребрам.
Вычерчивание графа, начинающееся в одной вершине и заканчивающееся в другой, называется обходом. Нас интересует весьма специальный класс обходов — такие, при которых каждое ребро посещается ровно один раз; они называются эйлеровыми обходами. Если эйлеров обход начинается и заканчивается в одной и той же вершине, то она называется эйлеровым циклом. В общем случае циклом называется обход графа, который начинается и заканчивается в одной и той же вершине и не проходит по одному ребру дважды. Произвольный (не эйлеров) цикл может не проходить по каждому ребру.
На языке теории графов мы можем переформулировать задачу о кёнигсбергских мостах следующим образом:
Существует ли для графа кёнигсбергских мостов (рис. 11.3) эйлеров обход? Вообще, как узнать, существует для произвольного графа эйлеров обход?
Эйлер решил обе эти задачи. В переводе на современный язык решение описывается следующим образом.
Для графа существует эйлеров обход тогда и только тогда, когда граф связный и в нем имеется ноль или две вершины нечетной степени. Если имеется две вершины нечетной степени, то обход должен начинаться в одной из них, иначе он может начинаться в любой вершине.
С помощью этого критерия задача о кёнигсбергских мостах легко решается. Поскольку в графе четыре вершины нечетной степени, то эйлерова обхода не существует! Неудивительно разочарование жителей Кёнигсберга, которые никак не могли отыскать маршрута для идеальной вечерней прогулки.
Но почему решение Эйлера правильно? Требование связности графа очевидно. А вот требование о существовании нуля или двух вершин нечетной степени нуждается в осмыслении. Для доказательства теоремы нужно сделать две вещи. Во-первых, мы должны показать, что в любом графе, допускающем эйлеров обход, существует ноль или две вершины нечетной степени. Во-вторых, мы должны доказать обратное: если в связном графе имеется ноль или две вершины нечетной степени, то он допускает эйлеров обход.
Предположим, что имеется граф, допускающий эйлеров обход; мы покажем, что в нем имеется ноль или две вершины нечетной степени. Положим лист кальки поверх графа и начнем вычерчивать эйлеров обход. В начале вычерчивания первая вершина будет иметь степень 1, а остальные — степень 0. После того как мы дойдем до второй вершины и оставим ее позади, она будет иметь степень 2. Начиная с этого момента, каждый проход через вершину увеличивает ее степень на два. Это продолжается, пока мы не дойдем до конца обхода. В этот момент мы увеличиваем степень последней вершины на единицу. Если обход начинается и заканчивается в разных вершинах, то обе они будут иметь нечетную степень, и это будут единственные вершины нечетной степени. Если же обход начинается и заканчивается в одной и той же вершине, то она, как и все остальные вершины, будет иметь четную степень.
Обратное утверждение Эйлер принял как само собой разумеющееся: если в графе имеется ноль или две вершины нечетной степени, то он допускает эйлеров обход. Первое доказательство этого факта было дано Карлом Хирхольцером (1840–1871) и опубликовано после его смерти, в 1873 году90.