§ 58. Раскраска планарных графов

Проблема раскраски планарных графов является од­ной из самых знаменитых проблем теории графов. Воз­никшая в середине прошлого века, она до сих пор при­влекает внимание специалистов и любителей.

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

Позднее понятия карты и ее раскраски были форма­лизованы следующим образом. Связный плоский мульти-граф без мостов называется картой. Грани карты, имею­щие общее ребро, называются смежными. Функция ƒ, ставящая в соответствие каждой грани Г карты нату­ральное число ƒ(Г) € {1, 2, ..., k) — цвет грани Г— на­зывается k-раскраской, если цвета смежных граней раз­личны. Карта называется k-раскрашиваемой, если для нее существует k-раскраска.

В 1879 году британский математик А. Кэли опубли­ковал в первом томе Трудов Лондонского географиче­ского общества статью, посвященную проблеме раскрас­ки карт, в которой сформулировал гипотезу четырех кра­сок (сама задача была известна и ранее).

Гипотеза четырех красок: всякая карта 4-раскрашиваема.

Часто пользуются другой формулировкой гипотезы четырех красок: всякий планарный граф 4-раскрашиваем.

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

Теорема 58.1. Карта G является k-раскрашиваемой тогда и только тогда, когда геометрически двойственный граф G* вершинно k-раскрашиваем.

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

Аналогичным образом можно перейти от правильной ракраски графа G* к правильной раскраске карты G.

Заметим, что существуют плоские графы, которые зльзя раскрасить правильно менее чем четырьмя цветами. Таков, например, граф К4.

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

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

Сначала рассмотрим раскраски планарных графов двумя и тремя цветами.

Согласно теореме Кёнига χ(G) = 2 для непустого графа G тогда и только тогда, когда он не содержит циклов нечетной длины, откуда несложно получить следующее утверждение.

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

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

Пусть внутренняя часть плоскости содержит грани Г₁,Г₂, ..., Г_k с числом ребер в их границах l1, l2, ..., lk соответственно. Так как любое из чисел li четное, то их сумма также четная. Но каждое ребро, не принадлежа­щее циклу С, входит в эту сумму дважды, откуда сле­дует, что длина цикла С четная. Из теоремы 9.1 следует, что рассматриваемый граф является двудольным.

Аналогичное утверждение верно и для односвязных графов, только в этой ситуации каждый мост, входящий в границу грани, учитывается дважды.

Утверждение 58.3. Карта G является 2-раскрашиваемой тогда и только тогда, когда граф G эйлеров.

Учитывая теорему 58.1, нужно лишь доказать, что геометрически двойственный граф G* является двудоль­ным тогда и лишь тогда, когда граф G эйлеров. Послед­нее оставлено читателю.

Теорема 58.4 (М. Крол, 1973 г.). Плоский граф 3-раскрашиваем тогда и только тогда, когда он является подграфом плоской триангуляции с четными степенями вершин.

Необходимость. Будем считать, что порядок рассматриваемого графа более трех (для К3 утвержде­ние тривиально). Пусть вершины плоского графа G правильно раскрашены тремя цветами 1, 2, 3. Рассмотрим произвольную отличную от треугольника грань Г этого графа. Возможны следующие случаи.

1. Границей грани Г является цикл четной длины, вершины которого окрашены в два цвета, например, 1 и 2. Тогда поместим внутри Г вершину w, соединив ее ребрами с каждой из вершин этого цикла, и окрасим эту вершину в третий цвет 3 (рис. 58.1, а).

2. Границей грани Г является 4-цикл C = ( v₁, v₂ , v₃ , v₄ , v₁) , вершины которого окрашены в три цвета, напри­мер, v₁ — в цвет 1, v₂ — в 2, v₃ — в 3, v₄ — в 2. В этом случае поместим внутри грани Г цепь L = (v₁ , w₁ ,w₂, v₃),связывающую несмежные вершины цикла С, имеющие различные цвета. Соединим w₁ и w₂ с вершинами этого цикла, окрашенными в один цвет. Для получения пра­вильной раскраски остается каждой из вершин w₁ и w₂ приписать цвет 1 или 3, однозначно определенный (см.рис. 58.1, б).

3) Границей грани Г являетсяl-цикл, l ≥ 4, верши­ны которого окрашены в три цвета. Поместим в Г вер­шину w, припишем ей цвет 3 и соединим ее со всеми вершинами цикла, имеющими цвета 1 и 2. Грань Г при этом разобьется на несколько граней, границами которых

