Войти
Пример четырехцветной карты 
Четырехцветная карта состояний США (без учета озер). В математике, теорема о четырех цветах или теорема о четырехцветных картах гласит, что при любом разделение плоскости на смежные области, в результате чего получается фигура, называемая картой, для окраски областей карты требуется не более четырех цветов, чтобы никакие две соседние области не имели одинаковый цвет. Смежный означает, что две области имеют общий сегмент граничной кривой, а не просто угол, где встречаются три или более областей. Это была первая основная теорема, доказанная с помощью компьютера. Первоначально это доказательство не было принято всеми математиками, потому что компьютерное доказательство было неосуществимо для человека, чтобы проверить его вручную. С тех пор доказательство получило широкое признание, хотя некоторые сомневающиеся остаются.
Теорема о четырех цветах была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном после множества ложных доказательств. и контрпримеры (в отличие от теоремы о пяти цветах, доказанной в 1800-х годах, которая гласит, что пяти цветов достаточно, чтобы раскрасить карту). Чтобы развеять все оставшиеся сомнения относительно доказательства Аппеля – Хакена, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее те же идеи и все еще опирающееся на компьютеры. Кроме того, в 2005 году теорема была доказана Жоржем Гонтье с помощью универсального программного обеспечения для доказательства теорем.
На графике -теоретических терминов, теорема утверждает, что для loopless планарного графа 
Интуитивное утверждение теоремы о четырех цветах - «данный любое разделение плоскости на смежные области, области можно раскрасить, используя не более четырех цветов, так что никакие два дополнительных области acent имеют один и тот же цвет "- чтобы быть правильным, необходимо правильно интерпретировать.
Во-первых, регионы являются смежными, если они имеют общий сегмент границы; две области, имеющие только изолированные граничные точки, не считаются смежными. Во-вторых, не допускаются причудливые области, например, с конечной площадью, но бесконечно длинным периметром; карты с такими регионами могут потребовать более четырех цветов. (На всякий случай мы можем ограничиться областями, границы которых состоят из конечного числа отрезков прямых линий. Допускается, чтобы область полностью окружала одну или несколько других областей.) Обратите внимание, что понятие «смежная область» (технически: connected open подмножество плоскости) не то же самое, что «страна» на обычных картах, поскольку страны не обязательно должны быть смежными (например, Провинция Кабинда как часть Анголы, Нахчыван в составе Азербайджана, Калининград в составе России и Аляска в составе из США не являются смежными). Если мы требовали, чтобы вся территория страны была одного цвета, то четырех цветов не всегда достаточно. Например, рассмотрим упрощенную карту:
На этой карте два региона, помеченные A, принадлежат одной стране. Если бы мы хотели, чтобы эти области получали один и тот же цвет, тогда потребовалось бы пять цветов, поскольку две области A вместе соседствуют с четырьмя другими областями, каждая из которых смежна со всеми остальными. Подобное построение также применимо, если для всех водоемов используется один цвет, как это обычно бывает на реальных картах. Для карт, на которых несколько стран могут иметь несколько отключенных регионов, может потребоваться шесть или более цветов.
Карта с четырьмя областями и соответствующий плоский граф с четырьмя вершинами. Более простая формулировка теоремы использует теорию графов. Набор регионов карты может быть представлен более абстрактно как неориентированный граф, который имеет вершину для каждой области и край для каждой пары регионов, которые разделяют граничный сегмент. Этот граф плоский : его можно нарисовать на плоскости без пересечений, поместив каждую вершину в произвольно выбранное место в пределах области, которой она соответствует, и нарисовав ребра в виде кривых без пересечений, ведущих из одного. вершина области через общий сегмент границы до вершины соседней области. И наоборот, любой планарный граф может быть сформирован из карты таким образом. В теоретико-графической терминологии теорема о четырех цветах утверждает, что вершины каждого плоского графа можно раскрасить не более чем в четыре цвета, так что никакие две соседние вершины не будут иметь одинаковый цвет, или для краткости:
Письмо Де Моргана Гамильтону, 23 октября 1852 г. Насколько известно, гипотеза была впервые было предложено 23 октября 1852 года, когда Фрэнсис Гатри, пытаясь раскрасить карту графств Англии, заметил, что нужны только четыре разных цвета. В то время брат Гатри, Фредерик, был учеником Августа Де Моргана (бывшего советника Фрэнсиса) в Университетском колледже Лондона. Фрэнсис спросил об этом у Фредерика, который затем отнес его Де Моргану (Фрэнсис Гатри получил высшее образование в 1852 году и позже стал профессором математики в Южной Африке). Согласно Де Моргану:
«Мой ученик [Гатри] попросил меня сегодня назвать ему причину факта, о котором я не знал, был фактом - и пока не делаю этого. Он говорит, что если фигура будет какой-либо как разделены и по-разному окрашены отсеки, чтобы фигуры с любой частью общей граничной линии были по-разному окрашены - может потребоваться четыре цвета, но не более - вот его случай, когда требуются четыре цвета. Запрос не может быть необходимостью для пяти или более быть изобретенным… »(Wilson 2014, стр. 18)
« FG », возможно, один из двух Гатри, опубликовал вопрос в The Athenaeum в 1854 году, и Де Морган снова поставил вопрос в том же журнале в 1860 году. Другая ранее опубликованная ссылка Артура Кэли (1879), в свою очередь, приписывает гипотезу Де Моргану.
Было несколько ранних неудачных попыток доказательства теоремы. Де Морган полагал, что это следует из простого факта о четырех регионах, хотя он не верил, что этот факт можно вывести из более элементарных фактов.
Возникает это следующим образом. Нам никогда не понадобится четыре цвета в районе, если нет четырех округов, каждая из которых имеет общие границы с каждым из трех других. Такое не может произойти с четырьмя областями, если одна или несколько из них не будут охвачены остальными; и цвет, используемый для округа, находящегося в закрытом округе, таким образом, может продолжаться. Мы полностью уверены, что этот принцип, согласно которому четыре области не могут иметь общей границы со всеми остальными тремя, не может быть продемонстрирован на чем-либо более очевидном и элементарном; это должно стоять как постулат.
Одно предполагаемое доказательство было дано Альфредом Кемпе в 1879 году и получило широкое признание; другое было дано Питером Гатри Тейтом в 1880 году. Только в 1890 году доказательство Кемпе было показано неверным Перси Хивудом, а в 1891 году доказательство Тейта было признано неверным Юлиус Петерсен - каждое ложное доказательство не подвергалось сомнению в течение 11 лет.
В 1890 году, помимо выявления изъяна в доказательстве Кемпе, Хивуд доказал теорему о пяти цветах и обобщил четыре Гипотеза о цвете поверхностей произвольного рода.
Тейт в 1880 году показал, что теорема о четырех цветах эквивалентна утверждению, что определенный тип графа (в современной терминологии называется snark ) должны быть не планарными.
В 1943 году Хьюго Хадвигер сформулировал гипотезу Хадвигера, далеко идущее обобщение проблемы четырех цветов, которая до сих пор остается нерешенной.
В течение 1960-х и 1970-х годов немецкий математик Генрих Хееш разработал методы использования компьютеров для поиска доказательства. Примечательно, что он был первым, кто использовал разрядку для доказательства теоремы, которая оказалась важной в части неизбежности последующего доказательства Аппеля-Хакена. Он также расширил концепцию сводимости и вместе с Кеном Дарре разработал для нее компьютерный тест. К сожалению, в этот критический момент он не смог выделить необходимое суперкомпьютерное время для продолжения своей работы.
Другие подхватили его методы, в том числе его компьютерный подход. В то время как другие команды математиков спешили завершить доказательства, Кеннет Аппель и Вольфганг Хакен из Университета Иллинойса объявили 21 июня 1976 года, что у них есть доказал теорему. В некоторой алгоритмической работе им помогал.
Если бы гипотеза о четырех цветах была ложной, была бы по крайней мере одна карта с наименьшим возможным числом регионов, для которой требуется пять цветов. Доказательство показало, что такой минимальный контрпример не может существовать, благодаря использованию двух технических концепций:
Используя математические правила и процедуры, основанные на свойствах сводимых конфигураций, Аппель и Хакен обнаружили неизбежный набор приводимые конфигурации, тем самым доказывая, что минимальный контрпример к четырехцветной гипотезе не может существовать. Их доказательство сократило бесконечное количество возможных отображений до 1834 сводимых конфигураций (позже уменьшилось до 1482), которые нужно было проверять одну за другой на компьютере, и это занимало более тысячи часов. Эта приводимая часть работы была независимо перепроверена с помощью различных программ и компьютеров. Однако неотъемлемая часть доказательства была проверена на более чем 400 страницах микрофиш, которые пришлось проверять вручную с помощью дочери Хакена Доротеи Блоштейн (Appel Хакен 1989).
Объявление Аппеля и Хакена широко освещалось в средствах массовой информации по всему миру, а математический факультет в Университете Иллинойса использовал почтовый штемпель с надписью «Четырех цветов достаточно». В то же время необычный характер доказательства - это была первая крупная теорема, доказанная с обширной компьютерной помощью, - и сложность проверяемой человеком части вызвали серьезные споры (Wilson 2014).
В начале 1980-х годов распространились слухи о недостатке доказательства Аппеля – Хакена. Ульрих Шмидт из RWTH Aachen изучил доказательство Аппеля и Хакена своей магистерской диссертации, опубликованной в 1981 году (Wilson 2014, 225). Он проверил около 40% части неизбежности и обнаружил значительную ошибку в процедуре разгрузки (Appel Haken 1989). В 1986 году редактор Mathematical Intelligencer попросил Аппеля и Хакена написать статью, направленную на слухи о недостатках в их доказательстве. Они ответили, что слухи возникли из-за «неправильного толкования результатов [Шмидта]», и предоставили подробную статью (Wilson 2014, 225–226). Их magnum opus «Каждая планарная карта может раскрашиваться в четыре цвета», книга, требующая полного и подробного доказательства (с приложением микрофишей более 400 страниц), появилась в 1989 году; он объяснил и исправил ошибку, обнаруженную Шмидтом, а также несколько других ошибок, обнаруженных другими (Appel Haken 1989).
С момента доказательства теоремы были найдены эффективные алгоритмы для 4-цветных карт, требующих всего O (n) времени, где n - количество вершин. В 1996 году Нил Робертсон, Дэниел П. Сандерс, Пол Сеймур и Робин Томас создали квадратичное время, улучшая алгоритм четвертого времени, основанный на доказательстве Аппеля и Хакена. Это новое доказательство похоже на доказательство Аппеля и Хакена, но более эффективно, поскольку оно снижает сложность проблемы и требует проверки только 633 приводимых конфигураций. Как неизбежность, так и сводимость этого нового доказательства должны выполняться на компьютере, и их невозможно проверить вручную. В 2001 году те же авторы объявили альтернативное доказательство, доказав гипотезу снарка. Однако это доказательство остается неопубликованным.
В 2005 году и Жорж Гонтье формализовал доказательство теоремы в помощнике по доказательству Coq. Это устранило необходимость доверять различным компьютерным программам, используемым для проверки конкретных случаев; необходимо доверять только ядру Coq.
Следующее обсуждение представляет собой краткое изложение, основанное на введении в «Каждую планарную карту можно раскрашивать в четыре цвета» (Appel Haken 1989). Несмотря на то, что первоначальное доказательство теоремы о четырех цветах Кемпе было ошибочным, оно предоставило некоторые из основных инструментов, которые позже использовались для ее доказательства. Объяснение здесь переформулировано в терминах современной формулировки теории графов выше.
Аргумент Кемпе состоит в следующем. Во-первых, если плоские области, разделенные графом, не триангулированы, т.е. не имеют ровно трех ребер на своих границах, мы можем добавить ребра, не вводя новых вершин, чтобы сделать каждую область треугольной, включая неограниченную внешнюю область. Если этот триангулированный граф можно раскрасить в четыре цвета или меньше, то же самое можно сделать и с исходным графом, поскольку такая же раскраска действительна при удалении ребер. Таким образом, достаточно доказать теорему о четырех цветах для триангулированных графов, чтобы доказать ее для всех плоских графов, и без ограничения общности мы предполагаем, что граф триангулирован.
Предположим, что v, e и f - количество вершин, ребер и областей (граней). Поскольку каждая область имеет треугольную форму и каждое ребро является общим для двух областей, мы имеем, что 2e = 3f. Это вместе с формулой Эйлера, v - e + f = 2, можно использовать, чтобы показать, что 6v - 2e = 12. Теперь степень вершины - это количество ребер, примыкающих к ней. Если v n - количество вершин степени n, а D - максимальная степень любой вершины,
Но поскольку 12>0 и 6 - i ≤ 0 для всех i ≥ 6, это показывает, что существует по крайней мере одна вершина степени 5 или меньше.
Если существует граф, требующий 5 цветов, то существует минимальный такой граф, в котором удаление любой вершины делает его четырехцветным. Назовите этот граф G. Тогда G не может иметь вершину степени 3 или меньше, потому что, если d (v) ≤ 3, мы можем удалить v из G, раскрасить меньший граф в четыре цвета, затем добавить обратно v и расширить четырехцветную раскраску. к нему, выбрав цвет, отличный от его соседей.
Граф, содержащий цепь Кемпе, состоящую из чередующихся синих и красных вершин. Кемпе также правильно показал, что G не может иметь вершины степени 4. Как и раньше, мы удаляем вершину v и раскрашиваем оставшиеся вершины в четыре цвета. Если все четыре соседа v имеют разные цвета, скажем, красный, зеленый, синий и желтый в порядке по часовой стрелке, мы ищем чередующийся путь вершин красного и синего цвета, соединяющий красные и синие соседей. Такой путь называется цепочкой Кемпе. Может существовать цепочка Кемпе, соединяющая красных и синих соседей, и может быть цепь Кемпе, соединяющая зеленых и желтых соседей, но не то и другое, поскольку эти два пути обязательно пересекаются, а вершина, где они пересекаются, не может быть окрашена. Предположим, что это красные и синие соседи, которые не связаны друг с другом. Изучите все вершины, прикрепленные к красному соседу чередующимися красно-синими путями, а затем поменяйте местами красный и синий цвета на всех этих вершинах. В результате все еще остается допустимая четырехцветная раскраска, и теперь можно добавить v и покрасить в красный цвет.
Остается только случай, когда G имеет вершину степени 5; но аргумент Кемпе был ошибочным в данном случае. Хивуд заметил ошибку Кемпе и также заметил, что если кто-то удовлетворился доказательством того, что необходимы только пять цветов, можно было бы пройти через приведенный выше аргумент (изменив только то, что минимальный контрпример требует 6 цветов) и использовать цепи Кемпе в ситуации степени 5, чтобы доказать, что Теорема о пяти цветах.
В любом случае, чтобы иметь дело с этим случаем вершины 5 степени, требуется более сложное понятие, чем удаление вершины. Скорее, форма аргументации обобщается на рассмотрение конфигураций, которые являются связными подграфами G со степенью каждой указанной вершины (в G). Например, случай, описанный в ситуации вершины степени 4, представляет собой конфигурацию, состоящую из одной вершины, помеченной как имеющая степень 4 в G. Как и выше, достаточно продемонстрировать, что если конфигурация удалена, а оставшийся граф четырехцветный, то раскраска может быть изменена таким образом, что при повторном добавлении конфигурации четырехкратная раскраска может быть распространена и на нее. Конфигурация, для которой это возможно, называется сокращаемой конфигурацией. Если хотя бы одна из наборов конфигураций должна произойти где-то в G, этот набор называется неизбежным. Приведенное выше рассуждение началось с предоставления неизбежного набора из пяти конфигураций (одна вершина со степенью 1, единственная вершина со степенью 2,..., единственная вершина со степенью 5), а затем продолжилось, чтобы показать, что первые 4 приводимы; показать неизбежный набор конфигураций, где каждая конфигурация в наборе приводима, доказывает теорему.
Поскольку G треугольная, степень каждой вершины в конфигурации известна, и известны все ребра, внутренние по отношению к конфигурации, количество вершин в G, смежных с данной конфигурацией, фиксировано, и они соединяются в цикле. Эти вершины образуют кольцо конфигурации; конфигурация с k вершинами в своем кольце является конфигурацией k-кольца, а конфигурация вместе со своим кольцом называется кольцевой конфигурацией. Как и в описанных выше простых случаях, можно перечислить все различные четырехцветные раскраски кольца; любая окраска, которая может быть расширена без изменения до окраски конфигурации, называется изначально хорошей. Например, приведенная выше конфигурация с одной вершиной с 3 или менее соседями изначально была хорошей. В общем, окружающий граф должен систематически перекрашиваться, чтобы сделать раскраску кольца хорошей, как это было сделано в случае выше, когда было 4 соседа; для общей конфигурации с большим кольцом это требует более сложных методов. Из-за большого количества различных четырехцветных цветов кольца это первый шаг, требующий помощи компьютера.
Наконец, остается идентифицировать неизбежный набор конфигураций, поддающихся сокращению с помощью этой процедуры. Основным методом, используемым для обнаружения такого набора, является метод разрядки. Интуитивная идея, лежащая в основе разряда, состоит в том, чтобы рассматривать планарный граф как электрическую сеть. Первоначально положительный и отрицательный «электрический заряд» распределяется между вершинами, так что общая сумма оказывается положительной.
Вспомните формулу выше:
Каждой вершине назначается начальный заряд 6 градусов (v). Затем «перетекают» заряд, систематически перераспределяя заряд от вершины к соседним вершинам в соответствии с набором правил, процедурой разрядки. Поскольку заряд сохраняется, некоторые вершины все еще имеют положительный заряд. Правила ограничивают возможности для конфигураций положительно заряженных вершин, поэтому перечисление всех таких возможных конфигураций дает неизбежный набор.
Пока какой-то элемент неизбежного набора не восстанавливается, процедура выгрузки модифицируется для его устранения (при введении других конфигураций). Окончательная процедура разгрузки Аппеля и Хакена была чрезвычайно сложной и вместе с описанием неизбежного набора конфигураций занимала 400-страничный том, но созданные им конфигурации можно было проверить механически на возможность сокращения. Проверка тома, описывающего неизбежный набор конфигураций, проводилась путем экспертной оценки в течение нескольких лет.
Техническая деталь, не обсуждаемая здесь, но необходимая для завершения доказательства, - это погружение сводимость.
Теорема о четырех цветах была печально известна тем, что за свою долгую историю привлекла большое количество ложных доказательств и опровержений. Сначала The New York Times отказалась из соображений политики сообщать о доказательстве Аппеля-Хакена, опасаясь, что доказательство окажется ложным, как и предыдущие (Wilson 2014). Некоторые предполагаемые доказательства, такие как упомянутые выше Кемпе и Тейта, находились под пристальным вниманием общественности более десяти лет, прежде чем были опровергнуты. Но многие другие, написанные любителями, вообще никогда не публиковались.
Карта (слева) раскрашена пятью цветами, но, например, четыре из десяти областей можно изменить, чтобы получить раскраску только четырьмя цветами (справа). Как правило, простейшие, хотя и неверные, контрпримеры попытаться создать один регион, который касается всех остальных регионов. Это заставляет остальные области быть окрашенными только тремя цветами. Поскольку теорема о четырех цветах верна, это всегда возможно; однако, поскольку человек, рисующий карту, сосредоточен на одной большой области, он не замечает, что оставшиеся области на самом деле могут быть раскрашены тремя цветами.
Этот трюк можно обобщить: существует множество карт, на которых, если цвета некоторых регионов выбраны заранее, становится невозможным раскрасить остальные регионы, не превышая четырех цветов. Случайный проверяющий контрпример может не подумать об изменении цвета этих областей, так что контрпример будет выглядеть так, как будто он действителен.
Возможно, одним из эффектов, лежащих в основе этого распространенного заблуждения, является тот факт, что ограничение цвета не является транзитивным : только область должна быть окрашена иначе, чем области, которых она касается непосредственно, а не области, соприкасающиеся с областями, которых она касается. касается. Если бы это было ограничением, планарные графы потребовали бы сколь угодно большого количества цветов.
Другие ложные опровержения нарушают предположения теоремы, например, использование области, состоящей из нескольких несвязанных частей, или запрещение областей одного цвета касаться точки.
В то время как каждую планарную карту можно раскрасить в четыре цвета, NP-полная в сложности решить, будет ли произвольная планарная карта может быть раскрашена всего в три цвета.
Соединяя вместе одиночные стрелки и двойные стрелки вместе, мы получаем тор с семью взаимно соприкасающимися областями; поэтому необходимы семь цветов 
Эта конструкция показывает тор, разделенный максимум на семь областей, каждая из которых касается друг друга. Теорема о четырех цветах применима не только к конечным планарным графам, но и к бесконечные графы, которые можно нарисовать без пересечений на плоскости, и, в более общем смысле, до бесконечных графов (возможно, с несчетным числом вершин), для которых каждый конечный подграф является плоским. Чтобы доказать это, можно объединить доказательство теоремы для конечных плоских графов с теоремой Де Брейна – Эрдеша, утверждающей, что если каждый конечный подграф бесконечного графа является k-раскрашиваемым, то весь граф является также k-colorable Нэш-Уильямс (1967). Это также можно рассматривать как непосредственное следствие теоремы Курта Гёделя о компактности для логики первого порядка, просто выражая раскрашиваемость бесконечного графа с помощью набор логических формул.
Можно также рассматривать проблему раскраски на поверхностях, отличных от плоскости (Weisstein). Проблема на сфере или цилиндре эквивалентна проблеме на плоскости. Для замкнутых (ориентируемых или неориентируемых) поверхностей положительного рода максимальное количество необходимых цветов p зависит от эйлеровой характеристики χ поверхности в соответствии с формулой
где крайние скобки обозначают функцию пола .
. В качестве альтернативы, для ориентируемой поверхности формула может быть задана в терминах рода поверхности, g:
(Weisstein).
Интерактивная модель многогранника Силасси с каждым лицом разного цвета. В изображении SVG переместите мышь, чтобы повернуть его. Эта формула, гипотеза Хивуда, была выдвинута П. J. Heawood в 1890 году и доказано Герхардом Рингелем и J. У. Т. Янгс в 1968 году. Единственным исключением из формулы является бутылка Клейна, которая имеет эйлерову характеристику 0 (следовательно, формула дает p = 7) и требует только 6 цветов, как показано П. Франклин в 1934 году (Вайсштейн).
Например, тор имеет эйлерову характеристику χ = 0 (и род g = 1) и, следовательно, p = 7, поэтому для раскраски любой карты на карте требуется не более 7 цветов. тор. Эта верхняя граница числа 7 точна: некоторые тороидальные многогранники, такие как многогранник Силасси, требуют семи цветов.
Титце подразделение ленты Мебиуса на шесть смежных областей, требующих шести цветов. Вершины и ребра подразделения образуют вложение графа Титце на полосу. A Лента Мёбиуса требует шести цветов (Tietze 1910), как и 1 -планарные графы (графы, нарисованные не более чем с одним простым пересечением на ребро) (Бородин 1984). Если и вершины, и грани плоского графа раскрашены таким образом, что никакие две соседние вершины, грани или пара вершина-грань не имеют одинакового цвета, то снова требуется не более шести цветов (Бородин 1984).
Нет очевидного распространения результата окрашивания на трехмерные сплошные области. Используя набор из n гибких стержней, можно сделать так, чтобы каждый стержень касался другого стержня. Тогда для набора потребуется n цветов или n + 1, если учесть пустое пространство, которое также касается каждого стержня. Число n может быть любым целым числом, сколь угодно большим. Такие примеры были известны Фредерику Гатри в 1880 году (Wilson 2014). Даже для параллельных оси кубоидов (считающихся смежными, когда два кубоида имеют общую двухмерную граничную область) может потребоваться неограниченное количество цветов (Reed Allwright 2008 ; Магнант и Мартин (2011)).
Дрор Бар-Натан дал утверждение относительно алгебр Ли и инвариантов Васильева, которое эквивалентно теореме о четырех цветах.
Несмотря на мотивацию раскрашивания политических карт стран, теорема не представляет особого интереса для картографов. Согласно статье историка математики Кеннета Мэя, «Карты, использующие только четыре цвета, встречаются редко, а те, которые обычно требуют только трех цветов. В книгах по картографии и истории картографирования четырехцветные карты не упоминаются. свойство "(Wilson 2014, 2). Теорема также не гарантирует стандартного картографического требования, чтобы несмежные регионы одной страны (такие как эксклав Калининград и остальная часть России) были окрашены одинаково.
Портал математики  | На Викискладе есть материалы, связанные с Теорема четырех цветов. |
