Реферат: Раскраски § 53. Правильная раскраска

Глава IX

Раскраски

§ 53. Правильная раскраска

Пусть G — некоторый граф, k — натуральное число. Произвольная функция вида

f:VG->{i, 2, ..., k} назы­вается вершинной k-раскраской, или просто k-раскраской, графа G. Если позволяет контекст, то k в этом определе­нии опускается. Раскраска называется правильной, если j(u) ≠ f(v) для любых смежных вершин и и v. Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым (или раскрашиваемым к цветами). В определении раскраски вместо множества {1, 2, ..., к} можно взять произвольное k-элементное множество.

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

множества вершин VG на не более чем k непустых клас­сов, каждый из которых является независимым множест­вом. Классы этого разбиения называются цветными классами.

Минимальное число k, при котором граф G является k-раскрашиваемым, называется хроматическим числом этого графа и обозначается χ(G). Если χ(G) = k, то граф называется k-хроматическим. Правильная k-раскраска графа G при k = χ(G) называется минимальной.

В качестве иллюстрации рассмотрим граф G, изображеный на рис. 53.1, где указана одна из правильных раскрасок. Меньшим числом цветов этот граф раскрасить правильно нельзя. Действительно, граф содержит цикл (v1,v2, v3, v4, v5, v1) для правильной раскраски которого нуж­но не менее трех цветов, а для вершины v6 требуется новый цвет. Итак, χ (G) = 4.

Рассмотрим некоторые практи­ческие задачи, сводящиеся к пра­вильной раскраске графов.

1. Задача составления расписа­ний. Предположим, что нужно про­честь несколько лекций за крат­чайшее время. Чтение каждой лек­ции в отдельности занимает один час, но некоторые лекции не могут

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

2. ^ Задача распределения оборудования. Заданы множества V = {v1, v2, ..., vn} и S = {s1, s2, ..., sm} работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы будущее время выполнения всех работ было минимальным. Построим граф G, положив VG = V и объявив вершины vi и vj(i ≠ j) смежными тогда и только тогда, когда для выполнения работ vi и vj, требуется хотя бы один общий механизм. При правильной раскраске графа G ра-тьт. соответствующие вершинам одного пвета. Можно выполнять одновременно, а наименьшее время выполне­ния всех работ достигается при минимальной раскраске.

3. ^ Задача о проектировании коробки скоростей. Короб­ка скоростей — механизм для изменения частоты враще­ния ведомого вала при постоянной частоте вращения ве­дущего. Это изменение происходит за счет того, что на­ходящиеся внутри коробки шестерни (зубчатые колеса) вводятся в зацепление специальным образом. Одна из задач, стоящая перед конструктором коробки, заключает­ся в минимизации ее размеров, а это часто сводится к минимизации числа валов, на которых размещаются шестерни.

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

Для некоторых графов, хроматические числа найти не­сложно. Например, χ (Кп) = п, χ (Кп — е) = п—1, χ (Kn,m) =2, χ (С2п+1) = 2, χ (С2n+1) = 3.

Очевидно, что граф является 1-хроматическим тогда и только тогда, когда он пустой, а 2-хроматическим — когда он двудольный и непустой. Обычно 2-хроматический граф называют бихроматическим. Поэтому теорему Кёнига о двудольных графах можно сформулировать в следующем виде:

Теорема 53.1. ^ Непустой граф является бихромати­ческим тогда и только тогда, когда он не содержит цик­лов нечетной длины.

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

Алгоритм последовательной раскраски.

Произвольной вершине v1 графа G припишем цвет 1.

Если вершины v1, v2, ..., vi раскрашены l цветами 1, 2, ..., l, l ≤ i, то новой произвольно взятой вершине vi+1 припишем минимальный цвет, не использованный при раскраске вершин из ее окружения.

Раскраека, к которой приводит описанный алгоритм, называется пдследовательной. Очевидно, что это — пра­вильная раскраска. Для некоторых классов графов (на­пример, полных однодольных) последовательная раскраска является минимальной. В общем случае это не так.

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

Теорема 53.2. ^ Если каждый блок графа к-раскрашиваем, то и сам граф также к-раскрашиваем.

Воспользуемся индукцией по числу блоков рассмат­риваемого графа. Для графа, являющегося блоком, ут­верждение тривиально. Предположим, что теорема верна для графов, состоящих из m ≥ 1 блоков. Пусть теперь G — граф, имеющий ровно m + 1 блоков, В — один из его концевых блоков, Н — объединение всех остальных бло­ков. По индуктивному предположению оба графа В и Н являются k-раскрашиваемыми. Зафиксируем для каждого из них правильную k-раскраску.

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

§ 54. Оценки хроматического числа

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

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

Т
еорема 54.1. Для любого графа G верно неравенст в о

Е> Утверждение теоремы очевидно для пустых графов, [усть G — произвольный χ –хроматический граф χ ≥ 2, а H — его минимальный порожденный подграф, удовлет­воряющий условию χ (Н) = χ. В этом случае χ (H — v) ≤ χ -1. Для любой вершины v графа Н.

П
редположим, что deg Hv1 < χ — 1. Граф Н — v правиль­но раскрасим χ — 1 цветами. Окрасив затем вершину v в один из этих цветов, не использованный при окраске смежных с ней вершин, получим правильную (χ —1)-рас­краску графа Н. Следовательно, deg Hv ≥ χ - 1 и

Как и ранее, через Δ(G) обозначим наибольшую из степеней вершин графа G.

С
ледствие 54.2. Для любого графа G верно нера­венство

Некоторое улучшение последней оценки дает сле­дующая

Теорема Брукса (1941 г.). Если G — связный граф не являющийся полным, и Δ (G)≥3, то χ (G) ≤ Δ (G).

Пусть Δ (G) — m>3. Очевидно, что максимальная степень вершин каждого блока графа G не превосходит m. Поэтому, с учетом теоремы 53.2, достаточно, не теряя общности, провести доказательство для двусвязных графов.

Пусть G — двусвязный граф. Сначала покажем су­ществование в графе G таких вершин и и v, что расстоя­ние d(u, v) равно 2 и граф G — u — v связен. Это очевид­но, если χ (G) ≥ 3.

Допустим, что χ (G)=2. Пусть D — множество всех доминирующих вершин графа G. Поскольку G не явля­ется полным графом, то I VG\D\ ≥ 2. Если D ≠ 0, то в ка­честве вершин и и v можнр взять любые две несмежные вершины из VG\D.

Пусть D≠ 0. Выберем в графе G вершину z степени не менее трех. Если граф G — z 2-связный, то в качестве вершины и возьмем z, а в качестве v — любую вершину, находящуюся от z на расстоянии 2.

Пусть χ(G — z) = 1, А и В — два концевых блока гра­фа G — z. Существуют две вершины и € А и v € B, не яв­ляющиеся точками сочленения графа G — z смежные с вершиной z, иначе оказалось бы, что χ (G)=l.

Легко видеть, что граф G — u — v связен. Действитель­но, удаление вершин и и v не нарушает связности блоч в A и B, поэтому граф G — u — v — z связен. Из того, deg z ≥ 3, следует теперь связность графа G — u — v. Итак, показано существование нужных вершин и и смежных с некоторой вершиной z'. Поскольку граф G — u — v связен, то его вершины можно так занумеровать числами 1, 2, ..., п — 2, что каждая вершина, кроме =z'', будет смежна по крайней мере с одной вершиной, имеющей меньший номер.

Теперь окрасим несмежные вершины и и v в цвет 1. Затем будем последовательно приписывать вершинам 2, zn-3, ..., z1 один из цветов 1, 2, ..., т по следующе­му правилу. Пусть к > 1 и верши­ны и, v, zn-2, zn-3,..., z1 уже окрашены. Так как zk смежна хо­тя бы с одной из вершин с мень­шим номером, то степень верши­ны zk в порожденном подграфе G(u, v, zn-2,..., zn+1,zk) меньше т. Вершине zh присвоим любой цвет, не использованный при рас­краске смежных с ней вершин. Так же поступим и с вершиной z1. Так как deg z1 ≤ m и хотя бы две вершины из окружения вер­ны z1(и и v) окрашены в один цвет, то в множестве цветов (1, 2, ..., т) существует цвет, не использованный в раскраске вершин из этого окружения. Этот цвет и припишем вершине z1. Очевидно, что получена правильная m-раскраска графа G.

Оценка, устанавливаемая теоремой Брукса, достижима. Так, для кубического графа G, изображенного на 54.1, существует правильная 3-раскраска, а правильная 2-раскраска невозможна, ибо это не двудольный граф. Следовательно, χ(G)=3=Δ(G). Однако теорема может дать и завышенную оценку матического числа. Например, из этой теоремы следует, что χ(K1,n)≤n, в то время как χ(K1,n)=2. Две вершины графа называются соцветными относительно некоторой правильной раскраски, если при этой краске они имеют один цвет.

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

Пусть G — связный неполный граф. При χ = χ(G)=2 утверждение тривиально, так как в этом случае G является связным двудольным графом, имеющим не ме­нее трех вершин.

Если χ ≥ 3, то из предыдущей теоремы следует, что граф содержит хотя бы одну вершину v, для ко­торой deg v ≥ χ Поэтому среди смежных с v вершин найдутся по крайней мере две вершины, имеющие один цвет.

Следующая теорема связывает хроматическое число графа с числами его вершин и ребер.

Т
еорема 54.4 (А. П. Ершов, Г. И. Кожухин, 1962г.). ^ Для любого связного (п, m)-графа G верны неравенства

(Напомним, что пара [ ] квадратных скобок означает целую часть числа, а пара { } фигурных скобок —дроб­ную часть.);

Докажем только правое неравенство (доказатель­ство левого громоздко).

Если ^ G — полный граф, то неравенство проверяется непосредственно.

Пусть граф G не является полным и χ(G) = χ. Соглас­но следствию 54.3 при любой минимальной раскраске граф имеет пару соцветных вершин v1 и v2, для которых d(v1, v2) = 2. Построим граф G1, слив v1 и v2 в вершину v. Граф G1 имеет на одну вершину и по крайней мере на одно ребро меньше, чем граф G. Очевидно, что χ (G1)=χ В противном случае, правильно раскрасив χ1 цветами (χ1 < χ) Граф G1, можно было бы построить и χ 1-раскраску графа G. Для этого нужно было бы окрасить вершины v1 и v2 в цвет вершины v, а для остальных вер­шин сохранить их цвета в графе G1.

Операции слияния соцветных вершин будем произво­дить до тех пор, пока не получим полный граф K1 Пусть таких слияний потребуется s. Так как по-прежнему χ(К1) = χ, то l = χ = n-s.

Г
раф К1 имеет l(l -1)/2 = χ (χ - 1)/2 ребер, т. е. на m- χ (χ —1)/2 ребер меньше, чем граф G. Поскольку после каждого слияния число ребер графа уменьшалось хотя бы на единицу, то имеем

П
оэтому, учитывай, что χ — п — s, получаем


Из последнего неравенства следует

Существуют графы, для которых оценки, установленные предыдущей теоремой, достигаются. Таковы, напримep, полные графы.

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

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

Теорема 54.5 (А. А. Зыков, 1949 г.). ^ Существуют графы без треугольников с произвольно большим хроматическим числом.

Для доказательства индуктивно построим последо­вательность S = (G2 , G3 ,...,Gi, ...) графов Gi без тре­угольников, таких, что χ(Gi) = i. Положим G2= K2. Если граф Gi уже построен, i≥2 и VGi = {v1, v2, ..., vn}, то граф Gi+1 определим по следующему правилу: VGi+1 = VGi U V' U v1, V'={v'1,v'2,...,vn}, VGi(\ Vf= ¢ v € VGi U V; каждую вершину vj соединим ребрами с те­ми вершинами из VGt, с которыми смежна vi, в графе Gt; вершину v соединим ребрами с каждой вершиной из V’ (см. рис. 54.2 и 54.3, где изображены графы G3 и G4) . Полученный таким образом граф имеет 2n + 1 вершин.

Покажем, что Gi+1 — искомый граф. Так как вершина v не смежна ни с одной вершиной из множества VG{, а вершины из V’ попарпо не смежны, то никакой тре­угольник в Gi+1 не может содержать вершину v. По той же причине треугольник не может содержать более од­ной вершины из V’. Если же треугольник образовывали бы вершины vj, vk, vi то в графе Gi, вершины vj, vk, viтакже составляли бы треугольник. Поскольку в графе Gi треугольники отсутствуют, отсюда следует, что в гра­фе Gi+1 их также нет.

Т
еперь докажем, что χ (Gi+1)= i+1. В самом деле, любую правильную i-раскраску графа Gi легко продол­жить до правильной (i+ 1)-раскраски графа Gi+1, поло­жив f(vj’) = f(vj) для j = 1, п и приписав вершппе v некоторый новый цвет. С другой стороны, если бы су­ществовала правильная i-раскраска графа Gi+1, то на

раскраску вершин из V’ понадобилось бы не более i — 1 цветов (отличных от цвета вершины v). Изменив окраску вершин графа Gt так, чтобы каждая вершина vj получила тот же цвет, что и vj’, можно было бы построить правиль­ную (i—1)-раскраску графа Gi+1 в то время как χ(Gi) = i

Таким образом, доказано, что граф Gi+1 не содержит треугольников и χ (Gi+1) = i + 1.

Заметим, что графы, существование которых гаранти­руется предыдущей теоремой, являются экзотическими, поскольку для почти каждого графа G верно следующее утверждение: если φ(G) ≤ k, то и χ (G) ≤ :k (Ф.Колайтис, X.Прёмель, В.Ротшильд, 1987 г.).

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

Теорема 54.6 (П. Эрдёш, 1961 г.). ^ Для любых на­туральных чисел l и χ существует χ -хроматический граф, обхват которого превосходит l.

Оценим хроматическое число в терминах числа неза­висимости.

Т
еорема 54.7. Для любого графа G верно


При любой минимальной раскраске множество VG разбивается на χ цветных классов V1, V2, ..., Vn, каждый из которых является независимым множеством. Поэтому ели /Vi/ = ni, то ni ≤ ао для всех i — 1, χ , и

откуда следует левое из неравенств (1).

Перейдем к доказательству правого неравенства. В графе ^ G есть независимое множество вершин S, содер­жащее ровно ао элементов. Так как \G — S\=n — ао, то ,(G — S) < п — ао и, следовательно, χ < n — ао + 1.

С
ледствие 54.8. Если G — связный граф, не являющйся полным, и Δ(G) ≥ 3, то


Рассмотрим последовательность неравенств

Первое из неравенств вытекает из предыдущей теоремы, а второе — из теоремы Брукса.

Дополнением теоремы 54.7 является

Теорема 54.9. Для любых натуральных чисел n, ао и χ , удовлетворяющих неравенствам (1), существует граф порядка п с числом вершинной независимости ао и хро­матическим числом χ.

Рассмотрим отдельно три случая:

1) ао = 1; 2) ао>1 и n = aol, где l — целое число;3) п не крат­но ао.

