Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Предположим, что это утверждение неверно. Тогда найдется одна или несколько карт, которые нельзя раскрасить шестью цветами. Найдем в этом множестве «плохих» карт карту с наименьшим числом стран. Пусть число стран на этой карте равно N. Такой наименьший контпример часто называют минимальным злодеем. Польза выделения минимального злодея в том, что можно с уверенностью сказать, что любую карту, содержащую N - 1 или меньше стран, можно раскрасить шестью цветами.
Рассмотрим граф смежности G минимального злодея. По теореме о пяти соседях, в G найдется вершина v степени 5 или меньше. После удаления v и всех инцидентных ей ребер из G получится новый граф H. Легко видеть, что H является графом смежности карты с N - 1 странами. Поскольку H содержит N - 1 вершин, его можно раскрасить шестью цветами. Теперь вернем удаленную вершину вместе с ребрами в граф. Поскольку v соседствует не более чем с 5 другими вершинами, найдется хотя бы один неиспользованный цвет, которым можно покрасить v. Таким образом, G можно раскрасить в шесть цветов. Это противоречит предположению о том, что G — минимальный злодей, а следовательно, любая карта допускает 6-раскраску. На рис. 14.6 эта техника использована для раскрашивания графа в красный, синий, зеленый, фиолетовый и оранжевый цвета.
Рис. 14.6. Раскрашивание минимального злодея шестью цветами
К сожалению, это доказательство не проходит, когда число доступных цветов равно 4 или 5. Когда придет время вставить вершину v обратно, может не оказаться свободного цвета для ее окрашивания. В этих случаях нужны более тонкие рассуждения.
Одно такое рассуждение придумал Альфред Брей Кемпе (1849–1922). 17 июля 1879 года Кемпе, ученик Кэли, объявил, что нашел доказательство гипотезы четырех красок, и это доказательство было опубликовано в том же году118.
Рис. 14.7. Альфред Брей Кемпе
В отличие от большинства неверных доказательств, найденных за последующие сто лет, доказательство Кемпе было очень убедительным. Он предложил несколько новых остроумных методов, что позволило ему покрасить последнюю оставшуюся вершину минимального злодея. Математическое сообщество было взбудоражено.
Доказательство Кемпе оставалось последним словом в гипотезе четырех красок на протяжении десяти лет. Но, к сожалению для Кемпе, дело не было закрыто. В 1889 году Перси Джон Хивуд (1861–1955) нашел ошибку в рассуждениях Кемпе. И она оказалась фатальной. Хивуд предъявил пример карты, для которой аргументация Кемпе потерпела крах. В публикации, появившейся в 1890 году, Хивуд писал:
Настоящая статья не претендует на доказательство исходной Теоремы; на самом деле ее цели скорее деструктивные, чем конструктивные, т. к. будет показано, что в общепризнанном доказательстве имеется дефект119.
Хотя доказательство Кемпе оказалось неправильным, предложенная им техника очень важна. Хивуд признал, что идей Кемпе достаточно для доказательства теоремы о пяти красках. Более того, они вошли неотъемлемой частью в окончательное доказательство теоремы о четырех красках. И хотя неверное доказательство стало ударом по репутации Кемпе, окончательно его карьеру оно не подорвало. Он остался активным членом Лондонского королевского общества (в которое был избран за математические работы, не относящиеся к теореме о четырех красках), а впоследствии был возведен в рыцари.
Всякий, кто пытался раскрасить большую карту в четыре цвета, знает, что поначалу все идет легко, но в какой-то момент оказывается, что дальнейшее раскрашивание невозможно[8]. В этот момент приходится вернуться и перекрасить части карты в другие цвета. Прием, придуманный Кемпе, дает простой способ перекрасить карту.
Начнем с любого раскрашенного (или частично раскрашенного) графа. Выберем два цвета, скажем красный (R) и синий (B), и вершину, покрашенную в один из них. Проследуем по всем возможным путям из этой вершины, которые проходят через синюю вершину, потом красную, затем синюю и т. д. Это множество красных и синих вершин называется красно-синей цепочкой, или цепочкой Кемпе (см. рис. 14.8). Заметим, что цепочка Кемпе часто нелинейная, в ней могут быть ветвления или циклы. Ключевое наблюдение состоит в том, что поскольку никакая вершина, смежная с цепочкой Кемпе, не может быть ни красной, ни синей, мы можем перекрасить каждую красную вершину в цепочке в синий цвет и наоборот, и полученная раскраска графа по-прежнему будет правильной.
8
Стивен Барр предложил в связи с этим игру для двоих. Первый игрок рисует страну и раскрашивает ее в один из четырех цветов. Второй игрок добавляет страну и тоже раскрашивает ее. Так продолжается до тех пор, пока какой-то игрок не будет вынужден использовать пятый цвет120.