Теорема о четырех цветах

Пример четырехцветной карты

Четырехцветная карта штатов США (без учета озер и океанов)

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

Теорема представляет собой более сильную версию теоремы о пяти цветах , которую можно показать, используя значительно более простое рассуждение. Хотя более слабая теорема о пяти цветах была доказана уже в 1800-х годах, теорема о четырех цветах сохранялась до 1976 года, когда ее доказали Кеннет Аппель и Вольфганг Хакен . Это произошло после множества ложных доказательств и ошибочных контрпримеров в предыдущие десятилетия.

Доказательство Аппеля-Хакена основано на анализе очень большого числа приводимых конфигураций. Это было улучшено в 1997 году Робертсоном, Сандерсом, Сеймуром и Томасом, которым удалось уменьшить количество таких конфигураций до 633 - все еще чрезвычайно длинный анализ случая. В 2005 году теорема была проверена Жоржем Гонтье с помощью универсального программного обеспечения для доказательства теорем .

Точная формулировка теоремы

С точки зрения теории графов, теорема утверждает, что для без петель плоского графа $G$, его хроматическое число равно $\chi (G)\leq 4$.

Интуитивное утверждение теоремы о четырех цветах – «при любом разделении плоскости на смежные области эти области можно раскрасить не более чем в четыре цвета так, чтобы никакие две соседние области не имели одинаковый цвет» – необходимо правильно интерпретировать. .

Во-первых, регионы являются смежными, если они имеют общий сегмент границы; два региона, которые имеют только изолированные граничные точки, не считаются соседними. (В противном случае карта в форме круговой диаграммы создала бы сколь угодно большое количество регионов, «смежных» друг с другом в общем углу, и в результате потребовало бы сколь угодно большого количества цветов.) Во-вторых, причудливые регионы, такие как объекты с конечной площадью, но бесконечно длинным периметром не допускаются; карты с такими регионами могут потребовать более четырех цветов. (На всякий случай мы можем ограничиться регионами, границы которых состоят из конечного числа отрезков прямых линий. Допускается, что регион имеет анклавы , то есть он полностью окружает один или несколько других регионов.) Обратите внимание, что понятие «смежный регион» (технически: связанное открытое подмножество плоскости) — это не то же самое, что «страна» на обычных картах, поскольку страны не обязательно должны быть смежными (у них могут быть эксклавы , например, провинция Кабинда как часть Анголы , Нахчыван как часть Азербайджана Калининград , в составе России, Франция с ее заморскими территориями и Аляска в составе США не являются смежными). Если мы требовали, чтобы вся территория страны была окрашена в один и тот же цвет, то четырех цветов не всегда достаточно. Например, рассмотрим упрощенную карту:

На этой карте два региона, отмеченные буквой А, принадлежат одной стране. Если бы мы хотели, чтобы эти регионы получили один и тот же цвет, тогда потребовалось бы пять цветов, поскольку два региона А вместе соседствуют с четырьмя другими регионами, каждый из которых соседствует со всеми остальными. Заставить две отдельные области иметь один и тот же цвет можно смоделировать, добавив «манипулятор», соединяющий их вне плоскости.

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

Карта с четырьмя регионами и соответствующий плоский граф с четырьмя вершинами.

Более простая формулировка теоремы использует теорию графов . Набор регионов карты можно представить более абстрактно как неориентированный граф , имеющий вершину для каждого региона и ребро для каждой пары регионов, имеющих общий граничный сегмент. Этот граф является плоским : его можно нарисовать на плоскости без пересечений, поместив каждую вершину в произвольно выбранное место внутри области, которой она соответствует, и нарисовав ребра в виде кривых без пересечений, ведущих из вершины одной области через общую область. граничный сегмент к вершине соседней области. И наоборот, любой планарный граф может быть сформирован из карты таким способом. В терминологии теории графов теорема о четырех цветах утверждает, что вершины каждого планарного графа можно раскрасить не более чем в четыре цвета, так что никакие две соседние вершины не будут окрашены в один и тот же цвет, или, короче: каждый планарный граф раскрашивается в четыре цвета .

История

доказательства

Письмо Де Моргана Уильяму Роуэну Гамильтону , 23 октября 1852 г.

