Реферат Курсовая Конспект
Алгоритм раскраски - раздел Математика, Эти множества – независимые, т.к. в пределах 1 множества нет смежных двух вершин Пусть Множество Вершин Упорядочено И ...
|
Пусть множество вершин упорядочено и - вершина этого множества
Связь с задачей раскраски
Пусть нужно выбрать время проведения лекций по различным предметам с учетом того , что студенты желают посещать и те и другие. Строим граф. Вершины его- лекции по различным предметам , а рёбра соединяют те пары лекций, которые не должны назначаться на 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- расрашеный
Алгоритмы и программы.
– Конец работы –
Эта тема принадлежит разделу:
Разнообразные задачи возникающие при планировании производства составлении графиков осмотра хранении и транспортировке товаров могут быть... Задача о раскраске графа Графы неориентированные и без петель простые... Граф G хрономический если его вершины могут быть раскрашены с помощью цветов красок так что не найдутся две...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм раскраски
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов