Проблема четырёх красок.

Среди ранних и глубоких достижений топологии есть ряд теорем, которые первоначально были сформулированы как проблемы и лишь затем доказаны. Некоторые из них, вроде уже упоминавшейся теоремы о жордановой кривой, быть может, потому так знамениты, что их наглядная очевидность столь явно контрастирует с трудностью доказательства.

Существует и ещё одна теорема, даже более знаменитая, чем выше названная, ибо прошло более ста лет, как она сформулирована, а доказательства до сих пор нет. В 1976 г. эта теорема была доказана с использованием ЭВМ [7] – [8]. Она известна как проблема четырёх красок (формально, пока не получено доказательство, её нельзя назвать теоремой). В ней утверждается: чтобы «правильно» раскрасить любую карту, изображённую на односвязной поверхности вроде поверхности глобуса или этой страницы, необходимо только четыре краски.

Раскрашивая географическую карту, обыкновенно стараются распределить цвета, таким образом, между странами, чтобы две страны, имеющие общую границу, были окрашены по-разному. Было обнаружено на опыте, что любая карта, сколько бы ни было изображено на ней стран и как бы они ни были расположены, может быть раскрашена с соблюдением указанного правила не более чем четырьмя красками. Легко убедиться, что меньшее число достаточным для всех случаев не является. На рис. 5 изображён остров посреди моря, который никак нельзя раскрасить менее чем четырьмя красками, так как на нём имеется четыре страны, из которых каждая соприкасается с остальными тремя.

Разумеется, что на карте могут существовать точки, в которых сходится любое число областей (или стран), что ещё совсем не означает, что каждую из них необходимо закрасить своей краской. Шахматную доску можно, как обычно раскрасить только двумя красками, хотя на ней есть точки, где сходятся четыре клетки. Чтобы две страны было необходимо закрасить в разные цвета, надо чтобы у них был хот бы небольшой общий участок границы. Нам не требуется также все моря красить голубой краской или все британские владения — розовой; мы обязаны лишь красить в разные цвета прилегающие страны. Никому не удалось построить карты, для которой потребовалось бы более четырёх красок, никому не удалось также доказать, что такой карты построить нельзя, хотя огромное количество учёных умов пытались это сделать. Было доказано, что пять областей нельзя расположить таким образом, чтобы каждая из них касалась всех остальных (доказательство, если проводить его абсолютно строго, оказывается хитрее, чем можно было бы предложить.) Однако отсюда ещё вовсе не следует справедливость общей теоремы о четырёх красках, хотя существование подобных пяти областей, конечно, опровергло бы эту теорему.

Тот факт, что до настоящего времени не было ни разу найдено такой карты, для раскрашивания которой потребовалось бы более четырёх красок, приводит к мысли о справедливости такой теоремы: При любом данном разбиении плоскости на области, не покрывающие друг друга ни полностью, ни частично, всегда возможно пометить их цифрами 1, 2, 3, 4 таким образом, чтобы «прилежащие» области были бы обозначены разными цифрами. Под «прилежащими» областями понимаются такие, которые имеют целый отрезок границы общим: две области, имеющие лишь одну общую точку(или даже конечное число общих точек), как например штаты Колорадо и Аризона, не будут называться «прилежащими», так как никакого смешения или неудобства не возникает, если их раскрасить одинаково.

Можно начать чертить карту и раскрашивать её по мере построения, но не исключено, что мы зайдём в тупик и нам придётся вернуться назад и раскрашивать карту по-новому. Во всех экспериментах нам удаётся выпутаться из любого положения, но до сих пор не доказано, что это действительно возможно всегда.

Есть основание полагать, что впервые проблема четырёх красок была поставлена Мёбиусом в 1840г.; позднее её формулировали де Морган в 1850г. и Кэли в 1878г. «Доказательство» её было опубликовано в 1879г. Кемпе, но Хивуд в 1890г. нашёл ошибку в рассуждении Кемпе. Пересматривая доказательство Кемпе, Хивуд обнаружил, что пяти красок всегда достаточно. Несмотря на усилия многих выдающихся математиков, положение вплоть до нашего времени остаётся в сущности неизменным. Было доказано, что пяти красок достаточно для всех карт, и имеется предположение, что достаточно также четырёх. Но, как и в случае знаменитой теоремы Ферма, ни доказательства этого предположения, ни противоречащего ему примера приведено не было, и оно остаётся одной из «больших» нерешённых математических проблем. Заметим, между прочим, что проблема четырёх красок была решена в положительном смысле для частных случаев, когда число областей не превышает тридцати восьми. Отсюда ясно, что если в общем случае теорема неверна, то опровергающий пример должен быть не особенно простым.

Самое досадное, что доказана теорема, которая кажется гораздо более трудной: на торе или на любой другой двусвязной поверхности существуют карты, для раскрашивания которых требуется 7 красок, и семи красок хватает для раскрашивания любой карты. В случае если читателю нравится озадачивать других, пусть он нанесёт рис. 6 на бумажный тор (бублики малопригодны для картографии) и после небольшой предварительной болтовни его раскрасить. Как можно заметить, на рисунке семь областей, каждая из которых касается всех остальных (помните о склейках, указанных стрелками).

Следует объяснить, что области на противоположных сторонах, которые соприкасаются между собой вдоль участка склейки, должны быть окрашены в разные цвета. Даже в случае ленты Мёбиуса удалось доказать, что нужно не более чем 6 красок и что есть карты, для которых требуется ровно 6 красок. Если разбить полоску, как показано на рис. 7, а затем перекрутить её и склеить, то мы увидим, что при этом получится 6 областей, каждая из которых будет касаться всех остальных. Поскольку у листа Мёбиуса одна сторона, мы считаем, что он прозрачен: каждый участок имеет один и тот же цвет, независимо от того, с какого направления мы на него смотрим.

К проблеме четырёх красок подступались с разных сторон, из которых по-видимому, наиболее обещающей является формула Эйлера для многогранников, поскольку любую карту можно топологически преобразовать в некоторый многогранник, а формула, как мы видели ранее, приложима к любой фигуре, состоящей из граней (стран на карте), рёбер (границ) и вершин ( точек соприкосновения границ). Несмотря на изнурительные исследования, основная проблема не решена до сих пор, хотя в качестве её «отходов» получен ряд интересных теорем. В некотором смысле эту проблему можно было бы назвать проблемой трёх красок, ибо если бы нам удалось построить карту, для внешнего «пояса» которой потребовалось бы более трёх красок, то мы могли бы затем окружить её ещё одной областью, для чего нам понадобилась бы пятая краска.

Это означает не то, что для всей такой карты, за исключением лишь окружающей карту области, используют только 3 краски, а то, что во всех случаях мы должны быть в состоянии так перекрасить карту, чтобы для областей внешнего «пояса» потребовалось только 3 краски. В случае карты, изображённой на рис.8, мы начинаем раскрашивать сначала внутренние области: 1, 2 и 3, а затем, как на показано, окружающие их области; при этом мы начинаем с тех же красок 1, 2 и 3, но уже для х потребуется четвёртая краска, а для у – пятая. Дабы этого избежать, мы должны отказаться от четвёртой краски для области х, закрасив этим цветом одну из внутренних областей, что позволит нам в случае «пояса» х обойтись тремя красками. Если мы найдём удачный метод удаления четвёртых красок для всех последовательно возникающих «внешних поясов», то сможем решить эту часть проблемы.

Любой карте можно придать более единообразную форму, преобразовав её в то, что называется правильной картой – такой, у которой в каждой точке соприкасается не более трёх областей. Это не повлияет на раскрашивание, поскольку при переходе к первоначальной карте окажется лишь, что несоприкасающиеся области соприкасаются в точке (но не по части границы!). Обычный способ состоит в том, чтобы заменить точку р, в которой соприкасается более трёх областей, новой областью А (рис.9). Теперь у нас образовалось 4 точки a, b, c, d, в каждой из которых соприкасаются только 3 области (страны). Если мы правильно раскрасим эту вторую карту, а затем удалим А, то в результате останется всё ещё правильно раскрашенная карта, с той оговоркой, что мы, быть может, используем 3 краски там, где окажется достаточно и двух. Мы принесли простоту в жертву единообразию – вещь, порой полезная в математике.

Отметим то замечательное обстоятельство, что для некоторых поверхностей более сложного типа, чем плоскость или сфера, соответствующие, соответствующие теоремы действительно были доказаны, так что, как это ни парадоксально, анализ более сложных (в геометрическом отношении) поверхностей в данном случае проводится легче, чем более простых. Как было сказано выше, для случая поверхности тора, имеющей вид «бублика», что всякая нарисованная на ней карта может быть раскрашена семью красками и что, с другой стороны, на ней мыслимы такие карты, составленные из семи областей, что каждая область соприкасается с остальными шестью.

Головоломка. Вам требуется раскрасить карту ( рис. 10). Площадь каждой области равна 8м², за исключением верхней, у которой площадь составляет 16м². У вас есть следующие краски: КРАСНАЯ, которой хватает ровно, на 24м²; ЖЁЛТАЯ, которой хватает на 24м²; ЗЕЛЁНАЯ, которой хватает на 16м², и СИНЯЯ, которой хватает на 8м². Результат должен удовлетворить обычному требованию: соприкасающиеся области нельзя закрашивать в одинаковый цвет. Остерегайтесь единорогов.

Фракталы.

Объекты, которые мы теперь называем фракталами, впервые появились в воображении математиков начала прошлого столетия. И тогда вряд ли могло прийти в голову, что в окружающей нас природе встретится что-либо похожее на эти необычные и изысканные кривые. И хотя в этом параграфе речь пойдёт в основном о физических системах, начать придётся с маленького и очень нестрогого математического введения.