Хроматические числа, или взрослые игры с окрашиванием пространств

Шпаргалки для юных математиков

Середина 19 века. Френсис Гатри, окрашивая в минуты досуга карту графств Британии так, чтобы граничащие между собой графства не имели одинакового цвета, сталкивается с проблемой наименьшего количества цветов, достаточных для выполнения своего развлечения. Ему хватило четырех цветов. Однако быть может, возможны такие каверзно составленные карты, для которых развлекающемуся "маляру" четырех цветов окажется недостаточно? Вскоре он сообщает о проблеме своему брату-студенту, тот - своему профессору, а тот - своему другу-математику. В конце концов эта весть облетела математический мир, но и здесь очень долго никто не мог убедительно показать, сколько же конкретно цветов хватит для такого вот задания отличительного окрашивания государственных территорий на карте какой угодно сложности расположения государств.

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

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

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

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

Вводные сведения

Несложно и понятно разобраться с хроматическими числами n-мерных пространств помогут графы - математические модели системы связей между объектами произвольной природы, в наиболее простых из которых так называемые вершины символизируют исходные объекты и так называемые ребра - это линии, соединяющие вершины, - символизируют конкретные связи между исходными объектами. Если природа исходных объектов есть точки или области определенного пространства, тогда для каких-нибудь умозрительных целей граф может быть элементарно помещен (изображен) в этом пространстве в виде графической конструкции так, чтобы вершины графа оказались в тех реальных точках или областях пространства, которым вершины соответствуют в математической модели; ребра помещенного графа при этом могут не иметь ничего общего со своей приобретенной пространственной ориентацией, а могут иметь таковую, если математическая модель была призвана отразить именно систему пространственных связей между объектами.

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

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

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

Приступаем к исследованию

Хроматическое число точки. В таком пространстве существует всего одна точка. Изображаем в ней вершину графа. Ребер нет вообще, ибо вторую вершину расположить негде. Следовательно хроматическое число точки равно 1.

Хроматическое число прямой. Здесь уже имеется одномерное незамкнутое пространство. Изобразим в произвольной точке прямой вершину графа, а для улучшения зрительного восприятия зададим этой вершине номер 1. Изобразим в другой произвольной точке вторую вершину графа, и соответственно зададим ей номер 2, а затем соединим две эти вершины ребром. Третью вершину графа изобразить на прямой хотя и возможно вне области, занятой только что прочерченным ребром, а также не составит труда беспрепятственно соединить третью вершину с ближайшей вершиной графа, однако никак не удастся соединить эту вершину еще и с наиболее отдаленной от нее вершиной графа, чтобы не нарушить воспрещения пролегать ребрам друг по другу. Обогнуть по кривой препятствующее ребро тоже невозможно, потому что в этом пространстве нет второго измерения, которое позволило бы "выйти за прямую". Следовательно хроматическое число прямой равно 2.

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

Хроматическое число плоскости. Это двумерное незамкнутое пространство, произведением двух прямых определяется его площадь: множество точек, где с любой точкой соседствует подмножество точек, образующих вокруг нее замкнутую линию. Значит если на плоскости изображать граф с оговоренными правилами построения, сколько-то вершин графа связующими их ребрами в конце концов образуют замкнутую линию (контур). Геометрическим путем легко установить, что это может быть только 3 вершины, расположенные по форме треугольника. Зададим этим вершинами соответственно номера 1, 2 и 3. Сформировать контур большим количеством вершин не получится, ибо в возникшем многоугольнике в силу необходимости соединения всех вершин графа с остальными его вершинами неизбежно произойдет воспрещенное пересечение ребер, диагонально соединяющих вершины графа в противолежащих углах многоугольника.

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

Может ли связный граф иметь здесь пять вершин? Нет, потому что если пятую вершину изобразить вне контура, то возникнет конфликт пересечения контура исходящим из пятой вершины ребром, которое должно соединить ее с вершиной графа в центре контура. Внутри же себя контур сам поделен ребрами от вершины в его центре на три треугольного вида области. Если пятую вершину графа изобразить внутри этого контура, она окажется в какой-то из трех областей. Из этой области беспрепятственно доступны только три вершины графа. Соединение с четвертой вершиной возможно только через воспрещенное пересечение собственного контура области. Поскольку у плоскости нет третьего измерения, то не удастся и обогнуть препятствие, изогнув ребро над или под плоскостью. Следовательно хроматическое число плоскости равно 4.

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

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

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

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

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

Высказанное сейчас утверждение попросту понимается так: прямая состоит из соседствующих точек (у каждой есть два несмежных соседа), плоскость - из тем же образом соседствующих прямых, бесконечно большой куб - из тем же образом соседствующих плоскостей, четырехмерный мир - из тем же образом соседствующих кубов, пятимерный мир - из тем же образом соседствующих четырехмерных миров, и так далее. В основе лежит прямая, только объектами на ней выступают или точки, или прямые, или плоскости, или кубы, или миры большей размерности.

Из этого становится ясно, что хроматическое число n-мерного пространства никак не может оказаться меньше, чем хроматическое число (n-1)-мерного пространства. То есть: число цветов для окраски точки - 1, а на прямой имеется хотя бы одна точка, поэтому число цветов для окраски объектов на прямой не меньше 1; в реальности объекты прямой можно всегда окрасить 2 цветами, а на плоскости имеется хотя бы одна прямая, поэтому число цветов для окраски объектов плоскости не меньше 2; в действительности объекты плоскости всегда возможно окрасить 4 цветами, а в кубе имеется хотя бы одна плоскость, поэтому число цветов для окраски объектов в кубе не меньше 4; и так далее.

Так вот уже в трехмерном пространстве хроматическое число равно бесконечности. Следовательно хроматическое число всех пространств большей размерности тоже равно бесконечности.

Вопрос интерпретации

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

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

А как будет в замкнутых пространствах?

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

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

Из упомянутого факта имеется также одно необычное следствие о "двойниках": если пространство замкнуто в каком-то направлении, тогда произвольную точку на линии этого направления можно соединить со всякой другой точкой, тоже находящейся на этой линии, причем сразу двумя отрезками, не пролегающими друг по другу. Иначе говоря, из некоей точки A на замкнутой прямой другая ее точка B "видна" как с одной стороны от точки A, так и с противоположной стороны. Скажем то же самое в еще лучшей форме: если из точки A на замкнутой прямой в одном направлении "видна" точка B и следом за ней точка C, то в противоположном направлении "видна" сначала точка C и следом за ней точка B.

Последнее следствие как нельзя лучше позволяет подойти к рассмотрению хроматических чисел замкнутых пространств.

Хроматическое число замкнутой прямой. Пусть имеется прямая, концы которой где-то в бесконечности замыкаются. Сколько максимально вершин может иметь связный граф, расположенный в этом пространстве? Ответ: 3 вершины, то есть хроматическое число замкнутой прямой равно 3. Объясняется этот результат дальше, только для облегчения понимания разделим построение графа на фазы.

Фаза A: Изобразим где-то на прямой вершину 1 графа и вершину 2 в какой-то другой точке прямой, соединив эти вершины ребром.

Фаза Б: По причине изначальной замкнутости прямой, а равно в согласии со следствием о "двойниках", изобразим на прямой двойников вершин 1 и 2 так, чтобы вершина 2 графа оказалась между вершиной 1 и ее двойником д1, и чтобы вершина 1 графа оказалась между вершиной 2 и ее двойником д2. Договоримся вершины-двойники изображать пунктиром и помечать их номер в виде дX, где X равен номеру той вершины, чьим двойником помечаемая является.

