фарбування графа G. Таким чином, складання оптимального Розкладая зводу до знаходження оптимального розфарбування побудованого нами графа.
Розглянемо приклад Завдання на складання Розкладая . У студентських групах КН - 101 и КН - 102 треба провести заняття з алгебри, діскретної математики, математичного АНАЛІЗУ та історії України (по одному занятть за шкірним предмету). Заняття за шкірним предмету проводяться з шкірними Груп окремо. Заняття з алгебри та з діскретної математики веде викладач X, з математичного АНАЛІЗУ - викладач Y, з історії Росії - викладач Z. знайте мінімальне число пар, в Які можна «укласті» всі заняття, и Скласти відповідній розклад.
Рішення . Побудуємо граф з вершинами А1, А2, Д1, Д2, Ml, М2, І1 и І2 (літера відповідає предмету, а цифра - номеру групи). З'єднаємо ребрами вершини, что відповідають парам, Які нельзя Проводити одночасно. Отрімаємо граф, збережений на малий. 5 ліворуч. Вершини А1, А2, Д1 и Д2 цього графа породжують в цьом графі підграф, ізоморфній графу. Отже, хроматична число нашого графа НЕ менше 4. На малий. 5 праворуч вказана правильне розфарбування нашого графа в 4 кольори. Отже, хроматична число графа дорівнює 4, тобто всі заняття можна провести за 4 парі. Відповідній розклад вказано в табліці.
Мал. 5
КН - 101КН - 1021 параАлгебраМатематічній аналіз2 параМатематічній аналізАлгебра3 параІсторія УкраїніДіскретна математіка4 параДіскретна математікаІсторія України
Завдання розподілу обладнання
Друге Завдання, Пожалуйста ми розглянемо, - Завдання розподілу обладнання. Є Деяка Кількість робіт и механізмів для їх Здійснення. Для виконан кожної роботи нужно одна и тієї самий годину. При цьом Жодний з механізмів НЕ может буті зайнятості одночасно более чем в одній работе. Потрібно розподіліті Механізми так, щоб загальний годину Виконання робіт Було мінімально можливіть.
Для перекладу цього Завдання на мову Теорії графів розглянемо граф G , вершинами которого є роботи, причому две Різні вершини суміжні тоді и только тоді, коли для виконан відповідніх робіт нужно хоча б одна загальний Механізм. При правильному розфарбовуванні цього графа вершини, розфарбовані одним и тім же Кольорах, відповідають роботам, Які можна Проводити одночасно. Тому Завдання зводу до знаходження оптимального розфарбування графа G .
Розглянемо приклад . На підприємстві планується віконаті 8 робіт ,, ... ,. Для виконан ціх робіт необхідні Механізми ,, ... ,. Використання механізмів для кожної з робіт візначається Наступний таблицею:
МеханізмРобота ++++ ++ +++ ++++ +++ +++
Жоден Із механізмів НЕ может буті використаних одночасно на двох роботах. Виконання кожної роботи займає 1 годину. Як розподіліті Механізми так, щоб сумарная годину виконан всех робіт БУВ мінімальнім и Який цею годину?
Рішення. Розглянемо граф G , вершинами которого є плановані роботи ,, ... ,, а ребра з'єднують роб?? ти, в якіх бере доля хоча б одна загальний Механізм (і Які, з цієї причини, не можна Проводити одночасно). Цей граф збережений на малий. 6. Вершини ,,, породжують підграф графа G ізоморфній. Отже,.
Цифри в дужках на малий. 6 вказують правильно Розмальовки графа G в 4 кольори. Отже,. Таким чином, всі роботи можна віконаті за 4 години. Для цього, відповідно до знайденого розфарбування графа G , треба в 1-у годину Виконувати роботу І, у 2-й - роботи І, в третіх - роботи І, в 4-й - роботи и.
Мал. 6
2. Практична частина
Завдання графу матрицею суміжності:
Uses crt; MS=array [1..10,1..10] of Integer;: MS; n, i, j: Integer ;; ( Введіть Кількість вершин: ); (n); ( Введіть матрицю суміжності: ); i:=1 to n doj:=1 to n do (j * 2, i + 3); ( ); (a [i, j]) ;;;;
Завдання графу списком суміжності: GList=array [1..10] of record: Integer;:Array [1..10] of Integer; ;=array [1..10] of Byte; Graph: GList; Color: Clist;
2.1 Програмна реалізація алгоритму розфарбування графів
Procedure GetColor; i:=1 to n do [i]:=1; i:=2 to n do:=1; (j lt;=Graph [i] .Count) and (Graph [i] .List [j] lt; i) doColor [i]=Color [Graph [i] .List [j]] Then [i]:=Color [i] +1;:=1 ;: =j + 1 ;;;;
.2 Контрольні приклада
Повний код програми:
Program algorytmGraf; crt; GList=array [1..10] of record: Integer;: array [1..10] of Byte ;;=array [1..10] of Byte; Graph: GList; Color: CList; i, j, n: Byte; G: File of GList; s: string; GetColor; ...
