Раскраска графов

                                      рис. 1.15

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

§2. Понятие хроматического числа и хроматического многочлена графа

Пусть граф G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета. Если граф G является k-раскрашиваемым, но не является (k-1)-раскрашиваемым, то назовём его k-хроматическим, а число k назовём храмотическим числом графа G и обозначим через χ(G). На (рис. 2.1) изображён 4-хроматический (и, следовательно, k-раскрашиваемый при k>=4) граф; цвета обозначены греческими буквами. Для удобства будем предпологать, что все рассматриваемые графы, не содержат петель; однако мы будем допускать существование кратных рёбер, так как они не влияют на наши рассуждения.

                               рис. 17.1

Ясно, что χ(K_n) = n, и,  следовательно, легко построить графы со сколь угодно большим хроматическим числом. С другой стороны, нетрудно видеть, что χ(G) = 1 тогда и только тогда, когда G- вполне несвязный граф, и что χ(G)= 2 тогда и только тогда, когда G- двудольный граф, отличный от вполне несвязного графа.

При каких условиях граф является 3-хроматическим, неизвестно, хотя легко привести примеры таких  графов; к ним относятся циклические  графы с нечётным числом вершин, колёса с нечётным числом вершин, граф Петерсена. Колёса с чётным числом вершин являются 4-хроматическими.

О хроматическом числе  произвольного графа мало что  можно сказать. Если граф имеет n вершин, то очевидно, что его хроматическое число не превосходит n, а если граф содержит в качестве подграфа K_r, то его хроматическое число не меньше r, однако в таком запасе сведений далеко не уедешь. Значительного прогресса можно добиться, если известна степень каждой вершины графа.

ТЕОРЕМА 1. Если наибольшая из степеней вершин графа G равна p, то этот граф (p+1)-раскрашиваем.

Доказательство: Проведём индукцию по числу вершин в G – граф с вершинами; если из него удалить произвольную вершину v вместе с инцидентными ей рёбрами, то в оставшемся графе будет (n-1) вершин, причём степени вершин по-прежнему не превосходит p. По предложению индукции этот граф (p+1)-раскрашиваем; отсюда получится (p+1)-раскраска для G, если окрасить вершину v цветом, отличным от тех, которыми окрашены смежные с ней вершины (а их не более чем p).▼

ТЕОРЕМА 2: (Брукс 1941). Пусть наибольшая из степеней вершин графа G равна p. Тогда G является p-раскрашиваемым, за исключением тех случаев, когда (i) G содержит в качестве компоненты граф K_p+1 или (ii) p=2  и цикл нечётной длины является компонентой G.

§3. Гипотеза четырёх красок

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

а) некоторая область ограничена не более чем четырьмя сторонами;

б) каждая область ограничена не более чем пятью сторонами;

в) имеется не более 21 вершины степени 3;

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

д) карта —  кубическая, не содержит мостов, и число  сторон каждой области кратно трем. Однако очень мало предложено конструкций, способов, указывающих, как надо раскрашивать некоторые достаточно общие классы карт. Следующая схема продемонстрирует нам, каким образом можно раскрасить в три цвета ребра карты из одного такого класса. Пусть М — кубическая карта, не имеющая мостов. Предположим также, что число ребер на границе каждой области кратно трем, т. е. карта М удовлетворяет условию д). Рингель предложил конструктивную схему окрашивания ребер карты М в три цвета. Перенумеруем цвета 1, 2 и 3, которые циклически упорядочим: за 1 следует 2, за 2 — 3, за 3 — 1. Если е, f и g—три ребра карты М, сходящиеся в одной вершине, то упорядочим их по направлению часовой стрелки, условившись, что, двигаясь от ребра е по часовой стрелке, мы встретим сначала f и потом g.

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

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

                                               рис .19    

Сформулируем  знаменитую теорему Хивуда о раскраске  карт на таких поверхностях. Любая  карта, расположенная на (ориентируемой) поверхности SP рода р (р=1, 2...), может быть раскрашена в число цветов, не превосходящее χ_p, где     

