5. Графы. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Теоремы об оценках хроматического числа графа (Лекции)

Лекция 5. Графы. Раскраски графов.Хроматическое число графа. Критерийдвуцветности графа. Верхние оценкихроматического числа графа.Лектор — д.ф.-м.н. Селезнева Светлана Николаевнаselezn@cs.msu.suЛекции по «Дискретным моделям».Магистратура, 1-й курс,факультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suРаскраска графаДвуцветные графыВерхние оценкиРаскраска вершин графаРаскраска графа G = (V , E ) в k цветов — отображениеρ : V → {1, 2, .

. . , k},где из (v , w ) ∈ E следует ρ(v ) 6= ρ(w ).Другими словами, любые смежные вершины обязаны бытьокрашены в разные цвета.Хроматическое число χ(G ) графа G — наименьшеевозможное число цветов, в которое можно окрасить еговершины.ЗадачиРаскраска графаДвуцветные графыВерхние оценкиДвуцветные графыГраф G — двуцветный, если χ(G ) = 2.Теорема 1. Граф G = (V , E ) — двуцветный тогда и толькотогда, когда в нем нет циклов нечетной длины.Доказательство.1. Если в графе G есть цикл нечетной длины, то вершиныэтого цикла в два цвета не раскрасить.ЗадачиРаскраска графаДвуцветные графыВерхние оценкиЗадачиДвуцветные графыДоказательство.2.

Пусть теперь в графе G нет циклов нечетной длины.Будем считать, что G — связный граф, иначе можно провестирассуждения для каждой его компоненты связности.Построим в графе G его остовное дерево D.В любом дереве для каждой пары вершин v , w ∈ V существуетровно одна цепь из v в w .Пусть v ∈ V — какая-то вершина.Рассмотрим раскраску ρ вершин w ∈ V дерева D в два цвета:ρ(w ) = 1, если длина единственной цепи из v в w четна;ρ(w ) = 2, если длина единственной цепи из v в w нечетна.Покажем, что при такой раскраске в графе G не окажетсяребер, оба конца которых окрашены в один и тот же цвет.Раскраска графаДвуцветные графыВерхние оценкиЗадачиДвуцветные графыДоказательство.Предположим противное: пусть (u, w ) ∈ E и ρ(u) = ρ(w ).Рассмотрим в графе G замкнутый маршрут M:сначала цепь из u в v в дереве D,затем цепь из v в w в дереве Dи по ребру (w , u) в u.Длина этого маршрута нечетна, т.к. у длин цепей из u в v и изv в w в дереве D одинаковая четность.Значит, из указанного замкнутого маршрута M можновыделить цикл нечетной длины.

Противоречие.Раскраска графаДвуцветные графыВерхние оценкиОценка хроматического числаТеорема 2. Для произвольного графа G = (V , E ) верноχ(G ) ≤ ∆(G ) + 1.Доказательство: индукция по числу вершин n = |V |.Базис индукции n = 1 верен.Индуктивный переход: пусть утверждение верно для всехграфов с n вершинами.Рассмотрим граф G = (V , E ) с n + 1 вершинами.ЗадачиРаскраска графаДвуцветные графыВерхние оценкиЗадачиОценка хроматического числаПусть v ∈ V и G 0 = G − v .Для графа G 0 верно предположение индукции, т.е.χ(G 0 ) ≤ ∆(G 0 ) + 1 ≤ ∆(G ) + 1.Перенесем раскраску вершин графа G 0 в χ(G 0 ) цветов навершины графа G .При этом вершина v останется неокрашенной.Окрасим вершину v в цвет, который не встречается средицветов вершин, смежных с ней.Тогда χ(G ) ≤ ∆(G ) + 1, т.к.

вершина v смежна не более, чем с∆(G ) вершинами.Раскраска графаДвуцветные графыВерхние оценкиВерхняя оценка хроматического числаТеорема 3. Если в графе G = (V , E ) с ∆(G ) ≥ 3 найдетсявершина v ∈ V , для которой dG (v ) < ∆(G ), то χ(G ) ≤ ∆(G ).Доказательство: индукция по числу вершин n = |V |.Базис индукции верен.Индуктивный переход: пусть утверждение верно для всехграфов с n вершинами.Рассмотрим граф G = (V , E ) с n + 1 вершинами.Выберем v ∈ V с dG (v ) < ∆(G ).Положим G 0 = G − v .Очевидно, что ∆(G 0 ) ≤ ∆(G ).Рассмотрим 2 случая.ЗадачиРаскраска графаДвуцветные графыВерхние оценкиВерхняя оценка хроматического числаДоказательство.Случай 1: ∆(G 0 ) ≥ 3 и в G 0 найдется такая вершинаu ∈ V \ {v }, что dG (v ) < ∆(G 0 ).Тогда для графа G 0 верно предположение индукции иχ(G 0 ) ≤ ∆(G 0 ).Перенесем раскраску вершин графа G 0 в χ(G 0 ) цветов навершины графа G .При этом вершина v останется неокрашенной.Окрасим вершину v в цвет, который не встречается средицветов вершин, смежных с ней.Тогда χ(G ) ≤ ∆(G ), т.к.

вершина v смежна не более, чем с∆(G ) − 1 вершинами.ЗадачиРаскраска графаДвуцветные графыВерхние оценкиЗадачиВерхняя оценка хроматического числаДоказательство.Случай 2: ∆(G 0 ) = 2 или в графе G 0 для каждой вершиныu ∈ V \ {v }, верно dG (v ) = ∆(G 0 ).Тогда ∆(G 0 ) ≤ ∆(G ) − 1.По теореме 2 раскрасим вершины графа G 0 в ∆(G 0 ) + 1 цветов.Перенесем раскраску вершин графа G 0 в χ(G 0 ) цветов навершины графа G .При этом вершина v останется неокрашенной. Окрасимвершину v в цвет, который не встречается среди цветоввершин, смежных с ней.Тогда χ(G ) ≤ ∆(G ), т.к.

χ(G 0 ) ≤ ∆(G 0 ) + 1 ≤ ∆(G ) и вершинаv смежна не более, чем с ∆(G ) − 1 вершинами.Раскраска графаДвуцветные графыВерхние оценкиТеорема БруксаЕсли G = Kn , то ∆(G ) = n − 1 и χ(G ) = n.Если G — цикл нечетной длины, то ∆(G ) = 2 и χ(G ) = 3.Теорема 4 (Брукса). Если граф G не является полнымграфом или циклом с нечетной длиной, то χ(G ) ≤ ∆(G ).ЗадачиРаскраска графаДвуцветные графыВерхние оценкиЗадачи1. Найти хроматическое число графа G = (V , E ), если:1) G — граф2) G — графслучаи);3) G — граф4) G — графслучаи).K4 без одного ребра;K4 без двух ребер (рассмотреть все возможныеK5 без одного ребра;K5 без двух ребер (рассмотреть все возможные2. Какое наименьшее число ребер надо удалить из графаG = (V , E ), чтобы оставшийся граф можно было раскраситьв k цветов, если:1) G = K4 , k = 2;2) G = K5 , k = 3;3) G = K6 , k = 2;4) G состоит из 7 вершин, занумерованных числами от 0 до 6,и ребер вида (i, i + 1(mod 7)), i = 0, 1, .

. . , 6, k = 2.ЗадачиРаскраска графаДвуцветные графыКонец лекции 5Верхние оценкиЗадачи.