Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
В постскриптуме Бальцер пришел к неверному выводу, будто неразрешимость этой задачи означает, что теорема о четырех красках верна. Он писал: «С каким восторгом Мёбиус, должно быть, видел далеко идущие применения» этой задачи117. Тонкая связь между проблемой пяти принцев и проблемой четырех красок заключается в том, что если бы нужное разделение царства существовало, то его карту (подобно карте на рис. 14.2) было бы невозможно раскрасить только лишь четырьмя цветами. Однако на самом деле это устраняет лишь одно препятствие к доказательству теоремы о четырех красках. Остается теоретическая возможность построить сложную карту, в которой нет пяти взаимно граничащих областей, но тем не менее раскрасить ее четырьмя цветами невозможно. По словам Мартина Гарднера, многие неправильные доказательства теоремы о четырех красках, ложившиеся в его почтовый ящик, на самом деле были не чем иным, как замаскированной проблемой пяти принцев.
Но не следует совсем отбрасывать задачку Мёбиуса. Метод соединения дворцов дорогами действительно полезен. Как и в задаче о кёнигсбергских мостах, точная география стран несущественна, важны лишь относительные местоположения. Это топологическая задача, которую можно переформулировать в терминах теории графов.
В графе смежности карты имеется по одной вершине для каждой страны, и две вершины соединены ребром, если у соответствующих стран есть общая граница (см. рис. 14.4). Если две страны граничат в нескольких местах, то мы все равно проводим между соответствующими вершинами только одно ребро. Нетрудно видеть, что граф смежности любой карты планарный. Просто будем считать, что вершины — это столицы стран, а ребра — дороги между столицами, проложенные внутри стран. По построению, в графе смежности нет ни петель, ни параллельных ребер; такой граф называется простым. Короче говоря, граф смежности карты является простым планарным графом. Заметим, что если карта связная, то таковым будет и граф смежности.
Рис. 14.4. Граф смежности карты
Создав граф смежности карты, мы преобразовали проблему раскраски карты в проблему раскраски графа. Вместо раскрашивания стран на карте мы раскрашиваем вершины графа. Если карту (или граф) можно раскрасить n цветами, так что соседние страны (вершины) будут раскрашены в разные цвета, то мы говорим, что она допускает n-раскраску. Гипотезу четырех красок можно переформулировать следующим образом:
На рис. 14.5 показана карта Невады и ее соседей, а также соответствующий граф смежности. Мы раскрасили граф четырьмя цветами, а затем перенесли эту раскраску на исходную карту.
Рис. 14.5. Раскраска графа смежности порождает раскраску карты
На типичной карте могут встречаться страны, имеющие много соседей, но это невозможно для всех стран сразу. На любой карте найдется страна, имеющая пять или менее соседей. Этот важный факт называется теоремой о пяти соседях. Для его доказательства нужна формула Эйлера и немного арифметики. В терминах теории графов она формулируется так:
Пусть имеется простой планарный граф. Поскольку в нем нет петель и параллельных ребер, можно добавить ребра так, что каждая грань будет ограничена ровно тремя ребрами. Мы докажем, что этот (больший) триангулированный граф содержит вершину степени 5 или меньше, а потому такая вершина должна быть и в (меньшем) исходном графе. Предположим, что триангулированный граф имеет V вершин, E ребер и F граней (внешняя область считается гранью). Каждое ребро является общей границей двух граней, а каждая грань ограничена тремя ребрами, поэтому 3F = 2E. По формуле Эйлера, V – E + F = 2, или, эквивалентно, 6E – 6F = 6V – 12. Подставляя 4E вместо 6F, получаем
2E = 6V – 12.
Поскольку у каждого ребра два конца, сумма степеней всех вершин равна 2E. Поэтому средняя степень вершин равна
Так как средняя степень меньше шести, то должна существовать по меньшей мере одна вершина степени 5 или меньше.
Чтобы продемонстрировать полезность теоремы о пяти соседях в задачах раскрашивания графов, докажем теорему о шести красках.