Насколько известно, гипотеза была впервые выдвинута 23 октября 1852 года. когда Фрэнсис Гатри , пытаясь раскрасить карту графств Англии, заметил, что нужно всего четыре разных цвета. В то время брат Гатри, Фредерик , был студентом Огастеса Де Моргана (бывшего советника Фрэнсиса) в Университетском колледже Лондона . Фрэнсис поинтересовался этим у Фредерика, который затем отнес его Де Моргану (Фрэнсис Гатри получил высшее образование позже, в 1852 году, а позже стал профессором математики в Южной Африке). По словам Де Моргана:

Мой студент [Гатри] попросил меня сегодня объяснить ему причину факта, о факте которого я не знал — и еще не знаю. Он говорит, что если фигура каким-либо образом разделена и ее отсеки окрашены по-разному, так что фигуры с любой частью общей ограничительной линии четыре цвета окрашены по-разному (может потребоваться четыре цвета, но не более), то следующий его случай, в котором требуются . Запрос не может быть необходимостью для пяти и более человек…

«ФГ», возможно, один из двух Гатри, опубликовал этот вопрос в «Атенеуме» в 1854 году. и Де Морган снова поставил этот вопрос в том же журнале в 1860 году. Другая ранняя опубликованная ссылка Артура Кэли ( 1879 г. ), в свою очередь, приписывает эту гипотезу Де Моргану.

Было несколько первых неудачных попыток доказать теорему. Де Морган полагал, что это следует из простого факта о четырех регионах, хотя он не верил, что этот факт можно вывести из более элементарных фактов.

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

Одно предложенное доказательство было дано Альфредом Кемпе в 1879 году и получило широкое признание; другое было дано Питером Гатри Тейтом в 1880 году. Лишь в 1890 году Перси Хивуд показал неверность доказательства Тейта показал неверность доказательства Кемпе, а в 1891 году Юлиус Петерсен - каждое ложное доказательство оставалось неоспоримым в течение 11 лет.

В 1890 году, помимо выявления ошибки в доказательстве Кемпе, Хивуд доказал теорему о пяти цветах и ​​обобщил гипотезу о четырех цветах на поверхности произвольного рода.

Тейт в 1880 году показал, что теорема о четырех цветах эквивалентна утверждению, что определенный тип графа (называемый снарком в современной терминологии ) должен быть непланарным .

В 1943 году Хьюго Хадвигер сформулировал гипотезу Хадвигера . далеко идущее обобщение проблемы четырех цветов, которое до сих пор остается нерешенным.

Доказательство с помощью компьютера

В 1960-х и 1970-х годах немецкий математик Генрих Хиш разработал методы использования компьютеров для поиска доказательств. Примечательно, что он был первым, кто использовал разрядку для доказательства теоремы, что оказалось важным в части неизбежности последующего доказательства Аппеля-Хакена. Он также расширил концепцию сводимости и вместе с Кеном Дюрре разработал для нее компьютерный тест. К сожалению, в этот критический момент он не смог получить необходимое время суперкомпьютера для продолжения своей работы.

Другие подхватили его методы, в том числе компьютерный подход. Пока другие группы математиков спешили завершить доказательства, Кеннет Аппель и Вольфганг Хакен из Университета Иллинойса объявили 21 июня 1976 года: что они доказали теорему. В некоторой алгоритмической работе им помогал Джон А. Кох .

Если бы гипотеза о четырех цветах была ложной, существовала бы хотя бы одна карта с наименьшим возможным количеством регионов, для которой требуется пять цветов. Доказательство показало, что такой минимальный контрпример не может существовать благодаря использованию двух технических концепций:

1. — Неизбежный набор это набор конфигураций, такой, что каждая карта, удовлетворяющая некоторым необходимым условиям для того, чтобы быть минимальной триангуляцией , не раскрашиваемой в 4 цвета (например, имеющая минимальную степень 5), должна иметь хотя бы одну конфигурацию из этого набора.
2. — Приводимая конфигурация это такое расположение стран, которое не может возникнуть в минимальном контрпримере. Если карта содержит сокращаемую конфигурацию, ее можно уменьшить до карты меньшего размера. У этой карты меньшего размера есть условие: если ее можно раскрасить в четыре цвета, это также относится и к исходной карте. Это означает, что если исходную карту нельзя раскрасить в четыре цвета, то и меньшая карта тоже не может быть раскрашена, и поэтому исходная карта не является минимальной.