Рис. 58.1

Будут треугольники и 4-циклы (рис. 58.1, в). С последними поступим так же, как в предыдущих случаях.

Проделав описанные построения для выбранной грани Г, отличной от треугольника, получим новый правильно 3-раскрашенный граф, в котором Г уже разбита на треугольники. Выполнив эти операции для всех таких граней, придем к правильно 3-раскрашенной плоской триангуляции, подграфом которой и будет исходный граф. Покажем, что степени всех вершин этой триангуляции четны. Пусть v — произвольная вершина, имеющая, для определенности, цвет 1. Поскольку G ≠ K3, то вершины; смежные с v, образуют цикл. Так как для их раскраски достаточно двух цветов 2 и 3, то этот цикл имеет четную длину и, следовательно, степень вершины v четная.

Достаточность. Пусть граф G является подгра­фом плоской триангуляции Т с четными степенями вершин. Покажем, что он 3-раскрашиваем.

Поскольку Т — эйлеров граф, то согласно утвержде­нию 58.3 его грани можно раскрасить двумя цветами, например, красным и синим. Ориентируем ребра, ограничивающие каждую красную грань, так, чтобы при; движении по ориентированному ребру грань оставалась справа. Произвольную вершину v графа Т окрасим в цвет 1 и для каждой вершины w рассмотрим любую простую (v, w)-цепь Р. Пусть α(Р) и β(Р) — числа ребер этой цепи, ориентация которых совпадает и, соответственно, не совпадает с направлением цепи от v к w. Припишем вершине w цвет c(w)= 1 + α(Р)— β(Р) (mod3).

Покажем,что выполненная таким образом раскраска окажется правильной. Сперва докажем, что окраска лю­бой вершины w не зависит от выбора цепи Р. Рассмот­рим произвольный простой цикл С в графе Т, ограничи­вающий некоторую область F. Если при движении по ориентированному ребру, принадлежащему С, от его начала к концу область на­ходится справа от ребра, то назовем это ребро a-ребром, в противном случае — b-ребром. Пусть αиβ — числа а-ребер и, соответственно, b-ребер в С, а k и s — числа красных и синих внутрен­них граней в области F. Каждое а-ребро принадлежит красной внутренней грани, а b-ребро — синей внутрен­ней грани.

Вычислим число р ребер, находящихся внутри цик­ла. С одной стороны, они принадлежат красным граням, поэтому р = 3 k — α. С другой стороны, эти ребра принад­лежат синим граням, так что р = 3s — β. Отсюда Зk — α = =3s-β, или α-β = 3k-3s = 0 (mod3).

ПустьР₁ и Р₂ — Две различные простые (v, w)-цепи. Покажем, что c1(w) = c2(w), где

Вначале рассмотрим случай, когда цепи Р₁ и Р₂ не имеют общих вершин, отличных от v и w (см. рис. 58.2, на котором красные грани обозначены буквой К, а си­ние — С).

ПустьС — цикл, полученный объединением цепей Р₁ и Р₂ Для определенности считаем, что ориентация а-ре­бер совпадает с направлением цепи Р₁. Тогда С содер­жит α(Р₁)+β(Р₂) a-ребер и α(Р₂)+β(Р₁) b-ребер. По до­казанному выше

Если цепи Р₁ и Р₂ имеют общие вершины, отличные от v и w, то объединение этих цепей разбиваем на про­стые циклы и цепи, а далее проводим доказательство так, как для случая одного цикла.

Таким образом доказано, что после выбора цвета вер­шиныv остальные вершины графа Т однозначно рас­крашиваются тремя цветами. Покажем, что эта раскра­ска является правильной. Рассмотрим любые две смеж­ные вершины и и w графа Т ,отличные от вершины и. Из простых (v, и)- и (v, w)-цепей выберем кратчайшую. Пусть ею окажется (u, w)-цепь Р. Рассмотрим также (v, и)-цепь, полученную при присоединении к цепи Р ребра wu. Тогда

(знак последнего слагаемого зависит от ориентации реб­ра wu). В случае, когда v = w, последнее соотношение принимает вид с(и)= 1 ± 1.

Отсюда следует, что c(w)≠ с(и), и раскраска графа Т является правильной.

Поскольку G — подграф 3-раскрашиваемого графа Г, то он также 3-раскрашиваем.

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

Теорема 58.5. Любой плоский граф, содержащий менее четырех 3-циклов, 3-раскрашиваем.