Курсовая работа: Алгоритм раскраски графа (точный)

Задачи определения наибольших полных подграфов и НВУП являются дополнительными друг к другу. Наибольшему полному подгра­фу графа G=(Х,U) соответствует наибольшее ВУП в графе G=(Х,U), где U_полн \U, U_полн – множество ребер полного графа, построенного на n вершинах. Аналогичные рассуждения могут быть сделаны и для максимальных НП и МВУП.

Все эти задачи относятся к так называемым NP полным задачам, временная сложность которых экспоненциальна относительно входа (числа вершин или ребер графа).

Согласно классификации всех задач теории графов по их сложности, приведенной в основополагающей работе Э. Рейнгольда и других, задачи определения МВУП и МПП (нахождение клик) графа по сложности относятся к четвертому классу задач, для которых не существует и не может существовать точного полиноминального алгоритма, так как задачи этого класса обязательно экспоненциальные относительно входа. Задачи определения НПП и МВУП (наибольшей клики) относятся к третьему классу, для которого открытие полиноминального алгоритма возможно.

2. Алгоритмы раскраски вершин графа

Раскраской вершин графа G называется разбиение множества вершин Х на l непересекающихся подмножеств Х₁ , Х₂ , ..., Х_l ; ХÈХ_I ; X_i ÇX_j =Æ; i,jÎI={1,2,..,l}, (1)

таких, что внутри каждого подмножества X_i не должно содержаться смежных вершин (X_i -внутренне устойчивые подмножества).

Если каждому подмножеству х_i поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Х_j - в другой цвет и т.д. до раскраски всех подмножеств.

В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом c(G).

Очевидно, что полный граф K_n можно раскрасить только n цветами, следовательно, c(К_n ) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)<m<n(n-1)/2 верхняя оценка хроматического числа c(G) определяется как

c(G)

Нижней оценкой c(G) является число вершин в наибольшем полном подграфе графа G,т.е. его плотность. Известно утверждение, что для любого графа c(G)<1+maxr(x_i ),где х_i Î Х, iÎI={1,2,...,n},r(x_i )- локальная степень вершины х_i .Приводятся также следующие оценки:

c(G)³n² /(n² -m² ); c(G)£n+1-c(G_д ),

где G_д = К\G( дополнение графа G до полного К).

Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.

К точным алгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного программирования.

К приближенный алгоритмам раскраски относятся алгоритмы, основанные на упорядочивании множества вершин графов , последовательном удалении из графа вершин, имеющих максимальную степень и на анализе подмножеств смежности вершин.

2.1 Точные алгоритмы

Алгоритм, использующий метод Магу - Вейссмана

1. Для графа G (Х,U) построим семейство МВУП F={F_j }, где j= 1,... ,1; 1 - число МВУП.

1. 2. Составим матрицу

C_ij =

3. Для. каждой вершины графа G =(Х,U) по матрице С находим суммы тех F_j ÎF, в которые она входит, и записываем произведение этих сумм.

4. Раскрываем скобки по правилам булевой алгебры и выбираем слагаемое, состоящее из наименьшего числа сомножителей.

Рассмотрим работу описанного алгоритма на примере графа (рис.16).Согласно алгоритму Магу - Вейссмана для поиска семейства МВУП составим произведение

П_G = (X1 +Х2) (Х1+ХЗ) (Х2+ХЗ) (Х2+Х5) (Х2+Х7) (ХЗ+Х5) (ХЗ+Х6) (ХЗ+X7)*

(Х4+Х5) (Х4+Х6) (Х4+Х7) = (Х1+Х2ХЗ)*(Х2+ХЗХ5Х7) (ХЗ+Х5Х6Х7) (Х4++Х5Х6Х7) = (Х1Х2+Х1ХЗХ5Х7+Х2ХЗ+Х2ХЗХ5Х7) (ХЗХ4+ХЗХ5Х6Х7+Х4Х5Х6X7++Х5ХбХ7) =Х1Х2Х3Х4+Х1Х2Х5ХбХ7+Х1Х3Х4Х5X7+Х1Х3Х5Х6Х7+Х2ХЗХ4+

+Х2ХЗХ5Х6Х7. Р_i = Х1Х2ХЗХ4 поглощается подмножеством Р₅ =Х2ХЗХ4.

Используя условие, что в П_G в качестве сомножителей будут вершины Х\Р_j получаем следующее семейство

МВУП F={F₁ ,F₂ ,F₃ ,F₄ ,F₅ }: F₁ =X\{X1,X2,X5,X6,X7}={X3,X4}; F₂ ={X2,X6}; F₃ ={X2,X4}; F₄ ={X1,X5,X6,X7}; F₅ ={X1,X4}.

Составляем матрица C