Теорема Визинга

Пусть G –простой граф, а V и W – его несмежные вершины. Пусть граф получается из G путём соединения ребром вершин V и W, а граф -путём отождествления вершин V и W( и кратных рёбер , если они при этом получаются)Тогда

Дан граф

Многочлен имеет вид:

(а, в, с –положительный const.)

Пример.

 

 

=

 

+

Итак,

 

=

 

+

=

 

+

+

 

+

 

=

 

+

 

+2

+

Итак, (К)=К (К-1)(К-2)(К-3)(К-4)+3К (К-1)(К-2)(К-3)+2К (К-1)(К-2)=К (К-1)(К-2)=

 

 

Хроматический полином Р (G,) имеет значение для каждого целого , равное числу различных правильных -раскрасок графа G. Рассмотрим граф

 

Среди данных цветов мы можем выбрать любой для раскраски вершин а. Вершину b можно раскрасить в один из оставшихся-1 цветов. Для каждой раскраски вершины b существует -1 различных способов раскраски вершины С. Итак, данный граф можно раскрасить различными способами. Хроматический полином графа равен .Повторяя эти рассуждения , получим, что хроматический полином пути на n вершинах равен

Другим важным крайним случаем является полный граф , имеющий n вершин. При ….

цветов вершину можно раскрасить в любой из них, -в любой из оставшихся -1 цветов, вершину -в любой из оставшихся -2 цветов. Итак, Р ()=(-1), и (-n+1)

Выведем формулу для определения хроматического полинома графа G.

Теорема 7

Пусть U и V – несмежные вершины простого (без петель и циклов) графа G. Пусть е=(U,V)

Если G*e – простой граф полученный из графа G замыканием вершин U и V и заменой получившегося множества параллельным ребёр на одно ребро, а G+e – граф, полученный добавлением к графу G ребра е , то Р(G,)=Р(G+е, )+Р(G*e, ).

 

Док-во:

Любая- раскраска графа G , в которой вершинам U и V присваиваются различные цвета , соответствует -раскраска графа G+e , и наоборот .Аналогично, любая -раскраска графа G , в которой U и V присвоен 1 цвет, соответствует -раскраска графа G*e , и наоборот .

Следовательно, Р(G, )=Р(G+е, )+Р(G*e, ).

Можно сформулировать следствие

Если е=(U,V) –ребро простого графа G, то Р (G, )=Р(G-е, )+Р(G*e, ), где G-е получается из G удалением ребра е, а G*e определяется в теореме.

Если повторно применить формулу, приведённую в теореме 7 к графу G, то процесс закончится полных графах, например,поэтому Р(G, )=

С другой стороны, если использовать формулу следствия , то процесс закончится на пустых графах (без ребер), поэтому хроматический полином- линейная комбинация хроматических полиномов пустых графов.

Хроматический полином пустого графа на n вершинах

Следствие. Хроматические функции простого графа представляет собой многочлен.

Док - во: Повторим процедуру, описанную в теореме 7, выбирая несмежные вершины в G1 и в G2 и соединяя и отождествляя их, в результате получим 4 новых графа. Процесс заканчивается, когда каждый граф – полный. Итак, хроматическая функция графа G является суммой многочленов и поэтому сама должна быть многочленом.

- хроматический многочлен графа G.

Если G имеет n вершин, то степень равен n , т.к. на каждом шаге не возникает новых вершин, т.к. G –полный граф с n вершинами , то коэффициент при =1

Коэффициент при равен m , где m число рёбер в G. Знаки коэффициентов чередуются .Постоянный член хроматического многочлена равен 0 , т.к. если нет красок , то нельзя раскрасить граф.

Пример 1

=

+

=

 

+

 

 

+

Р=(-1)( -2)( -3)+2(-1)( -2) +(-1) +(-1)=

(-1)= (-1)

 

 

=

+

=

+

 

+

+

=

 

+

+2

++

 

P(G)=К(К-1)(К-2)(К-3)(К-4)+3К(К-1)(К-2)(К-3)+2К(К-1)(К-2)= =

 

G- 3-хроматический граф.

Связь с задачей раскраски

Пусть нужно выбрать время проведения лекций по различным предметам с учетом того , что студенты желают посещать и те и другие. Строим граф. Вершины его- лекции по различным предметам , а рёбра соединяют те пары лекций, которые не должны назначаться на 1 время. Если каждому предмету для лекции времени сопоставить некоторый цвет, то раскраски- правильное расписание. Хроматический многочлен покажет, можно ли составить расписание требуемым образом , если да, то сколькими способами.