Жемчужина Эйлера
- Автор: Ричесон Дэвид С.
- Год: 2021
- Язык: русский
- Жанр: Прочее научное
Электронная книга - «Жемчужина Эйлера». Краткое содержание книги:
В 1750 году Эйлер заметил, что любой многогранник, имеющий V вершин, E ребер и F граней, удовлетворяет соотношению V – E + F = 2. Из книги вы узнаете, что греки совсем не заметили эту формулу, что Декарт был в шаге от ее открытия, что математики XIX века обобщили ее в направлениях, о которых Эйлер и не подозревал, а в XX веке было доказано, что у любого тела есть своя формула Эйлера. На тщательно подобранных примерах представлены многие элегантные и неожиданные применения этой формулы, например: почему на Земле всегда существует точка, где нет ветра, как измерить площадь лесного участка, посчитав деревья на нем, и сколько разноцветных карандашей необходимо для раскрашивания любой карты.
Издание предназначено для широкого круга любителей математики.
Рис. 14.8. Перестановка цветов в красно-синей цепочке дает еще одну допустимую раскраску
Выше мы доказали теорему о шести красках. А прием Кемпе позволит нам доказать теорему о пяти красках.
Начнем доказательство точно так же, как для теоремы о шести красках. Предположим, что имеется минимальный злодей — карта с наименьшим количеством стран N, которую нельзя раскрасить пятью красками. По теореме о пяти соседях, в графе смежности G существует вершина v степени 5 или меньше. Обозначим H граф, полученный удалением вершины v. Поскольку H содержит N — 1 вершин, его можно раскрасить в пять красок. Рассмотрим вершины, соседние с v. Если для раскрашивания этих вершин использовано 4 или меньше красок (например, если степень v не больше 4), то раскраску можно завершить, выбрав для окрашивания v неиспользованный цвет. Но если для раскрашивания вершин, соседних с v, использованы все пять цветов, то решение не такое простое.
Назовем a, b, c, d, e вершины, соседние с v (перечислены по часовой стрелке), и предположим, что они раскрашены в красный, синий, желтый, зеленый и фиолетовый цвета. Рассмотрим красную вершину a и содержащую ее красно-желтую цепочку. Необходимо рассмотреть два случая. Сначала предположим, что вершина c не принадлежит этой красно-желтой цепочке (как на рис. 14.9). Тогда мы можем переменить цвета красных и желтых вершин в цепочке на противоположные, не меняя цвета вершины c. В частности, мы сможем покрасить v красным и получить 5-раскраску G. С другой стороны, предположим, что c принадлежит красно-желтой цепочке (как на рис. 14.10). Тогда перемена цветов в цепочке изменила бы и цвет c, поэтому для v не освободился бы цвет. Это нам ничего бы не дало. Однако поскольку граф планарный, сине-зеленая цепочка, содержащая вершину d, не может содержать вершину b. Поэтому перемена цветов в этой сине-зеленой цепочке позволяет покрасить v зеленым цветом, и мы получим 5-раскраску G.
Рис. 14.9. Перестановка цветов в красно-желтой цепочке для завершения раскраски
Рис. 14.10. Перестановка цветов в сине-зеленой цепочке для завершения раскраски
Дефектное доказательство Кемпе теоремы о четырех красках было похоже на это доказательство теоремы о пяти красках. Но рассуждение было по необходимости более тонким. Может случиться, что вершина v степени 5 окружена вершинами четырех разных цветов. Пришлось бы перекрасить одну или две цепочки Кемпе, чтобы уменьшить это число до трех и покрасить v. Но хотя этот метод, на первый взгляд, кажется корректным, был упущен один случай, когда перекрашивание двух цепочек Кемпе дает недопустимую раскраску.
Популярность этой завораживающей задачи продолжала увлекать как профессиональных математиков, так и любителей. Такие известные математики, как Джордж Д. Биркгоф (1884–1944), Хасслер Уитни (1907–1989), Анри Лебег (1875–1941) и Освальд Веблен (1880–1960), приняли этот вызов. Несмотря на длинные послужные списки, гиганты не смогли расколоть этот трудный орешек. Некоторые авторитетные математики, например Г. С. М. Кокстер, даже выражали сомнение в правильности гипотезы.
Наступил XX век, и внимание ученых обратилось к неизбежным множествам и приводимым конфигурациям. Неизбежным множеством называется набор конфигураций, из которых по меньшей мере одна должна присутствовать в каждом графе смежности. Например, теорема о пяти соседях дает простейшее неизбежное множество, показанное на рис. 14.11, — должна существовать вершина степени меньше 6.
Рис. 14.11. Неизбежное множество конфигураций
С другой стороны, приводимой конфигурацией называется набор вершин и ребер, которые не могут встречаться в минимальном злодее. Используя метод цепочек Кемпе, легко показать, что первые четыре конфигурации на рис. 14.11 приводимые. Мы можем удалить вершину, раскрасить оставшийся граф, при необходимости перекрасить его один раз с помощью цепочек Кемпе, а затем покрасить последнюю вершину. Пятая конфигурация составляет проблему.
Таким образом, целью стало нахождение неизбежного множества неприводимых конфигураций. Сделав это, мы доказали бы теорему о четырех красках, потому что это был бы набор конфигураций, которые не могут встречаться в минимальном злодее, но должны встречаться в любом графе смежности. Это противоречило бы существованию минимального злодея.
22 июля 1976 г., спустя почти сто лет после ошибочного доказательства Кемпе, два исследователя из Иллинойского университета, Кеннет Аппель (1932–2013) и Вольфганг Хакен (родился в 1928 г.), объявили, что нашли неизбежное множество, содержащее 1936 приводимых конфигураций. К моменту появления своих двух статей в следующем году они сумели упростить работу, исключив избыточность и уменьшив количество до 1482121. (Они также добавили в одну из статей третьего автора, Джона Коха, за помощь в вычислениях.) Теорема о четырех красках наконец-то пала!