"Геометрия", Смирнова И.М., Смирнов В.А.
Проблема четырёх красок изучает раскраску карт на плоскости. Области, имеющие общую границу, должны быть окрашены в разные цвета, а соприкосновение одной точкой ограничением не считается. Главный вопрос состоит в том, хватит ли четырёх цветов для любой карты. Ответ утвердительный: любую плоскую карту можно правильно раскрасить не более чем четырьмя цветами, хотя отдельным картам достаточно одного, двух или трёх.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Карта — изображение областей на плоскости, разделённых границами. Отдельными считаются области, которые отделены друг от друга границей и занимают разные части карты. Это понятие позволяет изучать не внешний вид рисунка, а отношения между его областями.
Соседние области — области, имеющие общую границу ненулевой длины. Если две области касаются только одной точкой, например общим углом, соседними их не считают. Такое уточнение нужно, чтобы точно определить, где цвета обязаны различаться.
Правильная раскраска карты — раскраска, при которой любые соседние области имеют разные цвета. Несоседние области могут получить один и тот же цвет. Поэтому правильная раскраска не означает, что всем областям нужны разные цвета.
Проблема четырёх красок — вопрос о том, достаточно ли четырёх цветов для правильной раскраски любой карты на плоскости. Ответ выражается теоремой о четырёх красках: пяти и более цветов для такой карты не требуется. При этом некоторым картам хватает меньшего числа цветов.
При раскраске важны не форма, площадь и положение области на листе, а только её соседство с другими областями. Две длинные области могут требовать столько же цветов, сколько две маленькие, если набор их соседей одинаков. Поэтому карту можно заменить схемой связей между областями, не сохраняя точные очертания.
Чтобы определить ограничения, прослеживают границы каждой области. Если два участка имеют общую часть границы ненулевой длины, их цвета должны различаться. Общая точка не создаёт такого ограничения: вокруг неё области не соприкасаются вдоль участка и не образуют общей границы.
Некоторым картам достаточно двух цветов, если области можно разделить на две группы так, чтобы соседние области всегда относились к разным группам. Три цвета нужны, например, при наличии нечётного цикла соседств: при чередовании цветов в конце возникает конфликт. Значит, число цветов определяется устройством связей, а не количеством нарисованных областей.
Иногда встречаются четыре области, каждая из которых соседствует с тремя остальными. Первой области нужен один цвет, второй — другой, третьей — третий, а четвёртой нельзя взять ни один из них. Поэтому такой карте необходимы четыре цвета, хотя это ещё не означает, что четыре цвета нужны каждой карте.
Утверждение о четырёх красках говорит: любую карту на плоскости можно правильно раскрасить не более чем четырьмя цветами. Идея кажется очевидной после просмотра множества примеров, но пример не заменяет доказательство для всех возможных карт. Историческое решение потребовало строгого рассуждения и компьютерной проверки большого числа специально выделенных случаев.
В таблице указано минимальное число цветов для характерных ситуаций. Сначала определите, какие области имеют общую границу, затем сравните получившуюся схему с условием строки. Число «4» в последней строке означает верхнюю границу для любой плоской карты, а не обязательное число цветов.
| Ситуация | Условие соседства | Минимальное число цветов | Вывод |
|---|---|---|---|
| Карта без соседствующих областей | Общие границы отсутствуют | 1 | Все области можно сделать одного цвета |
| Цепочка или двудольная схема областей | Соседства чередуются между двумя группами | 2 | Достаточно двух цветов |
| Карта, где двух цветов недостаточно, но нет трёх взаимно соседних областей | Есть цикл нечётной длины | 3 | Требуется не менее трёх цветов |
| Карта с четырьмя попарно соседними областями | Каждая из четырёх областей соседствует с остальными | 4 | Четырёх цветов достаточно и необходимо |
| Произвольная карта на плоскости | Соседства задаются границами областей | Не более 4 | Пять и более цветов не нужны |
Дана схема из пяти областей, соединённых в цепочку: первая граничит со второй, вторая — с третьей, третья — с четвёртой, четвёртая — с пятой. Других общих границ нет. Требуется понять, хватит ли двух цветов.
Ответ: двух цветов достаточно. Области с нечётными номерами получили один цвет, а области с чётными номерами — другой.
Центральная область окружена четырьмя областями. Каждая окружающая область граничит с центральной, а соседние между собой окружающие области имеют общие границы. Нужно проверить, можно ли использовать три цвета.
Ответ: трёх цветов достаточно, если последняя окружающая область не соседствует с первой так, чтобы возник конфликт. Решение всегда проверяют по каждой общей границе, а не только по расположению областей вокруг центра.
Рассмотрим схему из четырёх областей, каждая из которых имеет общую границу с каждой другой. Нужно найти минимальное число цветов и связать результат с проблемой четырёх красок.
Ответ: минимально нужны четыре цвета. Этот пример показывает, что теорема не утверждает возможность всегда обойтись тремя цветами, а устанавливает достаточность четырёх.
Считать соседними области, касающиеся одной точкой. Ошибка появляется из-за смешения общей границы и общего угла. Проверьте себя: ищите участок границы ненулевой длины, а не только место встречи линий.
Утверждать, что четыре цвета нужны любой карте. Четыре — это верхняя граница, поэтому конкретной карте может хватить одного, двух или трёх цветов. Сначала попробуйте уменьшить число цветов, проверяя все соседства.
Путать правильную раскраску с полной разноцветностью. Разные цвета обязательны только для соседних областей, а несоседние могут совпадать. Для проверки составьте список пар областей с общей границей.
Считать компьютерную проверку простым рассуждением. Историческое решение требовало строгого доказательства и проверки выделенных случаев, а не просмотра нескольких удачных карт. Разделяйте саму теорему и способ подтверждения её общего утверждения.
До темы нужны понятия плоскости, области, границы, графического изображения и логики доказательства. Они помогают точно описывать карту и не путать рисунок с условием задачи.
В теории графов области изображают вершинами, а соседство — рёбрами. Такая модель превращает раскраску карты в задачу о раскраске графа.
Идея применяется в комбинаторике, составлении расписаний, распределении радиочастот и других задачах, где конфликтующие объекты должны получить разные обозначения.
Почему области, соприкасающиеся только в одной точке, не считают соседними?
Общая точка не образует границы, через которую области соприкасаются на участке. Поэтому изменение цвета одной области не создаёт заметного конфликта с другой.
Всегда ли для раскраски карты нужны именно четыре цвета?
Нет. Четыре цвета — это наибольшее число, которого достаточно для любой карты на плоскости. Конкретной карте может хватить одного, двух или трёх цветов.
Как доказать, что для некоторой карты трёх цветов недостаточно?
Нужно найти четыре области, каждая из которых соседствует с тремя остальными. Тогда им нельзя назначить один цвет с соседней областью, и для всех четырёх понадобятся разные цвета.
Почему проблема четырёх красок оказалась настолько сложной?
Нужно было доказать утверждение сразу для бесконечного множества возможных карт. Простые примеры не подтверждают теорему полностью, поэтому потребовалось сложное доказательство с проверкой большого числа случаев.
Можно ли применять идею четырёх красок к картам на поверхности, отличной от плоскости?
Не всегда. Для других поверхностей меняются возможное соседство областей и максимальное число необходимых цветов. Поэтому теорема о четырёх красках относится именно к плоскости.
§ 26*. Проблема четырех красок