Здесь, как и  раньше, квадратные скобки означают целую часть числа, заключенного в них. Доказательство этой теоремы можно найти в книге Харари. Заметим, что χ_p=4, т. е. справедливость этой теоремы при р=0 была бы равнозначна справедливости гипотезы четырех красок. Но, к сожалению, единственное известное доказательство теоремы существенно зависит от предположения р>0. Хивуд, обнаруживший ошибку в доказательстве Кемпе, сам оказался в какой-то мере в роли Кемпе. А именно он считал, что ему удалось доказать, что число χ для р>=0 достигается хоть для одной карты на поверхности рода S_p, т. е. на поверхности S_p имеется карта, хроматическое число которой равно χ_р. Через год Хеффтер указал неточности в рассуждениях Хивуда и, помимо этого, доказал точность числа χ_p для 1<=р_B=6. В самое последнее время Рингелю и Янгсу удалось доказать для любого целого положительного р, что на поверхности рода р имеется карта, хроматическое число которой в точности равно χ_p.

Рассмотрим  достаточность шести цветов.

ТЕОРЕМА 1: Любая планарная карта может быть раскрашена в шесть цветов.

Доказательство: Проводится индуктивно по числу областей. Если карта состоит не более чем из шести областей, то она, конечно, раскрашивается в шесть цветов. Предположим уже доказанным, что любая карта, состоящая из r областей, раскрашивается шестью цветами. Докажем теперь, что любая карта с r+1 областями обладает этим же свойством. Рассмотрим карту с r+1 областями. Как мы уже видели, вследствие формулы Эйлера хотя бы одна из областей имеет не более пяти сторон. Тогда, разделив эту область на части (рис. 3.1) и присоединив их к соседним областям, получим новую карту с r областями.

                       рис. 3.1 рис. 3.2

Эту карту можно  по предположению индукции раскрасить в шесть цветов. Возвращаясь к  исходной карте с r+1 областями и учитывая, что выделенная область имеет не более пяти соседей, получаем, что для этой области имеется «свободная» краска из числа шести. ▼

Рассмотрим  достаточность пяти цветов.

ТЕОРЕМА 2 (теорема Хивуда): Любая планарная карта может быть раскрашена в пять цветов.

Доказательство: Проводится в терминах дуальных планарных графов индукцией по числу вершин r. Если r>=5 , то теорема очевидна. Предположение индукции заключается в том, что каждый планарный граф с r вершинами можно раскрасить в пять цветов. Пусть G— планарный граф с r+1 вершинами. В графе G имеется вершина v степени 5 или меньше. Граф G — v, получающийся из G удалением вершины v и инцидентных с ней ребер по предположению индукции можно раскрасить в пять цветов. Рассмотрим такую раскраску графа G— v. Цвета будем обозначать через C₁, C₂, C₃, C₄, C₅. Понятно, что если в раскраске вершин, смежных с v, хотя бы один цвет не используется, то его можно использовать для окрашивания вершины и, поэтому если, в частности, степень вершины v меньше пяти, то граф G раскрашивается в пять цветов. Пусть степень вершины v равна пяти, и для вершин графа G, смежных с v, при пятицветной раскраске графа G— v использованы все пять цветов. Пусть смежные вершины v1, v2, v3, v4, v5. окрашенные соответственно в цвета c1,с2,с3, с4, с8, циклически упорядочены (рис. 3.2) (это всегда можно сделать, занумеровав подходящим образом смежные вершины и перенумеровав, если нужно, цвета). Обозначим через G₁₃ подграф графа G— v, порожденный всеми вершинами, окрашенными в один из цветов с₁ и с₃. Этот граф может быть несвязным. Если вершины v₁ и v₃ принадлежат при этом разным компонентам, то граф G—v можно перекрасить в те же пять цветов, поменяв для этого в компоненте графа G13, содержащей v₁, друг с другом цвета вершин с₁ и с₃ (с₁ на с₃ и с₃ на с₁). И тогда для окраски вершины v высвобождается цвет с₁. Рассмотрим теперь случай, когда вершины v₁ и v₃ принадлежат одной компоненте G₁₃. Тогда в графе G— v имеется элементарная цепь, соединяющая v₁ с v₃, все вершины которой попеременно окрашены в с₁ и с₃. Эта цепь вместе с цепью v₃vv₁ образует в графе G элементарный цикл, который окружает либо вершину v₂, либо две вершины v₄ и v₅. В любом из этих случаев вершины v₂ и v₄ нельзя соединить цепью в графе G— и, вершины которой были бы окрашены попеременно в цвета с₂ и с₄. Поэтому рассматривая подграф G₂₄ графа G—v, порожденный всеми вершинами, окрашенными в цвета с₂ и с₄, заключаем, что вершины v₂ и v₄ принадлежат различным его компонентам. Меняя между собой цвета с₂ и с₄ вершин той компоненты подграфа G₂₄, которая содержит вершину v₂, выделяем «освободившийся» цвет с₂ для вершины v.▼ 