Из (1) следует, что χ = п, и Кп — нужный граф, так как ао(Кп)= 1 =а0, χ (Kn) = n = χ.

Пусть G — полный l-дольный граф, в каждой доле которого ровно ао вершин. Тогда i(G) = l = n/ao. Фикси­руем некоторую долю U и каждую из не входящих в эту долю вершин будем последовательно превращать в доми­нирующую, добавляя недостающие ребра. На каждом таком шаге хроматическое число возрастает на 1. В результате придем к полному (п — ао+ 1) -дольному графу F, все доли которого, кроме доли U, одновершинные. Очевидно, что χ (F)= n — ao+i.

Если п не кратно ао, то в качестве исходного графа берется n-вершинный полный ([п/ао] + 1) –дольный граф, [п/ао] долей которого содержат по ао вершин. Выбрав в качестве U одну из таких долей, дальнейшие рассуждения проведем так же, как в случае 2. Естественный интерес вызывает стремление уточнить оценку хроматического числа, устанавливаемую теоре­мой Брукса. О. В. Бородин и А. В. Косточка в 1977 го­ду выдвинули следующую гипотезу, пока не доказан­ную и не опровергнутую:

Гипотеза. Если Δ (G) ≥ 9 и φ(G) ≤ Δ (G), то χ (G) ≤ Δ (G)-1.

