В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 44
Текст из файла (страница 44)
Если 6 — полный граф, то неравенство проверяется непосредственно. Пусть граф 6 не является полным и у(6) =)(. Согласно следствию 54.3 при любой минимальной раскраске граф имеет пару соцветпых вершин о~ и ог, для которых д(оь ог) = 2. Построим граф 6ь слив о1 и ог в вершину и. Граф 61 имеет на одну вершину и по крайней мере па одно ребро меньше, чем граф 6. Очевидно, что ~(6~)=1. В противном случае, правильно раскрасив р цветами (т1(~) граф 6н можно было бы построить и р-раскраску графа 6. Для этого нужно было бы окрасить вершины о~ и ог в цвет вершины о, а для остальных вершин сохранить их цвета в графе 6ь Операции слияния соцветных вершип будем производить до тех пор, пока не получим полный граф К,.
Пусть таких слияний потребуется в. Так как по-прежнему у (К,) = у, то 1 = т = и — в. Граф К, имеет 1(1 — 1)/2 =т(у — 1)/2 ребер, т. е. па т — у (т, — 1) /2 ребер меньше, чем граф 6. Поскольку после каягдого слияния число ребер графа уменьшалось хотя бы па единицу, то имеем т — К(Х вЂ” 1)/2 ~ в. $6 в, А, ивезичев и вв.
Поэтому, учитывал, что )( = и — г, получаем т — у (у — 1) /2 ра и — т,. Из последнего неравенства следует 2(6) = 2( —,(3+ тт9+ 8(т — п)). е1 Существуют графы, для которых оценки, установленные предыдущей теоремой, достигаются. Таковы, например, полные графы. Ниже рассматриваются оценки хроматического числа, имеющие скорее теоретический интерес, поскольку параметры графа, с которыми онн связаны, вычксляются столь же слонспо, как и само хроматическое число.
Трнвнальнои нижней границей для хроматического числа является плотность. Очевидно, что у(6) ~ ~р(6) для любого графа С. На первый взгляд может показаться, что плотность графа тесно связана с его хроматическим числом, и если плотность ~р(6) невелика, то невелико н 2(6). Однако па самом деле разность 2(6) — ~р(6) может быть сколь угодно большим числом. А именно, верна следующая Теорема 54.5 (А. А. Зыков, 1949 г.). Суи1еетвуют графы без треугольников с произвольно болыиим хроматическим числом.
> Для доказательства ипдуктивпо построим последовательность Я = (См Сз, ..., 6ь ...) графов С~ без треугольников, таких, что у(С,) =-1. Положим Сг =Кг. Если граф С~ уже построен, 1~2 и т'6,=(оь нм ..., о„), то граф С„л определим по следузощему правилу: РС;.ь~ = = т'Ст 9 )т'0 о, )т'= (о„о„...,о ), )тС;9 Г'= О, оФ Ф )тС;0 т"; каятдую вершину о; соединим ребрами с теми вершинами нз ГСь с которыми смежна о~ в графе 6„' вершину о соединпм ребрами с каждой вершиной на т" (см. рис. 54.2 и 54.3, где изображены графы Сз и С4). Полученный таким образом граф имеет 2н+ 1 верпшп, Пенах(ем, что С~~д — искомый граф.
Так как вершина и не смежна нп с одной вершиной нэ мпохтсстза ГСь а вершины пз )т' попарно пе смо)кпы, то никакой треугольник в Сы~ пс моятот содерткать вершину о. По той я~е причине треугольник пе может содержать более одной вершины нз Г. Если же треугольник образовывалн бы вершины о;, им нь то в графе С, верпшны иь вн о~ такятс составляли бы треугольник. Поскольку в графе 242 С, треугольники отсутствуют, отсюда следует, что в графе С,+~ их также нет. Теперь донажем, что Х(Сг.,1)=о+1.
В самом деле, любую правильную 1-раскраску графа С, легко продолжить до правильной (1+1)-раскраски графа С;+н положив 1(г;) = ((н;) для !'=1, и и приписав вершние и некоторыи новый цвет. С другой стороны, если бы существовала правильная г-раскраска графа Сгг.н то па о 1- ог Рис. 54.2 Рнс. 563 раскраску вершин из $" понадобилось бы не более 1 — 1 цветов (отличных от цвета вершины о).
Изменив окраску вершин графа 6; так, чтобы каждая верппша нг получила тот же цвет, что п гггч можно было бы построить правильную (г — 1)-раскраску графа 6„в то время как Х(6,) = й Таким образом, доказано, что граф С,~г не содержит треугольников и Х(Сгьг) =1+1. <г Заметим, что графы, существование которых гарантируется предыдущей теоремой, являются экзотическими, поскольку для почти каждого графа 6 верно следующее утверждение: если гр(6) < й, то и Х(6) < й (Ф. Колайтис, Х. Премель, В.
Ротшильд, 1987 г.). Как показывает теорема 54.5, графы с плотностью, равной 2, могут иметь сколь угодно болыпое хроматическое число. Следующая теорема, принодимая здесь без доказательства, свидетельствует об отсутствии связей между хроматическим числом и обхватом графа. Теорема 54.6 (П. Зрдеш, 1961 г.) . Для любых натуральных чисел 1 и Х существует Х-хрогяатичеекий граф, оохват которого превосходит й Оженим хроматическое число в терминах числа независимости. Теор ем а 54.7. Для любого графа С верно и!ао -Х<п — ао+1, (1) где п = ~ 6~, ао = ао(6), Х =Х(6) ° 16в С' При любой минимальной раскраске множество т'6 разбивается на т цветных классов )тп )тм ..., $'„, каждый нз которых является независимым множеством.
Поэтому если 1 г,! = пч то и, =-ав ДлЯ всех 1= 1, 11, и откуда следует левое пз неравенств (1). Перейдем к доказательству правого неравенства. В графе 6 есть независимое множество вершин Я, содержащее ровно ав элементов. Так как !6 — Я! =и — ав, то т (6 — Я) < и — ав и, следовательно, т < п — аз+ 1.
0 Следствие 54.8. Если 6 — связный граф, не являющийся полным, и Л(6) ~ 3, то ав(6)> 161!й(6). > Рассъштрим последовательность неравенств ав(6) ~ !6 УХ(6) ~~ 16УК (6). Первое пз неравенств вытекает пз предыдущей теоремы, а второе — из теоремы Брукса. <1 Дополнением теоремы 54.7 является Те о р ем а 54.9. Для любых патуральпых чисел и, аэ и т, удовлетворяющих неривепствим (1), существует граф порядка и с числом вершинной независимости ав и хроматическим числом у.
> Рассмотрим отдельно три случая; 1) аэ = 1; 2) ав > 1 и и = ав1, где 1 — целое число; 3) и пе кратно ав. 1) Из (1) следует, что у„=п, и ʄ— нужный граф, так как ао(К.)= 1 = ао, т(К.)= и =т, 2) Пусть 6 — полпын 1-дольный граф, в каждой доле которого ровно ав вершин. Тогда у(6)=1=пикав Фиксируем некоторую долю У и каждую из пе входящих в эту долю вершин будем последовательно превращать в домипирующую, добавляя недостающие ребра. На каждом таком шаге хроматическое число возрастает на 1. В результате придем к полному (и — аз+1)-дольпому графу Е, все доли которого, кроме доли У, одповершипные. Очевидно, что т (Е) = п — ав+ 1. 3) Гслп и зте кратно ав, то в качестве походного графа берется и-вериппптьш полный ( [и!ав) + 1) -дольный граф, (и/аэ] долей которого содержат по ав вершин.
244 Выбрав в качестве У одну из таких долей, далы1ейшпе рассуждения проведем так же, как в случае 2. ч Естественный интерес вызывает стремление уточнить оценку хроматического числа, устанавливаемую теоремой Брукса. О. В. Бородин и Л. В. Косточка в 1977 году выдвнпулн следующую гипотезу, пока пе доказанную и пе опровергнутую; Гипотеза. Если Л(6)~9 и ф(С)~Л(С), то ~(С) =- Л(6)-1. Приведем без доказательства теорему, дающую аспмптотпку хроматического числа.
'Г соре ма 54.10 (Л. Д. Коршунов, 1980 г.). Хроматическое число почти каждого зрафв С порядка и удовлетворяет соотношению )((6) и/21еяз и. й 55. Хроматический полипом Поскольку 1-раскраской графа С является произвольное отобраятекпе вида )тС вЂ” (1, 2, ..., Л, то число попарно различных т-раскрасок этого графа равно числу всех таких отображений, т. е. Г, где и =!$'СБ По если ограничиться только правильнымн раскрасками, то вопрос о числе различных среди ннх становится сложным. Количество попарно различных правильных г'-раскрасок графа С называется хроматической фупкиией графа С и обозначается через 1(6, ~).
Очевидко, что наименьшее нз чисел г, для которых 1(6, г)ФО, есть у,(6). Для некоторых графов хроматическая функция определяется совсем легко. Например, 1(0, ~) = 1", так как цвета всех вершин пустого графа моятко выбирать независимо друг от друга. 1!ри правильной раскраске полного графа К„первая вершина может иметь любой из ~ заданных цветов, а для окраски каждой нз последующих вершин разрешается использовать на один цвет меньше, чем для предыдущей. Поэтому 1(К„, ~) = 1(~ — 1)...
...(г — и+ 1). Итак, имеем О, 1(1 — 1)... (~ — и + 1), если 1) и, если 1 ( и. В общем случае, как отмечалось выше, вычисление хроматической функции сопряжено с большнмн трудностями, Приведем несколько утвернсдеппй, позволяющих упрощать ее вычисление. У т в е р ж д е н и е 55.!. Если С = С1 0 Сг 0... 0 ф— дизъюнктное объединение графов, то /(С,~) =П/(Сь~) $='1 ~> Ото утверждение вьпекает пз того, что раскраска кагкдой пз компонент С, может выбираться незавнм, а Утв арнгд ение 55.2.
Если С = С10 Сг и графы С1 и Сг имюот только одну обшую вершину, то /(С, г) = -,' /(С„~)/(С„г). Ь Ф1гкспруем каку1о-либо правильную раскраску графа Сь Для продолягенпя ее до правильной раскраски графа С нужно взять такую правильную раскраску графа Сю прп которой цвет /г(о) вершппы о, общей для графов С1 и См равен цвету /1(о). Поскольку число правильных Е-раскрасок графа Сю прп которых цвет вершины и фиксирован, пе завнскт от этого цвета, то для выбора раскраски /г имеется /(Сг, ~)/1 возможностей, откуда и следует равенство (1).
ч Утверждение 55.3. Луста и и о — две несмелсные вершины графа С. Если С1=С+по, а Сг получается из графа С в результате слияния вершин и и о, то /(С, ~)=/(Сн ~)+/(Сг, ~). ь. Число правильных ~-раскрасок графа С, при которых цвета вершин и и о различны, не изменится, если к С присоединить ребро ио. Следовательно, это число равно /(Сп ~).
Аналогично, число правильных ~-раскрасок графа С, при которых цвета вершин и п о совпадают, равно /(Сг, г). Складывал этп два числа, получим число всех правильных 1-раскрасок графа С, т. е. /(С,г), а Предыдущее утверждение позволяет свестн вычисление функции /(С, т) произвольного графа С к вычислению хроматических функций графов с болыппм числом ребер или с меньшим числом вершин, п следовательно, в конца копцов,— хроматических функций полных графов. К сожалению, число этих графов может оказаться катастрофнчсскп большим. Очевидно С л е д с т в и е 55.4.
Хроматическая функция любого графа С равна сумме хроматических функций некоторого 246 числа полных графов, порядки которых не болыне, чем !6!. Поскольку /(К„, 1) — полипом от 1, то верно Следствие 55.5. Хроматическая функция /(С, 1) любого графа является полиномом от 1, Поэтому хроматическую функцию /(С, 1) обычно называют хроматическим полиномом графа, С.
Найдем с помощью утверждения 55,3 хроматический полипом графа 6, изобрая1епного па рпс. 55.1. Прп этом Рис. э5.1 Рис. 55.2 вместо /(С, 1)=/(Си 1)+/(См 1) будем писать С= = 6~ ~ Сг или рисовать соответствующие графы. Па первом шаге получим ситуацию, представленную яа рис, 55.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
