МІНІСТЕРСТВО ОСВІТИ І НАУКИ
РОСІЙСЬКОЇ ФЕДЕРАЦІЇ
Пензенський державний університет
Кафедра САПР
Пояснювальна записка
до курсового проекту з дисципліни
"Дискретна математика "
На тему: "Алгоритм розмальовки графа (Точний) "
Виконав: студентка гр. 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 використаних джерела, додатки.
1. Теоретична частина
Графом, в загальному випадку, називаються два безлічі, що знаходяться між собою в деякому відношенні: G = (V, Е), де V - безліч вершин, Е - безліч зв'язків між ними. Вершини графа зображуються точками, а зв'язки між ними - лініями довільної конфігурації.
Зв'язок невпорядкованою пари вершин називається ребром, впорядкованої-дугою. Граф, у якого всі вершини з'єднані дугами називається орієнтованим. Граф, у якого всі вершини з'єднані ребрами називається неорієнтованим, якщо в графі присутні і ребра і дуги, то такий граф називається змішаним.
Дві вершини називаються суміжними, якщо вони визначають дугу (ребро), і дві дуги називаються суміжними, якщо вони мають спільну вершину. Вершина інцидентна дузі (ребру), якщо вона є початком або кінцем цієї дуги (ребра). Аналогічно, дуга (ребро) інцидентна вершині, якщо вона входить або виходить з цієї вершини. Число дуг (ребер), інцидентних деякої вершини, називають локальної ступенем даної вершини.
Граф, у якому будь-яка пара вершин з'єднана ребром називається повним. Повний граф зазвичай позначають через До n (n - число вершин у графі).
Число ребер повного графа m = n * (n-1)/2. Повний підграф G `= (X`, U `) графа G = (Х, U), X` ОµX називається максимальним повним подграфом (МПП) або клікою, якщо цей підграф не міститься в більшому (по числу вершин) повному підграфі.
Максимальний повний підграф, що містить найбільше число вершин з усіх МПП графа називається найбільшим повним подграфом (НПП). Число вершин найбільшого повного подграфа називається щільністю графа - П† (G). Якщо дві будь-які вершини підмножини X `графа G (Х, U), де X` ОµX не суміжні, то підмножина X `називається внутрішньо стійким.
Підмножина П€ i X графа G (Х, U) називається максимальним внутрішньо стійким підмножиною (МВУП), або незалежним підмножиною (НП), якщо додавання до нього будь-якої вершини x j ОµХ робить його не внутрішньо стійким. Підмножина Y i буде визначатися як х 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 ; 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)
c (G)
Нижньої оцінкою c (G) є число вершин у найбільшому повному підграфі графа G, тобто його щільність. Відомо твердження, що для будь-якого графа c (G) <1 + max r (x i ), де х i ГЋ Х, iГЋI = {1,2, ..., n}, r (x i ) - локальна ступінь вершини х i . Наводяться також наступні оцінки:
c (G) Ві n 2 /(n 2 -m 2 ); 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. Розкриваємо дужки за правилами булевої алгебри і вибираємо доданок, що складається з найменшого числа співмножників.
Розглянемо роботу описаного алгоритму на прикладі...