Приведем без доказательства теорему, дающую асимп­тотику хроматического числа.

Т
еорема 54.10 (А. Д. Коршунов, 1980 г.). Хрома­тическое число почти каждого графа G порядка п удов­летворяет соотношению

. § 55. Хроматический полином

Поскольку t-раскраской графа G является произволь­ное отображение вида VG->{1, 2, ..., n}, то число по­парно различных t-раскрасок этого графа равно числу всех таких отображений, т. е. tn, где n=\VG\. Но если ограничиться только правильными раскрасками, то вопрос о числе различных среди них становится сложным. Ко­личество попарно различных правильных t-раскрасок графа G называется хроматической функцией графа G и обозначается через f(G, t).

Очевидно, что наименьшее из чисел t, для которых f(G, t)≠0, есть χ (G).

Для некоторых графов хроматическая функция опре­деляется совсем легко. Например, f (О„, t) = tn, так как цвета всех вершин пустого графа можно выбирать неза­висимо друг от друга. При правильной раскраске пол­ного графа Кп первая вершина может иметь любой из t заданных цветов, а для окраски каждой из последующих вершин разрешается использовать н
а один цвет меньше, чем для предыдущей. Поэтому f(Kn, t) = t(t—l).... ,(t—n+ 1). Итак, имеем

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

