Алгоритм раскраски

Пусть множество вершин упорядочено и - вершина этого множества

1. окрасить в цвет 1
2. каждая из оставшихся вершин окрасить : в цвет с наименьшим возможным номером ( не использованный при окраски вершины, смежной с .

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

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

 

 

Хроматические полиномы

Подсчитаем количество различных правильных К - раскрасок графа.

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

Рассмотрим граф

 

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

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

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

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

Теорема

Пусть 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 определяется в теореме.

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

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

Хроматический полином Р (G,К) графа на n вершинах имеет степень n с главным числом и const.=0. Кроме того, все коэффициенты целые и чередуются по знаку.

Док-во:

Проведём индукцией по числу рёбер m.Очевидно, что теорема справедлива для m=0, т.к. хроматический полином пустого графа на n вершинах равен .Допустим, что теорема верна для всех графов, имеющих менее m рёбер , рассмотрим граф G на n вершинах с m рёбрами. Пусть е –ребро графа G, тогда G-е – граф на n вершинах с m-1 рёбрами, а G*e –граф на n-1 вершинах с m-1 или менее рёбрами из индуктивного предположения следует, что существует такие неотрицательные целые коэффициенты и ,что

Р(G-e,К)=и . Согласно следствию Р(G,К)=

= Р(G-e,К)- Р(G*e,К)=Таким образом, граф G также удовлетворяет теореме.

Пример 1

=

+

=

 

+

 

 

+

Р(G)=К(К-1)(К-2)(К-3) К(К-1)(К-2) К(К-1)(К-2) К(К-1)

К(К-1)(К-2)(К-3)+2К(К-1)(К-2)+К(К-1)=К(К-1)((К-2)(К-3)+2(К-2)+1)=К(К-1); Р(0)= Р(1)=0; P(2)=2*10, (хроматический)

2-раскрашеный граф!

Пример 2

=

-

=

-

-

+

 

Р(G,K)=

P(0)=P(1)=0 P(2)=20,граф 2-раскрашиваемый

Пример 3

=

+

=

+

 

+

+

=

 

+

+

++

 

 

 

+

=

+3

+2

=К(К-1)(К-2)(К-3)(К-4)+3К(К-1)(К-2)(К-3)+2К(К-1)(К-2)=К(К-1)(К-2)((К-3)(К-4)+3(К-3)+2)=К(К-1)(К-2)(=;

при К=0,1,2, PG(K)=0 , при К=3: PG(K),G-3-х –хроматический граф.

Пример 4

G:

=G1

+G2

 

Тогда, =К (К-1)(К-2)(К-3)+К (К-1)(К-2)=К (К-1)(К-2)(К-3+1)=К (К-1)(К-2)

 

При К=0,1,2 =0, при К=3

=3*2*1=6 -граф 3- расрашеный

Алгоритмы и программы.