Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Начнем со связного графа, имеющего ноль или две вершины нечетной степени. если таких вершин две, то поместим карандаш в одну из них, в противном случае — в произвольную вершину. Начнем вычерчивание в любом направлении. Дойдя до первой вершины, выберем случайным образом следующее ребро. Будем продолжать таким образом — делать случайный выбор в каждой вершине (конечно, избегая уже посещенных ребер), пока дальнейшее движение не станет невозможным. В силу приведенного выше рассуждения, если мы начинали с вершины нечетной степени, то закончим вычерчивание в другой вершине нечетной степени, иначе вычерчивание завершится в той вершине, с которой начинали. На рис. 11.4 путь abcdefghi определяет такой обход.
Если этот путь не проходит по всем ребрам графа, то удалим все посещенные ребра и посмотрим на оставшийся граф (возможно, он уже не связный). Поместим карандаш в какую-нибудь вершину, которая посещалась при первоначальном вычерчивании. Как и раньше, будем вычерчивать граф, пока не окажется, что дальше двигаться невозможно. В нашем примере получится обход jkl. Теперь вставим новую трассу вычерчивания в нужное место построенного ранее обхода. В нашем примере путь jkl вставляется между ребрами b и c первоначального обхода. Таким образом, мы получили путь abjklcdefghi, являющийся эйлеровым обходом. В общем случае, возможно, придется проделать такую вставку несколько раз, пока не будут вычерчены все ребра.
Рис. 11.4. Построение эйлерова обхода
Заметим, что мы узнали о вычерчивании графов больше, чем видно из этого решения на первый взгляд. Мы ставили целью найти эйлеровы обходы, но заодно определили, когда обход может начинаться и заканчиваться в одной и той же вершине. Точнее:
Граф допускает эйлеров цикл тогда и только тогда, когда он связный и не содержит вершин нечетной степени. В этом случае эйлеров цикл может начинаться и заканчиваться в любой вершине.
В 1875 году, спустя полтора века после того, как Эйлер проанализировал маршруты прогулок по Кёнигсбергу, в городе был построен новый мост91. Он был возведен к западу от острова Кнайпхоф и соединил северный берег реки с южным (рис. 11.5). Наконец-то жители Кёнигсберга смогли совершить прогулку по всем мостам, пройдя по каждому ровно один раз, поскольку теперь оказалось ровно две вершины нечетной степени — соответствующие острову и суше между рукавами реки. Конечно, некоторые горожане не могли начать прогулку от порога своего дома, и никому не удалось бы закончить прогулку в том же месте, где она началась.
Рис. 11.5. Новый мост в Кёнигсберге и новый граф
Решение задачи о кёнигсбергских мостах иллюстрирует общее для математики явление. Начиная изучать проблему, мы сталкиваемся с уймой лишней информации. Хороший метод решения позволяет устранить все несущественное и сконцентрироваться на сути. В данном случае такие детали, как точное положение мостов и участков суши, ширина реки и форма острова, оказались не важны. Эйлер упростил задачу, так что ее стало возможно сформулировать в терминах теории графов. Это и есть признак гения.
В заключение приведем три примера. В 1847 году Иоганн Бенедикт Листинг (1808–1882), математик, с которым мы еще встретимся снова, придумал граф, изображенный на рис. 11.6, чтобы проиллюстрировать проблему вычерчивания (мы рисуем граф так, как это сделал Листинг, опуская вершины в точках пересечения)92. Допускает ли этот граф эйлеров обход? А эйлеров цикл? Предлагаем читателю подумать над этой задачей, прежде чем продолжить чтение.
Мы видим, что все вершины имеют четную степень, кроме самой левой и самой правой, степень которых равна 5. Поскольку существует ровно две вершины нечетной степени, граф Листинга опускает эйлеров обход, и каждый такой обход должен начинаться в одной из этих вершин и заканчиваться в другой. Поскольку в графе есть вершины нечетной степени, то эйлерова цикла не существует.
Рис. 11.6. Головоломка Листинга на вычерчивание графа
Второй пример — вариация на тему задачи о мостах. Рассмотрим рисунок, напоминающий кирпичную стену (рис. 11.7). Можно ли провести непрерывную кривую, пересекающую каждый отрезок ровно один раз (кривая может начинаться и заканчиваться в разных кирпичах)? Попытка, показанная на правом рисунке, — не решение, потому что кривая не пересекает один отрезок.
Рис. 11.7. Неправильное решение головоломки
Это невозможно. Обосновать это утверждение можно, преобразовав задачу в задачу о вычерчивании графа. Поместим по одной вершине внутри каждого кирпича и еще одну вне стенки. Проведем между вершинами ребра, соответствующие отрезкам, разделяющим кирпичи (см. рис. 11.8). Достаточно выяснить, допускает ли этот граф эйлеров обход. Поскольку в графе четыре вершины степени 5, эйлеров обход невозможен. Поэтому не существует кривой, обладающей желаемыми свойствами.