Теорема четырех цветов - Four color theorem - Wikipedia

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

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

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

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

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

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

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

4CT Inadequacy Example.svg

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

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

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

Каждый планарный граф четырехцветный.[5]

История

Ранние попытки доказательства

Письмо де Моргана к Гамильтон, 23 октября 1852 г.

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

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

"F.G.", возможно, один из двух Гатри, опубликовал вопрос в Атенеум в 1854 г.,[8] и Де Морган снова задал этот вопрос в том же журнале в 1860 году.[9] Еще одна ранее опубликованная ссылка Артур Кейли  (1879 ), в свою очередь, приписывает гипотезу Де Моргану.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С момента доказательства теоремы были найдены эффективные алгоритмы для 4-раскраски карт, требующие только О (п2) время, где п количество вершин. В 1996 г. Нил Робертсон, Дэниел П. Сандерс, Пол Сеймур, и Робин Томас создал квадратичное время алгоритм, улучшающий квартика -временной алгоритм, основанный на доказательстве Аппеля и Хакена.[18] Это новое доказательство аналогично доказательству Аппеля и Хакена, но более эффективно, поскольку оно снижает сложность проблемы и требует проверки только 633 приводимых конфигураций. Как неизбежность, так и сводимость этого нового доказательства должны выполняться на компьютере, и их невозможно проверить вручную.[19] В 2001 году те же авторы объявили альтернативное доказательство, доказав язвить предположение.[20] Однако это доказательство остается неопубликованным.

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

Резюме идей доказательства

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

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

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

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

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

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

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

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

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

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

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

Вспомните формулу выше:

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

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

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

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

Теорема четырех цветов была известна тем, что за свою долгую историю привлекла большое количество ложных доказательств и опровержений. Во-первых, Нью-Йорк Таймс отказался из соображений политики сообщить о доказательстве Аппеля – Хакена, опасаясь, что доказательство окажется ложным, как и предыдущие (Уилсон 2014 ). Некоторые предполагаемые доказательства, такие как упомянутые выше Кемпе и Тейта, находились под пристальным вниманием общественности более десяти лет, прежде чем были опровергнуты. Но многие другие, написанные любителями, вообще никогда не публиковались.

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

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

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

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

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

Трехцветная окраска

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

Обобщения

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

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

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

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

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

(Weisstein ).
Интерактивная модель многогранника Силасси с каждой гранью разного цвета. В изображение SVG, переместите мышь, чтобы повернуть его.[23]

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

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

Титце подразделение Лента Мебиуса на шесть смежных областей, требующих шести цветов. Вершины и ребра подразделения образуют вложение График Титце на полосу.

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

Нет очевидного распространения результата раскраски на трехмерные твердые области. Используя набор п гибкие стержни, можно сделать так, чтобы каждый стержень касался другого стержня. Тогда для набора потребуется п цвета, или п+1, если учесть пустое пространство, которое также касается каждого стержня. Номер п может быть любым целым числом, сколь угодно большим. Такие примеры были известны Фредерику Гатри в 1880 г. (Уилсон 2014 ). Даже для параллельных осям кубоиды (считается смежным, когда два кубоида разделяют двумерную граничную область) может потребоваться неограниченное количество цветов (Рид и Олрайт, 2008 г.; Магнант и Мартин (2011) ).

Отношение к другим разделам математики

Дрор Бар-Натан сделал заявление относительно Алгебры Ли и Инварианты Васильева что эквивалентно теореме о четырех цветах.[24]

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

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

Смотрите также

Примечания

  1. ^ Из Гонтье (2008): "Определения: Плоская карта - это набор попарно непересекающихся подмножеств плоскости, называемых регионами. Простая карта - это карта, регионы которой являются связными открытыми множествами. Две области карты являются смежными, если их соответствующие замыкания имеют общую точку, которая является не угол карты. Точка является углом карты тогда и только тогда, когда она принадлежит замыканиям по крайней мере трех областей. Теорема: области любой простой плоской карты можно раскрасить только четырьмя цветами, таким образом так, чтобы любые две соседние области имели разные цвета ".
  2. ^ Сварт (1980).
  3. ^ Уилсон (2014), 216–222.
  4. ^ Хадсон (2003).
  5. ^ Томас (1998, п. 849); Уилсон (2014) ).
  6. ^ Есть некоторые математические предания, которые Мебиус возникла гипотеза о четырех цветах, но это представление кажется ошибочным. Видеть Биггс, Норман; Ллойд, Э. Кейт; Уилсон, Робин Дж. (1986). Теория графов, 1736–1936 гг.. Издательство Оксфордского университета. п. 116. ISBN  0-19-853916-9. & Мэддисон, Изабель (1897). «Заметка об истории проблемы раскраски карты». Бык. Амер. Математика. Soc. 3 (7): 257. Дои:10.1090 / S0002-9904-1897-00421-9.
  7. ^ Дональд Маккензи, Механизация доказательств: вычисления, риск и доверие (MIT Press, 2004) стр.103
  8. ^ Ф. Г. (1854); Маккей (2012)
  9. ^ а б Де Морган (аноним), Август (14 апреля 1860 г.), «Философия открытия, главы исторические и критические. Автор У. Уэвелл», Атенеум: 501–503
  10. ^ У. В. Роуз Болл (1960) Теорема о четырех цветах, в «Mathematical Recreations and Essays», Макмиллан, Нью-Йорк, стр 222–232.
  11. ^ Томас (1998), п. 848.
  12. ^ Хивуд (1890).
  13. ^ Тейт (1880).
  14. ^ Хадвигер (1943).
  15. ^ а б Уилсон (2014).
  16. ^ Гэри Чартран и Линда Лесняк, Графы и диграфы (CRC Press, 2005) стр.221
  17. ^ Уилсон (2014); Аппель и Хакен (1989); Томас (1998, стр. 852–853).
  18. ^ Томас (1995); Робертсон и др. (1996) ).
  19. ^ Томас (1998) С. 852–853.
  20. ^ Томас (1999); Pegg et al. (2002) ).
  21. ^ Гонтье (2008).
  22. ^ Дейли, Д. П. (1980), "Единственность раскрашиваемости и раскрашиваемости плоских 4-регулярных графов NP-полна", Дискретная математика, 30 (3): 289–293, Дои:10.1016 / 0012-365X (80) 90236-8
  23. ^ Бранко Грюнбаум, Лайош Силасси, Геометрические реализации специальных тороидальных комплексов., Вклад в дискретную математику, Том 4, номер 1, страницы 21-39, ISSN 1715-0868
  24. ^ Бар-Натан (1997).

Рекомендации

внешняя ссылка