Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 105
Текст из файла (страница 105)
14.47 Рис. 14.48 Поскольку грани графа С стали вершинами С', раскрашиваем теперь вершины графа С'. Исходная проблема раскрашивания стран на карте при условии, чтобы никакие две страны, имеющие общую границу, не были окрашены в один цвет, стала теперь проблемой раскрашивания вершин графа при том же условии. А теперь рассмотрим новую задачу. Зафиксируем для графа количество цветов и попытаемся определить, сколько существует способов раскрашивания вершин при условии, что никакие две смежные не будут одного цвета.
Эта концепция принадлежит Г.Д. Биркгофу (П. Р. В!гйпо!!) [11). Предположим, например, что имеется пять цветов и необходимо раскрасить граф, изображенный на рис. 14.49. Для раскрашивания первой вершины имеется пять цветов, и только четыре цвета для раскашнвания второй. Необходимо учесть, что вторая вершина отличается по цвету от первой. Следовательно, существует 5 4 = 20 способов раскрашивания графа. Заметим, что данный метод использовался в разделе 8.1 для подсчета количества перестановок, а также и в других случаях, при использовании комбинаторного принципа умножения. Предположим, что имеются четыре цвета и необходимо раскрасить граф С, изображенный на рис.
14.50 М Рис. 14.50 Для раскрашивания первой вершины а имеются четыре цвета. Далее, имеются три цвета для раскрашивания вершины Ь.Только два цвета остается для раскрашивания вершины с, поскольку она смежная с а и Ь, цвет ее вершины должен отличаться от цвета вершин а и Ь. Для раскрашивания вершины Н также имеются два цвета.
Цвет вершины г! может совпадать с цветом вершины Ь, но должен отличаться от цвета смежных вершин а и с. Таким образом, имеем 4 3 2 2 = 48 способов раскраски графа С. Важно не раскрашивать вершины Ь и с! до определения количества цветов для вершины с, иначе потребуется разбить подсчет на два РАЗДЕЛ 143. Раскраска арвфое 589 случая: когда Ь и й — одного цвета и когда Ь и й по цвету не совпадают. Предположим, что имеется Л цветов для раскрашивания графа С. Имеются Л цветов для раскрашивания вершины а, Л вЂ” 1 цветов для раскрашивания вершины Ь, Л вЂ” 2 цветов для раскрашивания с и Л вЂ” 2 цветов для раскрашивания й. Следовательно, имеются (Л)(Л вЂ” 1)(Л вЂ” 2НЛ вЂ” 2) способов раскраски графа С. Обозначим эту величину через Со(Л).
Таким образом, Со(Л) — число способов раскраски графа С с использованием Л цветов. Заметим, что Сс(0) = Са(1) = Са(2) = О. Функция Со(Л) предполагается полиномиальной при формулировке нижеприведенного определения. На интуитивном уровне это кажется верным и будет доказано позже. ОПРЕДЕЛЕНИЕ 14.57. Пусть С вЂ” граф. Раскраской графа С называется окрашивание вершин графа С такое, что никакие две смежные вершины не имеют один цвет. Пусть Сд(Л) обозначает количество способов раскраски графа С с использованием Л цветов, так что никакие две смежные вершины не имеют один цвет, т.е. Со(Л) — количество способов раскраски графа С. Для фиксированного графа С функция Сс(Л) является полиномиальной функцией от Л, называемой хроматическим многочленом графа С.
Хроматическое число графа — это наименьшее число цветов, которое используется для раскраски графа. Это наименьшее положительное число и такое, что Сс(п) ~ О. ПРИМЕР 14.58. Пусть граф С состоит из пяти изолированных вершин, так что в нем нет ребер, поэтому нет смежных вершин.
Если раскрашивать граф Л цветами, то будем иметь Л вариантов для каждой вершины, поэтому будет сушествовать Л Л Л Л. Л = Лз способов раскраски графа и Со(Л) = Лз. Очевидно, что если граф С состоит из й изолированных вершин, то Со(Л) = Л", а хроматическое число равно 1. П ПРИМЕР 14.59. Пусть С вЂ” граф Кз, так что каждая из пяти его вершин является смежной с остальными четырьмя вершинами.
Если раскрашивать этот граф Л цветами, то для первой вершины имеется Л вариантов цвета. Поскольку вторая вершина смежная с первой, то имеем Л вЂ” 1 вариантов выбора цвета для следующей вершины. Третья вершина является смежной с первой и со второй, поэтому для нее имеется Л вЂ” 2 вариантов выбора. Четвертая вершина — смежная с каждой из первых трех раскрашенных, поэтому для нее имеется Л вЂ” 3 вариантов выбора цвета.
И, наконец, пятая вершина является смежной с каждой из первых четырех окрашенных вершин, поэтому имеется Л вЂ” 4 вариантов выбора цвета для этой вершины. Таким образом, Со(Л) = (ЛИЛ вЂ” 1)(Л вЂ” 2ИЛ вЂ” ЗНЛ вЂ” 4). Отметим, что этот граф не может быть раскрашен четырьмя цветами, поскольку Сс(4) = О, но учитывая, что граф С не является планарным, этот факт не противоречит утверждению, что планарный граф может быть окрашен четырьмя цветами. Используя рассмотренный выше частный случай графа Кз в качестве ориентира для изучения графа С = К„, находим, что если С = К„, то Сс(Л) = (Л)(Л вЂ” 1НЛ вЂ” 2)(Л вЂ” 3) (Л вЂ” (и — 1)).
Таким образом, хроматическое число для графа С равно и. П 690 ГЛАВА 14. Некоторые специальные еопросы теории графов Раскраска одной компоненты графа не ограничивает раскрашивание другой компоненты, поскольку никакая из вершин одной компоненты не является смежной с вершиной другой компоненты. Следовательно, имеем следующую теорему. ТЕОРЕМА 14.60. Если С = Сг Ш Сз и Сз О . О С„, где Сы Сз, Сз,..., ф— компоненты графа С, то Са(Л) = Сс,(Л) .
Сс,(Л) Са,(Л) .. Са„(Л). Из теоремы следует, что Сс(Л) = 0 тогда и только тогда, когда Со,(Л) = 0 для некоторого 1 < 1 < и. Отсюда вытекает приведенное ниже следствие. СЛЕДСТВИЕ 14.61. Если для раскраски графа С требуется к цветов, то и для одной из его компонент требуется для раскраски й цветов. Учитывая этот результат, рассмотрим раскрашивание только связных графов. Теперь на основе заданного графа С(К Е) сформируем два специальных графа. Пусть е = (а, Ь) — ребро графа С. Пусть Се — граф С, в котором удалено ребро е, но сохранены вершины а и Ь. Пусть С1.
— граф С; с отождествленными (склеенными) вершинами а и Ь. Отметим, что граф С1„фактически, является гомоморфным образом графа Сьч где гомоморфизм 1: С; — С1, определен на вершинах графа С; таким образом; ~(а) = 1 (Ь) и ~(о) = о для всех о из Ъ' — (а, Ь). Для ребер имеем 1'((и, о)) = (Г"(и),1(о)). Также отметим, что Г' = 1 о Г", поскольку для вершин и ребер графа С1, функция 1 представляет собой тождественное отображение. Функция с такими свойствами называется стягиваюшим отображением. ПРИМЕР 14.62.
Пусть С вЂ” граф, изображенный на рис. 14.51. Тогда граф Се изображен на рис. 14.52, а С1, — на рис. 14.53. 7 Рис. 14.53 П Рис, 14.52 Рис. 14.51 ПРИМЕР 14.63. Пусть С вЂ” граф, изображенный на рис. 14.54. Тогда С; — граф на рис. 14.55, а С1, — на рис. 14.56. .Е Рис. 14.55 С) Рис. 14.ББ Рис. 14.54 Введенные специальные графы используем для доказательства следующей теоремы.
ТЕОРЕМА 14.64. Для произвольного планарного графа С с ребром е имеет место равенство Сск(Л) = Сс(Л) + Са,.(Л). РАЗДЕЛ 14.Э. Раскраска графоа 591 ДОКАЗАТЕЛЬСТВО. Предположим, что имеется раскраска графа Сг. Если цвет вершины а не совпадает с цветом вершины Ь, то эта раскраска будет также раскраской графа С и наоборот. Если цвет вершины а совпадает с цветом вершины Ь, в таком случае имеем раскраску графа С~, и наоборот. Поэтому произвольная раскраска графа С; является либо раскраской графа С, либо раскраской графа Су„ но не обоих одновременно.
Следовательно, количество раскрасок графа Сг равно количеству раскрасок графа С плюс количество раскрасок графа Су„ или С;(Л) = Со(Л) + Су,(Л). Интуитивно понятно, что для произвольного планарного графа С с и вершинами Со(Л) — многочлен степени и, поскольку всякий раз в примерах при построении Со(Л) формировалась для каждой вершины величина Л вЂ” к для некоторого целого числа О < к < и. Фактически, это предположение было использовано при определении хроматических многочленов. Теперь докажем это, строго используя предыдушую теорему и метод индукции по числу ребер.
ТЕОРЕМА 14.65. Для произвольного планарного графа С с и вершинами функция Сс(Л) представляет собой многочлен и-ой степени. ДОКАЗАТЕЛЬСТВО. Пусть т — количество ребер в планарном графе С с и вершинами. Если т = О, тогда согласно примеру (4.58 функция Со(Л) = Л", т.е. является многочленом и-ой степени. Предположим, что теорема верна для всех планарных графов, у которых и вершин и й ребер. Напомним, что к фиксированное число, а и — нет. Пусть граф С имеет и вершин и 9+ 1 ребер. По теореме )4.64, функция Са(Л) = Ссг(Л) — Са, (Л). Но граф Сг имеет и вершин и 1с ребер, и граф С~, имеет и — 1 вершину и й ребер.
К тому же оба графа планарны. Следовательно, по индуктивному предположению функции Сак(Л) и Са, (Л)— многочлены степени и и и — 1 соответственно. Поэтому Со(Л) = Сок(Л) — Со, (Л) — многочлен степени и. Из доказанной теоремы вытекает следующая теорема. ТЕОРЕМА 14.66. Для произвольного непустого планарного связного графа С постоянный член в Са(Л) равен О. Если граф С имеет две или более вершин, то сумма коэффициентов многочлена Со(Л) равна О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
