Алгоритм раскраски графа (точный) — страница 3

  • Просмотров 3868
  • Скачиваний 89
  • Размер файла 133
    Кб

содержаться смежных вершин (Xi-внутренне устойчивые подмножества). Если каждому подмножеству хi поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Хj - в другой цвет и т.д. до раскраски всех подмножеств. В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется

хроматическим числом (G). Очевидно, что полный граф Kn можно раскрасить только n цветами, следовательно, (Кn) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)<m<n(n-1)/2 верхняя оценка хроматического числа (G) определяется как (G) Нижней оценкой (G) является число вершин в наибольшем полном подграфе графа G,т.е. его плотность. Известно утверждение, что для любого графа (G)<1+max (xi),где хi  Х, iI={1,2,...,n},(xi)- локальная степень

вершины хi.Приводятся также следующие оценки: (G)n2/(n2-m2); (G)n+1-(Gд), где Gд= К\G ( дополнение графа G до полного К). Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами. К точным алгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного

программирования. К приближенный алгоритмам раскраски относятся алгоритмы, основанные на упорядочивании множества вершин графов , последовательном удалении из графа вершин, имеющих максимальную степень и на анализе подмножеств смежности вершин. 2.1 Точные алгоритмы Алгоритм, использующий метод Магу - Вейссмана 1. Для графа G (Х,U) построим семейство МВУП F={Fj}, где j= 1,... ,1; 1 - число МВУП. 2. Составим матрицу Cij= 3. Для. каждой вершины

графа G =(Х,U) по матрице С находим суммы тех Fj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 поглощается подмножеством Р5 =Х2ХЗХ4. Используя условие, что в ПG в качестве сомножителей будут вершины Х\Рj получаем следующее семейство МВУП F={F1,F2,F3,F4,F5}: F1=X\{X1,X2,X5,X6,X7}={X3,X4}; F2={X2,X6}; F3={X2,X4}; F4={X1,X5,X6,X7}; F5={X1,X4}. Составляем матрица C Для каждой вершины Хi  Х по матрице С составим суммы тех