У
тверждение 55.1. Если G = G1 U G2 U ... U Gk — дизъюнктное объединение графов, то

Это утверждение вытекает из того, что раскраска каждой из компонент Gt может выбираться незави­симо.

У
тверждение 55.2. Если G = Gi U G2и графы G1 и G2имеют только одну общую вершину, то

Фиксируем какую-либо правильную раскраску ƒ1 графа G1. Для продолжения ее до правильной раскраски графа G нужно взять такую правильную раскраску f2графа G2, при которой цвет f1(v) вершины v, общей для графов G1 и G2, равен цвету f2(v). Поскольку число правильных t-раскрасок графа G2, при которых цвет вер­шины v фиксирован, не зависит от этого цвета, то для выбора раскраски f2имеется f(G2, t)/t возможностей, откуда и следует равенство (1).

Утверждение 55.3. Пусть и и v — две несмежные вершины графа G. Если G1 = G + uv, a G^ 2получается из графа G в результате слияния вершин и и v, то f(G,t) = f(G1t) + f(G2,t).

Число правильных t-раскрасок графа G, при кото­рых цвета вершин и и v различны, не изменится, если к G присоединить ребро uv. Следовательно, это число равно f(G1, t). Аналогично, число правильных f-раскрасок графа G, при которых цвета вершин и и v совпада­ют, равно f{G2, t). Складывая эти два числа, получим число всех правильных f-раскрасок графа G, т. е. f(Gj).

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

Очевидно

Следствие 55.4. ^ Хроматическая функция любого графа G равна симме хроматических функций некоторого числа полных графов, порядки которых не больше, чем \G\.

Поскольку f(Kn, t) — полином от t, то верно

Следствие 55.5. Хроматическая функция f(G, t) любого графа является полиномом от t.

Поэтому хроматическую функцию f(G, t) обычно на­зывают хроматическим полиномом графа G.

Н
айдем с помощью утверждения 55.3 хроматический полином графа G, изображенного на рис. 55.1. При этом

в
место f(G, t) = f(G1t) + f(G2, t) будем писать G = G1 + G2 или рисовать соответствующие графы. На пер­вом шаге получим ситуацию, представленную на рис. 55.2. Далее см. рис. 55.3. Итак,


Используя утверждение 55.3, можно уточнить вид хроматического полинома. Следующую теорему предла­гаем доказать самостоятельно.

Рис. 55.3

Т
еорема 55.6. Хроматический полином любого (п, т)-графа G, содержащего ровно k связных компо­нент, имеет вид

где а{ —целые неотрицательные числа.

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

Т
еорема 55.7. Граф G порядка п является деревом тогда и только тогда, когда


Докажем только необходимость условия теоремы, а достаточность оставим читателю в качестве упражне­ния. Пусть ^ G — дерево порядка п. Воспользуемся индук­цией по п. При п =1 имеем G = K1, f (G, t) = t, при n = 2 — G = K2, f (G, t) = t(t — 1). Следовательно, при п = 1,2 равенство (2) верно. Предположим теперь, что это равенство верно для любого дерева G порядка m, 2 ≤ m < п, и рассмотрим дерево Т порядка п. Если и — концевая, a v — смежная с ней вершины дерева Т, Т1 = T (u , v), Т2= Т - и,то


и по индуктивному предположению f(T2, t) = t (t — l) n-2. Применяя затем утверждение 57.2, получаем

§ 56. Раскраска ребер

Реберной k-раскраской графа G называется функция φ, ставящая в соответствие каждому его ребру е число φ (е) из множества (1, 2, ..., к). Если φ — реберная рас­краска и ф(е) = с, то говорят, что ребро е окрашено в цвет с. Множество всех ребер, окрашенных в фиксиро­ванный цвет, называют реберным цветным классом. Ре­берная раскраска называется правильной, если смежные ребра имеют разные цвета. Граф, допускающий правиль­ную реберную k-раскраску, называется реберно k-раскрашиваемым. Минимальное число k, при котором граф G является реберно k-раскрашиваемым, называется хрома­тическим индексом (хроматическим классом, реберным хроматическим числом) графа G и обозначается через χ‘(G).Если χ '(G) = k, то граф G называется реберно k-хроматическим.

Поскольку ребра любого графа G смежны тогда, когда смежны соответствующие вершины реберного графа L(G), то χ'(G) можно определить как хроматическое число графа L(G),т. е. χ'(G) = χ(L(G)).

При правильной реберной раскраске каждое множе­ство ребер одного цвета является паросочетанием. По­этому число χ'(G) можно рассматри­вать как наименьшее число паросочетаний, на которые разбивается множе­ство ребер графа G.

Поскольку при любой правильной раскраске графа ^ G ребра, инцидент­ные одной вершине, имеют различные цвета, то χ'(G) ≥ Δ(G). Легко приве­сти примеры, когда χ'(G)> Δ(G) (см. рис. 56.1).

С
ледующая теорема, принадлежа­щая В. Г. Визингу (1964 г.), дает поразительно точные оценки хроматического индекса графа.

Теорема 56.1. Для любого графа G верны не­равенства

Как отмечалось выше, левое из этих неравенств очевидно, остается доказать правое. Оно верно для К2. Предположим, что в общей ситуации правое неравенство не выполняется. Среди всех графов, ему не удовлетво­ряющих, выберем граф G с минимальным числом ребер. П
усть е1 € EG, Н = G — е1. Имеем

Пусть Δ = Δ(G). Зафиксируем правильную раскраску φ’: ЕН -> {1, 2, ..., Δ + 1} ребер графа H и скажем, что цвет q € {1, 2, ..., Δ + 1} отсутствует в вершине v € VH, если φ(е) ≠ q для любого ребра е, инцидентного верши­не v. Так как число возможных цветов больше чем Δ, то в каждой вершине отсутствует хотя бы один цвет.

Пусть е1 = ху1, a s и t1 — цвета, отсутствующие в вер­шине х и в вершине у1 соответственно. Исходя из пары у1, t1, построим индуктивно две последовательности —

вершин у1, у2,…, уk и цветов t1, t2, ..., th,— удовлетво­ряющие следующим трем условиям:

xyi= ei€ EG ( i=1,k);

цвет ti отсутствует в вершине yi(i = i,k);

φ(ei+1) = ti (i = 2, k-1).

Пусть последовательности у1, ..., уi и t1, ...., ti уже по­строены. Если существует такое ребро е = ху € ЕН, ин­цидентное вершине x , что у € (у1, ..., уi), φ(е) = ti, то полагаем уi+1 = y и берем в качестве ti+1 один из цветов, отсутствующих в вершине у. Если же описанного ребра е не существует, то полагаем k = i. Нужные последова­тельности построены.

Далее возможны две ситуации.

Не существует ребра ху € ЕН, для которого φ(xy) = th. Переопределим функцию φ, положив φ(е{) = ti(i = 1, k) и оставив значения на других ребрах неизмен­ными. Получена правильная раскраска φ: EG -> {1, 2, .., Δ + 1} ребер графа G.

Существует ребро ху € ЕН, для которого φ(ху) = tk. Тогда это ребро совпадает с каким-либо из ei (i = 2, к). Пусть, скажем, ху = еj. Снова переопределим функцию φ, полагая φ(ei) = ti (i=1,j —1). Ребро еj пока не окрашено, значения функции φ на всех остальных ребрах не меняются.

Рассмотрим остовный подграф F графа G, ребрами которого служат все ребра графа G, имеющие цвет s или tk. Очевидно, что степень каждой вершины графа F не более двух, и потому каждая его связная компонента является либо простой цепью, либо простым циклом, либо К1. Степени вершин х, yj, и yk в F не более едини­цы, следовательно, эти три вершины не могут входить в одну компоненту. Рассмотрим отдельно два случая.

а) Вершины х и yj, находятся в разных компонентах графа F. В этом случае в компоненте, содержащей вер­шину yj, переставим цвета s и tk, т. е. положим φ(е) = s,
если было φ(е) = tk, и наоборот. Тогда цвет s будет отсутствовать и в вершине x, и в вершине yj, что позволит положить φ(е) = s. Вновь получается правильная
(Δ + 1)-раскраска ребер графа G.

б) Вершины х и yh находятся в разных компонентах графа F. Положим φ(еi) = ti{i = j, k — i), а ребро екоставим пока не окрашенным. Это действие не затраги­вает ребер графа F. Переставим теперь цвета s и th в компоненте графа F, содержащей вершину yh. Теперь цвет s отсутствует и в вершине x, и в вершине ук. По­лагаем далее φ(еk) = s.Построена правильная (Δ + 1)-раскраска ребер графа G.