Фаза В: Изобразим вершину 3 графа на прямой где-то между вершинами 2 и д1, соединив ее ребром сначала с вершиной 2, а затем с вершиной-двойником д1. Таким образом, вершина 3 графа оказалась связанной одновременно и с вершиной 1 (посредством ее вершины-двойника), и с вершиной 2. А значит граф продолжает быть связным, так как отдельно стоящая вершина д2 в расчет не берется, ибо она есть всего лишь двойник вершины 2.

Фаза Г: Коль скоро на прямой появилась вершина 3, в отношении нее тоже справедливо следствие о "двойниках". То есть изобразим на прямой где-то между вершинами 1 и д2 двойника д3 вершины 3. Почему именно здесь? Из вершины 2 в одну сторону прямой "видна" сначала вершина 2 и следом за ней 3, и значит в противоположную сторону по причине замкнутости пространства должна быть "видна" сначала вершина 3 (или ее вершина-двойник д3) и следом за ней 2 (или ее вершина-двойник д2). Это синхронно удовлетворяет подобным размышлениям касательно вершины 2 графа.

Можно ли теперь изобразить четвертую вершину вне области, занятой только что прочерченными ребрами, чтобы четвертая вершина графа соединялась с вершинами 1, 2 и 3 или их вершинами-двойниками? Нет, потому что ее вершина-двойник д4 вынужденно окажется на каком-то из ребер, разрушая тем самым непосредственное соединение между соседними вершинами, двойниками которых являются вершины, расположенные по бокам вершины 4.

Обратите внимание, что рассуждение о хроматическом числе замкнутого пространства можно запросто вести на примере незамкнутого пространства. Это наглядно.

Хроматическое число замкнутой плоскости. Плоскость в отличие от прямой может быть замкнута по разным направлениям, а именно по всем сразу или только по определенным из них, разве что в последнем случае оставаясь незамкнутой в прочих направлениях. Элементарным примером тому служит поверхность бесконечно длинной трубки: по направлению вдоль оси трубки эта поверхность не замкнута, по направлению перпендикулярно оси трубки - замкнута, то есть таким курсом можно обойти трубку по поверхности и вернуться в отправную точку.

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

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

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

В каком-то смысле мы уподобимся опытному геометру Джону Хивуду, в свое время молодому доценту Кембриджа, который в уме нашел семицветное расположение территорий на поверхности тора и доказал это исключительно зрительным образом, продемонстрировав найденную окраску. Его идея очень простая. Разметим трубку чередующимися кольцами подобно окраске жезла постового. Теперь замкнем края трубки. Получился тор. Каждая кольцеобразная территория на нем граничит только с двумя другими, которые по бокам от нее. А что если по внешней стороне тора прочертить круг как дополнительную границу? Тогда каждая территория так и граничит с двумя другими по бокам, и еще граничит сама с собой как "сверху" от себя, так и "снизу" от себя, ведь круг по сути превратил кольцеобразные территории в прямоугольные, только расположенные в виде кольца. Что если теперь разрезать поверхность тора по всей длине того внешнего круга и вдоль разреза сдвинуть в противоположных направлениях верхнюю и нижнюю части поверхности, а затем снова склеить по линии разреза? Получится прежний тор, только территории на нем искривлены так, что каждая граничит по бокам от себя с двумя другими, "сверху" от себя - еще с двумя другими, и "снизу" от себя - еще с двумя другими. Но если изначально кольцеобразных территорий было всего 7, они в конце станут граничить все со всеми, и значит для отличительной окраски потребуется 7 цветов.

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

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

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

Хроматическое число замкнутых пространств размерностью n>3. В любом из них хроматическое число равно бесконечности в силу соображения, что n-мерное пространство - это множество (n-1)-мерных пространств. То есть хроматическое число n-мерного пространства (вообще говоря, не имеет принципиального значения - замкнуто это пространство или нет) никак не меньше хроматического числа пространства на единицу меньшей размерности.

Дмитрий Сахань, 29 марта 2007 года