Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример четырехцветной карты
Четырехцветная карта штатов США (без учета озер).

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

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

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

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

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

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

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

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

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

Каждый планарный граф раскрашиваем в четыре цвета . [5]

История [ править ]

Первые попытки доказательства [ править ]

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

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

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

«FG», возможно, один из двух Гатри, опубликовал вопрос в «Атенеуме» в 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. Неизбежными набор представляет собой набор конфигураций , таких , что каждая карта , которая удовлетворяет некоторые условия , необходимые для того минимального не-4-Colorable триангуляции (например, имеющие минимальную степень 5) должен иметь по меньшей мере одну конфигурацию из этого множества.
  2. Приводимая конфигурация представляет собой расположение стран , которые не могут произойти в минимальном контрпримере. Если карта содержит сокращаемую конфигурацию, карту можно уменьшить до меньшего размера. У этой меньшей карты есть условие, что если она может быть раскрашена в четыре цвета, то это также относится к исходной карте. Это означает, что если исходная карта не может быть раскрашена в четыре цвета, меньшая карта тоже не может, и поэтому исходная карта не является минимальной.

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

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

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

Упрощение и проверка [ править ]

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

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

Краткое изложение идей доказательства [ править ]

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

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

Предположим, что v , e и f - количество вершин, ребер и областей (граней). Поскольку каждая область имеет треугольную форму, а каждое ребро является общим для двух областей, мы имеем, что 2 e = 3 f . Это вместе с Эйлером формулой , V - е + е = 2, может быть использовано , чтобы показать , что 6 V - 2 е = 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-полна в сложности , чтобы решить , является ли произвольная плоская карта может быть окрашена только три цвета. [22]

Обобщения [ править ]

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

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

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

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

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

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

Эта формула, то гипотеза работы Хивуда , была высказана гипотеза , с помощью PJ работы Хивуда в 1890 году и доказала Gerhard Рингель и JWT Youngs в 1968 г. Единственное исключение из формулы является бутылка Клейна , который имеет эйлерово характеристика 0 (следовательно, формула дает р = 7) и требует всего 6 цветов, как показал П. Франклин в 1934 году ( Weisstein ).

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

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

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

Нет очевидного распространения результата раскраски на трехмерные твердые области. Используя набор из n гибких стержней, можно сделать так, чтобы каждый стержень касался другого стержня. Тогда для набора потребуется n цветов или n +1, если учесть пустое пространство, которое также касается каждого стержня. Число n может быть любым целым числом, сколь угодно большим. Такие примеры были известны Фредерику Гатри в 1880 году ( Wilson 2014 ). Даже для параллельных оси кубоидов (которые считаются смежными, когда два кубоида разделяют двумерную граничную область) может потребоваться неограниченное количество цветов ( Reed & Allwright 2008 ; Magnant & Martin (2011) ).

Отношение к другим разделам математики [ править ]

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

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

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

См. Также [ править ]

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

Примечания [ править ]

  1. ^ Из Gonthier (2008) : «Определения: плоская карта - это набор попарно непересекающихся подмножеств плоскости, называемых регионами. Простая карта - это карта, регионы которой являются связными открытыми множествами. Две области карты являются смежными, если их соответствующие замыкания имеют общую точку, которая не является углом карты. Точка является углом карты тогда и только тогда, когда она принадлежит замыканиям по крайней мере трех областей. Теорема: области любой простой плоской карты можно раскрасить только четыре цвета, так что любые две соседние области имеют разные цвета ".
  2. Перейти ↑ Swart (1980) .
  3. ^ Wilson (2014) , 216-222.
  4. ^ Хадсон (2003) .
  5. ↑ Thomas (1998 , стр. 849); Уилсон (2014) ).
  6. ^ Есть некоторые математические предания, что Мёбиус создал гипотезу о четырех цветах, но это представление кажется ошибочным. См. Биггс, Норман ; Ллойд, Э. Кейт; Уилсон, Робин Дж. (1986). Теория графов, 1736–1936 . Издательство Оксфордского университета. п. 116 . ISBN 0-19-853916-9.И Мэддисон, Изабель (1897). «Заметка об истории проблемы раскраски карты» . Бык. Амер. Математика. Soc . 3 (7): 257. DOI : 10.1090 / S0002-9904-1897-00421-9 .
  7. ^ Дональд Маккензи, Механизация доказательства: вычисления, риски и доверие (MIT Press, 2004), стр.103
  8. ^ FG (1854) ; Маккей (2012)
  9. ^ a b Де Морган (анонимно), Август (14 апреля 1860 г.), «Философия открытия, главы исторические и критические. Автор В. Уэвелл», The Athenaeum : 501–503
  10. ↑ WW Rouse Ball (1960) Теорема о четырех цветах , в «Mathematical Recreations and Essays», Macmillan, New York, pp 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, DOI : 10.1016 / 0012-365X (80) 90236- 8
  23. ^ Бранко Грюнбаум, Лайош Силасси, Геометрические реализации специальных тороидальных комплексов , Вклад в дискретную математику, Том 4, номер 1, страницы 21-39, ISSN 1715-0868
  24. ^ Бар-Натан (1997) .