Итак, в любой ситуации строится правильная (Δ + 1)-раскраска ребер графа G, что противоречит не­равенству (1). Это противоречие и доказывает теорему.

В частности, теорема Визинга свидетельствует о том, что теорема 54.5 о существовании графов без треуголь­ников с произвольно большим хроматическим числом пе­рестает быть верной в классе реберных графов, где хро­матическое число и плотность графа различаются не бо­лее чем на 1. Тем не менее даже в этом случае, т. е. в узком классе реберных графов, хроматическое число определяется сложно: несмотря на то, что величина χ'(G) может принимать только два значения — Δ(G) или Δ(G)+1 — ее определение является весьма трудной задачей.

Найдем хроматический индекс для некоторых клас­сов графов.

Т
еорема 56.2. Справедливы равенства

Д
окажем первое равенство. Пусть

—
разбиение множества ЕК2n+1 на цветные классы. Так как ребра одного класса не смежны, то

о
ткуда получаем

Из теоремы 56.1 теперь следует, что χ'(К2n+1)=l=2n+1.

Перейдем ко второму соотношению. Пусть v — про­извольная вершина графа К2n- Рассмотрим граф G = К2n — v = K2n-1. По доказанному выше ребра графа G можно раскрасить 2п — 1 цветами. Так как степень лю­бой вершины и графа G равна 2n — 2, то некоторый цвет не будет представлен в вершине и. С другой стороны, множество всех ребер цвета ci образует паросочетание в графе G. Поэтому вследствие нечетности \VG\ найдется такая вершина иi, что цвет ci, будет отсутствовать в иiОтсюда следует, что цвета, отсутствующие в вершинах графа G, попарно различны. Для получения требуемой раскраски ребер графа К2п нужно приписать каждому ребру vиi цвет, не представленный в вершине иi.

