Изменить язык

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Войдите в Mathigon

или

Новый аккаунт     Сброс пароля     

Графики и Сети
Введение
Мосты Кенигсберга
Рукопожатия и знакомства
Планарные Графики
Раскраска карты
Проблема коммивояжера
Проблемы с расписанием
Графики в повседневной жизни

Поделиться

Сбросить прогресс

Это приведет к удалению вашего прогресса и данных чата для всех глав этого курса, и их нельзя будет отменить!

Глоссарий

Выберите одно из ключевых слов слева ...

Графики и СетиРаскраска карты

Время чтения: ~10 min

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

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

Некоторым простым «картам», таким как шахматная доска, нужны только два цвета (черный и белый), но большинству сложных карт нужно больше.

При раскрашивании карты штатов США, очевидно, достаточно 50 цветов, но нужно гораздо меньше. Попробуйте раскрасить карты ниже как можно меньшим количеством цветов:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

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

Как и раньше, мы можем преобразовать карту со странами и границами в планарный график: каждая страна становится и страны, соединенный ребром:

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

В 1852 году студент-ботаник Фрэнсис Гатри должен был раскрасить карту графств Англии. Он заметил, что четырех цветов, по-видимому, достаточно для любой карты, которую он пробовал, но он не смог найти доказательства, подходящего для всех карт. Это оказалось чрезвычайно трудной проблемой и стало известно как теорема о четырех цветах .

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

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

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

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

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

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

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

This map on a torus requires seven colours.

Archie