Новиков Ф.А. Дискретная математика для программистов (860615), страница 67
Текст из файла (страница 67)
Множество вершин, покрашенных в один цвет, называетсяодноцветным классом. Одноцветные классы образуют независимые множествавершин, то есть никакие две вершины в одноцветном классе не смежны.Способ явного выражения хроматического числа через другие стандартные инварианты графа неизвестен. Известны только некоторые оценки, часть из которыхприведена ниже.ТЕОРЕМА 1x(G)ДОКАЗАТЕЛЬСТВО^1 +A(G).Индукция по р. База: р = 1 ==> x(G) = 1 & A(G) = 0. ПустьVG ( p ( G ) < p = > X ( G ) < A ( G ) + l ) .Рассмотрим граф G, такой, что p(G) = р.
Тогда\/v Е V (x{G -v)^A(G - v) + 1 ^ A(G) + 1).35710.7. Раскраска графовНо d(v) ^ A(G), значит, хотя бы один цвет в (A(G) + 1)-раскраске графа G - vсвободен для v. Покрасив вершину v в этот цвет, получаем (A(G) + 1)-раскраскуграфа G.•ТЕОРЕМА 2p/Po{G) ^ X{G) < р - f30{G) + 1.ДОКАЗАТЕЛЬСТВО[ p/Po(G) ^ x(G) ] Пусть x(G) =п и V = VIU- • -UV^, где V* — одноцветные классы.Vi — независимое множество вершин, следовательно,^ Po(G). Имеем:Т1Р= X )г= 1^ nPo(G)р/00 < X.[ x(G) ^ р- Po(G) + 1 ] Пусть S <Z V — наибольшее независимое множество, \S\ == /3o(G). Тогда x(G — S) ^ |V" —=p — (3o(G).
Из n-раскраски графа G — S можнополучить (п + 1)-раскраску графа G, так как все вершины из 5 можно покраситьв один новый цвет. Следовательно, x{G) ^ x{G — S) + 1 ^ р — /50 + 1.•10.7.2. Хроматические числа графа и его дополненияХроматическое число графа G и его дополнения G связаны: если в G сравнительно мало рёбер, то и x{G) будет невелико, но тогда в G — много рёбер и x{G)будет близко к р.ТЕОРЕМАПусть х • = x(G), X • = x(G).
ТогдаДОКАЗАТЕЛЬСТВО[рп ^ XX ] Пусть x{G) = п, Vi,...,Vn— одноцветные классы, Pi: = \Vi\. ТогдаJ2 Pi = р, следовательно, т а х р * ^ р/п. Но Vi — независимые множества в G,следовательно, Vi — клики в G. Значит, х ^ т а х р * ^ р/п. Имеем х х ^ п-р/п = р.г= 1[ 2у/р ^ х + X ] Известно, что среднее геометрическое двух чисел не превосходитсреднего арифметического: (а + Ь)/2 ^ \J~ab. Следовательно, х + Х ^ 2 ^2^/р.[ X + X < Р + 11 Индукция по р. База: р = 1 ==>• х = 1 & х = 1- Пусть х +X ^ р для всех графов с р — 1 вершинами. Рассмотрим граф G с р вершинами ивершину v е V. Тогда, очевидно, x(G) ^ x(G — v) + 1 и х ( ^ ) ^ x{G — v) + 1.
Если- и) + +1,1тоX(G) <X{G-v)X+ X+= 1X или( G ) + X ( G )<+++Следовательно, х + Х ^ Р + 1 - Пусть теперь x(G) = x(Gr —г») + 1 и x(Gr) = x ( G r - f ) + l.Положим d: = d(v) в графе G, тогда d = p — d— 1 — степень вершины v в графе G.Имеем d ^ x{G — v). Действительно, x(G) = x(G - v) + 1, и если бы d < x{G - v),358Глава 10. Циклы, независимость и раскраскато вершину v можно было бы покрасить в любой из свободных x{G—v)—d цветови получить x(G - г;)-раскраску графа G.
Аналогично, d = р — d - 1 ^ x(G - v).Таким образом,X + X = X{G) + X(G) = x(G-v)] Имеем 2+ l + x(G-v)++ l ^ d + l + p - d - l + l = p+l.Следовательно,^хх••10.7.3. Точный алгоритм раскрашиванияПоскольку формула для хроматического числа неизвестна, задача нахождениянаилучшей раскраски графа оказывается, как и следовало ожидать, труднорешаемой.Рассмотрим следующую схему рекурсивной процедуры Р:1.
Выбрать в графе G некоторое максимальное независимое множество вершин 5.2. Покрасить вершины множества S в очередной цвет.3. Применить процедуру Р к графу G — S.На псевдокоде процедура Р может быть записана следующим образом.Вход: граф G(V,E), номер свободного цвета г.Выход: раскраска, заданная массивом C\V), — номера цветов, приписанные вершинам,if V = 0 thenreturn { раскраска закончена }end ifS: = Selectmax(G) {S — максимальное независимое множество }C[iS]: = г { раскрашиваем вершины множества S в цвет г }P(G - S, г + 1) { рекурсивный вызов }ЗАМЕЧАНИЕФункция Selectmax может быть реализована, например, алгоритмом 10.3.ТЕОРЕМАЕсли граф G — к-раскрашиваемый, то существует такая последовательность выборов множества S на шаге 1 процедуры Р, что применение процедуры Р к графу G построит не более чем k-раскраску графа G.ДОКАЗАТЕЛЬСТВОПусть имеется некоторая /с-раскраска графа G(V, Е).
Перестроим её в такую не более чем А;-раскраску, которая может быть получена процедурой Р. Пусть V\ С V — множество вершин в данной к-раскраске, покрашенных вцвет 1. Множество Vi — независимое, но, может быть, не максимальное. Рассмотрим множество Vi', такое, что V\ U V\ — максимальное независимое множество(может оказаться, что V\ = 0 ) . Вершины из V / не смежны с Vi, значит, вершины из V\ можно перекрасить в цвет 1. Пусть далееС V\(Vi U Vi') —множество вершин, покрашенных в цвет 2.
Аналогично рассмотрим множествоV2', такое, чтоU— максимальное независимое в G\(Vi U V/), покрасим10.7. Раскраска графов359вершины V2 U V2 в цвет 2 и т. д. Всего в исходной раскраске было к независимых множеств. При перекраске их число не возрастёт (но может уменьшиться,если x(G) < к). На каждом шаге алгоритма рассматривается одно из множеств,следовательно, процесс закончится.•10.7.4.
Приближённый алгоритм последовательногораскрашиванияВ этом подразделе на примере алгоритмов раскрашивания графов вводится понятие приближённого алгоритма в более широком смысле по сравнению с тем, который обычно подразумевается в вычислительной математике и при проведениичисленных расчётов на компьютере.В предыдущем подразделе некоторый алгоритм точного раскрашивания был построен на основе алгоритма выделения максимальных независимых множестввершин, который имеет переборный характер.
Таким образом, предложенныйалгоритм точного раскрашивания также имеет переборный характер. Можно показать, что это не случайно и задача построения точной раскраски являетсяiVP-полпой. При практическом решении ./VP-полных задач целесообразно рассматривать приближённые алгоритмы, которые не всегда находят точное решение задачи (иногда они находят только приближение к нему, и мы не можемзнать этого заранее), но зато достаточно эффективны. Рассмотрим следующийалгоритм последовательного раскрашивания.Алгоритм 10.4 Алгоритм последовательного раскрашиванияВход: граф G.Выход: раскраска графа — массив С : array [l..p] of 1 ..р.for v е V doC[v): = 0 { все вершины не раскрашены }end forfor v € V doA : ={1,...
,p} { все цвета }for и € Г + (и) doA : = A \ {C[u]} { занятые для вершины v цвета }end forC[v)-. = min A { минимальный свободный цвет }end forЗАМЕЧАНИЕТаким образом, красить вершины необходимо последовательно, выбирая среди допустимых цветов минимальный.ОБОСНОВАНИЕВ основном цикле рассматриваются все вершины, и каждая из нихполучает допустимую раскраску. Таким образом, процедура строит допустимуюраскраску.•360Глава 10. Циклы, независимость и раскраска10.7.5. Улучшенный алгоритм последовательногораскрашиванияСледующий алгоритм также строит допустимую раскраску, применяя такую эвристику: начинать раскрашивать следует с вершин наибольшей степени, поскольку если их раскрашивать в конце процесса, то более вероятно, что для них ненайдётся свободного цвета и придётся использовать еще один цвет.Алгоритм 10.5 Улучшенный алгоритм последовательного раскрашиванияВход: граф G.Выход: раскраска графа — массив С : array [l..p] of 1 ..р.Sort(V) { упорядочить вершины по невозрастанию степени }с: = 1 { первый цвет }for v Е V doC[v]: = 0 { все пе раскрашены }end forwhile V ф 0 dofor v e V dofor и e T+(v) doif C[u] = с thennext for v { вершину v нельзя покрасить в цвет с }end ifend forC[v]: = с { красим вершину v в цвет с }={ и удаляем её из рассмотрения }end forс: = с + 1 { следующий цвет }end whileОБОСНОВАНИЕЗаметим, что данный алгоритм отличается от предыдущего тем,что основной цикл идет не по вершинам, а по цветам: сначала всё, что можно,красим в цвет 1, затем в оставшемся красим всё, что можно, в цвет 2 и т.
д.В остальном алгоритмы аналогичны, и данный алгоритм заканчивает свою работупостроением допустимой раскраски по тем же причинам, что и предыдущий.•ОТСТУПЛЕНИЕАлгоритм 10.5 несколько сложнее алгоритма 10.4 и основан на остроумной эвристике.Можно было бы ожидать, что он даст существенно лучшие результаты. Однако прямыевычислительные эксперименты показывают, что алгоритм 10.4 работает почти так же хорошо, как алгоритм 10.5. Таким образом, программистские «хитрости» далеко пе всегдадают практически значимые результаты.36110.8. Планарность10.8.
ПланарностьОбсуждение планарности в этом разделе позволяет решить вторую историческуюзадачу из перечисленных в подразделе 7.1.1, а также подготавливает результаты,необходимые для доказательства теоремы о пяти красках.10.8.1. Укладка графовГраф укладывается на некоторой поверхности, если его можно нарисовать наэтой поверхности так, чтобы рёбра графа при этом не пересекались. Граф называется планарным, если его можно уложить на плоскости.
Плоский граф — этограф, уже уложенный на плоскости.Область, ограниченная ребрами в плоском графе, называется гранью. Грань несодержит других граней. Число граней плоского графа G обозначается f(G).ЗАМЕЧАНИЕВнешняя часть плоскости также образует грань.Пример На рис. 10.8 показаны диаграммы плапарного графа К4 и его укладкана плоскости. Этот граф имеет 4 грани.АР и с . 1 0 . 8 . Планарный граф и его укладкаОТСТУПЛЕНИЕТочное определение некоторых понятий, используемых в этом разделе, в частности, таких понятий, как «поверхность», «область», «граница», выходит далеко за рамки этогоучебника и стандартного курса дискретной математики. Мы полагаемся на геометрическую интуицию читателя и не даём никаких определений. Для понимания простейшихрассуждений этого раздела достаточно неформальных интуитивных представлений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
