Алгоритм раскраски графа (точный) (стр. 1 из 4)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра САПР
Пояснительная записка
к курсовому проекту по дисциплине
“Дискретная математика”
На тему: “Алгоритм раскраски графа (точный)"
Выполнил: студентка гр. 06ВА-1
Молоткова Е.
Принял: к.т.н., доцент Валько А.Ф.
Пенза 2007г.
СОДЕРЖАНИЕ
Аннотация
1. Теоретическая часть
2. Алгоритм, использующий метод Магу - Вейссмана
2.2 Разработанный алгоритм
3. Описание программы
3.1 Общие сведения
3.2 Вызов и загрузка
3.3 Функциональное назначение
3.4 Описание логической структуры программы
3.5 Инструкция пользователю
3.6 Решение контрольных примеров
Заключение
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ
В настоящей пояснительной записке приведено описание алгоритма раскраски графа (точный). Изложены вопросы проектирования структуры программы и данных. Разработаны схемы алгоритмов решения задачи. Разработана и отлажена программа, реализующая представленные алгоритмы на языке Visual C. Представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы на ПК Intel core 2 Duo.
Пояснительная записка содержит 34 страницы, 5 рисунков, 4 использованных источника, приложения.
Графом,в общем случае, называются два множества, находящиеся между собой в некотором отношении: G=(V,Е), где V – множество вершин, Е – множество связей между ними . Вершины графа изображаются точками, а связи между ними – линиями произвольной конфигурации.
Связь неупорядоченной пары вершин называется ребром, упорядоченной- дугой. Граф, у которого все вершины соединены дугами называется ориентированным. Граф, у которого все вершины соединены ребрами называется неориентированным, если в графе присутствуют и ребра и дуги, то такой граф называется смешанным.
Две вершины называются смежными, если они определяют дугу (ребро), и две дуги называются смежными, если они имеют общую вершину. Вершина инцидентна дуге (ребру), если она является началом или концом этой дуги(ребра). Аналогично, дуга (ребро) инцидентна вершине, если она входит или выходит из этой вершины. Число дуг(ребер), инцидентных некоторой вершине, называют локальной степенью данной вершины.
Граф, в котором любая пара вершин соединена ребром называется полным. Полный граф обычно обозначают через Кn (n – число вершин в графе).
Число ребер полного графа m=n*(n-1)/2. Полный подграф G`=(X`,U`)графа G=(Х,U), X`εX называется максимальным полным подграфом (МПП) или кликой , если этот подграф не содержится в большем (по числу вершин) полном подграфе.
Максимальный полный подграф, содержащий наибольшее число вершин из всех МПП графа называется наибольшим полным подграфом (НПП). Число вершин наибольшего полного подграфа называется плотностью графа – φ(G). Если две любые вершины подмножества X` графа G(Х,U), где X`εXне смежны, то подмножество X` называется внутренне устойчивым.
Подмножество ψiX графа G(Х,U) называется максимальным внутренне устойчивым подмножеством (МВУП), или независимым подмножеством (НП), если добавление к нему любой вершины xjεХ делает его не внутренне устойчивым. Подмножество Yi будет определяться как хjεψi (Гхj uψi =)
МВУП различаются по числу входящих в них элементов. МВУП, содержащее наибольшее число элементов (вершин), называют наибольшим (предельным). Мощность НВУП (число вершин наибольшего ВУП) называется числом внутренней устойчивости
h (G) = |mах ψi |, где ψiεψ, ψ-семейство всех МВУП.
Число внутренней устойчивости называет также неплотностью графа.
Задачи определения наибольших полных подграфов и НВУП являются дополнительными друг к другу. Наибольшему полному подграфу графа G=(Х,U) соответствует наибольшее ВУП в графе G=(Х,U), где Uполн\U, Uполн – множество ребер полного графа, построенного на n вершинах. Аналогичные рассуждения могут быть сделаны и для максимальных НП и МВУП.
Все эти задачи относятся к так называемым NP полным задачам, временная сложность которых экспоненциальна относительно входа (числа вершин или ребер графа).
Согласно классификации всех задач теории графов по их сложности, приведенной в основополагающей работе Э. Рейнгольда и других, задачи определения МВУП и МПП (нахождение клик) графа по сложности относятся к четвертому классу задач, для которых не существует и не может существовать точного полиноминального алгоритма, так как задачи этого класса обязательно экспоненциальные относительно входа. Задачи определения НПП и МВУП (наибольшей клики) относятся к третьему классу, для которого открытие полиноминального алгоритма возможно.
2. Алгоритмы раскраски вершин графа
Раскраской вершин графа G называется разбиение множества вершин Х на l непересекающихся подмножеств Х1, Х2, ..., Хl; ХÈХI; XiÇXj=Æ; i,jÎI={1,2,..,l}, (1)
таких, что внутри каждого подмножества Xi не должно содержаться смежных вершин (Xi-внутренне устойчивые подмножества).
Если каждому подмножеству хiпоставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Хj - в другой цвет и т.д. до раскраски всех подмножеств.
В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом c(G).
Очевидно, что полный граф Kn можно раскрасить только 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(xi),где хiÎ Х, iÎI={1,2,...,n},r(xi)- локальная степень вершины хi.Приводятся также следующие оценки:
c(G)³n2/(n2-m2); c(G)£n+1-c(Gд),
где Gд= К\G( дополнение графа G до полного К).
Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.
К точным алгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного программирования.
К приближенный алгоритмам раскраски относятся алгоритмы, основанные на упорядочивании множества вершин графов , последовательном удалении из графа вершин, имеющих максимальную степень и на анализе подмножеств смежности вершин.
2.1 Точные алгоритмы
Алгоритм, использующий метод Магу - Вейссмана
1. Для графа G (Х,U) построим семейство МВУП F={Fj}, где j= 1,... ,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Î Х по матрице С составим суммы тех FjÎF, в которые оно входит и запишем произведение этих сумм
ПС=(F4+F5)(F2+F3)F1*(F1+F3+F5)F4*(F2+F4)F4=(F2+F3F4)F1F4=F1F2F4+F1F3F4.
Каждое из двух полученных слагаемых содержит в неявном виде все вершины графа G =(Х,U), Таким
образом, для раскраски требуется минимум 3 цвета. Раскроем слагаемые и удалим дублирующие вершины.
В результате получаем два варианта решения:
F1F2F4={ХЗ,Х4;Х2;Х1,Х5,Х6,Х7} или
F1F2F4={ ХЗ,Х4;Х2X6;Х1,Х5,Х7};
F1F3F4={X3;X2,Х4;Х1,Х5,Х6,Х7}
или F1F3F4={XЗ,X4;X2;X1,X5,Xб,X7}.
Первый и последний варианты совпали. Получены три различных варианта минимальной раскраски вершин графа.
Разработанный алгоритм работает на основе операций с матрицей смежности.
Данный алгоритм реализуется следующим образом:
За основу берется матрица смежности M для данного графа G.
Затем создается массив A, в каждой строке которого содержится множество вершин A[i]. первым элементом этого множества является вершина Xi0, номер которой совпадает с номером строки. Остальные члены этого множества – все вершины данного графа G, смежные первой вершине из этого множества.
Далее с этим массивом A проводятся следующие манипуляции: