Додаток Б

     Прикладна задача теорії графів

Методи теорії графів дозволяють розв’язувати багато технічних та теоретичних задач, таких як розрахунок електронних схем, задачі аналізу та синтезу кінцевих автоматів, задачі визначення потоків в мережах та інші.

Розглянемо задачу мінімального розфарбування графа, для розв’язання якої використаємо процедури мінімізації в алгебрі логіки.

Короткі відомості з теорії графів.

Вважають, що граф G = (X, U, F) заданий, якщо маємо X − множина вершин, U − множина ребер, F – тримісний предикат, який називають інцидентором, та який визначає, котрій парі вершин x,yÎX ставиться у відповідність ребро uÎU.

Граф можна задати графічно у вигляді рисунка та за допомогою матриць. Розглянемо приклад графа G(X, U), який зображений на рисунку 1, де X={x₁, x₂, x₃, x₄, x₅} – множина вершин, U={u₁, u₂, u₃, u₄, u₅} – множина ребер. Число вершин графа називається потужністю.

Матриця R = ||r_ij|| називається матрицею суміжності графа G = (X,U), якщо її елементи створюються за правилом: r_ij=1, якщо вершини x_ix_jX з'єднані з ребром U і r_ij=0, якщо вершини x_ix_jX не суміжні.

Для графа G ( рис. 1) матриця суміжності має вигляд:

    

Матриця І = ||і_kl||_n×r, |x| = n (число вершин графа) |u| = r (число ребер графа), називається матрицею інцидентності графа G, якщо її елементи створюються за правилом: і_kl=1, якщо вершини х_k інцидентна ребру U_l і і_kl=0 якщо х_k не інцидентна ребру U_l

Для графа G ( рис.2 ) матриця інцидентності має вигляд:

Рисунок 2 – Матриця інцидентності графа

Дамо поняття розфарбування графа.

Граф G(X, U) називається k – хроматичним (k – розфарбування), якщо можна відмітити всі вершини Х графа G індексами 1, 2, … , k, тобто розфарбувати вершини k різними кольорами) так, щоб будь-які дві суміжні вершини були відмічені різними індексами. Хроматичне число графа k(G) визначається найменшим значенням k.

Зробимо індексацію вершин графа G₁, зображеного на рис. 3.

    

В даному випадку використано мінімальну кількість фарб – дві, тобто хроматичне число дорівнює k(G) = 2.

Підмножина вершин графа називається внутрішньо стійкою, якщо будь-які дві вершини з цієї підмножини не суміжні. В кожному графі G можна виділити сім’ю Ψ={Ψ₁ ,Ψ₂ … Ψ_l} всіх внутрішньо стійких підмножин. Число внутрішньої стійкості ŋ(G) визначається потужністю внутрішньо стійкої підмножини, яка має найбільшу кількість елементів.

Для графа на рис. 3 будемо мати сім’ю внутрішньо стійких підмножин Ψ={ Ψ₁ ,Ψ₂}, де Ψ₁={ x₁ , x₃} , Ψ₂={ x₂}, отже ŋ(G) = 2.

Розв’язання задач розфарбування графа з використанням методів булевої алгебри

Розфарбування графа здійснимо за допомогою алгоритму Х. Магу, Дж.Уесмана [14]. За цим алгоритмом на основі матриці інцидентності графа складається добуток:

,

де l – множник добутка є сумою 2-х доданків, які відповідають двом вершинам графі, які з’єднані k-м ребром.

Підмножина вершин  є внутрішньо стійкою, якщо ДG=1 для системи змінних , які визначаються таким чином: xi'=1, якщо xi ψi і xi'=0 якщо xi ψi.

Для отримання мінімальної форми виразу для Д_G використаємо такі закони булевої алгебри: дистрибутивний, асоціативний та комутативний закони, а також співвідношення та закон поглинання. Тоді всі доданки цієї суми як множники будуть мати вершини з Х\ (тільки тоді Д_G =1)

Приклад: Розглянемо рішення задачі для графа G(X,U) на рис. 1. Використовуючи матрицю інцидентності складаємо вираз для Д_G :

Д_G=(х₁+ х₅)( х₂+ х₄)( х₃+ х₄)( х₃+ х₅).

Розкриваємо дужки і спрощуємо вираз за законами алгебри логіки:

Д_G=(х₁ ·х₂+ х₁·х₄+ х₂·х₅+х₄·х₅)( х₃+ х₄·х₅)= х₁ ·х₂ ·х₃+ х₁·х₃·х₄+ х₂·х₃·х₅+х₄·х_5.

Отже отримаємо сім’ю Ψ ={ Ψ₁,Ψ₂ ,Ψ₃ Ψ₄}, де , Ψ₁={ x₁ , x₂ ,x₃}

Ψ₂={ x₁ , x₄}, Ψ₃={ x₄ , x₅}, Ψ₄={ x₂ , x₅} .

Для знаходження мінімального розфарбовування множини вершин графа виконаємо такі дії [14]. Будуємо матрицю А=||а_ij||, рядки (і) якої відповідають вершинам графа Х_і, а стовпці (j) – внутрішньо стійким підмножинам ψ_i . На перетині і-го рядка і j-го стовпця ставиться 1, якщо x_i ψ_j , 0 – якщо x_ii . Для графа на рис. 1, матриця А має вигляд:

Після побудови матриці А кожній з вершин графа G співвідносять суму тих , які містять цю вершину, і записують добуток цих сум. Отже будемо мати такий вираз:

Д′_G=(Ψ₁ + Ψ₂) (Ψ₁ + Ψ₄) (Ψ₂ +Ψ₃) (Ψ₃ + Ψ₄)Ψ ₁

У виразі Д′_G розкриваємо дужки та спрощуємо вираз за правилами булевої алгебри. Після мінімізації виразу будемо мати:

Д′_G=(Ψ₁ + Ψ₁Ψ₂Ψ₄) (Ψ₃ + Ψ₂ Ψ₄) = Ψ₁Ψ₃+Ψ₁Ψ₂Ψ₄.

Кожний додаток Д′_G має підмножини, які містять в неявному вигляді всі вершини графа G. Для знаходження всіх можливих мінімальних розфарбувань треба розписати доданки і скасувати вершини, які дублюються в найменшому з додатків. Отже для графа G на рис.1 мінімальна кількість фарб є дві, які визначаються внутрішньо стійкими підмножинами Ψ₁ та Ψ₃; тобто, наприклад, вершини {x₁, x₂, x₃} пофарбуємо в білий колір, а вершини{x₄, x₅} – в червоний.