4.6. Графы и поверхности

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

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

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

Если многообразие компактно, то оно называется замкнутым. Например, -мерная сфера. В противном случае оно незамкнутое. Замкнутое двухмерное многообразие, гомеоморфное многограннику, называется замкнутой поверхностью. Известно, что каждое замкнутое двумерное многообразие гомеоморфно некоторому многограннику. Примером замкнутой поверхности является двумерная сфера. Плоскость является незамкнутой поверхностью.

Геометрический n-мерный симплекс есть множество точек определенных с помощью линейных независимых точек следующим образом: где есть координата -симплекс замкнут, если выполняется условие

Геометрический симплициальный комплекс К есть конечное множество непересекающихся симплексов, в -мерном евклидовом пространстве таких, что если симплекс принадлежит комплексу, то ему принадлежат и все его грани и два различных симплекса не могут иметь полностью совпадающих граней. Размерность комплекса есть Многогранник есть точечное множество, объединяющее все симплексы

комплекса К и, следовательно, множество точек, принадлежащих некоторому симплексу в К.

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

Рис. 4.13.

Если правый конец прямоугольника, изображенного на рис. 4.13, повернуть на полоборота и затем соединить с левым концом, то мы получим ленту, отличающуюся от обычного кольца, выполненным полуоборотом. Это так называемый лист Мёбиуса. Заметим, что он является односторонней поверхностью, т. е. начав свое движение с некоторой точки поверхности, мы можем вернуться в нее, не пересекая при этом края поверхности. Нетрудно видеть, что лист Мёбиуса является неориентируемой поверхностью. С другой стороны, сфера и плоскость являются примерами двусторонних ориентируемых поверхностей.

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

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

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

Теорема 4.28. Каждый замкнутый многогранник имеет, по крайней мере, две грани с одинаковым числом ребер.

Доказательство. Пусть число ребер грани, причем грани упорядочены так, что [31], где число граней. Если ни одна пара граней не содержит одинакового числа ребер, то для всех Таким образом,

Так как то мы имеем 2, т. е. грань смежна, по крайней мере, с гранями, что невозможно.

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

Замечание 2. Формула Эйлера может быть обобщена на многогранник в -мерном пространстве, если обозначить через число граней 1-й размерности. Например, число вершин. В этом случае формула Эйлера будет иметь вид

где правая часть равна или 2 в зависимости от четности

Возвращаясь в трехмерное пространство, заметим, что формула Эйлера для поверхностей с дырками имеет вид

где число независимых дырок, называемое родом поверхности. Род поверхности — это наибольшее число простых замкнутых кривых на поверхности, которые не разъединяют поверхность. Сфера является поверхностью нулевого рода, так как любая замкнутая кривая на этой поверхности разъединяет ее. Тор является поверхностыд 1-го рода. Любая поверхность рода эквивалентна сфере с ручками (подобно ручке на чайной чашке).

Для неориентируемой поверхности правая часть формулы Эйлера заменяется на где род поверхности.

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

Теперь мы получаем формулу Хнвуда, которая для определяет достаточное число цветов для раскраски карты на поверхности рода в виде

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

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

Теперь для однородной карты степени 3 мы имеем где а — среднее число ребер для данной грани. Подстановкой в формулу Эйлера для поверхности рода мы получим

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

достаточно для раскращивания граней. Если то из рис. 4.14 следует, что всегда

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

Рис. 4.14.

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

Необходимость доказана для различных значений и требует построения специальных карт (см. [2]).

Необходимость семи цветов для тора показана на карте рис. 4.15. Из формулы Хивуда следует также их достаточность.

Рис. 4.15.

4.17. Показать, что для раскраски карты на листе Мёбиуса необходимо шесть цветов.

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

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

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

ЛИТЕРАТУРА

(см. скан)

(см. скан)

(см. скан)