Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 43
Текст из файла (страница 43)
Частным случаем частичного упорядочения мографа является транзитивная ориентация графа. Здесь мограф рассматривают без моделизации, т. е. словами полученной модели являются макси- мально полные подграфы графа, над которым проводится транзи- тивная ориентация. Для этого случая имеем три запрещенные фигуры. Первыми двумя фигурами являются фигуры типа (,)д и Яц, рассматривае- мые без моделизации, третьей фигурой — граф (х без модели- М эации, являющийся композицией неустойчивой запрещенной фи- гуры типа А и устойчивой фигуры типа Б.
Рассмотрим применение теоремы при трангитивиой ориеитаиии грифов на примере представителя одного иа транвитивно иеориентнруемых семейств гра- фов — графа, дополняющего пипл, длина которого превышает 5, до пол- ного. Граф С = ()г, () ) навывагтся троновтоеяо ориентированным, если ив (оь ог) Е () и (оу, оа) Е () слелует (оь оа) Е (). Рассмотрим пипл, ллина которого равна б.
Этот пипл до полного дополняет граф С, ивобранениый на рис. 3.57, о. 238 Гл.3. Теория графов и могрофов 13.10. Логарифмические оценки ароматического числа 239 Применяя алгоритм выделения полныл подграфов к рассматриваемому графу (рис. 3.5Т, б), получаеммноиество полнил полграфов ((Ь, И, у), (о, с, е), (о, д), (Ь, е), (с, у)), которое образует сигнатуру мографа (рис. 3.57, в)." С~ = (1г, Яа, Яз), 1г = (о, Ь, с, д, е, зз), Яз = ((Ь, д, у), (о, с, е ), оз = ((о, И), (Ь, е), (с, У3).
Мограф ьз = (зг, Яз, Яз) солериит дае устойчивые аапрешенные фигуры паза Б: С3пз = (Ь, д, у), (Ь, е), (а, д), (с, У)) ь)гз = ((о, с, е), (о, И), (с, у), (Ь, е)). Расщепляя одну из вершин треугольника каидой аапрешенной фи. гуры, получаем транзитнвно ориентированный граф. Воамоииы девять способов расщепления. В вандом из кил следует расщеплять две вершины, так как зги треугольники ие пересекаются. Для определенности выберем вершины с (с 3) е с' 4> д Рис. 3.57 и у (рис.
3.5Т,г), В результате получаем транантивио ориентированный граф (рис. 3.57, д), который паоле удаления транзитиано ааьаякаюшит дуг преобразуется в структурный граф (рис. 3.57, е). 23.10. Логарифмические оценки хроматического числа.
Решение проблемы четырех красок Как уже отмечалось, частным случаем квазиполной модели является квазиполный граф, который не следует путать с критическим графом, введенным Г.А. Дираком (39]. Критический граф изменяет хроматическое число при удалении хотя бы одной вершины. На рис. 3.38 приведен критический граф, но не квазнполный. Действительно, сужение сигнатуры графа удалением одного или всех ребер множества ((а, у), (Ь, у), (с, у), (а, у), с Ь (с, Я не меняет хроматическое число, оно остается постоянным, равным 4; нри удалении же любой вершины хроматическое число уменьшается на 1.
Теорема 3.48 (основноесвойство квазиполных графов). Для любой вершины и; квазиполкого графа (ьз найдется такая раскраска его вершин, при конторой не существует вершины и (сг ~ з), соцветнобсизч Доказательство проводим от противного. Пусть такая раскраска не существует, т. е. при каждой раскраске вершин графа Я найдется вершина и (сг 55 з), соцветнвя с и;. Но тогда после удаления вершины и; и ребер, инцндентных вершине и;, получаем, что число красок не изменяется; это противоречит определению квазиполного графа.
Следствие. При удалении любого ребра из квазиполного графа его квазиплогпиость уменьшается на 1. Теорема 3.48 'лежит в основе доказательства структуры квазиполного графа фд) квазиплотности д; квазиполный граф Я(д) состоит из основания — квазиполного графа Я(д — 1), замещаюшего и замыкаюшего слоев. Вершины замешаюшего слоя согласно основному свойству квазиполных графов взаимно однозначно соответствуют вершинам основания; при этом соответствующие вершины смежны с одними и теми же вершинами, принадлежащими основанию Я(д — 1).
Вершины замешаюшего слоя являются как бы "двойниками" вершин основания. Замыкающий слой представляет собой вершины, конуснруюшие вершины замешающего слоя, и число их колеблется от (ч(ч )) до 1, конусируюших весь замешаюший слой. Рассмотрим образование квазиполного графа ф2, зс), обладающего экстремальными свойствами, т. е. мощности его носителя и сигнатуры являются минимальными по сравнению с другими квазиполными графами плотности 2 и порядка )с. Согласно теоре- 13.10. Логарифмические оценки хроматического числа 241 240 Гл.
3. Теория графов и могрвфов ме 3.48, чем меньше мощность носителя или сигнатуры основания Я(2, Й вЂ” 1), тем меньше соответствующие мощности квазицолного графа Ч(2, »»с). Основанием графа Я(2, 1) является граф Я(2, О) (рис. 3.44, а), представляющий собой ребро 1а, Ь); замешающий слой — две вершины а' и 5», которые соответственно смежны с 5 и а. Замыкаюший слой представляет собой вершину, конуснруюшую вершины а' и 5'. В результате получен цикл длины 5 (рис. 3.44, б), Аналогично, продолжая процесс построения графов и взяв в качестве основания Я(2, 1) (рис.
3.44, б), получаем граф Я(2, 2) (рис. 3.44,в); взяв граф Ч(2, 2) в качестве основания, получаем квазиполный граф Я(2, 3) (рис. 3.44, г). Продолжая этот процесс, можно построить квазиполный граф Я(2, Й) с минимальными мошностями носителя и сигнатуры для любого Й. Определим зависимость минимальной мощности носителя графа Я(2, А) от его порядка й. Имеем Следовательно, ~1мин(Я(2, 1с))~ =2 (2 (...2 (2 2+1)+1...)+1)+1ее 1+1 =2'+'+2"-~+2~-~+21-~+...+21+2оке ~~ 2 -2 1=0 21+1 .
2 20 — — 2 =4 ° 2 — 2 — 1=3 ° 2 — 1. 2 — 1 Таким образом, окончательно имеем ~1мин(Я(2, Й))~ = 3. 2" — 1. (3.36) Найдем зависимость минимальной мощности сигнатуры графа Я(2, Й) от его порядка. Согласно структуре квазиполных графов и их основному свойству сумма мошностей сигнатуры основания Я(2, Й вЂ” 1) и сигнатуры замешаюшего слоя равна утроенной мощности сигнатуры основания Я(2, Й вЂ” 1) при построении графа Я(2, Й) с минимальной мощностью сигнатуры, а мошность сигнатуры замыкаюшего слоя согласно (3.36) равна мощности носителя основания 3 2" 1 — 1. Отсюда минимальная мошность сигнатуры ~Ум„„(ф2, »с))~ графа Я(2, й) равна: 1 при Й=О, 3 1+3 2о — 1прий=1, 3 (3 ° 1+ 3 2о — 1) + 3 21 — 1 при 1с = 2, 3 (3 (3 ° 1+ 3 ° 2 — 1) + 3 ° 21 — 1) + 3 ° 2т — 1 при й = 3, 3.
(3. (3. (3 3. (3.1+ 3. 2о 1)+ 3.21 1)+ Ь-1 скобки + 3 2т — 1)+...+3 2~ з — 1)+3 2~ ' — 1 при 1с = Ус. Последовательно упрошая выражение для ~У„„„Я(2, Й))~, получаем )умчи(я(2~ й))~ = 3~+3~.2о З~-1+3~-1 21 ЗЬ-э+3~-т 2г ь Ь-1 Зв-з + + 31 2~-1 Зо Зь + ~, 3 2а- ~ 3 ям 1 'мО =3 +З.(3 — 2 ) — 0,5 (3 — 1), 2~(Умчи(6)(2,й))~=7 3"-6 2" +1. (3.37) Квазиполный граф Я(р, »с), обладающий рассматриваемыми экстремальными свойствами, получается суммированием квази- полного графа Я(2, к) и полного графа плотности р — 2: Я(2, Й)+Я(р — 2, О) = Я(р, Й).
(3.38) Обобшением (3.38) является следующая теорема. Теорем а 3.49. Сумма квазиполных графов является квазиполиым графом: Я1(р;, 1с;) = Я ~~» р;, ~~»»»с1 . (3.39) 1 1 \ Согласно (3.38) минимальная мощность носителя квазиполного графа Я(р, »с) есть ~Ъ 1„(Я(р, Й))/ =3 (2" — 1)+р. (3.40) Минимальная мошность сигнатуры Я(р, Й) представляет собой сумму минимальной мощности сигнатуры графа С»(2, Й) и минимальной мошности сигнатуры полного графа плотности р — 2, каждая вершина которого конусирует граф Я(2, к). Согласно (3.36) и (3.37) имеем ~Гу »„Д(р, й))~ = О, 5 (7 . 3 — 6 .
2 + 1) + +0,5. (р — 2) (р — 3)+(р — 2) (3 2 — 1). 13.10. Логарифмические оценки хроматического числа 243 242 Гл.3. Теория графов и мографог Окончательно получаем 2~ Ц„;„Я(р, /с))~ = 7 3" + 6 2" (р — 3) + (р — 3) — р + 2. (3.41) Согласно (3.40) любой квази~олный граф первого порядка, имеющий плотность р, содержит не менее р+ 3 вершин. Граф Я(р, 1), имеющий ровно р+ 3 вершин, является суммой цикла длины 5 и полного графа с плотностью р — 2; Я(р, 1) = Я(2, 1) + Я(р — 2, 0).
Соотношения (3.40) и (3.41) справедливы для любых квазиполных графов, имеющих плотность 2 или 3, и для неразложимых по аддитивной операции "сумма" квазиполных графов. Структура этих графов была рассмотрена выше. Для разложимых квазиполных графов, у которых по теореме 3.49 плотность не меньше 4 и хотя бы у двух слагаемых Ь; > О, эти формулы неверны.
Например, квазиполный граф Я(4, 2), являющийся суммой двух графов Я,(2,1) иЩ2,1) (рис.3.59), Я(4,2) = = Я,(2, 1)+Яг(2, 1), имеет мощность Рис. З.зэ носителя, равную 10, и мощность сиг- натуры, равную 35, в то время как минимальные мощности носителя и сигнатуры неразложимого квазииолного графа Я(4, 2) равны соответственно 13 и 43 (согласно (3.40) и (3.41)), Теорема 3.50.
Хроматическое число ЦС) графа С равно его квазипяотности д(С): ЦС) = д(С). (3.42) Согласно определению квазиполного графа Ь(С) > ИС). Докажем, что в данном соотношении всегда имеет место равенство. Выделим все невключагмые кеазинолныг графы, т. е. графы, для каждого Я; из которых не найдется квазиполного графа Я, такого, что Я; СС Я,. Согласно (3.25) среди выделенных подграфов имеется хотя бы один, для раскраски которого необходимо а красок. Покажем, что для минимальной раскраски остальной части С ~ Я достаточно тех же о красок. Действительно, если для минимальной раскраски цодграфа С 1Я потребуется хотя бы еше одна новая краска, (а+ 1)-я, то это означает, что в подграфе С ~ Ч существуют замешающий и замыкающий слои, что приводит к ЦС) <р(Я;)+твхЩ;), Я; СС, С=(У, Щ Согласно (3.40) шах Щ;) < 1одз ™ + 1 Отсюда Ь(С) < р(С)+ 1обз +1 .
(3.44) В выражении (3.41) 6 ° 2 (р — 3) + (р — 3) — р+ 2 > 0 при любом Й; поэтому щах ЬД;) < 1обз — ~, р(С) > 4; 2!Ц Г следовательно, Ь(С) < Р(С) + !обз — ~, Р(С) > 4. 2ИГ (3.45а) При р(С) = 3 имеем (3.456) ЦС) < 3+ 1обз При р(С) = 2 выражение (3.33) принимает вид 2!У;„Я(2, Ь)~ = 7 3 — 6 2~+ 1 > 7 ° 3 — 6 3 +1 = 3~+1; поэтому шах Ь(ц;) < ]!оба (2!Ц вЂ” 1)(. Отсюда при р(С) = 2 получаем Ь(С) < 2+ 1!оба (2!Ц 1)( ° (3.45в) Согласно структуре квазиполного графа Я(р, Ь) степень г(о;) каждой вершины о; этого графа удовлетворяет неравенству г(о;) > а(С) — 1 = р + Ь вЂ” 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