Ссылки [ править ]

  • Аллер, Франк (1978), «Другое доказательство теоремы о четырех цветах. I.», в Д. Маккарти; HC Williams (ред.), Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Нумер. , 20 , Виннипег, Ман .: Utilitas Mathematica Publishing, Inc., стр. 3–72, ISBN 0-919628-20-6, MR  0535003
  • Аппель, Кеннет; Хакен, Вольфганг (1977), "Каждый Planar Карта Четыре Colorable I. Разрядка.", Штат Иллинойс Журнал математики , 21 (3): 429-490, DOI : 10,1215 / IJM / 1256049011 , MR  0543792
  • Аппель, Кеннет; Хакен, Вольфганг; Кох, Джон (1977), "Каждый Planar Карта Четыре Colorable II Приводимость..", Штат Иллинойс Журнал математики , 21 (3): 491-567, DOI : 10,1215 / IJM / 1256049012 , MR  0543793
  • Аппель, Кеннет; Хакен, Вольфганг (октябрь 1977 г.), «Решение проблемы четырехцветной карты», Scientific American , 237 (4), стр. 108–121, Bibcode : 1977SciAm.237d.108A , doi : 10.1038 / scientificamerican1077-108
  • Аппель, Кеннет; Хакен, Вольфганг (1989), Каждую плоскую карту можно раскрашивать в четыре цвета , Contemporary Mathematics, 98 , В сотрудничестве с Дж. Кохом, Провиденс, Род-Айленд: Американское математическое общество, doi : 10.1090 / conm / 098 , ISBN 0-8218-5103-9, MR  1025335
  • Бар-Натан, Дрор (1997), «Алгебры Ли и теорема о четырех цветах», Combinatorica , 17 (1): 43–52, arXiv : q-alg / 9606016 , doi : 10.1007 / BF01196130 , MR  1466574
  • Бернхарт, Франк Р. (1977), "Дайджест теоремы четырех красок", Журнал теории графов , 1 (3), стр 207-225,. DOI : 10.1002 / jgt.3190010305 , МР  0465921
  • Бородин О.В. (1984), "Решение задачи Рингеля о раскраске вершин плоских графов и раскраске 1-плоских графов", Методы Дискретного анализа (41): 12–26, 108, MR  0832128.
  • Кэли, Артур (1879), "О раскраске карт", Proc. Королевское географическое общество , Blackwell Publishing, 1 . (4), стр 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
  • FG (10 июня 1854 г.), «Подкрашивание карт» , The Athenaeum : 726.
  • Gonthier, Georges (2005), Проверенное компьютером доказательство теоремы о четырех цветах (PDF) , неопубликовано
  • Гонтье, Жорж (2008), «Формальное доказательство - теорема о четырех цветах» (PDF) , Уведомления Американского математического общества , 55 (11): 1382–1393, MR  2463991
  • Хадвигер, Хьюго (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Цюрих , 88 : 133–143
  • Heawood, PJ (1890), «Теорема о цвете карты», Quarterly Journal of Mathematics, Oxford , 24 , стр. 332–338
  • Хадсон, Хад (май 2003), "Четыре цвета не хватает", Американский Математический Месячный , 110 (5): 417-423, DOI : 10,2307 / 3647828 , JSTOR  3647828
  • Кемпе, AB (1879), "О географической проблеме четырех цветов", Американский журнал математики Джонса Хопкинса University Press , 2 (3): 193-220, DOI : 10,2307 / 2369235
  • Magnant, C .; Мартин, Д.М. (2011), «Раскрашивание прямоугольных блоков в 3-мерном пространстве» , Discussiones Mathematicae Graph Theory , 31 (1): 161–170, doi : 10.7151 / dmgt.1535
  • Маккей, Брендан Д. (2012), Заметка об истории четырехцветной гипотезы , arXiv : 1201.2852 , Bibcode : 2012arXiv1201.2852M
  • Nash-Williams, C. St. JA (1967), "Бесконечные графы-обзор", журнал комбинаторной теории , 3 (3): 286-301, DOI : 10.1016 / s0021-9800 (67) 80077-2 , MR  0214501.
  • О'Коннор; Робертсон (1996), Теорема четырех цветов , архив MacTutor
  • Пегг, Эд, младший ; Melendez, J .; Berenguer, R .; Сендра, младший; Эрнандес, А .; Дель Пино, Дж. (2002), «Рецензия на книгу: Колоссальная книга математики» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Bibcode : 2002ITED ... 49.1084A , doi : 10.1109 / TED.2002.1003756
  • Рид, Брюс ; Олрайт, Дэвид (2008), «Рисование офиса» , Примеры из практики « Математика в промышленности» , 1 : 1–8
  • Ringel, G .; Янгс, JWT (1968), "Решение проблемы раскраски карты Хивуда", Proc. Natl. Акад. Sci. США , 60 (2), стр 438-445,. Bibcode : 1968PNAS ... 60..438R , DOI : 10.1073 / pnas.60.2.438 , КУП  225066 , PMID  16591648
  • Робертсон, Нил; Сандерс, Дэниел П .; Сеймур, Пол; Томас, Робин (1996), "Эффективно четырехкратные плоские графы", Труды 28-го симпозиума ACM по теории вычислений (STOC 1996) , стр. 571–575, doi : 10.1145 / 237814.238005 , MR  1427555
  • Робертсон, Нил; Сандерс, Дэниел П .; Сеймур, Пол; Томас, Робин (1997), "Теорема о четырех цветах", J. Combin. Теория Сер. Б , 70 . (1), стр 2-44, DOI : 10,1006 / jctb.1997.1750 , МР  1441258
  • Саати, Томас ; Kainen, Павел (1986), "Четыре цвета Проблема: Нападения и Conquest", Наука , Нью - Йорк: Dover Publications, 202 (4366): 424, Bibcode : 1978Sci ... 202..424S , DOI : 10.1126 / наука. 202.4366.424 , ISBN 0-486-65092-8
  • Сварт, Эдвард Рейнир (1980), "Философские последствия четырехцветной проблемы" , American Mathematical Monthly , Mathematical Association of America, 87 (9), стр. 697–702, doi : 10.2307 / 2321855 , JSTOR  2321855 , MR  0602826
  • Томас, Робин (1998), "Обновление теоремы о четырех цветах" (PDF) , Уведомления Американского математического общества , 45 (7), стр. 848–859, MR  1633714
  • Томас, Робин (1995), Теорема о четырех цветах
  • Титце, Генрих (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Некоторые замечания по проблеме раскраски карты на односторонних поверхностях], Годовой отчет DMV , 19 : 155–159
  • Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», в Lamb, John D .; Прис, Д. (ред.), Исследования , проведенные в комбинаторике, 1999 , Лондон математического общества Лекция Примечание Серия, 267 , Кембридж. Cambridge University Press, стр 201-222, DOI : 10,1017 / CBO9780511721335 , ISBN 0-521-65376-2, MR  1725004
  • Tait, PG (1880), "Замечания о раскраске карт", Proc. R. Soc. Эдинбург , 10 : 729, DOI : 10,1017 / S0370164600044643
  • Уилсон, Робин (2014) [2002], Four Colours Suffice , Princeton Science Library, Princeton, NJ: Princeton University Press, ISBN. 978-0-691-15822-8, Руководство по ремонту  3235839

Внешние ссылки [ править ]

  • "Четырехцветная задача" , Энциклопедия математики , EMS Press , 2001 [1994]
  • Вайсштейн, Эрик В. "Blanuša snarks" . MathWorld .
  • Вайсштейн, Эрик В. «Раскраска карты» . MathWorld .
  • Список обобщений теоремы о четырех цветах на MathOverflow