Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 38
Текст из файла (страница 38)
Оценим хроматическое число графа через его параметры. Теорема 3.32. Если максимальная стпепень вершин графа С ровна я(0), то хроматпичгское число этого графа не превышает величины г(0) + 1: ЦС) < г(0)+1. (3.17) Для большинства графов эху оценку можно улучшить. Теорема 3.33 (Брукс). Граф С со степенью г(С) является г-раскрашиваемым, эа исключением двух случаев: 1) при в(0) > 2 граф С содержит компоненту, являющуюся полным графом плотности, равной г(0) + 1; 2) при г(С) = 2 граф С содержит компонентпу, являющуюся циклом нечетпной длины.
Оценки, полученные с помошью этих хеорем, дают, однако, хорошее приближение лишь тогда, когда степени всех вершин графа имеют близкие значения. В противном случае оценка может быть значительно завышена. Например, граф Кенига Кь „(эаеэдный граф) согласно теореме Брукса является п-раскрашиваемым, в действительности же он двудольный, и поэхому для его раскраски достаточно двух красок. Теорема 3.34 (Берж, Оре, Харрари). Для любого графа С = = (1т, у) — < Ь(0) < !1т! — 1уо+ 1, И Фо (3.18) где фо — вершинное число независимости графа. Теорема 3.35 (Гаддум, Нордхауз).
Сумма и произведение хроматпических чисел графа С = (1т, Щ и его дополнения С = = (У, У) удоглетворяютп неравенствам ~2ДГ!~ < Ь(0) +ЦС) < !'Ьт!+1, !,!„,.„,.-„(! !+ ),' (3,19) где ] ! — целая частпь. Теорема 3.38. Хроматпическое число ЦС) графа С удовлетпгоряет следующим соотношениягс Ь(0) < Н(Ся) ' 1ь(Сь), С = Са О Сь; (3.20) ЦС) = ЦСа) + Ь(СЬ)1 С = Сг +СЬ1 Са П СЬ = йЬу (3.21) Ь(0) < т1п (Ь(0,), Ь(Сь)), С = С, х Сь.
(3.22) Аналогично раскраске вершин графа определим раскраску его ребер. Раскраской ребер графа С = (У, У) называется разбиение сигнатуры УУ графа У = (.1 Ц, У; П(Утя — И, а ф ф, при котором кажт дое подмножество Ц не содержит ни одной пары смежных ребер. Каждому подмножеству сопоставляется краска, при эхом ребра, принадлежвшие одному и хому же подмножеству, называются соцветными. Граф С называется реберно х-раскрашиваемым, если его ребра можно раскрасить Й краскамн хак, чтобы никакие смежные ребра не были окрашены одним цветом. Хроматическим классом (хроматпическим индексом) графа называется числа Й такое, что граф является реберно Й-раскрашиваемым, но его ребра не могут быть раскрашены в й — 1 цветов.
Хроматический класс графа С обозначается Н(0). Например, хромахические классы для двудольных графов Н(Кь,а) и Н(Кг,з) равны соответственно 4 и 3. Хромахический класс Н(0) графа С совпадает с хроматическим числом графа С' = (Х', Г'), определяемого следуюшим образом: вершины Х' взаимно однозначно соотвехствуюх ребрам графа С и х', с Гх~ь, когда соответствуюшие ребра графа С смежны. Следовательно, задача определения хроматического класса сводится к аадаче определения хроматического числа. 33.7. Раскраска вершин и ребер графа 211 210 Гл.
3. Теория графов и мавра ое В связи со сведением раскраски ребер графа к раскраске его вершин рассмотрим важное свойство графов — свойство реберноети. Граф С = (У, (>') обладает свойством реберноети тогда и только тогда, когда сушествует взаимно однозначное соответствие, при котором каждая вершина о; 6 У графа»з сопоставлена ребру й 6 1>' графа д = (У, 1>), при этом матрица смежности вершин графа»з подобна матрице смежности ребер графа сз. Дде матрицы подобны, если они совпадают с точностью до перестановки строк (столбцов).
В общем случае граф д может быть мультиграфом, т. е. графом с параллельными ребрами. Теорема 3.37. Граф»з обладаетп евойетпвом ребернаетпи пюгда и пюлько пюгда, когда он раэложим по аддитивной операции "объединение" С = (з Г; на полные подграфы (Г;), в >соторые каждая вершина входитп не более двух раз. Пример 3.13 (рис. 3.37). Рассмотрим свойство ребериостн графа С: (У У), Ь> кс (а, Ь, с, >4, е), У ((а, Ь), (а, с), (а, б), (а, е), (Ь, с),(Ь, а), (с, а), (с, е), (а, еЦ. Граф С разложйм на два полных подграфв, С Г »з Гв (рис.
3.37,а): Г =(1,У), \ (а,Ь,с,б), Уз = ((а, Ь), (а, с), (а, аМ) > (Ь, с), (Ь, >4)> (с, »>Ц> Гл=(Уя Уд) Уя=(о,~ б ) Уд = ((а с) (о, >4), (а, е), (с, >4), (с, е), (>4, еЦ, У г> $~в = (а, с, б). Условия теоремы 3.37 выполнены, граф С обладает свойством реберносп», соответствусошвй ему реберио проивводный граф С изображен на рнс.
3.37, б. С С б ! Г» б Рнс. 3.38 Рнс. 3.37 Если наложить ограничения на декомпозицию исходного графа Г', а именно при разложении графа С на полные подграфы не допускать повторения ребер в полных подграфах, то реберно производный граф С не будет содержать параллельных ребер, т. е. он будет обыкновенным графом. Теорема 3.38. Граф С обладает свойством реберноети и еоответетпвуюи4ий ему реберно производный граф 0 являетпся обыкновенным графом тогда и только тпогда, когда еуи4еетвуеп! разбиение сигнатуры графа С на полные подграфы, в которые каждая вершина входит не более двух раз. Пример 3.14.
Определим, имеет ли граф С = (У, У) (рнс. 3.38) реберно проивводный граф. Граф С можно разложить иа 4 полных подграфа: С= )з) Гь (а, Ь), (а, е), (Ь, е)); (а, с), (а, б), (с, б); (Ь, с), (Ь, Ь), (с, Ь) (б, е), (б, Ь), (е, /сЦ. ге Г. >=1 И! =(а,Ь, е), >'з = (а, с, а) > Ъ~з м (Ь, с, Ь), $» =(а,е,й), б У входит в Г! =(У>, У!); Гз = (Ь>з, Уз), Гз = (с>з, Уз), Г» ш (У»', У»), Паж ая ве ш У! св Уз = Уз = У» = л р инею полные под р фы „,, 4, подво раза (рис.
3.38, а). Условия теоремы 3.37 выполнены, резерва производный граф С изображен на рнс. 3.38, б. При построении реберно производного графа С = (У, (>) ка- ждой вершине о; 6 У со степенью л(и;) ) 1 сопоставляют вы- деленный в графе Гу полный граф Г; С сс. Ребра, инцидентные вершине о; 6 У, взаимно однозначно соответствуют вершинам графа С, образующим этот полный подграф р;. Вершина о; 6 У со степенью в(от) = 1 коинцидентна ребру р, которому соответствует вершина о 6 У, вхот 3 дяшая в выделенные полные подграфы один раз.
о 3 5 Ь Используя свойства реберной раскраски гиперкуба> предложим оптимальный алго- ритм вложения графа С в гиперкуб. Оче- ь видно, что хроматический класс Н(Н„) и- мерного куба Н„равен его размерности п: Рнс. 3.39 Н(Н„) = и. При этом соцветные ребра гиперкуба образуют его разрез. Например, при и = 3 каждое множество соцветных ребер а = ((О, 4)> (1> 5)> (2, 6)> (3, 7)) > Ь = ((О, 2), (1, 3), (4, 6), (5, 7) ), е = ((О> Ц, (2, 3) > (4, 5), (6, 7)) образует разрез (рис.
3.39). В то же время множество ребер ((1, 3), (2, 3), (5, 7), (6, 7)) также является разрезом, хотя при этом ре- бра не являются соцветными: не образуют пустого реберного под- 33.7. Раскраска вершин и ребер грофа 213 1л.3. Теория графов и могрофоа графа. Отсюда нетрудно доказать теорему 3.39, введя понятие паросочетательного разреза. Разрез называется паросочегпагпельным, если его ребра образуют пустой реберный граф.
Теорем а 3.39. Граф С вложйм в гиперкуб тогда и только тогда, когда множесгпво пустых ргберных подграфив включает все парасочггпагпгльные разрезы зтого графа. Из этой теоремы получаем алгоритм вложения графа С в гиперкуб. 1. Строя соответствуюшее дерево, выделяем реберно независимые подмножества (пустые реберные подграфы). Ребрам каждого из этих подграфов можно сопоставить одну и ту же краску. 2. Из полученного в п.
1 списка выделяем подмножества, каждое из которых образует разрез графа ст. 3. Используя выделенные в п. 2 подмножества, раскрашиваем ребра заданного графа. 4. Проверяем, образует ли каждое множество соцветных ребер разрез графа. Если нет, минимальным сужением сигнатуры или расширением носителя эквивалентируем [заменяем эквивалентом в смысле решаемой задачи) заданный граф С графом б, удовлетворяющим условиям теоремы 3.39. Если да, переходим к п. б.
б. Производим фактическое вложение графа, полученного в и. 4, в булеза пространство. При этом краска ребра взаимно однозначно соответствует разряду двоичного вектора, идентифицирующего вершину гиперкуба. При переходе через ребро (и;, иу), окрашенное в с-ю краску, двоичные коды вершин и; и и отличаются в е-м разряде. 6. Конец. Пример 3.15.
Вложим граф С (рис. ЗАО,а) в булеза пространство Н, испольвуя рассмотренный алгоритм. 1. Дерево, определяюшее распределение пустых реберньпс подграфов, содержит 20 висячих вершин, каждая ив которых соответсгвуег пустому ребериому подграфу (рис. 3.40,6). 2. Четыре пустых реберных подгрефа образуют раареаы заданного графа: Ес ж (2, 5з 8), Ез ш (1, 6, 8), Ез = (4, 7, 9), Ес = (3, 7, 10), 3. Раскрашиваем ребра заданного графа 17 с помошью покрытия столбцов строками двоичной таблицы, в которой строке взаимно однозначно соответствует пустой реберный граф, полученный в и.
2, столбду — ребро, а на пересечении с-й строки с у-м столбцом стоит 1, если с-й пустой реберный подграф содержит у'-е ребро, и 0 — в противном случае (табл. 3.4). Имеем штыре раскраски Ри(С) графа Й: лс(а) = ((2, 5, 8), (1, 6), (», т, 9), (з, 1о)), Не(С) ш ((2, 5, 8), (1, 6), (4, 9), (3, 7, 10)), л,(с) = ((2, 5), (1, 6, 8), (», т, 9), (з, 10)), я,(с) = ((2, 5), (1, 6, 8), (», 9), (з, т, 10)). Таблица ЗА 4.
Проверяем, образует лн каждое множество сопветньпс ребер разрез графа. В каждой раскраске имеются соцветлые вершины, не явлшошиеся разрезом за- б Рис. 3.40 (1, б] (2, 5) (7) (8) (3, 4) (9, ! Рис. 3.41 Гл. 3. Теория графов и моерафоа 214 33.7. Раскраска вершин и ребер графа денного графа: (1, 6)„(З, 10), (4, 9), (2, 5). Пля выполнения условий теоремы 3.39 необходимо улзлить из графе С любой злемент миевестве ((7), (8», (3, 4), (9, 10), (3, 10), (4, 9)), выбрав соответствуюшую раскраску ребер графе С (рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
