Задачи о четырех красках

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

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

Материалом исследования явились задачи, в которых с помощью теории графов доказывается теория о четырех красках.

«Наиболее знаменитая среди этих задач – проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов»

Известный математик и педагог О. Оре.

Всякую карту на сфере можно раскрасить не более чем в четыре цвета так, чтобы любые две соседние страны были окрашены в разные цвета.

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

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

Карты на сфере

Картой на сфере мы будем называть всякое разбиение сферы отрезками гладких кривых на конечное число областей – стран карты. Относительно этих отрезков кривых естественно предполагать следующее:

1. каждый из них не имеет самопересечений;

2. любые два из них либо совсем не пересекаются в концевых точках;

3. концевые точки любого из них входят в число концевых точек одного или нескольких других отрезков, то есть не являются «висячими».

Ясно, что всякий из этих отрезков, составляющих в совокупности границу карты, является частью границы двух стран (или всей этой границей); такие страны будем называть соседними. Отметим, кстати, что строгое доказательство утверждения, начинающегося выше словами «ясно, что » и называемого теоремой Жордана, чрезвычайно громоздко, несмотря на всю его очевидность.

Сферические карты удобно рисовать в виде разделенного на страны «континента», окруженного «океаном» - одной из стран. Страны М и Е – не соседние, хотя имеют общую точку границы; страны D и E обладают даже двумя разрозненными участками общей границы.

Потребуем еще, чтобы на карте не было стран, имеющих только одного соседа («острова» в «океане»); карты с такими странами раскрашивать, конечно, ничуть не труднее, но изложение осложняется исключениями и уточнениями.

Раскраски карт

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

Задание 1. Нарисуйте карту из четырех стран, которую нельзя было бы правильно раскрасить двумя или тремя красками.

Задание 2. а) На плоскости даны n окружностей. Докажите, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.

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

В результате многолетней кропотливой работы было доказано, что любая карта, содержащая не более 41 страны, имеет правильную 4-раскраску. Из этого примера ясно, что если и существует пример, опровергающий нашу теорию, то построить его очень трудно. Вместе с тем правильная 5-раскраска существует для любой сферической карты.

Графы карты

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

Как видно из определения и свойств 1 – 3 карты на сфере, она характеризуется своим графом границ; его вершины – точки, в которых сходятся не менее трех стран, ребра – участки границ между вершинами. Мы определим также граф столиц и дорог карты; его вершины – «столицы» стран (произвольные, но фиксированные точки, выбранные по одной внутри каждой страны), ребра «дороги», соединяющие столицы соседних стран (по одной на каждую пару соседей) и проходящие через участок границы между ними.

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

Приступая к раскраске вершин графа столиц и дорог карты на сфере, проверим, можно ли его дополнить ребром, не пересекающим других ребер графа, и, если можно, дополним (например граф на – ребром AK). Любая правильная 4-раскладка вновь полученного графа будет правильной и для исходного графа; обратное, вообще говоря, неверно – две несоседние вершины стали соседними и должны быть разноцветными. Мы продолжим этот процесс добавления ребер.

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

Такой граф называют графом триангуляции сфере, а треугольники называют гранями графа. Изображен граф вершин и ребер правильного двадцатигранника – икосаэдра; грань 20 выглядит как внешняя часть треугольника XYZ.

Задание 4. Какой должна быть карта, чтобы ее граф столиц и дорог был графом триангуляции?

Задание 5. а) Докажите, что граф вершин и ребер правильного восьмигранника – октаэдра – может быть правильно раскрашен тремя красками.

б) Сформулируйте условия, необходимые и достаточные для того, чтобы граф триангуляции обладал правильной 3-раскраской.

Геометрия раскраски

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

Рассмотрим некоторый тетраэдр, каждая из четырех вершин которого раскрашена в свой цвет. Предположим теперь, что некоторый граф триангуляции сферы правильно раскрашен в те же четыре цвета. Тем самым каждой его вершине соответствует вершина тетраэдра, причем любым двум соседним – разные. А это означает, что каждому ребру и каждой грани графа соответствует некоторое ребро и некоторая грань тетраэдра: ребру графа – то ребро тетраэдра, вершины которого окрашены в те же два цвета, что и вершины ребра графа, а грани графа – подобным же образом определяемая грань тетраэдра. Мы можем представлять себе это соответствие как наложение раскрашенной триангулированной поверхности сферы на четырехгранную поверхность тетраэдра, вершины которого символизируют четыре цвета раскраски. Это наложение можно начинать можно начинать с любой окрашенной в некоторый цвет вершины триангуляции, совместив ее с вершиной тетраэдра того же цвета. Переходя к соседней вершине триангуляции и совмещая ее с соответствующей по цвету вершиной тетраэдра (которая всегда отлична от первой!), мы одновременно получим совмещение ребра триангуляция с ребром тетраэдра. Подобным же образом совместим грань триангуляции с гранью тетраэдра, и, затем, шаг за шагом добьемся нужного наложения.

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

