Решение. 1 = 10 ребер и 6 вершин (по числу m ребер графа G).

1 Неориентированные графы Раздел. Пример. Построить реберный граф для графа на рис., c. 0. Решение Задачу решим графически, с помощью прямого построения реберного графа по определению. В центре каждого ребра исходного графа G поместим вершину будущего реберного графа L(G). Полученные вершины будем соединять ребрами графа L(G), если ребра графа G, на которых лежат эти вершины, смежны. На рисунке ребра графа L(G) для наглядности выделим более толстыми линиями. В результате реберный граф получит m = 0 ребер и вершин (по числу m ребер графа G). Рис. Число m соответствует тому числу, которое должно получиться по формуле (.). Степенная последовательность графа Вычислим m = ( ) = = 0. Таким образом, на рисунке совмещены исходный граф G (тонкие линии) и его реберный граф L(G) (толстые линии). Решение задачи о нахождении реберного графа в системе Maple приведено на с Хроматический полином Произвольная функция f(v) на множестве вершин графа называется раскраской графа. Раскраска называется правильной, если f(v ) f(v ) для любых смежных вершин v и v. Минимальное число k, при котором граф G является k- раскрашиваемым, называется хроматическим числом графа χ(g). Для хроматического числа имеются оценки: Теорема 7. (Брукс ). Для любого графа G, не являющегося полным, χ(g) (G), если (G) максимальная из степеней вершин графа. Для определения числа способов раскраски графа в x цветов можно составить хроматический полином P(G, x). Значение полинома при конкретном x = x 0 равно числу правильных раскрасок графа в x 0 цветов. Brooks R.L.

2 .. Хроматический полином 7 Имеется лемма, утверждающая, что хроматический полином графа имеет вид P(G, x) = P(G, x) + P(G, x), (.) где G граф, полученный из G добавлением нового ребра (uv), а граф G получается из G отождествлением вершин u и v. Другой вариант леммы: P(G, x) = P(G, x) P(G, x), (.) где G граф, полученный из G удалением ребра (uv), а граф G получается из G отождествлением вершин u и v. Операцию отождествления вершин u и v называют также стягиванием ребра (uv). Оба варианта леммы составляет основу для хроматической редукции графа. Хроматическая редукция графа представление графа в виде нескольких пустых или полных графов, сумма хроматических полиномов которых равна хроматическому полиному графа. Очевидно, что хроматический полином пустого графа O n равен x n (каждая вершина может быть раскрашена независимо от других), а для полного графа P(K n, x) = x(x )(x ). (x n + ). Последнее выражение называют факториальной степенью переменной x: P(K n, x) = x (n). Разложения по пустым и полным графам связаны. Факториальную степень можно представить в виде полинома x (n) = n s (n, k)x k, (.) k=0 где s (n, k) числа Стирлинга первого рода и, наоборот, степень x n можно выразить через факториальные степени x n = n s (n, k)x (k), (.) k=0 Граф G называется стягиваемым к графу H, если H получается из G последовательным стягиванием его ребер. Число Хадвигера (Hadwiger H.) графа G максимальный порядок полного графа, к которому стягивается граф G. Факториальная степень связана с символом (a) k Похгаммера (Pochgammer L.), который определен как (a) k = a(a + ). (a + k ). Очевидно, (a) k = = (a + k ) (k). Для символа Похгаммера имеется большое число форумул, см., например, Прудников А.П., Брычков Ю.А., Маричев О.И. Интегралы и ряды. Дополнительные главы. М.: Наука. 98

3 8 Неориентированные графы Раздел где s (n, k) числа Стирлинга второго рода, обладающие следующими свойствами s (n, k) = s (n, k ) + ks (n, k), 0 < k < n, s (n, n) =, (n 0), s (n, 0) = 0, (n > 0). (.7) При получении хроматического полинома могут быть полезны следующие теоремы []. Теорема 8. Коэффициенты хроматического полинома составляют знакопеременную последовательность. Теорема 9. Абсолютная величина второго коэффициента хроматического полинома равна числу ребер графа. Теорема 0. Наименьшее число i, для которого отличен от нуля коэффициент при x i в хроматическом полиноме графа G равно числу компонент связности графа G. Кроме вершинной раскраски существует еще реберная раскраска и раскраска граней. Задачи. Найти хроматический полином графа (..9) и вычислить число способов раскраски графа в x 0 цветов x 0 = x 0 = x 0 = x 0 = x 0 = x 0 = Stirling T.

4 .. Хроматический полином x 0 = x 0 = x 0 = Ответы C(x) C(x 0 ). x 8x + x 8x + 8x 8x 88. x 9x + 9x 9x + 8x 0. x x + x x + x 0. x x + 0x 9x + x 00. x 8x + x x + x x. x 9x + x x + x x x 9x + x x + x 0x 80.8 x 8x + x x + x x x 8x + x 8x + 8x 8x 0. Пример. Найти хроматический полином графа (рис. ). Решение В зависимости от числа ребер графа можно использовать разложение (.) или (.). Если графа почти полный, то добавив несколько ребер по разложению (.), получим хроматический полином в виде суммы факториальных степеней. Если же ребер мало, и для получения Рис. пустого графа требуется удалить только несколько ребер, то следует использовать разложение (.) с удалением ребер. Такие действия называются хроматической редукцией.. Хроматическая редукция по пустым графам. Воспользуемся леммой (.). Удаляя ребра и отождествляя соответствующие вершины (стягивая ребра), сведем исходный граф к пустым графам. Сначала разложим граф на два, убрав, а затем стянув ребро -. Выполненное действие запишем в виде условного равенства

5 0 Неориентированные графы Раздел G = = = G G. Здесь операция сложения или вычитания относится не к самому графу, а к его хроматическому полиному. Таким образом последнее равенство означает,что P(G) = P(G ) P(G ). Длясокращениязаписи обозначение P() будем опускать. Далее разложим каждый из графов G и G, пользуясь той же леммой G = = = = O O (O O ), G = = = = O O (O O ). Приведем подобные члены G = G G = O O (O O ) (O O (O O )) = O O + O O. Получим в итоге искомый хроматический полином (.8) P(G, x) = x x + x x. (.9) Разложение (.8) называется хроматической редукцией графа по пустым графам. Очевидно, результат соответствует утверждениям теорем 8-0. Коэффициенты в.9 образуют знакопеременную последовательность, а коэффициент при x равен числу ребер. Наименьшая степень x в полиноме равна, т.е. числу компонент связности графа.. Хроматическая редукция по полным графам. Добавим сначала к графу (рис. ) ребро -, получим граф с большим числом ребер. Затем в этом же (исходном) графе отождествим вершины и. В результате получим два графа G = = + (.0) Отождествление вершин всегда приводит к уменьшению порядка и (иногда) размера графа. Второй граф это полный граф K, его преобразовывать больше не требуется. К первому графу добавим ребро - и отождествим вершины и : = + = K + K. (.)

6 .. Хроматический полином В итоге Хроматический полином примет вид = K + K. (.) P(G, x) = x () + x () = x(x )(x )(x )+ + x(x )(x ) = x x + x x. (.) Разложение (.) называется хроматической редукцией графа по полным графам. Оба способа дали один результат, и из редукции по полным графам легко следует редукция по пустым. Для этого достаточно раскрыть скобки и привести подобные члены, как в (.). Однако обратное действие не очевидно. Для того, чтобы полином x x + x x, полученный из пустых графов, выразить в виде суммы факториальных степеней, необходимы числа Стирлинга -го рода. Согласно рекуррентным формулам (.7) имеем следующие числа s (, ) = s (, ) + s (, ) =, s (, ) = s (, ) + s (, ) = + = 7, s (, ) = s (, ) + s (, ) = + =. Пользуясь (.) и найденными числами Стирлинга -го рода, получим x = x () + x (), x = x () + x () + x (), x = x () + 7x () + x () + x (). Таким образом произведем преобразование хроматического полинома x x + x x = x () + 7x () + x () + x () (x () + x () + x () ) + (x () + x () ) + x () = x () + x (). Хроматическое число χ(g) графа лучше всего получить, разложив хроматический полином на сомножители P(G, x) = x(x ) (x ). Минимальное натуральное число x, при котором P(G, x) не обращается в ноль равно. Отсюда получаем χ(g) =. Так как максимальная степень вершин графа (G) =, то выполняется оценка χ(g) (G) (с. ). Maple-программа для нахождения хроматического полинома графа с использованием оператора chrompoly пакета networks приведена на с. 97.