Однозначность раскрашивания: Каждая раскраска графа G в k цветов порождает разбиение множества его вершин на k одноцветных классов. Если любой другой раскраске в k цветов индуцированное разбиение на классы будет тем же, то говорят, что граф G однозначно раскрашивается в k цветов. Заметим, что при любой k-раскраске однозначно раскрашиваемого в k цветов графа каждая вершина v должна быть смежна хотя бы с одной вершиной каждого цвета, отличающегося от цвета вершины v. Иначе, перекрасив только одну вершину и, получили бы другую раскраску. Мы здесь приведем некоторые результаты относительно однозначности раскрашивания графа в k цветов.

ТЕОРЕМА 3: При k-раскраске однозначно раскрашиваемого графа в k цветов подграф, являющийся объединением любых двух одноцветных классов вершин, связен.

ТЕОРЕМА 4: Однозначно k-раскрашиваемый граф — (k—1)- связный. Соответствующий подграф из т одноцветных классов (2<=m<=k)–(m-1)- cвязный

ТЕОРЕМА 5: Для каждого k<=3 существует однозначно k-раскрашиваемый граф, не содержащий в качестве подграфа полный граф на k вершинах. Заметим, что здесь речь шла не только о планарных графах. Что касается планарных графов, то поскольку в каждом таком графе обязательно имеется хотя бы одна вершина не более чем с пятью смежными вершинами, планарный граф раскрашивается в k цветов при k>= 6 неоднозначно. Более того, не существует планарных графов, однозначно раскрашиваемых в пять цветов. Известно также, что каждый однозначно 4-раскрашнваемый планарный граф является максимальным планарным.

ТЕОРЕМА 6: Пусть G—3-хроматический планарный граф. Если в G содержится такой треугольник Т, что какую вершину v ни взять, существует последовательность треугольников Т₁,.... Т_m, в которой соседние два треугольника имеют общее ребро, и вершина v есть вершина последнего треугольника Т_m, то граф G раскрашивается в три цвета однозначно.

Однозначно раскрашиваемый в три цвета планарный граф, имеющий не менее четырех вершин, должен содержать по крайней мере два треугольника. В общем же случае раскрашивание карты или графа неоднозначно. Некоторые последние результаты, рассматриваемых в этой работе, осталась проблема раскраски бесконечных планарных графов, в связи с которой можно было бы упомянуть об исследованиях Эрдеша, Хэжнала, Хэймена.  Можно определить несвязное раскрашивание (или D-раскрашивание) графа как разбиение множества вершин на подмножества V₁, V₂, ... V_n, такое, что для каждого i часть графа G, порожденная множеством V_i, несвязна. D-хроматическое число χ_d (G). аналогично хроматическому числу, есть наименьшее число подмножеств при любом D-раскрашивании графа G. D-хроматическое число обладает многими свойствами хроматического числа, но кое в чем есть различие. Например, доказана следующая теорема: если G —планарный граф, то X_d(G)>= 4 Несколько слов об эвристическом методе раскрашивания графа, разработанном Пеком и Уильямсом. Они рассматривают граф и предлагают выполнить для нахождения тех вершин, которые должны быть окрашены в k-й цвет, следующие операции: