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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 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Верхние оценкиЗадачи.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций