В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 45
Текст из файла (страница 45)
Далее см. рис. 55.3. Итак, /(С, 1) = /(Кг, 1)+ 3/(К4, 1) + 2! (Кз, 1) = 1(1 — 1) (1 — 2) (1 — 3) (1 — 4) + + 31(1 — 1) (1 — 2) (1 — 3)+ 21(1 — 1) (1 — 2) = 1з 71~+ 191з 231т+ 101 Используя утверя1депие 55.3, можно уточнить вид хроматического полинома. Следующую теорему продлагаем доказать самостоятельно. (х) — ( (х) о К ) о ~ Я е хх ~- - фоЕоноКо о -о~ Рис.
55.3 Т е о р е м а 55.6. Хроматический полинам любого (и, т)-графа С, содержащего ровно /г связных компонент, имеет вид /(С 1)=à — т1" '+а„з1" ' — а„з1" '+ +( — 1)" "а,Р, где а, — целые неотрицательные числа. Несомненный интерес представляет следующий вопрос, ответ па которьш пока пе получен; каким условпнм должен удовлетворять полинам, чтобы он был хроматическим полнномом некоторого графа? Любопытно было бы найти условия, при которых хроматические полиномы графов совпадают.
Примерами таких графов являются деровья, которые можно определить в терминах хроматических полиномов. Теорема 55.7. Граф С порядка п является деревом тогда и только тогда, когда С(6, С) = С(С вЂ” 1) " '. (2) Г> Докансем только необходимость условия теоремы, а достаточность оставим читателю в качестве упражнении. Пусть С вЂ” дерево порядка и. Воспользуемсл индукцней по и. При и = 1 имеем С =Кп 1(6, С) = С, при п = = 2 — 6 = Кг, С(6, С) = С(С вЂ” 1). Следовательно, при п = = 1, 2 равенство (2) верно. Предположим теперь, что это равенство верно длп любого дерева С порядка пс, 2 ( пс( п, и рассмотрим дерево Т порядка и. Если и— копцеваи, а и — смежнаи с ней вершины дерева Т, Т~ = =Т(и, е), Тг=Т вЂ” и, то Т~=Кг, 1(Тп С)=С(С вЂ” 1), Т=Т~ Ц Тм и по ипдуктивпому предполонсенпсо ((Тг, С) = С(С вЂ” 1)" г. Применяя затем утверждение 57.2, получаем С(Т,С) = —,С(С вЂ” 1) С(С вЂ” 1)" ' = С(С вЂ” 1)" '.
а 2 56. Раскраска ребер Реберней Сс-раскраской графа С пазываетсн функция ср, ставящая в соответствие каждому его ребру е число ср(е) из множества (1, 2, ..., Й. Если ср — ребернан раскраска и цс(е)= с, то говорят, что ребро е окрашено в цвет с. Мнонсество всех ребер, окрашенных в фиксированный цвет, называсот ребернылс цветным классом. Реберпан раскраска пазываетсн правильной, если сменсные ребра имеют разссые цвета. Граф, допускающий правпльпусо реборпусо Сс-расссраску, называется реберно й-раскрашиваемым. Минимальное число Сс, прл котором граф С пвляется реберпо Сс-раскрашссваемыьс, пазываотсп хролсатическпм индексолс (хроматичееким классом, реберным хроматическим числом) графа С и обозначается через 248 у'(6), Если у,'(6)=й, то граф 6 называется ргберно й-хроматическим. Поскольку ребра любого графа 6 сменсны тогда, когда смежны соответствующие вершины реберпого графа Е(6), то у (6) можно определить как хроматическое число графа Е(6), т.
е. у'(С) =т(Е(6)). Прп правилкой реберпой раскраске каждое множество ребер одного цвета является паросочетаппом. Поэтому число 1~'(6) можно рассматривать как наименьшее число паросочетапий, на которые разбивается множе- в ство ребер графа С. Поскольку при любой правильной раскраске графа С ребра, инцидентные одной вершине, имеют различные о г г цвета, то т'(6) > Л (6). Ле~ко приве- 1 сти примеры, когда т (6)>й(С) (см.
рпс. о6.1). Следующая теорема, принадлежа- и '. бед щая В. Г. Впзпнгу (1964 г.), дает поразительно точные оценки хроматического индекса графа. Т е о р е м а 56.1. Для любого графа С верны неравенства ~(6) == у,'(6) = ~(6)+1. ~' 1(ак отмечалось выше, левое нз этих неравенств очевидно, остается доказать правое. Оно верно для Кг. Предположим, что в общей ситуации правое неравенство пе выполняотся. Среди всех графов, ему пе удовлетворяющих, выберем граф С с минимальным числом ребер. Пусть в~ ~ ЕС, Н = С вЂ” ео Имеем у'(6)> Л(6)+1, (1) но у'(Н) =- й(Н)+1~ Л(6)+1. Пусть Л = Л(6).
Зафиксируем правильную раскраску ~р: ЕН- (1, 2, ..., Л+ 1) ребер графа Н п скажем, что цвот д ~н (1, 2, ..., гг+ 1) отсутствует в вершине о ~ )тН, если ~р(е)т- д для любого ребра е, нпцндептного вершине о. Так как число возможных цветов больше чем гг, то в каждой вершине отсутствует хотя бтл одпп цвет. Пусть в~ = хун а в и (~ — цвета, отсутствующие в вершине х и в верпшне у~ соответственно.
Исходя из пары уь 1и построим нпдуктивпо две последовательпостн— 249 верпшн уь ую ..., у» и цветов 1п 1з,, 1»,— удовлетворяющие следующим трем условиям: 1) ху, = е, »и ЕС (1 = 1, й); П) цвет й отсутствует в вершине у» (1=1,й); П1) ~р(е,»~)= й (1= 2, Й вЂ” 1). Пусть последовательпостя уь ..., у~ и 1п ..., й уже построены. Если существует такое ребро е =ху ~ЕН, ннцидептпоо вершние х, что уФ (уп ..., у,), »р(е) =1ь то полагаем у,ы =у и берем в качестве 1,.,~ один нз цветов, отсутствующих в вершине у. Если же описанного ребра е не существует, то полагаем й = й Пужные последовательности построены. Далее возмонтны две ситуации. 1) Не существует ребра ху ~ ЕН, для которого <р(ху) = 1,.
Переопределнм функцию <р, положив ~р(е;) = Ц (1=- 1, й) н оставив значения па других ребрах пеизмонпымн. Получена правплышя раскраска ~)с ЕС вЂ” (1, 2, ... ..., Л + 1) робер графа С. 2) Существует ребро ху ~ЕН, для которого гр(ху) = = »,. Тогда это ребро совпадаот с каким-либо из е; (1= = ", й). Пусть, скажем, ху = е,. Опона переопределпм функцию»р, полагая ср(е,) =1» (1= 1,/ — '1).
Ребро е, пока не окрашено, значения функции ~р па всех остальных ребрах не меняются. Рассмотрим остовный подграф Г графа С, ребрами которого служат все ребра графа С, имеющие цвет г или 1». Очевидно, что степень каждой вершины графа Г пе болое двух, н потому каждан ого связная компонента язляотся либо простой цепью, лнбо простым циклом, либо Кь Степени вершин х, у, н у, в Е пе более единицы, следовательно, этн трп впршппы пе могут входить в одну компоненту.
Рассмотрим отдельно дза случая. а) Вершины х и рл находятся в разных компонентах графа Г. В этом случае в компоненте, содержащей вершину у„переставим цвета г п 1„т. е. положим»р(е) = г, если было ~р(е)=1„и наоборот. Тогда цвот г будет отсутствовать и в вершине х, и в воршине у„что позволит положить»р(е,) = г. Вновь получается правильная (Л + 1) -раскраска рооор графа С.
б) Воршнпы х и р» находятся в разных ком»юнептах графа Е. Положим ~р(е»)=й (1=-1', й — 1), а ребро е» оставим пока не окрашенным. Вто действие не затрагивает ребер графа Г. Переставим теперь цвета з н 1» в 250 компоненте графа Г, содержащей вершкпу у,.
Теперь цвет в отсутствует и в вершине а, и в вершине у,. Полагаем далее ф(е,)=г. Построена правильная (Л+1)- раскраска ребер графа 6. Итак, в любой ситуации строится правильная (Л + 1)-раскраска ребер графа 6, что противоречит неравенству (1). Это противоречие н доказывает теорему. Э Б частности, тоорема Внэинга свидетельствует о том, что теорема 54.5 о существовании графов без треугольпиков с произвольно больпшм хроматическим числом перестает быть верной в классе реберных графов, где хроматическое число п плотность графа различаются не более чем на 1. Тем не менее даже в этом случае, т.
е. в узком классе реберных графов, хроматическое число определяется слолпш: несмотря на то, что величина т (6) может принимать только два значения — Л(6) или Л(С) + 1 — ее определение является весьма трудной задачей. Найдем хроматический индекс для некоторых классов графов.
Теорема 56.2. Справедливы равенства у'(Кт„ы) = Л (Кт,оы)+ 1 = 2п+ 1, д'(Кз„) = Л (Кз ) = 2п — 1. 1> Докажем первое равенство. Пусть Е~ 6 Ет 0... 0 Е, = ЕКз..~! — разбиение множества ЕКз +~ на цветные классы. Так как ребра одного класса не смежны, то ]Е~! -]]Кз„ы]/2]=п, 1=1,1, откуда получаем 1) ] ЕКз„т,] / тпах ] Е~]) ] ЕКз,+д]~п = 2п + 1. /'3.1<, Из теоремы 56.1 теперь следует, что Х'(Кз,.ы) =1= = 2п+ 1. Перейдем ко второму соотношению. Пусть и — про- извольная вершина графа Кт„. Рассмотрим граф 6 = =-Кт — и = Кз.-ь По доказанному выше ребра графа С можно раскрасить 2п — 1 цветами.
Так как степень лю- бой воршпны и графа 6 равна 2п — 2, то пекоторьш цвет не будет представлен в верзпнне и. С другой стороны, множество всох робер цвета с, образует паросочетание' в графе 6. Поэтому вследствие нечетпости ])тС] найдется 251 такая ворспппа иь что цвет с, будет отсутствовать в иь Отсюда следует, что цвета, отсутствусощпе в вершинах графа 6, попарно различны. Для получения требуемой раскраски ребер графа Кг„нужно приписать каждому ребру ои< цвет, не представленный в вершине иь < Теорема 56.3 (Д. Кениг, 1031), Для любого двудольного грофа, С верно ровенгтво )с'(6) = Л(6). > Пусть, папропсв, утверждение тооремы неверно, и 6 — двудольный граф с мссссссьсальвьсм числом ребер, для которого 11'(С) = Л(6)+ 1.
Тогда для любого ребра е ~ ЕС справедливо равенство у,'(6 — е) = бс(6 — е) < ~ Л (6) . Зафиксируем ребро е = ив вв Е6 и правильную реберпую Л(6)-раскраску ср графа 6 — е и обозначим через М„мпоисество цветов, отсутствующих в некоторой вершине ис. Очевидно, что М та И, М.ФИ. Если М П П М„ть Ы, то ребро е можно окрасить в цвет, ссрпнадлеясащий этому пересечению. Поэтому М„П М„= И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
