Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
И наконец, применим теорию графов и эйлеровых обходов к игре в домино. Этот пример придумал Орли Теркем (1782–1862) в 1849 году93. В стандартном комплекте домино на каждой половине костяшки нанесено от одной до шести точек. В комплекте нет двух одинаковых костяшек и все комбинации присутствуют. Всего, таким образом, получается 28 костяшек. Каждый игрок по очереди выкладывает костяшки, так чтобы число точек на одной половине его костяшки совпадало с числом точек на свободном конце уже выложенной костяшки. Костяшки с одинаковым числом точек на обеих половинах (дубли) можно класть перпендикулярно костяшке с соответствующим числом точек (как на рис. 11.9). Игра заканчивается, когда игрок не может выложить очередную костяшку. Спрашивается, всегда ли игра заканчивается, когда у какого-то игрока на руках есть костяшки? Или можно выложить все костяшки, так что у игроков ни одной не останется?
Рис. 11.8. Граф, ассоциированный с головоломкой о кирпичной стене
Рис. 11.9. Типичная партия в домино
Для анализа этой задачи построим граф следующим образом. Начнем с семи вершин, пронумерованных от 0 до 6. Каждой костяшке соответствует ребро графа. Костяшке с m точками на одной половине и n точками на другой соответствует ребро из вершины m в вершину n. Сопоставив ребра всем костяшкам, мы получим граф, показанный на рис. 11.10. Заметим, что в каждой вершине имеется петля, соответствующая костяшкам-дублям.
Все вершины в графе домино имеют степень 8. Поскольку степени всех вершин четные, граф допускает эйлеров обход. Следовательно, весь граф можно вычертить, не проходя по одному ребру дважды. Это наблюдение и есть ключ к ответу на поставленный вопрос. Чтобы показать, что можно сыграть все костяшки домино, достаточно предъявить соответствующую партию. Мы построим ее просто (хотя вряд ли такая конфигурация возникнет в реальной партии) — выстроив костяшки в линию.
Рис. 11.10. Граф, соответствующий комплекту костяшек домино
Начнем с первого ребра в эйлеровом обходе. Пусть оно соединяет вершины 0 и 3. Выложим костяшку, содержащую 0 и 3 точки (0:3). Теперь рассмотрим второе ребро в обходе. Допустим, что оно соединяет вершины 3 и 1. Выложим костяшку 3:1, приложим ее к предыдущей (рис. 11.11). Будем продолжать таким же образом, выкладывая костяшки на каждом шаге. Поскольку мы совершаем эйлеров обход, каждое ребро будет посещено ровно один раз. Поэтому мы сможем выложить все до одной костяшки.
Рис. 11.11. Часть партии в домино и соответствующая ей часть обхода графа
Как показывают эти примеры, теория графов имеет интересные применения в развлекательной математике. Однако это также весьма важная часть серьезной математики, имеющая многочисленные практические применения в таких разных областях, как информатика, вычислительные сети, социальные структуры, транспортные системы и моделирование эпидемий. Мы еще встретимся с теорией графов в последующих главах. В частности, мы выведем аналог формулы Эйлера для одного класса графов.
Приложения к главе
84. Thoreau (1894), 419.
85. Quoted in Sachs, Stiebitz, and Wilson (1988).
86. Там же.
87. Quoted in Hopkins andWilson (2004).
88. Euler (1736), английский перевод в Biggs, Lloyd, and Wilson (1986), 3-8.
89. Ball (1892).
90. Hierholzer (1873).
91. Barabasi (2002), 12.
92. Listing (1847).
93. Terquem (1849).
Глава 12
Плоскостные многогранники Коши
Коши — безумец, и с этим ничего не поделаешь, но сейчас он единственный, кто знает, как надо делать математику.