Теорема 56.3 (Д. Кёниг, 1931). Для любого дву­дольного графа G верно равенство χ' (G) = Δ (G).

Пусть, напротив, утверждение теоремы неверно, и ^ G — двудольный граф с минимальным числом ребер, для которого χ'(G) = ΔA(G)+ 1. Тогда для любого ребра ее EG справедливо равенство χ'(G - е) = Δ(G — e) ≤ Δ(G). Зафиксируем ребро e = uv € EG и правильную реберную Δ(G)-раскраску φ графа G — e и обозначим че­рез Мw множество цветов, отсутствующих в некоторой вершине w. Очевидно, что Ми≠ ¢, Mv≠ ¢. Если Ми ∩ Mv≠ ¢, то ребро е можно окрасить в цвет, принадле­жащий этому пересечению. Поэтому Ми ∩ Mv≠ ¢. Пусть s € Mu, t € Mv. Рассмотрим цепь L, начинающуюся в вер­шине v, ребра которой попеременно окрашены в цвета s и t и которая имеет наибольшую длину среди таких цепей. Вершина и не входит в L, иначе (v, и)-подцепь цепи L вместе с ребром е образовала бы в графе G цикл нечетной длины, что невозможно в двудольном графе. Переставив цвета s и t в цепи L, можно затем окрасить ребро е в цвет s, что противоречит исходному предполо­жению.

Типичная ситуация отражается следующей теоремой, приводимой без доказательства (см. обзор [21]).

Теорема 56.4. Для почти каждого графа G верно равенство

χ’(G) = Δ(G).

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

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

G = G1U G2 U ... U Gμ

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

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

Очевидно, что граф Gi для которого VGi = VG, EGi= Ei, является M-графом, и

G = G1U G2 U ... U Gk (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-графом, по­скольку все его связные компоненты — полные графы. Следовательно, если

V1U V2U...U Vk= VQ(G)

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

В качестве иллюстрации рассмотрим граф G, изобра­женный на рис. 57.1; для него Q(G) = K4, χ 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 = G1 U G2 (5)

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

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

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

Если же ребра е1= u1v1 и е2 = u2v2не смежны, то в графе G(Q) есть еще четыре ребра е3= u1u2, е4= v1v2, е5= u1v2, е6= v1u2. Для каждой пары смежных из этих ребер существует общий цвет, откуда очевидно вытека­ет, что существует цвет, общий для ребер е1 и е2.

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

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

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


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

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

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

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

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

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

Часто пользуются другой формулировкой гипотезы четы