Арифметика раскраски

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

Если при наложении грани графа триангуляции на грань тетраэдра ее внешняя сторона легла на внешнюю сторону грани тетраэдра, то сопоставим этой грани графа триангуляции число + 1, если же на внутреннюю, то -1.

Эти числа называют числами Хивуда раскраски – в честь английского математика П. Хивуда, пионера задач о раскрасках и первооткрывателя «арифметических» законов в проблеме четырех красок.

Основное, хотя и вполне очевидное свойство чисел Хивуда состоит в следующем:

Л е м м а. Если числа Хивуда двух соседних граней триангуляции равны, то эти грани отображаются на разные (но, конечно, всегда соседние) грани тетраэдра, если же они не равны, то эти грани отражаются на одну грань тетраэдра, одна «лицевой» стороной, другая «тыльной».

Эта лемма только детализирует определение чисел Хивуда; а вот следующие три арифметические свойства этих чисел на первый взгляд довольно неожиданны:

1. Сумма всех чисел Хивуда правильной раскраски вершин графа триангуляции делится на 4 (это свойство стало известно недавно).

2. Возьмем любую вершину триангуляции; сумма чисел Хивуда граней, сходящихся в этой вершине, делится на три (этот фундаментальный факт был открыт самим Хивудом в 1898 году).

3. Наоборот, если нам удастся подобрать числа ± 1 для граней графа триангуляции так, чтобы они удовлетворяли условию 2), то задача о раскраске решена – можно накладывать триангуляцию на поверхность тетраэдра, соблюдая правило; условие 2) обеспечит выполнимость такого наложения.

Иллюстрацией утверждений 1), 2), 3) может служить, где изображен граф икосаэдра и его правильная 4-раскраска.

Мы докажем только утверждение 1); доказательство утверждения 2) аналогично и составляет содержание задания 6; доказательство 3) не совсем элементарно, и мы его не приводим. Отметим только, что делимость на 3 связана с тем, что в каждой вершине тетраэдра сходятся три грани, а делимость на четыре – с тем, что у тетраэдра четыре грани.

Делимость на четыре

Итак, пусть вершины некоторого графа триангуляции правильно раскрашены в четыре цвета и каждой грани графа соответствует число Хивуда. Докажем, что сумма всех чисел Хивуда делится на 4.

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

Мы докажем, что суммы чисел Хивуда граней, входящих в каждую из этих групп, равны между собой (если какая-то из групп пуста, то естественно считать соответствующую сумму равной нулю; тогда и другие суммы будут равны нулю). Т. к. сумма всех чисел Хивуда распадается на суммы по четырем группам граней, то из равенства этих сумм по группам и будет следовать делимость на 4.

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

Задание 6. Докажите тем же методом свойство 2 чисел Хивуда.

Не раскрашивать, а вычислять.

Свойство 3 чисел Хивуда позволяет заменить задачу нахождения правильной 4-раскраски некоторой арифметической задачей на графе : ищутся значения неизвестных х (чисел Хивуда), удовлетворяющих условиям х = ± 1 и соотношениям 2 делимости на 3. Подсчитаем число неизвестных и число соотношений.

С каждым графом на сфере связаны 4 целых числа: число его вершин - В, ребер – Р, областей, на которые граф разбивает сферу, - Г и число К связных компонент, на которые распадается граф (из одной вершины такой компоненты можно попасть в любую другую вершину той же компоненты, «путешествия» по ребрам графа; в вершину же другой компоненты попасть так невозможно).

Задание 7. Докажите, что для любого графа на сфере

В – Р ∕ Г – К = 1

Задание 8. Докажите, что для любой карты число компонент ее графа столиц и дорог равно 1.

Следствием заданий 7 и 8 является знаменитая теорема Эйлера: Числа В, Р и Г графа столиц и дорог любой карты удовлетворяет равенству В – Р / Г = 2

Задание 9. Докажите, что для любого графа триангуляции сферы справедливо равенство: 2В = Г / 4

Итак, вернемся к нашим неизвестным – числам Хивуда. Кол-во неизвестных равно числу Г граней триангуляции, число соотношений 2) равно числу В вершин триангуляции. Как следует из равенства задания 9, число неизвестных почти вдвое превосходит число соотношений делимости (каждое из этих неизвестных может принимать только 2 значения: +1 и – 1). Поэтому и кажется обоснованной (вот уже более 70 лет!) надежда, что такие числа всегда могут быть найдены.