Связь матроидных разложений графов с раскрасками

Отметим простые связи, существующие между матро-идными разложениями графов и раскрасками. Напомним, что матроидным разложением графа G называется пред­ставление его в виде объединения

G = G₁ U G₂ U... U G_μ

М-графов, т. е. графов, все связные компоненты которых суть полные графы; минимальное число μкомпонент в матроидных разложениях графа G — матроидное чис­ло μ (G).

Зафиксируем правильную раскраску ребер графа G и рассмотрим разбиение множества ребер на цветные классы:

Очевидно, что граф G_i для которого VG_i = VG, EG_i = E_i, является M -графом, и

G = G₁ U G₂ U... U G_k (2)

— матроидное разложение. Итак, разбиение на цветные классы (1) определяет матроидное разложение (2) гра­фа G. Тем самым доказано

Утверждение 57.1. Для любого графа G верно неравенство

μ(G)<χ’(G)

Учитывая это неравенство и теорему 56.3, получаем

Утверждение 57.2. Если граф G не содержит тре­угольников, то

μ(G)<χ’(G)

Для любого двудольного графа G верно равенство

μ(G) = Δ(G).

Если граф G не содержит треугольников, то его реберный граф L(G) и граф клик Q(G) могут разли­чаться только изолированными вершинами. Следователь­но, если χ q(G) —хроматическое число графа Q(G), то χ q(G) = χ’ (G), так что для графа G без треугольников μ(G)= χ q(G) = χ’ (G). Применяя теорему 56.3, получим второе равенство.

Для матроидного числа произвольного графа хрома­тическое число его графа клик является верхней грани­цей. А именно, верно

Утверждение 57.3. Для любого графа G справед­ливо неравенство

Подграф, порожденный в G объединением клик, входящих в один цветной класс при правильной вершин­ной раскраске графа клик Q(G), является M -графом, по­скольку все его связные компоненты — полные графы. Следовательно, если

V₁U V₂ U...U V_k = VQ(G)

— разбиение на цветные классы множества вершин гра­фа клик, a Gi получается из порожденного подграфа G(V_i) в результате присоединения всех вершин из VG\ V_i как изолированных, то G = G₁ U G₂ U... U G_k — матроидное разложение. Тем самым неравенство (3) доказано.

В качестве иллюстрации рассмотрим граф G, изобра­женный на рис. 57.1; для него Q(G) = K₄, χ q(G) = χ’ (G)= 4, μ(G) =3.

Утверждение 57.4. Для произвольного графа G равенства μ(G) = 2 и χ q(G) = 2 равносильны.

Если χ q(G) = 2, то μ(G) ≤ 2. Но при μ(G) =1 ни­какие две максимальные клики графа G не пересекают­ся, и потому Q(G) —пустой граф, χ q(G) =1. Итак, при χ (G) = 2и μ(G) = 2.

Остается доказать истинность импликации

Доказательство основано на следующей очевидной комбинаторной лемме.

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

Пусть теперь

G = G₁ U G₂ (5)

— матроидное разложение графа G. Достаточно доказать, что любой полный подграф графа G целиком содержится в каком-либо из G_i; если это так, то разложение (5) определяет правиль­ную 2-раскраску графа клик и истин­ность импликации (4) доказана.

Каждому из ребер графа G следую­щим образом припишем один из цве­тов {1, 2} или оба эти цвета. Именно, всем ребрам графа G_i (i = l, 2) при­писывается цвет i. Пусть теперь Q — клика графа G, e_ue₂ € EG(Q).

Если ребра е₁ и е₂ смежны, то в порожденном под­графе G(Q) существует третье ребро е, смежное с ними обоими. Какие-то два из этой тройки ребер имеют общий цвет, поскольку цветов только два. Но концы этих трех ребер вместе входят в одну из связных компонент гра­фа Gi, являющихся полными графами, следовательно, а третье ребро имеет тот же цвет. Итак, для любой пары смежных ребер графа G(Q) существует общий приписан­ный им цвет.

Если же ребра е₁ = u₁v₁ и е₂ = u₂v₂ не смежны, то в графе G(Q) есть еще четыре ребра е₃ = u₁u₂, е₄ = v₁v₂, е₅ = u₁v₂, е₆= v₁u₂. Для каждой пары смежных из этих ребер существует общий цвет, откуда очевидно вытека­ет, что существует цвет, общий для ребер е₁ и е₂.

Доказано, что любые два ребра графа G(Q) имеют общий цвет. В силу леммы 57.5 существует общий цвет, например 1, приписанный всем ребрам графа G(Q). По­следнее означает, что G(Q) содержится в одной из ком­понент графа G₁.

Из утверждения 57.4 вытекает

Следствие 57.6. Если χ(G) = 3, то и μ(G) = 3.

§ 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-раскрашиваем.