Используя математические правила и процедуры, основанные на свойствах приводимых конфигураций, Аппель и Хакен нашли неизбежный набор приводимых конфигураций, доказав тем самым, что минимальный контрпример к гипотезе четырех цветов не может существовать. Их доказательство сократило бесконечность возможных карт до 1834 приводимых конфигураций (позже сократилось до 1482), которые приходилось проверять одну за другой на компьютере, что занимало более тысячи часов. Эта часть работы по сводимости была независимо перепроверена с помощью различных программ и компьютеров. Однако часть доказательства неизбежности была проверена на более чем 400 страницах микрофиш , которые пришлось проверять вручную с помощью дочери Хакена Доротеи Блостейн .

Заявление Аппеля и Хакена широко освещалось средствами массовой информации по всему миру. а математический факультет Университета Иллинойса использовал почтовый штемпель с надписью «Достаточно четырех цветов». В то же время необычный характер доказательства (это была первая крупная теорема, доказанная с помощью обширной компьютерной помощи) и сложность той части, которую можно проверить человеком, вызвали серьезные споры.

В начале 1980-х годов распространились слухи об ошибке в доказательстве Аппеля-Хакена. Ульрих Шмидт из RWTH Ахена изучил доказательство Аппеля и Хакена для своей магистерской диссертации, опубликованной в 1981 году. Он проверил около 40% части неизбежности и обнаружил значительную ошибку в процедуре выписки ( Appel & Haken 1989 ). попросил Аппеля и Хакена В 1986 году редактор журнала Mathematical Intelligencer написать статью, посвященную слухам об ошибках в их доказательстве. Они ответили, что слухи возникли из-за «неверной интерпретации результатов [Шмидта]» и предоставили подробную статью. Их выдающийся опус « Каждая плоская карта раскрашивается в четыре цвета» , книга, претендующая на полное и подробное доказательство (с приложением на микрофишах объемом более 400 страниц), появилась в 1989 году; он объяснил и исправил ошибку, обнаруженную Шмидтом, а также несколько других ошибок, обнаруженных другими.

Упрощение и проверка

После доказательства теоремы новый подход привел как к более короткому доказательству, так и к более эффективному алгоритму для карт с 4-мя раскрасками. В 1996 году Нил Робертсон , Дэниел П. Сандерс , Пол Сеймур и Робин Томас создали алгоритм квадратичного времени (требующий всего O ( n ² ) время, где n — количество вершин), улучшенный алгоритм четвертого времени, основанный на доказательстве Аппеля и Хакена. Новое доказательство, основанное на тех же идеях, похоже на доказательство Аппеля и Хакена, но более эффективно, поскольку снижает сложность задачи и требует проверки только 633 приводимых конфигураций. И части этого нового доказательства, касающиеся неизбежности и сводимости, должны выполняться компьютером, и их непрактично проверять вручную. В 2001 году те же авторы представили альтернативное доказательство, доказав гипотезу снарка . Однако это доказательство осталось неопубликованным.

В 2005 году Бенджамин Вернер и Жорж Гонтье формализовали доказательство теоремы с помощью помощника по доказательству Coq . Это устранило необходимость доверять различным компьютерным программам, используемым для проверки конкретных случаев; необходимо только доверять ядру Coq.

доказательства

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

Аргументация Кемпе заключается в следующем. Во-первых, если плоские области, разделенные графом, не являются триангулированными , т. е. не имеют ровно трех ребер в своих границах, мы можем добавлять ребра без введения новых вершин, чтобы сделать каждую область треугольной, включая неограниченную внешнюю область. Если этот триангулированный граф можно раскрасить, используя четыре или меньше цветов, то же самое относится и к исходному графу, поскольку та же раскраска действительна, если удалить ребра. Поэтому достаточно доказать теорему о четырех цветах для триангулированных графов, чтобы доказать ее для всех плоских графов, и без ограничения общности мы предполагаем, что граф триангулирован.

Предположим, v , e и f — количество вершин, ребер и областей (граней). Поскольку каждая область имеет треугольную форму и каждое ребро является общим для двух областей, мы имеем 2 e = 3 f . Это вместе с Эйлера формулой v − e + f = 2 можно использовать, чтобы показать, что 6 v − 2 e = 12. Теперь степень вершины — это количество примыкающих к ней ребер. Если v _n — количество вершин степени n , а D — максимальная степень любой вершины,

$6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$

Но поскольку 12 > 0 и 6 − i ≤ 0 для всех i ≥ 6, это показывает, что существует хотя бы одна вершина степени 5 или меньше.

Если существует граф, требующий 5 цветов, то существует минимальный такой граф, удаление любой вершины которого делает его раскрашиваемым в четыре цвета. Назовем этот G. граф Тогда G не может иметь вершину степени 3 или меньше, потому что, если d ( v ) ≤ 3, мы можем удалить v из G , раскрасить меньший граф в четыре цвета, затем добавить обратно v и расширить к нему четырехцветную раскраску, выбрав цвет отличается от соседей.

Граф, содержащий цепочку Кемпе, состоящую из чередующихся синих и красных вершин.

Кемпе также правильно показал, что в G не может быть вершины степени 4. Как и прежде, мы удалим вершину v и раскрасим оставшиеся вершины в четыре цвета. Если все четыре соседа вершины v имеют разные цвета, скажем, красный, зеленый, синий и желтый (по часовой стрелке), мы ищем чередующийся путь вершин, окрашенных в красный и синий цвета, соединяющий красных и синих соседей. Такой путь называется цепью Кемпе . Может существовать цепочка Кемпе, соединяющая красных и синих соседей, и может существовать цепочка Кемпе, соединяющая зеленых и желтых соседей, но не обе, поскольку эти два пути обязательно пересекутся, а вершину, в которой они пересекаются, нельзя раскрасить. Предположим, что это красные и синие соседи, которые не связаны между собой цепочкой. Исследуйте все вершины, присоединенные к красному соседу чередующимися красно-синими путями, а затем поменяйте местами красный и синий цвета на всех этих вершинах. Результатом по-прежнему является правильная четырехцветная раскраска, и теперь можно добавить обратно и покрасить красный цвет.

Остается только случай, когда G имеет вершину степени 5; но аргумент Кемпе в этом случае был ошибочным. Хивуд заметил ошибку Кемпе, а также заметил, что если кто-то удовлетворится доказательством необходимости только пяти цветов, то можно будет пройти через приведенный выше аргумент (изменив только то, что минимальный контрпример требует 6 цветов) и использовать цепи Кемпе в ситуации пятой степени, чтобы доказать Теорема пяти цветов .

В любом случае, чтобы справиться с этим случаем вершины степени 5, требуется более сложное понятие, чем удаление вершины. Скорее, форма аргумента обобщается для рассмотрения конфигураций , которые соединяют подграфы G с указанной степенью каждой вершины (в G). Например, случай, описанный в ситуации с вершиной степени 4, представляет собой конфигурацию, состоящую из одной вершины, помеченной как имеющая степень 4 в G . Как и выше, достаточно продемонстрировать, что если конфигурация удалена и оставшийся граф раскрашен в четыре цвета, то раскраску можно изменить таким образом, что при повторном добавлении конфигурации на нее можно будет распространить четырехцветную раскраску как хорошо. Конфигурация, для которой это возможно, называется приводимой конфигурацией . Если хотя бы одна из множества конфигураций должна встречаться где-то в G, этот набор называется неизбежным . Приведенный выше аргумент начался с указания неизбежного набора из пяти конфигураций (одна вершина со степенью 1, одна вершина со степенью 2, ..., одна вершина со степенью 5), а затем продолжился показом того, что первые 4 конфигурации приводимы; продемонстрировать неизбежный набор конфигураций, в которых каждая конфигурация в наборе приводима, доказало бы теорему.

Поскольку G треугольный, степень каждой вершины в конфигурации известна, и все ребра, внутренние в конфигурации, известны, количество вершин в G , смежных с данной конфигурацией, фиксировано, и они соединяются в цикл. Эти вершины образуют кольцо конфигурации; Конфигурация с k вершинами в кольце является k -кольцевой конфигурацией, а конфигурация вместе со своим кольцом называется кольцевой конфигурацией . Как и в приведенных выше простых случаях, можно перечислить все различные четыре раскраски кольца; любая раскраска, которую можно без изменения расширить до раскраски конфигурации, называется изначально хорошей . Например, описанная выше конфигурация с одной вершиной и тремя или менее соседями изначально была хорошей. В общем, окружающий граф необходимо систематически перекрашивать, чтобы раскраска кольца стала хорошей, как это было сделано в приведенном выше случае, когда было 4 соседа; для общей конфигурации с кольцом большего размера требуются более сложные методы. Из-за большого количества различных четырех раскрасок кольца это основной шаг, требующий помощи компьютера.

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

Напомним формулу выше:

$\sum _{i=1}^{D}(6-i)v_{i}=12.$

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

Пока какой-либо член неизбежного множества не является сокращаемым, процедура выгрузки модифицируется для его устранения (с введением других конфигураций). Окончательная процедура выгрузки Аппеля и Хакена была чрезвычайно сложной и вместе с описанием полученного неизбежного набора конфигураций занимала 400-страничный том, но сгенерированные ею конфигурации можно было проверить механически на предмет их сокращения. Проверка тома, описывающего сам набор неизбежных конфигураций, проводилась путем экспертной оценки в течение нескольких лет.

Техническая деталь, не обсуждаемая здесь, но необходимая для завершения доказательства, — это по погружению сводимость .

Ложные опровержения

Теорема о четырех цветах печально известна тем, что за свою долгую историю привлекла большое количество ложных доказательств и опровержений. Поначалу The New York Times из политических соображений отказалась сообщать о доказательстве Аппеля-Хакена, опасаясь, что это доказательство окажется ложным, как и предыдущие. Некоторые предполагаемые доказательства, такие как упомянутые выше доказательства Кемпе и Тейта, находились под пристальным вниманием общественности более десяти лет, прежде чем были опровергнуты. Но многие другие, написанные любителями, вообще никогда не публиковались.

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

Как правило, самые простые, хотя и недействительные, контрпримеры пытаются создать один регион, который затрагивает все остальные регионы. Это заставляет оставшиеся регионы окрашиваться только тремя цветами. Поскольку теорема о четырех цветах верна, это всегда возможно; однако, поскольку человек, рисующий карту, сосредоточен на одном большом регионе, он не замечает, что остальные регионы на самом деле могут быть раскрашены тремя цветами.

Этот трюк можно обобщить: существует множество карт, на которых, если цвета некоторых регионов выбраны заранее, становится невозможным раскрасить остальные регионы, не превысив четыре цвета. Случайный проверяющий контрпример может и не подумать об изменении цвета этих областей, так что контрпример будет выглядеть действительным.

Возможно, одним из эффектов, лежащих в основе этого распространенного заблуждения, является тот факт, что ограничение цвета не является транзитивным : область должна быть окрашена иначе, чем области, которых она касается непосредственно, а не области, касающиеся областей, которых она касается. Если бы это было ограничением, плоские графы требовали бы сколь угодно большого количества цветов.

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

Трехцветная

Доказательство без слов, что карта штатов США должна состоять как минимум из четырех цветов.

Хотя каждую плоскую карту можно раскрасить четырьмя цветами, является NP-полной по сложности . решение о том, можно ли раскрасить произвольную плоскую карту всего тремя цветами,

Кубическую карту можно раскрасить только тремя цветами тогда и только тогда, когда каждая внутренняя область имеет четное количество соседних областей. В примере с картой штатов США Миссури , не имеющий выхода к морю ( Миссури ), имеет восемь соседей (четное число): он должен быть окрашен в разные цвета, но соседи могут чередовать цвета, поэтому для этой части карты требуется только три цвета. Однако у Невады , не имеющей выхода к морю ( NV ), есть пять соседей (нечетное число): один из соседей должен быть другого цвета, чем он и все остальные, поэтому здесь нужны четыре цвета.

Обобщения

Бесконечные графики

Соединив одинарные стрелки вместе и двойные стрелки вместе, можно получить тор с семью соприкасающимися областями; поэтому необходимо семь цветов.

Эта конструкция показывает тор, разделенный максимум на семь областей, каждая из которых касается друг друга.

Теорема о четырех цветах применима не только к конечным плоским графам, но и к бесконечным графам , которые можно нарисовать без пересечений на плоскости, и, в более общем смысле, к бесконечным графам (возможно, с несчетным числом вершин), для которых каждый конечный подграф является плоским. . Чтобы доказать это, можно объединить доказательство теоремы для конечных плоских графов с теоремой Де Брейна–Эрдёша, утверждающей, что если каждый конечный подграф бесконечного графа k -раскрашиваем, то весь граф также k -раскрашиваем по Нэшу. Уильямс (1967) . Это также можно рассматривать как непосредственное следствие теоремы Курта Гёделя о компактности для логики первого порядка , просто выражая раскрашиваемость бесконечного графа с помощью набора логических формул.

Высшие поверхности

Можно также рассмотреть задачу раскраски на поверхностях, отличных от плоскости. Задача на сфере или цилиндре эквивалентна задаче на плоскости. Для замкнутых (ориентируемых или неориентируемых) поверхностей положительного рода максимальное необходимое число p поверхности цветов зависит от эйлеровой характеристики χ по формуле

$p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$

где крайние скобки обозначают функцию пола .

Альтернативно, для ориентируемой поверхности формула может быть задана через род поверхности g :

$p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .$

Эта формула, гипотеза Хивуда , была предложена П. Дж. Хивудом в 1890 году и после участия нескольких человек доказана Герхардом Рингелем и Дж. У. Т. Янгсом в 1968 году. Единственным исключением из формулы является бутылка Клейна , которая имеет эйлерову характеристику 0 (следовательно, формула дает p = 7), но требует всего 6 цветов, как показал Филип Франклин в 1934 году.

Например, тор имеет эйлерову характеристику χ = 0 (и род g = 1) и, следовательно, p = 7, поэтому для раскраски любого отображения на торе требуется не более 7 цветов. Эта верхняя граница 7 является точной : некоторые тороидальные многогранники, такие как многогранник Силасси, требуют семи цветов.

Лента Мёбиуса требует шести цветов ( Титце, 1910 ), как и одноплоскостные графы (графы, нарисованные не более чем с одним простым пересечением на каждом ребре) ( Бородин, 1984 ). Если и вершины, и грани плоского графа раскрашены таким образом, что никакие две соседние вершины, грани или пары вершина-грань не имеют одинакового цвета, то снова потребуется не более шести цветов ( Бородин 1984 ).

• 
  Радиально симметричный семицветный тор - области одного цвета оборачиваются по пунктирным линиям.
• 
  8-цветный двойной тор (поверхность второго рода) — пузыри обозначают уникальную комбинацию двух областей.
• 
  Шестицветная бутылка Клейна.
• 
  Титце Разделение ленты Мёбиуса на шесть взаимно смежных областей, требующее шести цветов. Вершины и ребра подразделения образуют вложение графа Титце в полосу.
• 
  Интерактивная модель многогранника Силасси, каждая из 7 граней которой примыкает друг к другу — на изображении SVG переместите мышь, чтобы повернуть его.
• 
  Доказательство без слов , что количество необходимых цветов неограничено в трех и более измерениях.

Для графов, вершины которых представлены парами точек на двух различных поверхностях, а ребра нарисованы в виде непересекающихся кривых на одной из двух поверхностей, хроматическое число может быть не менее 9 и не более 12, но более точные границы не установлены. известен; это Герхарда Рингеля проблема Земли и Луны .

Сплошные регионы

Нет очевидного распространения результата раскраски на трехмерные сплошные области. Используя набор из n гибких стержней, можно добиться того, чтобы каждый стержень касался каждого другого стержня. Тогда для набора потребуется n цветов или n +1, включая пустое пространство, которое также касается каждого стержня. Число n может быть любым целым числом, сколь угодно большим. Такие примеры были известны Фредрику Гатри в 1880 году. , параллельных осям Даже для кубоидов (считающихся соседними, когда два кубоида имеют общую двумерную граничную область) может потребоваться неограниченное количество цветов.

Связь с другими областями математики

Дрор Бар-Натан сделал утверждение об алгебрах Ли и инвариантах Васильева , которое эквивалентно теореме о четырех цветах.

Использование вне математики

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

См. также

• Аполлоническая сеть
• Теорема пяти цветов
• Раскраска графа
• Теорема Греча : плоские графы без треугольников раскрашиваются в 3 цвета.
• Задача Хадвигера-Нельсона : сколько цветов нужно, чтобы раскрасить плоскость так, чтобы никакие две точки, находящиеся на расстоянии единицы друг от друга, не имели одинаковый цвет?

Ссылки

