Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 44
Текст из файла (страница 44)
(3.46) образованию квазиполного графа квазиплотности а+ 1. Последнее противоречит соотношению (3.25). Используя формулы (3.40)-(3.42) для графов С; с плотностью р(С;) < 4 и для графов, которые не содержат квазиполные подграфы, разложимые по операции "сумма", можно предложить логарифмические оценки хроматического числа. Имеем Ь(С) = д(С) = глвх (р(Я;) + Щ;)) < шахр(Я;) + шаха;), (3.43в) (3.436) 13.10. Логарифмические оценки хроматического числа 245 Гл. 3.
Теория графов и мографов 244 Тогда цо формуле (3.40) мошность сигнатуры [ЦЯ(р, Ь))] нераз- ложимого квазиполного графа удовлетворяет неравенству ]ГГЯ(р, Ь))) > О, 5 (3 (2~ — 1) + р) (р + Ь вЂ” 1). (3.47) Эта оценка достигается цля полных графов, когда Й = О. Согласно (3.40), (3.43а) и (3.47) ь(а) <~ ~+1, а с а, 12-]ГГ(С))Г -1 )у(а)) ~ гце полграф С удовлетворяет всем неравенствам системы ]У(С)] > 3 (2а — 1) + р(С), 2)ГУ(С)) > 7 3~ = 6 2~ (р(С) — 3)+ (р(а) — 3)2 — р(а)+ 2, л(и;) > р(С) + Ь вЂ” 1, гч Е С, (3.48) (3.50) Ь= 1062 +1 Очевидно, что ]у(а)] ~ ! у(с) Отсюда имеем верхнюю оценку хроматического числа Ца) гра- фа С: ца) <) „,„„(а)(+1, (3.51) гце граф С С а удовлетворяет системе неравенств (3.49).
Оценка (3.51) является более эффективной, чем ранее приведенные оценки Брукса ЦС) < г„,„,(а) + 1 и (цля определенного класса графов) Ь(а) < в„,„,(С). Как композицию оценок (3.44), (3.45) и (3.51) получаем оценки хроматического числа Ь(а) графа С = (У, Щ: цри р(С) > 4 Ца) < ппп р(С) + 1об~ ) ) + 1 Р(а) + 1обз ~ ~ ~ лсредн(С) ~+ 1; (3.52а) (3.49) т. е. по своим ресурсам, как вершинному, так и реберному, и по локальной топологии (степеням вершин) поцграф С может включать квазиполный граф Я(р, /с), где при р(а) = 3 Ь(С) < ппп р(С)+ 1обт + 1 Р(С) + 1обз ~, ~ в,р,д„(С) ~+ 1; (3.526) 2 )ца)]+1Г 1 при р(С) = 2 Ь(а) < ппп 2+ 1обт +1 2+)ае а всю)$ — ц[, [~,щ]+1). (Вн) Для вычисления оценки хроматического числа Ь(С) графа С на основании формулы (3.51) находим плотность р(С) графа С и, уменьшая р от р(а) цо 2 с шагом 1, по формуле (3.50) находим Гс лля каждого из этих значений.
Максимальная сумма р и соответствующего значения й, для которых выполняются неравенства системы (3.49), согласно (3.43а) определяет верхнюю оценку хроматического числа Ь(а). Если оцениваемый граф является квази- полным или вычисленная верхняя оценка совпадает с нижней, то она равна хроматическому числу.
Нижняя оценка хроматического числа Ца) > р(с) (3.53) минорируется, как показано Майерсом и Линам, оценкой Геллера Ца) > ] ], (3.54) (]у(а)]' - 2)ца) Ц ' гле ( ] — ближайшее целое число, или ь(а) > ]'(')] 1. (3.,5) — ]у(а)] - „„„(а)1' Оценки хроматического числа (3.44), (3.45), (3.51), (3.52) минорируют известные верхние оценки Ь(а). Пример 3.19. Рассмотрим граф С = (У, У) (рнс. З.бо,а).
По оценкам Брукса и Геллера его хроматическое число Л(С) заключено в отрезке [2, 7]: [ з = =2, ]'(С)) 1 1' 1о' ]У(с)]' — 2)и(с)]3 = 1ш' — 2 20~ = 2' залка(С) = 7, 2 < Л(С) < 7. 43.10. Логарифмические оценки хроматического числа 249 Гл.з. Теория графов и мографов 248 Числа вершин со степенью з(а;) > 9, равна 28; 28 < 51. Следовательно, не- раалажимый квазиполный подграф Я(6, 4) не содержится в графе С.
Уменьшая порядок на 1, получаем (У»а»(С(6, 3))~ = 3 (2 — 1) + б = 27, (У ;( ; 6 4)(6, З)))(.( ;) > 8). Таким абрзаам, колучеи положительный ответ. Следовательно, определена вер~няя опенка: Ь(С) < 9. Случай 2. Квазиполпый граф Щ„~,) мзкснмалъной квазиплотности можно разложить иа два слагаемых: Ц(2, Ь.)+ Ц(4, Ь,); при этом Л(С) < 6+ гаах(Ь, + Ьь).
Определим гаах(Ь + Ьь). Для этого опреде,ь ллем Ьа =11обэ ( + 1) ~= 4 ~У»»»Я(2, 4))~ = 3' (2 1) + 2 = 47. Второе слагаемое содержит 27 вершин: 74 — 47 = 27. Тогда Ьь = ~!абэ ( — + 1) ~ = 3, (У„„Я(4, 3))/ = 3. (2 — 1) + 4 = 25, (Уа;(о; Е С (2, 4)))(з(о,) > и + Ь вЂ” 1+ (У Яь(4, 3))( = = 2 + 4 — 1 + 25 = 30), (У.ь(.,64).(4,3)))(.(.;) > .+Ь.-1+(У...(С)(2,4))(= = 4+ 3 — 1+ 47 = 53). Вершин с такими степенями в графе С нег. Продолжая аналогичные вычи- сления, находим, что шак(Ь, + Ьь) = 2+ 2 = 4 не выполняется, т. е, в графе С ,ь не мажет содержаться квазиполный граф Ц(10), рааложимый в виде суммы Сь(2, 2) + Сь(4, 2).
Действительно, (У...Я.(2, 2))) = 3 (2' — 1) + 2 = Ы, /У» ° (4)ь(4, 2))~ = 3 ° (2 — 1) + 4 ь» 13, (Уо, Е 4)»(2, 2)) (э(о,) > 2 + 2 — 1 + 13 ю 16), (У~; Е 47~(4, 2))(~(~,) > 4+ 2 — 1 + 11 = 16), (У„,~Я~(2, 2))!+ (У~»»Яь(4, 2))(+ (У~ь»(Я~(2, 2))~ (У»э (Сь(4', 2))~ = = О, 5 (7 . 3 + 6 .
2 (2 — 3) + (2 — 3) — 2 + 2) + + О, 5 (7 3 + б 2 (4 — 3) + (4 — 3) — 4 + 2) + 11 13 = 206. В эшм случае храмати гескзя опенка Ь(С) не изменяется. Остальные случаи предлагаем рассмотреть читателю самостоятельно. Окончательно аалучаем б < < Ь(С) < 9. Используя опенки Геллера — Брукса, мы получили бы стреаок [2, 13]: 2 < Ь(С) < 13. Согласно (3.42) запрешенными фигурами раскраски вершин графа в сг красок являются квазиполные графы квазиплотности сг+ 1.
Теорема 3.51 (М.В. Горбатове). Квазииолиый граф Я(р, и), Ь > 1, не обладает свойством реберности. Действительно, если порядок )с квазиполного графа Я превышает 1, то найдется вершина и, входяшая более чем в 2 полных подграфа. Такой вершиной является, например, вершина замыкающего слоя. Согласно теореме 3.37 такой граф не обладает свойством реберности. П риме р 3.21. Хвазнпалный граф Я(З, 1) (рис. 3,61, а) обладает свойством ребернастн согласно теореме 3.37 (рнс. 3.61, б, е). При увеличении ега порядка Ь е а, Рис. 3.61 Рнс. 3.62 на 1 условна теоремы 3.37 не выполняются. Действительно, уже прн построеняи вершины Ь замешающего слоя имеем нарушение условий этой теоремы Гл.
3. Теория графов и мографое 250 1 3.10. Логарифмические оценки громаоьического числа 251 (рнс. З.б2). Вершина Ь' шшягтся двойником веряиинг Ь: Гь — — Гь ддя вершин основания — О(з, 1). Если граф обладает свойством реберности, та его порядои не превышает 1. При построении реберно производного графа С па графу С ребра, инцидентные одной и той же вершине графа С, соответствуют вершинам полного подграфа графа С.
Следовательно, в < Н(С) < в+1, (3.57) где Н(С) — хроматический класс графа С, в — степень графа С, в = шах в(и;), иг Е С. 1 Для мультнграфа в < Н(С) < в+ р, (3.58) где р — параллельность мультиграфа, т. е. максимальное число параллельных ребер.
В соотношении (3.58) степень графа С и его параллельность удовлетворяют следующим соотношениям (рис. 3.63): в = 0 (пюс1 р), в ~ р, (3.59) где запись в = 0 (пюс) р) означает, что число в сравнимо по модулю р с числом О. Согласно (3.58) и (3.59) получаем оценку Шеннона Н(С) < — в . (3.60) Рассматривая характеризацию раскраски графа, интересно вспомнить проблему четырех красок. Эту проблему можно с полным основанием назвать еще "болезнью четырех ирасок", так г каи она во многом похожа на заболевание.
аОна в высшей степени заразна. Иногда 10 она протекает сравнительно легко, но в не- 9 которых случаях приобретает затяжной з или даже угрожающей характер. Никаких прививок от нее не существует; правда, люди с достаточно здоровым организмом б после короткой вспышки приобретают но- 5 жизненный иммунитет... Тем не менее именно попытки обосновать эту гипотезу стимулировали получение ряда результатов по раскраске графов, которые в свою 3 очередь привели к исследованиям некото! рых других разделов теории графов",— так пишет ведущий графист, профессор о 1 3 3 г 5 б р математики Мичиганского университета Рнс. З.бз Фрэнк Харари [31).
...1840 г. Идет заседание Королевского географического общества Англии. Профессор А. Мебиус обращается к слушателям своей лекции с вопросом о количестве мастей в игральных картах: "Почему четырр масти: крести, пики, черви, бубны? Почему не 5, 6 мастей?" После выдержки паузы А. Мебиус формулирует задачу, которая стала проблемой, не решенной в течение 123 лет: аЛюбая карта на поверхности нулевого рода (плоскость, сфера) может быть раскрашена в четыре цвета так, чтобы государства, имеющие общую границу, были окрашены в разные цвета".
Этой проблемой увлеклись в 40 — 50-е годы прошлого века студенты-математики Лондона, ее обсуждал А. де Морган. Первая волна интереса спала. В 1878 г. о ней упоминал А. Келн, который опублииовал в 1879 г. ее адоказательство". В 1880 г. свои адоказательствав дали Тейт и А. Кемпе. Но через 10 лет, в 1890 г., П. Хивуд их опроверг. Следующая волна интереса возникла уже в 50-х годах нашего столетия в связи с бурным развитием вычислительной техники. Габриэль А. Дирак [39) — один из ведущих европейских ученыхграфистов, изучающих раскраску графов, наставил вопрос о существовании графа С, плотность которого равна 2 (р(С) = 2), а хроматическое число принимает сколь угодно большое значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
