Теорема четырех красок, или Как раскрасить карту мира
@sciencegram
Задача звучит примерно так: любую карту можно раскрасить в четыре цвета, так что смежные страны будут всегда разного цвета. Другими словами — пятый цвет в принципе на карте не нужен.
И хотя кажется, что чем сложнее карта, тем больше нужно цветов — это не так, хотя доказать это очень трудно. Так трудно, что от формулировки теоремы в 1852 году потребовалось более 100 лет для ее доказательства. Решение нашли Кеннет Аппель и Вольфганг Хакен из Иллинойского университета в 1976 году — перебором всех опций. Теорема четырех красок — первая, для доказательства которой использовали компьютер (тогда это считалось сомнительным способом).
Как собственно, это доказывается — любую карту схематически можно представить в виде графа, где страны — точки, соединенные линией, если у них есть общая граница. Граф нужен для того, чтобы понять, что две по-разному выглядящие карты — по сути одно и то же.
Все карты можно представить в виде графа, но не все графы — в виде карты. Если в графе есть пересечения, то у вас не получится представить граф в виде карты.
При этом, почти каждая страна на карте выглядит примерно, как один из этих вариантов:
И тут обнаружится еще одно интересное свойство карт — не бывает больше пяти стран одновременно граничащих друг с другом.
Лирическое отступление:
У России, по разным подсчетам от 13 (материковой части, без Калининграда и учета непризнанных Абхазии и Южной Осетии) до 18 соседей, из них общих, например, с Китаем, у которого тоже много — 13 соседей, лишь два — Монголия и Казахстан.
Поскольку доказательство того, что любую карту можно раскрасить всего четыре цвета, потребовало перебора 1936 вариантов графов, то принцип объясняют на более простом примере — любую карту можно раскрасить в 6 цветов.
Берем карту в 7 цветов.
Убираем из нее какую-нибудь страну с большим числом соседей (тут пять).
Карта стала проще. Перекрасим одну из фиолетовых точек в зеленый.
Вторую в левом верхнем углу, соединенную с двумя белыми, одной зеленой, желтой и красной точками) перекрасим в синий. Этим же синим можно покрасить в синий и ту страну, которую мы убрали из схемы.
Источник: