23
Одна из глав превосходной книги по теории графов *) начинается с описания … болеени:
«Гипотезу четырех красок можно с полным основанием называть еще «болееью четырех красок», так как она во многом похожа на zabолевание. Она в высшей степени заразна. Иногда она протекает сравнительно легко, но в некоторых случаях преобретает затяжной или даже угрожающий характер. Никаких приввок против нее не существует …»
Это высказывание американского математика Ф. Харари, очень похожие на памятку врача-эпидемиология, стоит дополнительmente известного математика и педагога О. Оре:
«Ниболье знаменита среди этих задач **)— проблема четырех красок, впервые поставленная перед математики Де Морганом около 1850 года. Никакая другая пробела не вызывала столь многочисленных и остроумных работ в теории графов. Благодаря своей простой формулировке и разражающей неуловимости она до сих ocasется мощным стимулом исследовании различных свойств графов» ***).
*) Ф. Харари, Теория графов, перевод с англ. изд-во «Мир», М., 1973.
**) Имеются в виду задачи теории графов. — Прим. ред.
***) О. Оре, Теория графов, перевод с англ., изд-во «Нayka», М., 1968.
По-видимому, именно «раздражающая неуловимость» этой проблемы-гипотезы и есть главный возбудитель болеени, описанной Ф. Харари; что же касается «простой формулировки», то она, верятоно, известна большимству читателей: всякую карту на сфере можно раскрасть не более чем в четыре цвета мак, чтобы любые две сессии страны были окрашены в разные цвета.
Имеется в виду, конечно, идеализированная карта: на географических картах один (синей) цвет всегда соответствует водным поверхностям. Мы будем считать, что на наших картах их нет, как нет и стран, состоящих из двух и более не связанных между собой частей (так обстоит дело, например, с Данней и ее заморской провинцией Гренландей). Эти примеры показывают, что понятие карты нуждается в уточнении.
Наша цель — расскаазать об одном из наболее ранних и, пожалуй, наболее остроумных подходов к решению этой проблемы — условно его можно назвать аргументческим; работа в этом направлении продолжается и понятие, и наш расскааз не будет почти ничем напоминать персональноного изложения персоноткрытей.
Условия заданий, решения которых приведены в конце номера, являются фактически частью текста; некоторые из них не сложнее картинок из альбомов «Раскрась сам».
24
Карты на сфере
Картой на сфере мы будем называть всякое разбиение сферы отрезками гладких кривых на конечное число области — стран карты. Относительно этих отрезков кривых естественно предполагается следующие:
- каждый из них не имеет само-пересечений;
- любые два из них любо совсем не пересекаются, либо пересекаются в концевых точках;
- концевые точки любого из них входят в число концевых точек одного или нескольких других отрезков, то есть не является «висяцами».
Ясно, что всякий из этих отрезков, составляющих в совокупности границы карты, является частью границы двух стран (или всей этой границей); также страны мы и будем называть соседними. Отметим, кстати, что строое доказательство утверждения, начинающегося выше словами «ясно, что…» и называемого теоремой Жордана, чрезвычайно громоздко, несмотря на всю его очень видимость.
Сферические карты удобно рисовать в виде разделенного на страны «континента», окруженного «океаном» — одной из страны (на рисунке 1).
Рис. 1. Карта (страны от A до N), правильно раскрашенная в четыре цвета.
Рис. 2. Карта, для которой число не связанных между собой кусков графа границ (число «островов» в «океане» A) равно trem (Krp = 3).
ке 1 страной A; «континентов» может быть и несколько, как на рисунке 2). Страны M и E на рисунке 1 — не соседние, хотя и имеют общую точку границы; страны D и E обладают даже двумя разрозненными участками общей границы.
Потребуем еще, чтобы на карте не было страан, имеющих только одного соседа («острова» в «океане»); карты с таким странами раскрашивать, конечно, ничего не труднее, но изложение осложняет исключения и уточнениями.
Раскраски карт
Раскраску карты в п цветов называем правильной n- раскраской, если любая пара соседних страна окрашена в разные цвета. Нарисовав несколько сферических карта и раскрасив их, вы легко убедитесь в том, что хотя есть карты, для правильной раскраски которых достаточно трех или даже двух красок, но такие карты «нетипичны» — общую нужны четыре краски.
Задание 1. Нарисуйте карту из четырех стран, коморую нельзя было бы правильно раскрасть двумя или третья красками.
Задание 2. a) На плоскости даны n окружности. Доказте, что при любом расположении этих
25
самостояльно найти доказательство этого факта, установлено еще в конце XIX века.
Графы карты
Всякую систему точек и линей, соединяющих некоторые из этих точек и попарно не пересекающихся, называют графом; точки называют вершинами, линей — ребрами графа.
Как видно из определения и свойств 1) — 3) карты на сфере, она характеризуется своим графом границ; его вершины — точки, в которых сходятся не менее трех страны, ребра — участки границ между вершинами (рис. 3). Мы определим также граф столиц и дороге карты; его вершины — «столцы» стран (произвольные, но фиксированные точки, выбранные по одной внутренкой каждой страны), ребра — «дороги», соединяющие столцы соседних стран (по одной на каждой пару соседей) и прохождение через участок границ между ними (рис. 4, 5).
Раскраску карты можно заменить раскраской вершин графа столиц и дороге этой карты; правильность раскраски имеет тот же смысл, если условия две вершины любого гра-
Рис. 3. Граф границ карты.
окружностей образуемую ими карту можно правильно раскрасть двумя красками.
б) Сформируйте условия, необходимые и достаточно для того, чтобы карту можно было правильно раскрасть двумя красками.
В результате многоолетней коротлевой работы было доказано, что любая карта, содержащая не более 41 страны, имеет правильную 4-раскраску. Из этого ясно, что если и существует пример, опровергающий нашу гипотезу, то построить его трудно. Вместе с тем правильная 5-раскраска существует для любой сферического карты. Попытайтесь
Рис. 4. Страны от A до N, их столцы и дороги.
Рис. 5. Граф столиц и дороги карты и его правильная 4-раскраска.
26
Рис. 6. Красыми линяями изображены ребра, достаточно граф столиц и дорог карты рисука 1 до графа триангуляции; ребра эти можно было бы стройть и по-другому (например, ME вместе NI и т. п.).
фа считать соседними, когда они соединены ребром.
Приступая к раскраске вершин графа столиц и дорог карты на сфере, проверим, можно ли его дополнить ребром, не пересекающим других ребер графа, и если можно, то дополним (например, граф на рисуке 5 — ребром AK). Любая правильная 4- раскраска вовь полученного графа будет правильной и для исходного графа; обратное, вообщее говоря, неверно — две несоедние вершины стали соседними и должны быть разноветными. Мы продолжим этот процесс добавления ребер.
Задание 3. Докажите, что этом процесс завершится в том момент, когда граф будет разбиать сферу на кривolineные преуzelники. (На рисунке 6 изображен граф, полученный из графа рисука 5.)
Такой граф называют графом триангуляции сферы *), а треугольник называют граями графа. На рисунке 7 изображен граф вершин и ребер (в привчном геометрическом понимании этих слов — «вершина tetraэдра», «ребро куба») правильного двацатигранника — икосэдра; граь 20 выглядит как внешняя часть треугольника XYZ.
Задание 4. Какой должна быть карта, чтобы ее граф сполщил и dorое был графом триангуляции?
Задание 5. a) Докажите, что граф вершин и ребер правильного восемиранника — окнаэдра — может быть правильно раскраisen треязыми.
б) Сформулируйте условия, необходимые и достаточно для того, чтобы граф триангуляции обладает 3- раскраской.
Геометрия раскраски
Правильно 4- раскраске вершин любого графа триангуляции сферы можно придать простой и красный геометрический смысл. Этим и обьясняется наше желание перейти от графа столиц и дорог карты к его графу триангуляции, хотя сама задача раскраски на первый взгляд условия.
Рассмотрим неокторный tetraэдр, какая из четырех вершин которого раскрашения в свой цвет (рис. 8, д). Предположим теперь, что неокторный граф триангуляции сферы правильно
*) Триангуляция (геодезичный термин) — разбиение местности на треугольники.
27
Рис. 8. Процесс наложения поверхности octаэдра на поверхности tetraэдра.
раскрашен в те же четыре цвета. Тем самым каждой его вершине соответствует вершина tetraэдра, причем любым двум соседним — разные. А это означает, что каждому ребру и каждой грани графа соответствует некоторое ребро и некоторая грань tetraэдра: ребру графа — то ребро tetraэдра, вершины которого окрашены в те же два цвета, что и вершины ребра графа, а грани графа — подобным же образом определенная грань tetraэдра. Мы можем представлять себе это соответствие как наложение раскрашенной трианглрованной поверхности сферы на четырехгранную поверхности tetraэдра, вершины которого символьизуют четыре цвета раскраски. Это наложение можно найти с любой окрашенной в некоторых цветов вершины трианглации, совместив ее с вершиной tetraэдра того же цвета. Переход к соседней вершине трианглации и совмещая ее с соответствующей по цвету вершиной tetraэдра (которая всегда отлична от первой!), мы одновременно получим совмещение ребра трианглации с ребром tetraэдра. Подобным же образом совмещим грань трианглации с гранью tetraэдра, и затем, шаг за шагом добавляем нужного наложения.
Описанный процесс наложения изображен на рисунке 8 (а — д) для поверхности правильно восьми-граника — octaэдра. Внимательно проследив детали этого процесса на примере рисунка 8, нетрудно уяснить себе, почему такое наложение приправлен 4- раскраске возможно и как оно происходит (в частиности, поверхности сферы приходится считать гибкой и допускающей в случае необходимости самопересечения).
Арифметика раскраски
Если при наложении конкретиной вершины трианглации достаточно указаать вершину tetraэдра, в котором она переходит (то есть цвет цвета), а при наложении конкретиной грани недостаточно указаать грань tetraэдра — нужно еще знать, какой сторон она накладывается на эту грань — «лицевой» или «тыльной». Проследить это можно на примере наложения, изображенного на рисунке 8. Сформируем теперь следующие правила.
(*) Если при наложении грани графа призначении на грань метраэдра ее внешняя сторона ледла на внешнюю сторону грани метраэдра, то сопоставим этой грани графа призначении число +1; если же на внутреннюю, то — 1 (см. рис. 8, a).
28
Эти числа называют числами Хивуда раскраски — в честь английского математика П. Хивуда, пionера задач о раскрасках и первоткрывателя «арифметических» законов в проблемы четырехкраскок.
Основное, хотя и волне очевидное свойство чисел Хивуда состоит в следующем:
Лемма. Если числа Хивуда двух соседних граней тренагуляции равны, то эти грани отображаются на разные (но, конечно; всееда соседние) грани метраэдра, если они не равны, то эти грани отображаются на одну грань метраэдра, одна «лицевой» стороной, другой — «мыльной».
Эта лемма только детализирует определение чисел Хивуда; а вот следующие три арифметические свойства этих чисел на первый взгляд довольно неожиданны:
-
Сумма всех чисел Хивуда правильной раскраски вершин графа тренагуляции делится на 4 (это свойство стало известно недавно).
-
Возьмем любую вершину тренагуляции; сумма чисел Хивуда граней, сходящихся в этой вершине, делится на три (этот фундаментальный факт был открыт Хивудом в 1898 году).
-
Наоборот, если нам удостраняться подобрать числа ±1 для граней графа тренагуляции так, чтобы они удовлетворяли условию 2), то задача о раскраске решена — можно накладывать тренагуляцию на поверхность метраэдра, соблюдая правило (*); условие 2) обеспечит выполнимость такого наложения.
Иллюстрацией утверждений 1), 2), 3) может служить рисунок 9, где изображен граф икасэдра и его правильная 4- раскраска.
Мы доказем только утверждение 1); доказательство утверждения 2) аналогично и составляет содержание задания 6; доказательство 3) не совсем элементарно, и мы его не приводим. Отметим только, что делимость на три связана с тем, что в
29
Мы докажем, что суммы чисел Хивуда граней, входящих в каждую их этих групп, равны между собой (если какая-то из групп пуста, то есть не содержит ни одной грани, то естественно считать соответствующее сумму равной нулю; тогда и другие суммы будут равны нулю). Так как сумма всех чисел Хивуда распадается на суммы по четырем группам граней, то из равенства этих сумм по группам и будет следовать делимость на четые.
Выберем произвольным образом две грани tetraэдра. Расмотрим соответствующие им группы граней триангляции и составим суммы чисел Хивуда граней по каждой из этих групп. Возьмем теперь любую графа триангляции, входящую в одну из этих групп, и то ее ребро, которое отображается на общее ребро двух граей tetraэдра, выбранных нами вначале. Расмотрим ту графة триангляции, которая имеет с первой именного это общее ребро; понятно, что такая соедняя грань определяется однозначно. При этом она может отображаться лишь на одну из выбранных граней tetraэдра и поэтому либо входит в ту же группу граней, что и первая,— тогда по лемме числа Хивуда этих граней не равны, либо входит во вторую из этих групп— и тогда по той же лемме числа Хивуда этих двух граей равны. Отсюда следует, что если в одну из двух рассматриваемых нами сумм входит какое-то слагаемое (число Хивуда некоторой грани), то либо в другую сумму входит равное слагаемое (число Хивуда единственной соседней грани из второй группы), либо в ту же сумму входит равное по величины, но противоположное по значку слагаемое (число Хивуда опять единственной соседней грани, но на этот раз из той же группы). Эти равенство двух сумм доказано.
Задание 6. Докажите тем же методом свойство 2) чисел Хивуда.
Не раскрашивать, а вычислять
Свойство 3) чисел Хивуда позволяет зачать задачу нахождения правильной 4-раскраски некоторой арфметической задачей на графе: ищутся значения неизвестных (чисел Хи-