• Аллер, Франк (1978), «Еще одно доказательство теоремы о четырех цветах. I.», в Д. Маккарти; Х. К. Уильямс (ред.), Труды 7-й Манитобской конференции по числовой математике и вычислениям, Congr. Число. , том. 20, Виннипег, штат Ман.: Utilitas Mathematica Publishing, Inc., стр. 3–72, ISBN.  0-919628-20-6 , МР   0535003
• Аппель, Кеннет ; Хакен, Вольфганг (1977), «Каждая плоская карта раскрашивается в четыре цвета. I. Разрядка», Illinois Journal of Mathematics , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 , MR   0543792
• Аппель, Кеннет ; Хакен, Вольфганг ; Кох, Джон (1977), «Каждая плоская карта раскрашивается в четыре цвета. II. Сводимость», Illinois Journal of Mathematics , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 , MR   0543793
• Аппель, Кеннет ; Хакен, Вольфганг (октябрь 1977 г.), «Решение проблемы четырехцветной карты», Scientific American , vol. 237, нет. 4, стр. 108–121, Бибкод : 1977SciAm.237d.108A , номер документа : 10.1038/scientificamerican1077-108.
• Аппель, Кеннет ; Хакен, Вольфганг (1989), Каждая плоская карта раскрашивается в четыре цвета , Contemporary Mathematics, vol. 98, при сотрудничестве Дж. Коха, Провиденс, Род-Айленд: Американское математическое общество, номер документа : 10.1090/conm/098 , ISBN.  0-8218-5103-9 , МР   1025335 , S2CID   8735627
• Бар-Натан, Дрор (1997), «Алгебры Ли и теорема о четырех цветах», Combinatorica , 17 (1): 43–52, arXiv : q-alg/9606016 , doi : 10.1007/BF01196130 , MR   1466574 , S2CID   2103049
• Бернхарт, Фрэнк Р. (1977), «Обзор теоремы о четырех цветах», Journal of Graph Theory , vol. 1, нет. 3, стр. 207–225, номер документа : 10.1002/jgt.3190010305 , MR   0465921.
• Бородин, О. В. (1984), "Решение задачи Рингеля о вершинно-граничной раскраске планарных графов и раскраске 1-планарных графов", Методы дискретного анализа (41): 12–26, 108, MR   0832128 .
• Кэли, Артур (1879), «О раскрасках карт», Труды Королевского географического общества , 1 (4), Blackwell Publishing: 259–261, doi : 10.2307/1799998 , JSTOR   1799998
• Фрич, Рудольф; Фрич, Герда (1998), Теорема о четырех цветах: история, топологические основы и идея доказательства , перевод с немецкого оригинала 1994 года Джули Пешке., Нью-Йорк: Springer, doi : 10.1007/978-1-4612-1720-6 , ISBN  978-0-387-98497-1 , МР   1633950
• ФГ (10 июня 1854 г.), «Подкрашивание карт» , Атенеум : 726 .
• Гетнер, Э .; Спрингер, В.М. (2003), «Насколько ложно доказательство Кемпе теоремы о четырех цветах?», Congr. Номер , 164 : 159–175, МР   2050581 , Збл   1050.05049
• Гетнер, Эллен ; Каличанда, Бопанна; Ментис, Александр С. (2009), «Насколько ложно доказательство Кемпе теоремы о четырех цветах? Часть II», Involve , 2 (3): 249–265, doi : 10.2140/involve.2009.2.249
• Гонтье, Жорж (2005), Проверенное на компьютере доказательство теоремы о четырех цветах (PDF) , неопубликовано, заархивировано (PDF) из оригинала 8 сентября 2017 г.
• Гонтье, Жорж (2008), «Формальное доказательство — Теорема о четырех цветах» (PDF) , Уведомления Американского математического общества , 55 (11): 1382–1393, MR   2463991 , заархивировано (PDF) из оригинала в 2011 г. 08-05
• Хадвигер, Хьюго (1943), «О классификации комплексов маршрутов», Quarterjschr. Натуралист Гес, Цюрих , 88 : 133–143.
• Хивуд, П.Дж. (1890), «Теорема о цвете карты», Ежеквартальный журнал математики, Оксфорд , том. 24, стр. 332–338.
• Хадсон, Хад (май 2003 г.), «Четырех цветов недостаточно», The American Mathematical Monthly , 110 (5): 417–423, doi : 10.2307/3647828 , JSTOR   3647828
• Кемпе, AB (1879), «О географической проблеме четырех цветов», Американский журнал математики , 2 (3): 193–220, doi : 10.2307/2369235 , JSTOR   2369235
• Маньянт, К.; Мартин, Д.М. (2011), «Раскраска прямоугольных блоков в трехмерном пространстве», Дискуссии Mathematicae Graph Theory , 31 (1): 161–170, doi : 10.7151/dmgt.1535
• Маккей, Брендан Д. (2012), Заметка об истории гипотезы о четырех цветах , arXiv : 1201.2852 , Bibcode : 2012arXiv1201.2852M
• Нэш-Уильямс, К. Ст. Дж. А. (1967), «Бесконечные графы — обзор», Журнал комбинаторной теории , 3 (3): 286–301, doi : 10.1016/s0021-9800(67)80077-2 , MR   0214501 .
• О'Коннор; Робертсон (1996), Теорема о четырех цветах , архив MacTutor , заархивировано из оригинала 16 января 2013 г. , получено 5 августа 2001 г.
• Пегг, Эд младший ; Мелендес, Дж.; Беренгер, Р.; Сендра, младший; Эрнандес, А.; Дель Пино, Дж. (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A , doi : 10.1109/TED.2002.1003756 , заархивировано (PDF) из оригинала 9 апреля 2003 г.
• Рид, Брюс ; Олрайт, Дэвид (2008), «Покраска офиса» , Тематические исследования по математике в промышленности , 1 : 1–8, заархивировано из оригинала 03 февраля 2013 г. , получено 11 июля 2011 г.
• Рингель, Г. (1974), Теорема о цвете карты , Нью-Йорк – Берлин: Springer-Verlag
• Рингель, Г .; Янгс, JWT (1968), «Решение проблемы раскраски карт Хивуда», Proc. Натл. акад. наук. США , том. 60, нет. 2, стр. 438–445, Bibcode : 1968PNAS...60..438R , doi : 10.1073/pnas.60.2.438 , PMC   225066 , PMID   16591648
• Робертсон, Нил ; Сандерс, Дэниел П .; Сеймур, Пол ; Томас, Робин (1996), «Эффективно четырехцветные плоские графы», Труды 28-го симпозиума ACM по теории вычислений (STOC 1996) , стр. 571–575, doi : 10.1145/237814.238005 , ISBN  0-89791-785-5 , МР   1427555 , S2CID   14962541
• Робертсон, Нил ; Сандерс, Дэниел П .; Сеймур, Пол ; Томас, Робин (1997), «Теорема о четырех цветах», Дж. Комбин. Теория Сер. Б , том. 70, нет. 1, стр. 2–44, номер документа : 10.1006/jctb.1997.1750 , MR   1441258.
• Саати, Томас ; Кайнен, Пол (1986), «Проблема четырех цветов: нападения и завоевания», Science , 202 (4366), Нью-Йорк: Dover Publications: 424, Бибкод : 1978Sci...202..424S , doi : 10.1126/science. 202.4366.424 , ISBN  0-486-65092-8 , PMID   17836752
• Сварт, Эдвард Рейнир (1980), «Философские последствия проблемы четырех цветов» , American Mathematical Monthly , vol. 87, нет. 9, Математическая ассоциация Америки, стр. 697–702, номер документа : 10.2307/2321855 , JSTOR   2321855 , MR   0602826.
• Томас, Робин (1998), «Обновленная версия теоремы о четырех цветах» (PDF) , Уведомления Американского математического общества , том. 45, нет. 7, стр. 848–859, MR   1633714 , заархивировано (PDF) из оригинала 29 сентября 2000 г.
• Томас, Робин (1995), Теорема о четырех цветах
• Титце, Генрих (1910), «Некоторые замечания по проблеме раскраски карт на односторонних поверхностях», Годовой отчет Немецкой ассоциации математиков , 19 : 155-159.
• Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», в Лэмбе, Джон Д.; Прис, Д.А. (ред.), Обзоры по комбинаторике, 1999 , Серия лекций Лондонского математического общества, том. 267, Кембридж: Издательство Кембриджского университета, стр. 201–222, номер документа : 10.1017/CBO9780511721335 , ISBN.  0-521-65376-2 , МР   1725004
• Тейт, П.Г. (1880), «Замечания о раскрасках карт», Proc. Р. Сок. Эдинбург , 10 : 729, номер номера : 10.1017/S0370164600044643
• Уилсон, Робин (2014) [2002], Достаточно четырех цветов , Научная библиотека Принстона, Принстон, Нью-Джерси: Издательство Принстонского университета, ISBN  978-0-691-15822-8 , МР   3235839
• Уилсон, Робин; Уоткинс, Джон Дж.; Паркс, Дэвид Дж. (17 января 2023 г.), Теория графов в Америке , Принстон Оксфорд: Princeton University Press, ISBN  978-0-691-19402-8

Внешние ссылки

• «Задача четырех цветов» , Математическая энциклопедия , EMS Press , 2001 [1994]

• Список обобщений теоремы о четырех цветах на MathOverflow