|
Основная идея перекраски схемы по Кемпе заключается в том, что две соседние точки должны быть разных цветов — скажем, синего и красного, а еще в схеме используются зеленый и желтый. Если обе оставшиеся точки окажутся зелеными или желтыми, то второй цвет окажется свободным и может быть использован для удаленной точки. Исходя из этого, считаем, что одна из них зеленая, а вторая — желтая. Теперь найдем все точки, которые соединены с синей точкой последовательностью линий, проходящих только через синие и красные точки, и назовем их красно-синей цепочкой Кемпе. По определению, любой сосед любой точки в цепочке Кемпе, не принадлежащий цепочке, должен быть зеленым или желтым, поскольку синий или красный сосед там уже есть. Обратите внимание, что замена цветов в пределах цепочки Кемпе (синий на красный, и наоборот) дает новый вариант карты, в которой по-прежнему выполняется ключевое условие о том, что соседние точки должны быть разных цветов (см. рис. 11).
Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет — и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьте: она не сможет замкнуться на желтого соседа, поскольку на ее пути непременно встретится предыдущая красно-синяя цепочка. Поменяйте желтый и зеленый цвета в цепочке местами, и дело сделано. Остается последний случай: когда не существует точек с тремя или четырьмя соседями, но по крайней мере одна точка имеет пять соседей. Кемпе предложил аналогичное, но более сложное правило перекраски точек, которое, на первый взгляд, успешно решало и эту проблему. Вывод: теорема о четырех красках верна, и доказал ее Кемпе. Эта заявление попало даже в средства массовой информации: американский журнал The Nation упомянул решение Кемпе в своем обзоре. Казалось, с проблемой четырех красок было покончено, и математики в большинстве своем с этим согласились. Правда, Питер Тэт продолжал поиски более простого решения и время от времени публиковал статьи на эту тему. Исследования привели его к нескольким полезным открытиям, но простое доказательство по-прежнему не давалось.
И тут на сцене появляется преподаватель математики из Университета Дарема Перси Хивуд, прозванный за свои великолепные ухоженные усы «Котом». Еще студентом в Оксфорде он услышал от профессора геометрии Генри Смита о теореме о четырех красках. Смит сказал ему, что теорема эта, хотя, вероятно, и верна, но не доказана, так что у Хивуда есть шанс. Кроме того, как-то он наткнулся на статью Кемпе и попытался ее понять. Результат своих размышлений Хивуд опубликовал в 1889 г. под названием «Теорема о раскраске карты», высказав при этом сожаление, что цель его статьи более «деструктивна, чем конструктивна, ибо в ней будет показано, что в признанном, кажется, на сегодня доказательстве есть дефект». Кемпе допустил ошибку. Ошибка была достаточно тонкой и возникала в схеме перекраски в том случае, когда у удаляемой точки было пять соседей. В некоторых случаях изменение цвета одной точки (по схеме Кемпе) могло повлечь за собой невозможность дальнейших изменений. При этом Кемпе считал, что если какая-то точка меняет цвет, то происходит это лишь один раз. Хивуд же нашел карту (или сеть), в которой схема перекраски по Кемпе не срабатывала, и тем самым опроверг его доказательство. Кемпе, узнав об этом, без промедления признал ошибку и добавил, что ему «не удалось исправить этот дефект». |
