Проблема четырех красок кратко
Обновлено: 07.07.2024
Проблема четырёх красок — математическая задача, предложенная Ф. Гутри (англ.) в 1852 году, сформулированная следующим образом:
| Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. |
Стоит отметить две необходимые характеристики этой карты:
- Граница между любыми двумя областями является непрерывной линией.
- Каждая область является односвязной.
Содержание
Эквивалентные формулировки
Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, чтобы все стороны каждого треугольника были раскрашены в разные цвета.
О доказательстве
Кеннет Аппель (Kenneth Appel) и Вольфганг Хакен (Wolfgang Haken) из Иллинойского университета доказали в 1976 году, что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок [1] . Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.
Новое доказательство, основанное на алгебраических и топологических методах, дал индийский математик Ашей Дарвадкер [2] в 2000 году.
История доказательства
Наиболее известные попытки доказательства:
- Альфред Кэмпе предложил доказательство в 1879 году [3] , его опровергли в 1880 году, на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов. предложил другое доказательство в 1880 году [4] , его опровергли в 1891 году.
- В своей книге [5]В. А. Горбатов утверждает, что предложил классическое доказательство ещё в 1964 году (объёмом около 30 стр.). Однако опровержений, как и подтверждений, это доказательство пока не получило, см. также [6] .
Вариации и обобщения
Аналогичные задачи для других поверхностей (тор, бутылка Клейна и т. д.) оказались значительно проще. Для всех замкнутых поверхностей, кроме сферы (и ей эквивалентных плоскости и цилиндра) и бутылки Клейна, необходимое число красок может быть вычислено через эйлерову характеристику по формуле, предложенной в 1890 году Перси Джоном Хивудом (Percy John Heawood) [7] и окончательно доказанной на протяжении 1952—1968 годов группой математиков с наибольшим вкладом Герхарда Рингеля и Теда Янгса (Gerhard Ringel and J. T. W. Youngs) [8] [9]
Для бутылки Клейна число равно 6 (а не 7, как по формуле) — это показал П. Франклин в 1934 году, [10] а для сферы — 4.
Для односторонних поверхностей [9]
.
В старших размерностях разумного обобщения задачи не существует, так как легко придумать уже трёхмерную карту с произвольным числом областей, которые все друг друга касаются.
Для этой игры нужны четыре цветных карандаша. Первый игрок начинает игру, рисуя произвольную пустую область. Второй игрок закрашивает её любым из четырёх цветов и в свою очередь рисует свою пустую область. Первый игрок закрашивает область второго игрока и добавляет новую область, и так далее — каждый игрок раскрашивает область соперника и добавляет свою. При этом области, имеющие общую границу, должны быть раскрашены в разные цвета. Проигрывает тот, кто на своём ходу вынужден будет взять пятую краску.
Стоит отметить, что в этой игре проигрыш одного из игроков вовсе не является доказательством неверности теоремы (четырех красок оказалось недостаточно!). А лишь иллюстрацией того, что условия игры и теоремы весьма разнятся. Чтобы проверить верность теоремы для полученной в игре карты, нужно проверить связность нарисованных областей и, удалив с нее цвета, выяснить, можно ли обойтись лишь четырьмя цветами для закрашивания получившейся карты (теорема утверждает, что можно).
Представьте себе географическую карту поверхности планеты (шара), на которой есть только суша; каждая точка поверхности принадлежит какой-то стране. Все страны односвязные — представляют собой единый кусок без дырок.
Картографу нужно раскрасить карту так, чтобы никакие две соседние страны не были одного цвета. Соседние страны — это такие, у которых есть общая граница ненулевой длины; если у двух стран только одна общая точка границы, то они могут быть одноцветными.
Как много красок нужно картографу, чтобы раскрасить карту по таким правилам?
Оказывается, четыре, — в этом и состоит утвеждение теоремы о четырех красках.
Но ее долго не могли доказать, и она оставалась известной как задача о четырех красках. Считается, что в середине XIX века ее поставил Фрэнсис Гутри в письме своему брату.
Она хорошо переводится на язык графов. Представьте, что у вас есть раскрашенная карта; сожмите каждую страну до одной цветной точки, и соедините точки отрезками, если у этих стран есть общая граница. Получится граф, у которого ребра не пересекаются (планарный); концы всех ребер разноцветные. Мало того: у этого графа нет петель (страна не граничит сама с собой) и нет двойных ребер (у двух стран только одна граница).
В терминах графов теорема о четырех красках звучит так:
Для любого планарного графа без петель и кратных ребер можно раскрасить его вершины в 4 или менее краски так, что у любого ребра концы разноцветные.
В формулировке важно, что раскрашивать нужно именно сферу. Например, чтобы раскрасить по таким правилам тор, может потребоваться 7 красок, а чтобы раскрасить ленту Мёбиуса — 6 красок.
Доказывали теорему долго. Несколько раз публиковались, а потом опровергались доказательства. Были получены серьезные неочевидные результаты о других поверхностях; и только поверхность шара никак не поддавалась.
И только в 1974 году Аппель и Хакен с применением компьютера показали, что четырех красок достаточно, и это вызвало серьезный раздрай в математическом сообществе. Ведь ни один человек доказательство не мог проверить вручную, своими собственными силами! Мало того, в алгоритме 1974 года обнаружилась ошибка, пришлось в него вносить исправления. Текст доказательства занимал около 500 страниц с картинками; и только к 1981 году Шмидт проверил процентов 40% ключевых 400 страниц, исправив по дороге 15 ошибок. Похоже, что ни один человек так никогда и не проверил даже текстовую часть доказательства до конца.
В конце концов стало ясно, что проще создать новое доказательство, чем довести до безупречного состояния доказательство Аппеля и Хакена. Позднее это сделал Пол Сеймур. У него и компьютер был помощнее, и алгоритм более устойчивый.
Как и множество математических парадоксов, знаменитая Проблема четырех красок возникла в области, на первый взгляд, далекой от математики. В 1852 году англичанин Фрэнсис Гатри (по утверждениям одних, составляя карту британских графств, по утверждениям других, очевидно, на досуге, раскрашивая ее) неожиданно для себя выяснил, что, имея в наличии всего лишь четыре краски, он может совершенно свободно раскрасить карту таким образом, что две соседние области не будут окрашены в один и тот же цвет. С увлечением предаваясь этому занятию, через некоторое время Гатри задал себе вопрос: а что, если не только карты британских графств, но и любая другая карта с любым количеством областей может быть раскрашена с использованием минимального числа красок — четырех, и при этом две граничащие области не будут иметь общую окраску. Возможно ли это? Так родилась Проблема четырех красок.
С этого момента Проблема четырех красок — одновременно необыкновенно простая и удивительно сложная — начала свое триумфальное шествие по миру, и в конце XIX века была решена британским математиком Альфредом Кемпе, который научно обосновал использование для раскраски любой карты именно четырех красок. Однако радость Кемпе была недолгой: всего лишь через 10 лет Перси Хивурд опроверг доказательство Кемпе, в свою очередь представив новое решение Проблемы четырех красок, которое на деле также оказалось не лишенным существенных недостатков.
С течением времени, опираясь в большей степени на топологию, которую, в отличие от геометрии, не интересуют точные формы и размеры, математики сумели доказать, что только карта, содержащая определенное число областей (25, 27, 35, 39), может быть раскрашена четырьмя красками. Иными словами, рассматривались исключительно частные случаи решения проблемы, а общий — главнейший — для бесконечно большого числа областей — оставался непокоренным.
Однако в 1976 году математики Вольфганг Хакен и Кеннет Аппель, проанализировав с помощью компьютера 1482 карты, выяснили и научно доказали, что четырех красок для раскрашивания любой карты будет достаточно. Казалось бы, Проблема четырех красок решена, однако — не тут-то было. Любое доказательство — особенно сенсационное — требует тщательной проверки, но, поскольку в процессе решения проблемы одну из важнейших ролей сыграла компьютерная техника, результат был подвергнут сомнению со стороны тех математиков, которые, отказав компьютеру в надежности, требовали предъявить письменные — пошаговые — доказательства решения Проблемы четырех красок. На эти требования Хаген и Аппель утверждали, что их доказательство включает в себя такое количество текста и — самое главное — диаграмм, что для их проверки без помощи техники у некоторых скептиков не хватит и целой жизни. Таким образом, на сегодняшний день, несмотря на очевидное решение Проблемы четырех красок, она не может быть названа таковой в полной мере.
Раскрашивая географическую карту естественно пользоваться по возможности меньшим количеством цветов, однако так, чтобы две страны, имеющие общую часть границы (не только общую точку), были окрашены по-разному. В 1852 году Френсис Гутри (Guthrie), составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану (DeMorgan), а тот - математической общественности. Точная формулировка гипотезы опубликована А. Кэли (Cayley, 1878).
Первое доказательство появилось год спустя и принадлежало В. Кемпе (Kempe). Одиннадцать лет спустя П. Хивуд (Heawood) обнаружил в нем ошибку. (Однако из доказательства Хивуд понял, что пяти красок действительно достаточно. Тем не менее для любой конкретной карты хватало четырех красок!) За первым ошибочным доказательством последовало множество других. В этом отношении проблема четырех красок уступала лишь знаменитой проблеме Ферма. До середины XX века, хотя проблемой четырех красок занимались многие выдающиеся математики, положение с доказательством изменилось несущественно: идеи Дж. Д. Биркгофа позволили П. Франклину в 1913 году доказать гипотезу для карты с не более чем 25 странами. Позже это число было увеличено до 38.
В 1977 году доказательство гипотезы четырех красок было наконец получено К. Аппелем и У. Хакеном (Appel, Haken) и опубликовано в двух статьях [1]. Значительную часть рутинных проверок выполнил компьютер, и это революционное нововведение в сложившуюся практику дедуктивных рассуждений в чистой математике служит основанием для некоторого естественного скептицизма по отношению к данному доказательству и по сей день (подробнее об этом в конце статьи). Сначала мы приведем точные формулировки, докажем теорему о пяти красках и укажем некоторые эквивалентные проблемы.
Содержимое разработки
Проблема четырёх красок
Проблема четырёх красок
Административная карта России, раскрашенная в четыре цвета
Задача раскраски карты на плоскости эквивалентна задаче на сфере.
Для простых карт достаточно и трёх цветов, а четвёртый цвет начинает требоваться, например, тогда, когда имеется одна область, окруженная нечетным числом других, которые соприкасаются друг с другом, образуя цикл. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX века, но доказательство теоремы для случая четырёх цветов столкнулось со значительными трудностями.
Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем (англ.) и Вольфгангом Хакеном (англ.) из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих 1936 карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.
Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1) [2]
Многие люди путаются в непонятных математических символах и строгих математических правилах, всегда избегая решения тех проблем, в которых встречаются не только буквы, но и цифры. Безусловно, математика бывает очень сложной, но те результаты, которые можно с помощью нее получить, могут быть достаточно неожиданны, красивы и просто поразительны.
Теорема Брауэра о неподвижной точки
Это теорема из такого раздела математики как топология, была доказана Лёйтзеном Брауэром. Ее чисто математическое выражение является достаточно абстрактным, но ее можно неожиданным способом применить к разным реальным событиям. Допустим, что у нас есть какая-нибудь картина (к примеру Мона Лиза), и мы можем сделать ее копию. Потом мы можем делать с этой копией что захотим – увеличивать, уменьшать, вращать, сминать, все что угодно. Терема Брауэра о неподвижной точке гласит, что если эту деформированную копию положить на оригинал, то всегда найдется хотя бы одна точка на копии, которая будет находиться ровно над этой же самой точкой изображения на оригинале. Это может быть кусочек уха, рта или глаза Моны, но обязательно такая точка найдется.
Теорема работает и в трехмерном пространстве. Представьте, что у нас есть стакан воды, в который мы положили ложку и размешивали воду столько, сколько захотим. По теореме Брауэра, всегда будет хотя бы одна молекула воды, которая в итоге окажется ровно на том же самом месте, что и до размешивания.
Парадокс Рассела
На рубеже 20-го века многие ученые были увлечены новым разделом математики – теорией множеств. В принципе, множество – это совокупность каких-либо объектов. В те времена, считалось, что любой набор объектов можно считать множеством – множество всех фруктов, множество всех президентов США, и все это считалось верным. Стоит добавить, что одно множество может включать в себя другие множества. В 1901 году известный математик Бертран Рассел сделал нашумевшее открытие, когда понял, что такой способ мышления ошибочен – на самом деле не все совокупности объектов можно назвать множеством.
Решив разобраться в этом вопросе, Рассел описал множество всех множеств, которые не содержат себя в качестве своих элементов. Множество всех фруктов не содержит в себе само себя, так что его можно включить во множество Рассела, как и огромное количество других множеств. Но что насчет самого множества Рассела? Оно не содержит в себе само себя, так что его тоже надо включить в это множество. Погодите ка… теперь оно содержит себя в самом себе, так что нам нужно его исключить. Но теперь его нужно включить в себя снова, так как на этот момент, оно не содержит себя в самом себе. Ну и так далее. Этот логический парадокс привел к пересмотру теории множеств, одному из самых важных направлений в современной математике.
Теорема о конце света
Математика может быть использована для определения того, когда наш вид полностью вымрет. Используя вероятности, но тем не менее.
Это теорема (которая существует уже примерно 30 лет и была открыта и переоткрыта уже несколько раз) говорит о том, что время человечества уже на исходе. Одно из доказательств (которые принадлежит астрофизику Ричарду Готту) на удивление простое: если рассматривать все время существования человеческого вида как процесс жизни отдельного организма, то можно определить на каком этапе жизни наш вид находится.
Согласно Готту, человечество вымрет в интервале от 5100 лет до 7,8 миллионов лет от текущего времени. Итак, человечество, тебе пора писать завещание.
В середине ХIX столетия возникло совершенно новое течение в геометрии, которому было суждено вслед за тем стать одной из главных движущих сил современной математики. Предметом новой отрасли, называемой топологией (или analysis situs), является изучение свойств геометрических фигур, сохраняющихся даже тогда, когда эти фигуры подвергаются таким преобразованиям, которые уничтожают все их и метрические и проективные свойства.
Проблема четырех красок
2.1.История возникновения теоремы
С тех пор, как появились первые географические карты, встал и вопрос о том, как их лучше всего раскрашивать. С одной стороны, каждая отличная от прочих территория должна быть окрашена в свой цвет. С другой стороны, строгая функциональность не допускала кричащей пестроты. Да и типографские возможности тех времен были не так уж велики. В связи с этим, географы поставили перед математиками задачу, на первый взгляд казавшуюся довольно простой: каким минимальным количеством красок может быть раскрашена карта так, чтобы каждая из соприкасающихся на ней фигур имела свой цвет? Впервые этот вопрос сформулировал англичанин Френсис Гутри в далеком 1852 г. А об ответе – доказательстве или опровержении – математики спорят до сих пор.
Казалось бы: предположили и доказали, так и раскрашивайте. Но математики, как известно, уважают точность. А потому между ними разгорелись споры на эту тему. Одни пытались теорему доказать, другие – опровергнуть. В ходе этих споров уже к концу XIX в. было доказано, что простейшая карта может быть раскрашена с применением трех, а сложнейшая – пяти цветов. Однако случай с применением именно 4 цветов оставался загадкой. Вот карта графств Британии, раскрашенная четырьмя красками [Рис.1]
С увеличением числа стран лавинообразно растет и число различных вариантов их взаимного расположения, и число вариантов раскраски карт. Проблема становилась совершенно неприступной.
Заслуженный российский математик и инженер, профессор Вячеслав Афанасьевич Горбатов в своей книге, вышедшей в 1964 г. предложил свое классическое доказательство теории четырех красок, занявшее около 30 страниц. Но, по неизвестным причинам, оно прошло незамеченным и не встретило ни подтверждений, ни опровержений.
В итоге, как сама журнальная статья, так и многомиллионный судебный иск оказались апрельским розыгрышем. Однако математики отнюдь не сочли проблему исчерпавшей себя. Более того, искать решение стало еще интереснее, ведь в распоряжении ученых появились компьютеры! В 1976 г. математики из Иллинойского университета Кеннет Аппель и Вольфганг Хакен с помощью ЭВМ создали 1936 карт, ни одна из которых не могла опровергнуть верность теории. Доказательство заняло сотни листов. На его основании ученые утверждали, что контрпримера этой теореме существовать не может! Идея их доказательства состояла в следующем: сначала доказывается возможность раскраски для карт с числом n стран, 0, затем с помощью компьютера подтверждается возможность раскраски карт и для0. Потратив свыше тысячи часов машинного времени, перебрав громадное число вариантов, компьютер подтвердил справедливость гипотезы. Таким образом, вековая проблема четырех красок была решена.
Это доказательство, впервые в математике полученное с помощью компьютера, получило широчайшее признание. Оставались, конечно, отдельные скептики, противившиеся тому, что такое решение не может быть проверено вручную. Возможно, именно поэтому в 1997 г. группа американских ученых предложила новое, более простое доказательство. Впрочем, идеи были аналогичны, а главным помощником исследователей по-прежнему был компьютер. В 2005 г. доказательство снова подтвердилось Джорджсом Гонтиром, который использовал для этого специализированное программное обеспечение.
Пожалуй, на этом историю теоремы о четырех красках можно считать исчерпанной. Впрочем, если вы считаете себя великим математиком, вполне можете попытаться самостоятельно ее доказать либо опровергнуть. А можете просто поиграть, ведь тренировка мозга и развитие логического мышления не вредило до сих пор еще никому.
Я тоже попробовала самостоятельно раскрашивать карты, чтобы убедиться в том, что для раскраски любой конкретной карты хватает четырех красок. Вот, например, раскраска карты России, подтверждающая гипотезу Ф. Гутри, что карту можно раскрасить четырьмя красками [Рис 2].
Раскрашивая карту, я обратила внимание и на то, что её нельзя раскрасить тремя красками. В самом деле, если рассмотреть четыре территории Чукотский автономный округ, Камчатский край, Республика Якутия, Магаданская область, то можно заметить, что Чукотский автономный округ, окружен только тремя этими территориями. Это значит, если территорию Чукотского округа покрасить первым цветом, то для покраски территорий Камчатского края, Республики Якутия, Магаданской области потребуется ещё три цвета.
Здесь натуральными числами обозначен порядок появления областей на игровой схеме. Понятно, что нечетными числами обозначены области, нарисованные первым игроком, четными – вторым игроком. По правилам игры, когда первый игрок нарисовал 9-ую область, второй должен её закрасить, но для этого ему потребуется пятый цвет, значит, он проиграл.
Существуют также следующие вариации игры:
Карта заранее разбивается случайным образом на области различной величины, и каждый ход игры меняется игрок который закрашивает область, а также меняется цвет (в строгой последовательности). Таким образом каждый игрок закрашивает карту только двумя цветами, а в случае если не может закрасить так, чтобы области, имеющие общую границу были раскрашены в разные цвета. пропускает ход. Игра прекращается, когда ни один из игроков больше не сможет сделать ни одного хода. Выигрывает тот, у кого общая площадь закрашенных им областей больше.
Квадрат разбит на несколько квадратов (в основном 4x4), и его стороны окрашены в один из четырех цветов (каждый в разный цвет). Первым ходом закрашивается квадрат прилегающий к стороне, каждый последующий ход можно закрашивать тот квадрат, который прилегает к одному из закрашенных квадратов. Нельзя закрашивать квадрат теми цветами, которыми закрашен один из прилегающих к нему квадратов (в том числе и по диагонали) или прилегающая к квадрату сторона. Выигрывает игрок, делающий последний ход.
Далее приведу несколько задач данной тематики, которые обязаны своим рождением, так долго не решаемой проблемы четырех красок.
Задача 1. Раскрасьте эту карту из 100 стран в четыре цвета так, чтобы соседние страны были окрашены в разные цвета. Решение приведено на рисунке 4.
Задача 2. Рассмотрим все возможные карты на плоскости, образованные прямыми. Примером такой карты может служить обычная шахматная доска. Достаточно ли двух красок для раскрашивания всех таких карт?
Проведя еще одну кривую, пересекающую всю карту от одного ее края до другого, мы должны, как и прежде, изменить все цвета по одну сторону от кривой на противоположные. Если вновь проведенная кривая замкнута, то изменить нужно окраску всех областей, попавших внутрь кривой, или, если угодно, всех областей, оказавшихся снаружи. Замкнутые кривые могут иметь и точки самопересечения, но в этом случае перекрашивание областей более сложно.
Задача 3. На плоскости нарисовано n окружностей. В каждой окружности проведено по хорде так, что хорды двух окружностей имеют между собой самое большое одну общую точку (рис.7.1). Докажите, что получившуюся карту на рисунке слева всегда можно раскрасить тремя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Доказательство. Идею доказательства проведем для трёх окружностей с хордами, хотя все рассуждения можно обобщить на случай, когда на плоскости нарисовано n окружностей с хордами. Состоит она в следующем:
первая, малая окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис.7.2);
вторая, средняя окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис. 7.3);
третья, большая окружность и её хорда разбивает плоскость на три части. Во всех областях первой части поставим по 0, во всех областях второй части поставим 1, во всех областях третьей части поставим 2 (рис. 7.4).
При этом каждой области будет соответствовать три числа, найдем их сумму (рис. 7.5), и числа каждой области заменим остатком от деления его на 3 (рис.7. 6).
Области, у которых этот остаток равен 0, закрасим синей краской;
области, у которых этот остаток равен 1, закрасим желтой краской;
области, у которых этот остаток равен 2, закрасим красной краской.
Полученная таким образом раскраска (рис. 7.7) удовлетворяет условия задачи.
Читайте также: