4 Вказівки по виконанню курсової роботи

При виконанні КР необхідно послідовно розробляти основні розділи, використовуючи літературу, що рекомендується, і дані методичні вказівки.

У вступі варто відобразити застосування теорії графів і алгебри логіки в різних галузях виробництва й інших сфер людської діяльності; указати мету й основні задачі КР.

У розділі «Задачі теорії графів» необхідно:

1. Здійснити опис графа за допомогою таблиці, фактор-множини, матриці інціденцій, матриці суміжності вершин, матриці циклів, матриці розрізів і матриці шляхів.

2. Визначити числові характеристики графа такі як: ступеня всіх його вершин (v), вершинну (G) і реберну (G) зв’язність, цикломатичне число  (G), вершинне ₀(G) і реберне ₁(G) числа незалежності, числа вершинного ₀(G) і реберного ₁(G) покриття, вершинне ₀(G) і реберне ₁(G) числа зовнішньої стійкості, радіус R₀ і діаметр T графа.

3. Розв’язати одну із задач відповідно до варіанта:

   1. Задача розфарбування графа,

   2. Задача комівояжера,

   3. Задача про найкоротший шлях,

   4. Задача про максимальний потік.

У розділі «Синтез логічних схем» необхідно:

1. Для заданої функції алгебри логіки скласти таблицю істинності. Записати досконалі диз'юнктивну й кон’юнктивну нормальні форми.

2. Провести аналіз функції алгебри логіки на приналежність до класів функцій, що зберігають нуль, що зберігають одиницю, лінійних, самодвоїстих і монотонних.

3. Виконати мінімізацію логічної функції методом Квайна-МакКласки й за допомогою карт Карно.

4. Синтезувати логічну схему методом каскадів і реалізувати її в базисі (&, V, ¬) з використанням двовходових елементів.

Висновки повинні містити виводи й оцінку отриманих результатів у цілому, з погляду відповідності їхньому завданню, порівняння результатів розрахунків, проведених у різних розділах КР.

Літературні джерела, використані при виконанні КР, заносяться в список. Джерела в списку варто розташовувати у відповідності з посиланнями на них. Список оформляється як розділ КР відповідно до вимог ДЕРЖСТАНДАРТ 7.1-84.

У додатках розташовуються блок-схеми алгоритмів і тексти програм для ЕОМ, які були написані й використані при виконанні КР, а також роздруківки з результатами виконання цих програм.

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

5 Рекомендації з виконання курсової роботи

1. Теорія графів.

Граф є сукупність непустої множини V, ізольованої від неї множини E (можливо порожньої) і відображення Φ множини E на V&V. Елементи множин V і E називаються вершинами й ребрами графа відповідно, а Φ – відображенням інціденції графа. Граф позначають або . Самий наочний спосіб опису графа є його графічне зображення (рис. 5.1).

Рис. 5.1 - Неорієнтований граф

5.1.1 Формалізоване завдання графа

Граф задається на множині вершин V і множині ребер Е. Найбільш простий опис графа – складання таблиці відповідності ребер і вершин. Для графа, наведеного на рис. 5.1, таблиця відповідності складається наступним чином:

Табл. 5.1 - Таблиця відповідності графа

Е	e1	e2	e3	e4	e5	e6	e7	e8	e9	e10	e11
V	v5	v3, v5	v1, v3	v1, v2	v2, v3	v2, v4	v3, v4	v6, v7	v6, v8	v6, v8	v7, v8

Для формального опису графів можливо використовувати також фактор-множину. Для лівої частини графа наведеного на рис. 5.1 фактор-множина має вид

.

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

1) Матриця інціденцій A = [a_ij].

Для графа G, що має n вершин і m ребер матриця інціденцій має розмірність nm. Рядки цієї матриці відповідають вершинам, а стовпці – ребрам графа. Елемент a_ij = 1, якщо j-те ребро інцідентно i-ой вершині й a_ij=0 у противному випадку. При складанні матриці інціденцій петлі із графів видаляють. Для графа, наведеного на рис. 5.1, матриця інціденцій має вигляд:

Якщо граф складається з декількох окремих підграфів, то його матриця інціденцій має блокову діагональну структуру, у якій матриці А_i є матрицями інціденцій для кожного підграфа.

Для орієнтованого графа (рис. 5.2) елементи матриці інціденцій a_ij= +1, якщо дуга j орієнтована від вершини i, a_ij= -1, якщо дуга j орієнтована до вершини i, a_ij= 0, якщо дуга j не інцідентна вершині i.

Рис. 5.2

2) Матриця суміжності вершин V = [v_ij].

Для графа G, що має n вершин, матриця суміжності вершин має розмірність nn. Елемент v_ij цієї матриці дорівнює числу ребер, що інцідентні одночасно i-ой і j-ой вершинам графа. Для неорієнтованого графа, наведеного на рис. 5.1, матриця суміжності вершин має вигляд:

Для орієнтованого графа елементи матриці суміжності вершин дорівнюють числу дуг, направлених одночасно від i-ой вершини графа до його j-ой вершини. На рис. 5.3 приведений приклад складання матриці суміжності вершин для орієнтованого графа.

Рис. 5.3

3) Матриця циклів C = [с_ij].

Для графа G, що має n вершин і m ребер, матриця циклів має розмірність km, де k – число циклів у графі G. Елемент цієї матриці с_ij =1, якщо j-е ребро входить в i-ий цикл і с_ij = 0 у противному випадку. Для графа, наведеного на рис. 5.1, матриця циклів має вигляд:

Якщо граф складається з декількох окремих підграфів, то його матриця циклів, як і матриця інціденцій, має блокову діагональну структуру.

Для орієнтованих графів контурам (циклам) довільно задають орієнтацію, однакову для всіх контурів. Тоді с_ij = +1, якщо j-а дуга зінаправлена з i-им контуром, с_ij = -1, якщо j-а дуга протилежно направлена i-ому контурові й с_ij = 0, якщо j-а дуга не входить в i-ий контур. Приклад наведений на рис. 5.4.

Рис. 5.4

Для побудови матриць розрізів і шляхів варто ввести поняття зв’язності графа й розрізу на графі.

Характеристика графа, називана зв’язністю, застосовна до неорієнтованих граф. Граф G = (V, Е) зв'язний, якщо будь-які його дві вершини можна з'єднати хоча б одним ланцюгом. Якщо граф G = (V, Е) не зв'язний, то його можна розбити на такі підграфи G_i, що всі вершини в кожному підграфі зв'язні, а вершини з різних підграфів не зв'язні. Такі підграфи G_i називають компонентами зв’язності графа G.

Теорема: Граф G = (V, Е) зв'язний тоді й тільки тоді, коли множину його вершин не можна розбити на дві непустих підмножини V₁ і V₂ так, що обидві граничні точки кожного ребра знаходяться у тієї самої підмножині.

Для того, щоб визначити зв’язність орієнтованого графа, не слід звертати увагу на орієнтацію його дуг. Для орієнтованого графа існує поняття сильної зв’язності. Граф сильно зв'язний, якщо для будь-яких двох вершин v₁ і v₂ (v₁v₂) існує шлях, що йде з v₁ в v₂.

Вибравши у зв'язному графі початкову (v₁) і кінцеву (v₂) вершину, для нього можна скласти матрицю шляхів (матрицю ланцюгів) . Рядки цієї матриці відповідають ланцюгам між вершинами v₁ і v₂, а стовпці відповідають ребрам графа. Елемент матриці p_ij = 1, якщо j-е ребро належить i-ому ланцюгу й p_ij = 0 у противному випадку (рис. 5.5). Для одного графа можна скласти множину матриць ланцюгів, вибираючи для цього різні початкову й кінцеву вершини.

Рис. 5.5

Для орієнтованих графів матриця шляхів складається, якщо є хоча б один шлях, що веде з початкової в кінцеву вершину. Елемент матриці p_ij = 1, якщо j-а дуга належить i-ому шляху й p_ij = 0 у противному випадку (рис. 5.6).

Рис. 5.6

Якщо задано зв'язний граф G = (V, Е) і множу його вершин розбито на дві непустих підмножини W і W’, то множина ребер, що з'єднують W з W’ називають розрізом. Простим називають розріз, що розбиває зв'язний граф тільки на дві компоненти зв’язності. З використанням простих розрізів можна побудувати матрицю розрізів графа K = [k_ij]. Для графа G, що має n вершин і m ребер, матриця розрізів має розмірність lm, де l – число розрізів на графі G. Елемент цієї матриці k_ij =1, якщо j-е ребро входить в i-ий розріз і k_ij = 0 у противному випадку (рис. 5.7).

Рис. 5.7

При складанні матриці розрізів для орієнтованого графа варто враховувати орієнтацію його дуг. Елементи матриці, що відповідають протилежно направленим дугам, будуть мати протилежні знаки (+1 і -1). Приклад складання матриці розрізів для орієнтованого графа наведений на рис. 5.8.

Рис. 5.8.

5.1.2 Числові характеристики графа.

Число ребер неорієнтованого графа, інцідентних вершині v (петля враховується двічі), називається ступенем вершини v і позначається (v). Для ізольованої вершини (v) = 0. Для будь-якого кінцевого графа справедливе твердження:

.

Із цього твердження слід, що сума ступенів вершин кінцевого невиродженого графа завжди парне число.

Теорема: У кінцевому графі число вершин непарного ступеня завжди парно.

Нехай V₀ – множина вершин графа G, що мають парний ступінь, а V₁ – множина вершин того ж графа, що мають непарний ступінь. Очевидно, що парно, як кінцева сума парних чисел. Звідси треба, що

також обов'язково парно.

В орієнтованому графі дуга e позитивно інцідентной своїй початковій вершині v. Число дуг, позитивно інцідентних вершині v, називається позитивним ступенем вершини v і позначається ⁺(v). Число дуг, негативно інцідентних вершині v, називається негативним ступенем вершини v і позначається ^(v). Орієнтована петля, інцідентна вершині v, вважається позитивно й негативно інцідентній v одночасно. Очевидно, що (v) = ⁺(v) + ^(v). З огляду на те, що кожна дуга позитивно інцідентна тільки одній вершині й негативно інцідентна також тільки одній вершині, одержимо:

.

З погляду зв'язності графа становлять інтерес два випадки, наведених на рис. 5.9:

а) наявність у графі точки зчленування вершини v_С, видалення якої разом з інцідентними їй ребрами робить граф незв'язним;

б) наявність у графі «моста» - ребра е_С, видалення якого робить граф незв'язним.

Рис. 5.9

Мінімальне число вершин, видалення яких робить граф незв'язним, називається вершинною зв’язністю (G) графа G. Мінімальне число ребер, видалення яких робить граф незв'язним, називається реберною зв’язністю (G) графа G. Якщо позначити (G) мінімальний ступінь вершини в графі G, то має місце наступна нерівність:

(G)   (G)  (G).

Існує ще ряд спеціальних числових характеристик (інваріантів) графів.

Цикломатичне число. Нехай G = (V, E) – неорієнтований граф, що має n вершин, m ребер і r компонент зв'язності. Цикломатичним числом графа G називають число

 (G) = m – n + r.

Цикломатичне число дорівнює найбільшому числу незалежних циклів у графі. При розрахунку електричних кіл цикломатичним числом можна користуватися для визначення числа незалежних контурів.

Хроматичне число. Нехай р – натуральне число. Граф G = (V, E) називають р-хроматичним, якщо його вершини можна розфарбувати р різними квітами так, щоб ніякі дві суміжні вершини не були розфарбовані в той самий колір. Найменше число р, при якому граф є р-хроматичним, називають хроматичним числом графа (позначається  (G)). Якщо  (G) = 2, то граф називають бихроматичним. Необхідною й достатньою умовою бихроматичності графа є відсутність у ньому циклів непарної довжини (теорема Кеніга). Хроматичне число виконує важливу роль при розв'язанні задачі найбільш економічного використання пам'яті при програмуванні.

Множина внутрішньої стійкості. Множина S  V графа G = (V, Г) називають внутрішньо стійкою, якщо ніякі дві вершини з S не суміжні, тобто для будь-якого х  S має місце Гх  S = .

Множина внутрішньої стійкості, що містить найбільше число елементів, називають найбільшою внутрішньо стійкою множиною, а число елементів цієї множини – числом внутрішньої стійкості ₀ (G) графа G (іноді це число називають також вершинним числом незалежності графа).

Два ребра графа називають суміжними, якщо вони інцідентні однієї й тій же вершині. Максимальне число попарно несуміжних ребер графа називається його реберним числом незалежності ₁ (G).

Покриття графа. Якщо ребро графа інцідентно його вершині, то говорять, що вони покривають один одного. Множина вершин, що покривають всі ребра графа, називають вершинним покриттям графа G, а мінімальну потужність цієї множини – числом вершинного покриття графа ₀ (G). Аналогічно, множина ребер, що покривають всі вершини графа, називають реберним покриттям графа G, а мінімальну потужність цієї множини – числом реберного покриття графа ₁ (G).

Множина зовнішньої стійкості. Множина Т  V графа G = (V, Г) називають зовні стійким, якщо будь-яка вершина, що не належить Т, з'єднана ребрами з вершинами з Т, тобто для будь-якого х  Т має місце Гх  Т  .

Якщо прийняти, що кожна вершина графа покриває сама себе, а дві суміжні вершини покривають один одного, то множина зовнішньої стійкості можна визначити як множина вершин графа, що покриває всі його вершини.

Множина зовнішньої стійкості, що містить найменше число елементів, називають найменшою зовні стійкою множиною, а число елементів цієї множини – вершинним числом зовнішньої стійкості ₀ (G) графа G.

Аналогічно можна прийняти, що кожне ребро графа покриває саме себе, а два суміжних ребра покривають один одного. Мінімальна потужність множини ребер, що покривають всі ребра графа, називається реберним числом зовнішньої стійкості ₁ (G) графа G.

Радіус і діаметр графа. Нехай G = (V, Е) – зв’язний граф. Якщо , то є кількістю ребер, які містяться в найкоротшім ланцюгу, з’єднуючім v і w. Для усіх v . Для фіксованої вершини v ціле число відповідає відстані від v до найбільш віддаленої вершини графа. Радіусом графа називають , вершину вважають центром графа, якщо . Діаметром зв’язного графа є максимальна відстань між парами вершин – .

Обчислення розглянутих інваріантів графів потрібно при розв'язанні багатьох практичних задач. Розглянемо знаходження числових характеристик на прикладі графа, наведеного на рис. 5.10.

Рис. 5.10

а) вершинна зв'язність (G) = 2 (вершини 2 і 3 або 3 і 5);

б) реберна зв'язність (G) = 2 (ребра a і b або e і g);

в) цикломатичне число (G) = 7 – 5 + 1 = 3 (із шістьох контурів три незалежні);

г) хроматичне число (G) = 3 ((G)  2, тому що є цикл довжиною 3 ребра);

д) вершинне число незалежності графа ₀(G)=2 (наприклад, вершини 1 і 4);

е) реберне число незалежності графа ₁(G) = 2 (наприклад, ребра а й g);

ж) число вершинного покриття ₀(G) = 3 (наприклад, вершини 2, 3 і 4);

з) число реберного покриття ₁(G) = 3 (наприклад, ребра b, d і g);

и) вершинне число зовнішньої стійкості ₀(G) = 1 (вершина 3);

к) реберне число зовнішньої стійкості ₁(G) = 2 (наприклад, ребра а й f);

л) радіус ; центральна вершина 3.

м) діаметр .

5.1.3 Задачі теорії графів

1. Задача розфарбування графа.

Розфарбуванням вершин графа G (V, Е)  фарбами називається розбивка множини вершин V графа G, при якому кожна підмножина V_i не містить ні однієї пари суміжних вершин

.

Інакше кажучи, розфарбування графа λ фарбами називається правильною, якщо початок кожного його ребра розфарбований в один колір, а кінець - в інший колір, тобто суміжні вершини графа розфарбовані різними фарбами.

Стосовно до розфарбування графів звичайно виділяють задачі трьох видів:

1) Визначення хроматичного числа графа, тобто найменшої кількості фарб, яким можна правильно розфарбувати граф. Практичного способу точного визначення хроматичного числа графа не існує. У загальному випадку є гіпотеза про чотири фарби (яка не доведена й не спростована), що затверджує, що для плоского графа (G)  4.

Частковим випадком цієї задачі є перевірка графа на біхроматичність, що виконується на основі теореми Кеніга.

Хроматичне число графа може бути оцінене через його параметри (ступінь вершин і верхове число незалежності):

а) якщо максимальний ступінь вершини графа дорівнює _max(G), те хроматичне число графа не перевищує величини _max(G) + 1, тобто (G)  _max(G) + 1;

б) для будь-якого графа G(V, Е) з вершинним числом незалежності ₀(G) справедливе твердження:

.

2) Виконання правильного розфарбування графа. Ця задача при відомому хроматичному числі є досить простою і вирішується евристично. Одна з вершин використається в якості початкової й розфарбовується довільним кольором, всі суміжні з нею вершини розфарбовуються іншими фарбами з урахуванням їх суміжності між собою й т.д.

3) Визначення числа правильних розфарбувань графа з відомим хроматичним числом. Для невеликих графів число правильних розфарбувань із використанням λ фарб визначається по формулі:

,

де s – число ребер у підграфі; с – кількість компонентів зв'язності;

р(s, с) – число підграфів з s ребрами й c компонентами зв'язності.

Для графа G, що має n вершин і m ребер, параметр s буде приймати значення від 0 до m, а параметр c – від n до 1 (природно, що s і с – цілі числа). Для того, щоб уникнути помилок при підрахунку числа підграфів р(s, с) можна скористатися формулою

,

з огляду на при цьому наступні обставини:

• для будь-якого m (оскільки 0! = 1);

• значення р(s) розраховується для кожного значення s, без обліку значення с.

Відшукуємо число правильних розфарбувань графа G, що зображений на рис. 5.11.

Рис. 5.11

Розглянемо всі різноманітні випадки підграфів, що відрізняються кількістю ребер та компонент зв’язності:

1) s = 0; с= 5; р(0, 5) = 1

2) s = 1; с= 4; р(1, 4) = 5

3) s = 2; с = 3; р(2, 3) = 10

4) s = 3; с = 2; р(3, 2) = 10

Наступні етапи заслуговують на особливу увагу: р(4) = 5, але число підграфів у цьому випадку доцільно розділити залежно від числа компонентів зв'язності наступним чином:

5) s = 4; с= 2; р(4, 2) = 1

6) s = 4; с = 1; р(4, 1) = 4

та наприкінці

7) s = 5; с = 1; р(5, 1) = 1

В остаточному вигляді число правильних розфарбувань визначиться виразом:

Це вираження дає також можливість відшукати хроматичне число графа – їм буде найменше значення , при якому хроматичний поліном (G,)  0.

Для спрощення підрахунку числа правильних розфарбувань графа звичайно задачу розбивають на більш прості. Основою для такого спрощення служать наступні леми.

Лема 1: Якщо графи G₁ і G₂ не зв'язані, тобто являють собою компоненти зв'язності графа G (рис. 5.12), те

.

Рис. 5.12

Лема 2: Якщо граф G має точку зчленування v_С (рис. 5.13), те

.

Рис. 5.13

Лема 3: Якщо граф G має міст е_С (рис. 5.14), те

.

Рис. 5.14

Лема 4: Якщо граф G отриманий із графа G₁ додаванням ребра е без зміни числа вершин (рис. 5.15), те

де граф отриманий з G₁ склеюванням висячої вершини, інцидентній ребру е, і перетворенням отриманого графа в простий граф шляхом об'єднання паралельних ребер.

Рис. 5.15

2. Задача комівояжера.

Задача про комівояжера - пов'язана з пошуком найкоротшого гамільтонова контуру.

Комівояжер повинен побувати по одному разу у кожному з n міст (кожна пара міст пов'язана шляхом) і повернуться у вихідне місто. При цьому він повинен вибрати найкоротший маршрут.

Визначення найкоротшого маршруту за допомогою перегляду всіх гамільтонових циклів приводить до перебору ( n-1)!/2 можливих циклів; для великих n ця величина є астрономічною. Ефективного алгоритму розв'язання такої задачі ще не існує. Однак існують деякі обчислювальні алгоритми.

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

Передбачається, що граф є плоским і має хоча б одну вершину ступеня 5 або менше. Починаючи з довільної вершини v₁, мінімального ступеня δ ≤ 5 можна визначити C²_δ ≤ 10 різних підграфів, кожний з яких складається із всіх вершин графа G, всіх ребер, не інцідентних з v₁ і двох з δ ребер, інциідентних v₁. Таким чином, задача зводиться до знаходження гамільтонових циклів у C²_δ отриманих підграфах, кожний з яких містить вершину v₁ ступеня 2.

Розглянемо приклад. Нехай заданий граф G (рис. 5.16):

G:

Рис. 5.16

Вершина v₁ має мінімальний ступінь δ = 3, отже, число можливих підграфів для знаходження гамільтонових циклів С²₃=3. Вони мають такий вигляд.

G1:		G2:
G3:

У підграфі G_i вибирають вершину v₁ ступеня 2, починаючи з ребра е₁ інцідентного v₁ і суміжній вершини найменшого ступеня, будується гамільтонов цикл C_n з послідовності n простих ланцюгів C_k = (e₁,…,e_k), з урахуванням того, що v_n+1 ≡ v₁.

Ребро е_к може приєднаються до С_к-1, якщо виконуються наступні умови:

1. v_k+1 ≠ v_j (j = 1,2,…k),якщо k ≠ n (приєднується ще не розглянута вершина).

2. С_к = С_к-1 U {e_k} не розділяє граф, що залишився, таким чином, що будь-які дві вершини із тих, що залишилися {v_k+2,…,v_n+1≡v₁}, можуть бути зв'язані ланцюгом з ребер не інцідентних жодній вершині (тобто отриманий граф G_i повинен бути зв'язаний на кожному кроці).

Якщо декілька ребер задовольняють умовам додавання до ланцюга в одній і тій же вершині, то вибирається ребро найменшої довжини, а інші ребра запам'ятовуються.

Якщо жодне ребро не задовольняє умовам 1 і 2 і не може бути приєднане до кінцевої вершини v_k+1 ланцюга С_к, то такий ланцюг не є частиною гамільтонова циклу й відкидається. При цьому виконується повернення в останню вершину довільно обраного ребра й досліджується новий ланцюг.

Після того, як знайдений перший гамільтонов цикл С_n (у будь-якому підграфі), можна обчислити його довжину |С_n|. Нехай С’_к означає деяку частину ланцюга, що будується, в підграфі G_i довжиною |с'_к|. Для того, щоб ланцюг С’_к увійшов в гамільтонов цикл із довжиною меншою ніж |С_n|, необхідно забезпечити виконання умови

| С’_к| + (n - k)s_i < |С_n|,

де s_i – довжина найкоротшого ребра в підграфі G_i , на кожному кроці процедури (для всіх k = 1, 2, ..., n).

Розглянемо підграф G₁. Жирні ребра відповідають ребрам шуканого гамільтонова циклу. У дужках біля вершини відзначають число ребер (альтернативних варіантів), що залишились для дослідження.

G₁: s₁ = 1.

10.		20.
30.		40.

Довжина циклу C₆ підграфа G₁ дорівнює 13. Розглянемо альтернативу (розгалуження).

20а.

З ребер довжиною 1, 4 і 5, відповідно до умови 2, можна додати тільки 5.

Перевіримо умову | С’₃| + (6 - 3)s_i < |С_n|, тобто (1+7+5)+3 =16 > 13. Це означає, що другий (альтернативний) цикл гамільтона для цього підграфа буде довше першого.

Повторимо всі побудови для підграфа G₂: s₂ = 1.

10.		20.
30.		40.

Довжина знайденого гамільтонова циклу C₆ для підграфа G₂ дорівнює 10. Роздивимося розгалуження.

30а

Довжина циклу | С’₃| + (6 - 3)s_i < |С_n|, тобто (1+1+3)+3 =7 < 10. Приєднаємо ще одно ребро.

40а.

Перевіримо умову | С’₄| + (6 - 4)s_i < |С_n|, тобто (1+1+3+4)+2= 13 > 10, подальші побудови - неефективні.

Повернемося до більш ранньої альтернативи.

20б.

Оцінимо довжину ланцюга, що будується, | С’₂| + (6 - 2)s_i < |С_n|, тобто (1+7)+4 = = 12 > 10.

Таким чином, мінімальний гамільтонов цикл у другому підграфі має довжину рівну 10.

Розглянемо підграф G₃: s₃ = 1.

10.

20.

Довжина ланцюга | С’₂| + (6 - 2)s_i < |С_n|, тобто (2+5)+4 = = 11 > 10.

Кратчайшим гамильтоновым циклом графа G является цикл длиной равной 10, найденный в подграфе G₂.

Розглянутий метод добре працює для невеликих графів. Реалізація методу на ЕОМ ускладнена перевіркою умови 2, що дуже просто перевіряється графічно. Для розв'язання задачі про комівояжера на ЕОМ ефективно використовується метод гілок і границь.

3. Задача про найкоротший шлях.

Окремим класом задач у теорії графів є задачі визначення найкоротшого маршруту між двома довільними вершинами. Ці задачі знаходять широке застосування в мережевих моделях, теорії кодування, дослідженні моделей виробничих систем і звичайно називаються задачами відшукання найкоротшого шляху.

Формулюється задача про найкоротший шлях у такий спосіб.

Дано неорієнтований граф G(V, E). Кожному ребру цього графа приписане деяке число l (e)  0, називане довжиною ребра. При цьому будь-який ланцюг буде характеризуватися довжиною, обумовленою наступною формулою:

.

Необхідно відшукати найкоротший ланцюг серед всіх існуючих ланцюгів, що з'єднують задані початкову й кінцеву вершини, і визначити його довжину.

Найбільш простим випадком є задача відшукання найкоротшого шляху в графі з ребрами одиничної довжини. Одним з методів розв'язання цієї задачі є метод індексів. Загальне правило для знаходження найкоротшого шляху в графі полягає в тому, що кожній вершині v_i приписують індекс d_i, який дорівнює довжині найкоротшого шляху з даної вершини в кінцеву вершину. Приписування індексів вершинам у випадку графа з ребрами одиничної довжини виробляється в наступному порядку:

• кінцевій вершині v_n приписується індекс 0;

• всім вершинам, з яких йде ребро в кінцеву вершину, приписується індекс 1;

• всім вершинам, що ще не мають індексів, з яких іде ребро у вершину з індексом d_i, приписується індекс d_i+1.

Процес триває доти, поки не буде позначена вершина (початкова вершина v₀), від якої шукається мінімальна відстань до v_n, причому сам індекс цієї вершини буде довжиною найкоротшого шляху. Сам найкоротший шлях буде знайдений при переміщенні від кінцевої вершини в напрямку убування індексів.

Описаний спосіб визначення найкоротшого шляху є частковим випадком знаходження оптимального рішення по методу динамічного програмування. Задача приписування вершинам графа числових індексів ускладнюється, якщо ребра графа мають довільну довжину. Ускладнення викликане тим, що в складному графі шлях, що проходить через найменше число вершин, нерідко маєть довжину, що перевищує деякі «обхідні» шляхи. Процес приписування індексів у цьому випадку полягає в наступному:

• Кожна вершина v_i позначається індексом d_i . спочатку кінцевій вершині v_n приписується індекс d_n. Для інших вершин припускаємо d_i =  (i  n).

• Шукаємо таке ребро (v_i, v_j), для якого d_i – d_j > l (v_i, v_j), заміняємо індекс d_i індексом d’_i, що визначається за правилом:

d’_i = d_j + l (v_i, v_j).

• Процес заміни індексів продовжуємо доти, поки є хоча б одна дуга, для якої можна зменшити d_i.

Процес знаходження найкоротшого шляху методом індексів у графі, ребра якого мають ненегативну довжину, розглянемо на прикладі (рис. 5.17). Як кінцева вершина обрана вершина v₆, як початкова вершина - v₁. Початкові присвоєння індексів наведені на рис. 5.17,а. Процес послідовного аналізу ребер графа наведений в таблиці 5.2, а кінцевий результат - на рис. 5.17,б.

Таблиця 5.2

Розглянуті ребра	Умова оновлення індексу	Спосіб оновлення індексу	Нове значення
(v3, v6)	d3 > d6 + l (v3, v6)	d’3 = d6 + l (v3, v6)	d3 = 2
(v5, v6)	d5 > d6 + l (v5, v6)	d’5 = d6 + l (v5, v6)	d5 = 3
(v2, v3)	d2 > d3 + l (v2, v3)	d’2 = d3 + l (v2, v3)	d2 = 5
(v4, v3)	d4 > d3 + l (v4, v3)	d’4 = d3 + l (v4, v3)	d4 = 7
(v4, v5)	d4 > d5 + l (v4, v5)	d’4 = d5 + l (v4, v5)	d4 = 4
(v1, v2)	d1 > d2 + l (v1, v2)	d’1 = d2 + l (v1, v2)	d1 = 9
(v1, v4)	d1 > d4 + l (v1, v4)	d’1 = d4 + l (v1, v4)	d1 = 6

Рис. 5.17

Відзначимо дві властивості, яки будуть мати приписані вершинам індекси:

• Нехай (v_s, v_k) довільне ребро. Для нього обов'язково буде виконуватися умова d_s – d_k  l (v_s, v_k), оскільки в противному випадку індекс d_k можна було б зменшити.

• Нехай v_p – довільна вершина. При розгляді процесу приписування індексів індекс d_p монотонно зменшується. Нехай v_q – остання вершина, використовувана при зменшенні індексу d_p. Тоді d_p = d_q + l (v_p, v_q). Отже, для довільної вершини v_p з індексом d_p завжди найдеться вершина v_q, з'єднана ребром з v_p, така, що справедливо рівність d_p – d_q = l (v_p, v_q).

До недоліків даного методу варто віднести те, що при ускладненні графа буде значно зростати час відшукання найкоротшого шляху, оскільки буде потрібно розглянути велику кількість ребер.

Існує багато алгоритмів відшукання найкоротшого шляху, однак деякі краще піддаються автоматизації й можуть бути реалізовані у вигляді програм для ЕОМ. Такими є наприклад алгоритм Белмана – Форда та алгоритм Дейкстри.

4. Задача про максимальний потік.

Під мережею розуміють пару , де - довільний орієнтований граф, у якого s і t V – початкова й кінцева вершини графа G, відповідно називані джерелом і стоком. Функція f: , що кожній дузі ставить у відповідність не негативне число , називане пропускною здатністю цієї дуги. Для всієї мережі можна записати матрицю пропускних здатностей C, що формується аналогічно матриці суміжності вершин.

Дивергенцією функції f у вершині v називається число , що визначається в такий спосіб

Якщо ми інтерпретуємо як потік з в , то величина визначається як кількість потоку, що виходить із вершини . Ця величина може бути позитивною, якщо з вершини більше виходить, чим входить у неї; негативною, якщо у вершину входить більше, ніж виходить із її (тобто відбувається «нагромадження» потоку у вершині ), і може дорівнювати нулю.

Під потоком з у мережі розуміють довільну функцію f: , для якої виконуються умови:

1). Для кожної дуги

,

тобто потік через дугу не негативний і не перевершує пропускної здатності дуги.

2). Для кожної вершини

,

тобто дивергенція потоку дорівнює нулю у всіх вершинах крім джерела й стоку.

Число

називається величиною потоку .

Відповідно до описаного вище, ми маємо тут справу з потоком, що не виникає й не накопичується в жодній з вершин, відмінних від , , за умови, що через дугу ми можемо пропустити не більш ніж одиниць потоку.

Головною задачею в такій мережі є знаходження максимального потоку (потоку максимальної величини). Для викладу методу розв'язання цієї задачі введемо кілька простих понять.

Розрізом мережі , де A V, A ø, A V, називають множину дуг , таких що й , тобто

.

Для довільного потоку в мережі потік через розріз визначається природно:

.

Нехай P – (s,t) – розріз, . Всякий розріз визначається розбивкою множини вершин V на дві підмножини S і T, так що , , , , , , а в P потрапляють всі дуги, що з'єднують S і T. Тоді , де - дуги від S до T, - дуги T від до S. Сума потоків через дуги розрізу P позначається . Сума пропускних здатностей дуг розрізу P називається пропускною здатністю розрізу й позначається .

; .

Довільний розріз P, , , з мінімальною пропускною здатністю називають мінімальним розрізом, що розділяє й .

Теорема Форда-Фалкерсона. Максимальний потік у мережі дорівнює мінімальної пропускної здатності розрізу, тобто існує потік такий, що

.

Всі відомі алгоритми побудови максимального потоку ґрунтуються на послідовному збільшенні потоку з використанням методу ланцюгів, що збільшують.

Дуга в мережі є припустимою дугою з у відносно потоку , якщо

і (1)

або

и. (2)

Умова (1) справедлива для узгодженої припустимої дуги з в . Умова (2) справедлива для неузгодженої припустимої дуги з в . Ланцюгом, що збільшує, довжиною для даного потоку з у називається довільна знакозмінна послідовність попарно різних вершин і дуг така, що , і для кожного дуга - допустима з у відносно потоку .

При відомому ланцюзі, що збільшує, величину потоку можна легко збільшити на

,

де

Для цього необхідно збільшити на потік по кожній узгодженій дузі :

,

а також зменшити на потік по кожній не узгодженій дузі :

.

Величина усього потоку при цьому також збільшується на :

.

Для розв'язання задачі про максимальний потік можна використовувати алгоритм Дінітца.

Ідея Дінітца ґрунтується на розбивці процесу збільшення потоку уздовж ланцюгів, що збільшують, на фази, що відповідають використанню найкоротших ланцюгів певної довжини.

Фаза починається з побудови допоміжної безконтурної мережі (граф без контурів), у якій потім перебуває так званий псевдо максимальний потік. Псевдо максимальним потоком у мережі довжини називається довільний потік у такий, що в не існує ланцюга, що збільшує, довжини щодо потоку . Інакше кажучи, для довільного шляху з в в , визначеного послідовністю вершин ( , ) існує дуга , , така що

.

Псевдо максимальний потік потім переноситься з допоміжної мережі в початкову мережу, і складається з усіма потоками цієї мережі

.

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

Вирішимо задачу про максимальний потік у графі G, наведеному на рис. 5.18. Почнемо з нульового потоку в мережі . Будуємо допоміжну без контурну мережу (фаза 1, рис. 5.19).

Рис.5.18 - Потоки в графі G

Рис.5.19 - Підграф фази 1

На підграфі фази 1 знайдені ланцюги, що збільшують:

1)

2)

Сумарний потік підграфа G₁ дорівнює:

Після видалення насичених дуг, які не можуть входити в ланцюги, що збільшують, побудуємо допоміжну без контурну мережу (фаза 2, рис. 5.20).

Рис.5.20 - Підграф фази 2

Ланцюгів, що збільшують, у мережі немає. Нанесемо всі потоки на граф G (рис. 5.21) і перевіримо теорему про мінімальний розріз C(P₁)=4+3=7.

Рис.5.21 - Розріз при максимальному потоці з в.

2. Синтез логічних схем.

Логічною називають змінну, яка може приймати одне із двох можливих значень – «1» або «0» (істина або неправда, “так” або “ні”). Логічні змінні будемо позначати x_i. Найчастіше під індексом i мають на увазі розряд двійкового числа, що відповідає набору логічних змінних.

Функція, визначена на наборах і приймаюча на цих наборах значення 0 або 1, називається функцією алгебри логіки (ФАЛ), логічною функцією або булевою функцією. Тому що число наборів для n змінних дорівнює 2ⁿ, те кожну ФАЛ можна задати кінцевою таблицею з 2ⁿ рядками. При цьому змінні x_i є аргументами ФАЛ. Усього для n змінних можна записати різних ФАЛ.

Для однієї логічній змінної x₀ можна записати два набори x₀ = 0 і x₀ = 1 й отримати чотири ФАЛ:

• f₀ = 0 – константа нуля;

• f₁ = x₀ (функція дорівнює значенню змінній x₀);

• f₂ = (функція дорівнює запереченню змінній x₀);

• f₃ = 1 – константа одиниці.

У таблиці 5.3 показано, що для двох логічних змінних можна скласти 4 різних набори й записати 16 логічних (елементарних) функцій.

Таблиця 5.3

x1	x0	f0	f1	f2	f3	f4	f5	f6	f7
0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

Продовження таблиці 5.3

x1	x0	f8	f9	f10	f11	f12	f13	f14	f15
0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

Розглядаючи кожну з функцій (див. табл. 5.3) разом з наборами змінних, одержуємо таблиці істинності для всіх елементарних ФАЛ. Кожна з елементарних функцій має свою назву:

• f₀ – константа нуля;

• f₁ = x₀ & x₁ = x₀  x₁ = x₀x₁ – функція кон’юнкції (логічне множення, И);

• f₂ = - заперечення імплікації x₁ в x₀ (ЗАБОРОНА по x₀);

• f₃ = x₁ (функція несуттєво залежить від x₀);

• f₄ = - заперечення імплікації x₀ в x₁ (ЗАБОРОНА по x₁);

• f₅= x₀ (функція несуттєво залежить від x₁);

• f₆ = x₀  x₁ – функція додавання по модулю 2 (нерівнозначність, АБО, що виключає);

• f₇ = x₀  x₁ = x₀ + x₁ - функція диз'юнкції (логічне додавання, АБО);

• f₈ = – заперечення диз'юнкції (функція Вебба, АБО-НІ);

• f₉ = x₀  x₁ = x₀  x₁ = x₀  x₁ – функція рівнозначності (функція еквівалентності);

• f₁₀ = (функція несуттєво залежить від x₁);

• f₁₁ = – функція імплікації x₀ в x₁;

• f₁₂ = (функція несуттєво залежить від x₀);

• f₁₃ = – функція імплікації x₁ в x₀;

• f₁₄ = – заперечення кон’юнкції (функція Шеффера, І-НІ);

• f₁₅ – константа одиниці.

Існують різні способи завдання або подання ФАЛ:

• Словесне подання - відображає словесний взаємозв'язок аргументів зі значеннями ФАЛ (наприклад, функція трьох аргументів приймає значення одиниці, якщо два або більше її аргументи дорівнюють одиниці, а у всіх інших випадках функція дорівнює нулю).

• Задаючи значення ФАЛ на всіх можливих наборах логічних змінних (звичайно в порядку зростання їхніх номерів) можна побудувати таблицю істинності ФАЛ. У цьому складається табличний спосіб завдання логічної функції. У таблиці 5.4 представлена функція, словесно описана в попередньому прикладі.

Таблиця 5.4

№ набору	x2	x1	x0	f (x2, x1, x0)
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

• Аналітичний спосіб завдання ФАЛ полягає в тому, що функція f задається у вигляді алгебраїчного рівняння, у якому змінні x_i пов'язані між собою знаками логічних операцій. У попередньому прикладі

(5.1)

• Числовий спосіб завдання ФАЛ використовується для скорочення її запису. При цьому функція записується у вигляді логічної суми десяткових номерів двійкових наборів, на яких функція дорівнює одиниці. Наприклад, для розглянутої вище функції

(5.2)

1. Таблиця істинності функції алгебри логіки.

Функції двох змінних займають в алгебрі логіки особливе місце, оскільки, маючи набір функцій двох змінних, на підставі принципу суперпозиції можна утворити ФАЛ будь-якого числа змінних.

Використовуючи таблиці істинності, що визначають елементарні функції, можна задати у вигляді таблиці істинності кожну ФАЛ, що є суперпозицією цих функцій. При цьому варто враховувати пріоритети логічних функцій. Найвищий пріоритет має функція логічного заперечення, потім у порядку зниження пріоритету ідуть: кон’юнкція, диз'юнкція, імплікація, додавання по модулю 2, еквівалентність. При необхідності змінити порядок обчислень можна за допомогою дужок. Наприклад, побудуємо таблицю істинності для логічної функції

(5.3)

Таблицю істинності доцільно будувати послідовно виконуючи логічні операції з урахуванням їх пріоритету (див. табл. 5.5):

Таблиця 5.5

x2	x1	x0		[…]		(…)		{…}	f
0	0	0	1	0	1	1	0	0	1
0	0	1	0	1	0	0	1	1	0
0	1	0	1	0	1	0	1	0	1
0	1	1	1	0	0	1	0	0	1
1	0	0	1	1	1	1	0	0	1
1	0	1	0	1	1	1	0	0	1
1	1	0	1	1	1	0	1	1	1
1	1	1	1	1	1	0	1	1	1

Логічні функції для зручності запису виражають у вигляді суми добутків логічних змінних або у вигляді добутків їхніх сум. Перший запис називається диз'юнктивною нормальною формою (ДНФ), а другий – кон’юнктивною нормальною формою (КНФ). Для кожної логічної функції може існувати кілька рівносильних диз'юнктивних і кон’юнктивних форм, однак існує тільки один вид ДНФ або КНФ, у якому функція може бути записана єдиним способом (досконалі нормальні форми ДДНФ і ДКНФ). У ДДНФ функція записується у вигляді логічної суми констітуєнт одиниці (мінтермов), а в ДКНФ - у вигляді логічного добутку констітуєнт нуля (макстермов). Констітуєнти одиниці й нуля - це комбінації змінних, при яких функція відповідно обертається в одиницю або нуль.

• Розглянемо алгоритм знаходження ДДНФ:

1. Відзначаємо набори змінних, на яких функція дорівнює 1.

2. Змінні x_i, що прийняли в цих наборах значення 1, позначаємо як x_i, а що прийняли значення 0 – як .

3. Для кожного відзначеного набору записуємо елементарну кон’юнкцію, що складається з x_i і .

4. Поєднуємо елементарні кон’юнкції знаком диз'юнкції, у результаті отримуємо досконалу диз'юнктивну нормальну форму (ДДНФ).

ДКНФ знаходиться по схожому алгоритму:

1. Відзначаємо набори змінних, на яких функція дорівнює 0.

2. Змінні x_i, що прийняли в цих наборах значення 0, позначаємо як x_i, а те, що прийняли значення 1 – як .

3. Для кожного відзначеного набору записуємо елементарну диз'юнкцію, що складається з x_i і .

4. Поєднуємо елементарні диз'юнкції знаком кон’юнкції, у результаті отримуємо досконалу кон’юнктивну нормальну форму (ДКНФ).

Приклад: Знайти ДДНФ і ДКНФ функції, наведеної в табл. 5.3.

а) функція приймає значення 1 на наборах: 3, 5, 6 і 7. Для одержання ДДНФ запишемо елементарні кон’юнкції, що відповідають цим наборам, і об'єднаємо їх знаками диз'юнкції

;

б) функція приймає значення 0 на наборах: 0, 1, 2 і 4. Для одержання ДКНФ запишемо елементарні диз'юнкції, що відповідають цим наборам, і об'єднаємо їх знаками кон’юнкції:

.

Набір елементарних логічних функцій, що дозволяє будувати на їхній базі ФАЛ будь-якої складності, називається базисом. Наприклад, базис утворять функції логічного множення, додавання й заперечення (Й, АБО, НІ). Саме ці функції (і їхні логічні елементи, що реалізують) виконають основну роль при синтезі електронних схем. Крім того, досить часто використовуються елементи, що реалізують функції Й-НІ, АБО-НІ.

Аналітична форма запису ФАЛ дозволяє сформулювати основні закони алгебри логіки, доказ справедливості яких отримують шляхом підстановки всіх можливих комбінацій змінних x_i (при цьому ліва й права частини рівнянь повинні бути тотожні).

1. Закони переміщення: ;

2. Сполучні закони: ;

3. Розподільні закони: ;

4. Закони повторення: ;

5. Закони поглинання: ;

6. Закони додатковості: ;

7. Закон подвійного заперечення: ;

8. Закони універсальної множини: ;

9. Закони нульової множини: ;

10. Закони склеювання: ;

11. Правило де Моргана: .

Застосування наведених законів дозволяє спрощувати логічні функції й вирази.

2. Аналіз функції алгебри логіки на приналежність до класів.

Серед усьєй множини логічних функцій можна виділити п'ять класів. При аналізі ФАЛ можна визначити її приналежність (або не приналежність) до кожного із цих класів.

Логічна функція f ( xn-1, …, x₁, x₀) належить до класу ФАЛ, що зберігають константу нуля K₀, якщо при всіх x_i = 0, де i = 0, 1, …, (n-1), виконується рівність f = 0.

Логічна функція f ( x_n-1, …, x₁, x₀) належить до класу ФАЛ, що зберігають константу одиниці K₁, якщо при всіх x_i = 1, де i = 0, 1, …, (n-1), виконується рівність f = 1.

Логічна функція f ( x_n-1, …, x₁, x₀) належить до класу лінійних ФАЛ K_Л у тому випадку, коли її можна описати виразом

(5.4)

де , ₂ – знаки операції додавання по модулю 2.

Логічна функція f ( x_n-1, …, x₁, x₀) належить до класу самодвоїстих ФАЛ K_С, якщо для неї справедливе вираження

(5.5)

Логічна функція f ( x_n-1, …,x₁, x₀) належить до класу монотонних ФАЛ K_М, якщо при збільшенні (або збереженні) значення кожної зі змінних x_i, значення функції не убуває.

Приклад: Задана функція трьох змінних:

.

Необхідно проаналізувати цю функцію на приналежність до класів ФАЛ.

Розв'язання приклада будемо проводити поетапно:

1. Будуємо таблицю істинності для заданої функції (табл. 5.6)

Таблиця 5.6

x2	x1	x0	x1x0	[ … ]		f
0	0	0	1	1	1	1
0	0	1	1	1	1	1
0	1	0	0	1	0	0
0	1	1	1	1	1	1
1	0	0	1	0	1	0
1	0	1	1	0	1	0
1	1	0	0	1	0	0
1	1	1	1	0	1	0

2. Аналізуємо функцію на приналежність до класу К₀.

Тому що f (0, 0, 0) = 1, то можна зробити висновок, що f (x₂, x₁, x₀)  К₀.

3. Аналізуємо функцію на приналежність до класу К₁.

Тому що f (1, 1, 1) = 0, то можна зробити висновок, що f (x₂, x₁, x₀)  К₁.

4. Аналізуємо функцію на приналежність до класу К_Л. Припустимо, що задана функція лінійна, тоді відповідно до (5.4) знайдемо невідомі коефіцієнти С и С_i. Коефіцієнт С визначається на наборі :

f (0, 0, 0) = C  C₂ 0  C₁ 0  C₀ 0 = C = 1.

Коефіцієнт С₀ визначається на наборі :

f (0, 0, 1) = C  C₂ 0  C₁ 0  C₀ 1 = C  C₀ = 1.

Отже C₀ = 0.

Коефіцієнт С₁ визначається на наборі :

f (0, 1, 0) = C  C₂ 0  C₁ 1  C₀ 0 = C  C₁= 0.

Отже C₁ = 1.

Коефіцієнт С₂ визначається на наборі :

f (1, 0, 0) = C  C₂ 1  C₁ 0  C₀ 0 = C  C₂= 0.

Отже, C₂ = 1.

Якщо припущення про лінійність аналізованої функції вірно, то її значення повинні збігатися зі значеннями лінійної функції, що з урахуванням коефіцієнтів можна записати у вигляді f_Л (x₂, x₁, x₀) = 1  x₀. Перевіримо це на чотирьох наборах, що залишилися:

• набір : f (0, 1, 1) = 1; f_Л (0, 1, 1) = 0; ff_Л;

• набір : f (1, 0, 1) = 0; f_Л (1, 0, 1) = 0; f = f_Л;

• набір : f (1, 1, 0) = 0; f_Л (1, 1, 0) = 1; f  f_Л;

• набір : f (1, 1, 1) = 0; f_Л (1, 1, 1) = 0; f = f_Л.

Оскільки є набори, на яких f  f_Л, те зроблене припущення про лінійність функції невірно, отже, f(x₂,x₁,x₀)К_Л (перевірку можна припиняти після того, як перший раз виявлена розбіжність значень f і f_Л).

5. Аналізуємо функцію на приналежність до класу К_С. Для цього необхідно знайти значення функції й зрівняти їх зі значеннями функції f (x₂, x₁, x₀). Зворотна функція має вигляд:

Складемо таблицю істинності для цієї функції (табл. 5.7) і порівняємо між собою праві стовпи таблиць 5.6 і 5.7. Оскільки не на всіх наборах змінні значення функцій рівні між собою, можна зробити висновок, що f (x₂, x₁, x₀)  К_С.

Таблиця 5.7

x2	x1	x0		[ … ]
0	0	0	1	0	1	0	1
0	0	1	0	1	0	0	1
0	1	0	1	0	1	0	1
0	1	1	1	0	1	0	1
1	0	0	1	1	1	1	0
1	0	1	0	1	0	0	1
1	1	0	1	1	1	1	0
1	1	1	1	1	1	1	0

6. Аналізуємо функцію на приналежність до класу К_М. . Для цього потрібно побудувати матрицю (табл. 5.8), у якій по рядках (i) і стовпцям (j) записані набори змінних .

Потім відзначаємо зірочками наступні перетинання:

• всі елементи (значення змінних на конкретному наборі) рядка дорівнюють всім елементам стовпця, тобто i = j ;

• хоча б один елемент рядка більше елемента стовпця, тобто i  j .

У клітинках, що залишилися, ставимо плюс «+», якщо значення функції на наборі i менше або дорівнює значенню функції на наборі j , і мінус «-», якщо значення функції на наборі i більше значення функції на наборі j.

Таблиця 5.8

i \ j	0 0 0	0 0 1	0 1 0	0 1 1	1 0 0	1 0 1	1 1 0	1 1 1
0 0 0	*	–	+	+	+	+	+	+
0 0 1	*	*	*	+	*	+	*	+
0 1 0	*	*	*	+	*	*	+	+
0 1 1	*	*	*	*	*	*	*	+
1 0 0	*	*	*	*	*	+	+	+
1 0 1	*	*	*	*	*	*	*	+
1 1 0	*	*	*	*	*	*	*	+
1 1 1	*	*	*	*	*	*	*	*

Якщо в отриманій матриці є хоча б один знак «–», то функція не є монотонною, тобто f (x₂, x₁, x₀)  К_М.

3. Мінімізація функції алгебри логіки.

Подання ФАЛ у вигляді ДДНФ або ДКНФ є найбільш повним, оскільки в досконалих формах присутні всі набори, на яких функція дорівнює одиниці для ДДНФ або нулю для ДКНФ. Для обох досконалих форм можна відзначити ряд властивостей:

• у кожному елементарному наборі присутні всі змінні;

• відсутні невизначені стани;

досконалі форми майже завжди не є тупиковими, отже, їх можна спростити.

При практичній реалізації на логічних елементах (ЛЕ) обидві досконалі форми ФАЛ дуже часто виявляються надлишковими, тому для зменшення числа ЛЕ, що реалізують функцію, застосовують різні методи мінімізації ФАЛ. Метою мінімізації ФАЛ є одержання такого її представлення, що містить найменше число логічних операцій (у схемотехнічному аспекті - одержання логічної схеми, що містить найменше число ЛЕ з мінімальним числом входів). Для мінімізації нескладних функцій застосовуються алгебраїчні перетворення на основі законів поглинання й склеювання. Для більш складних функцій розроблені спеціальні методи мінімізації.

Метод мінімізуючих карт. Цей метод знайшов широке застосування при синтезі електронних схем завдяки своїй простоті й наочності. Він заснований на використанні карт Вейча або Карно. Ці карти – аналог таблиці істинності ФАЛ; вони побудовані таким чином, що суміжні кон’юнкції (які відрізняються значенням тільки однієї логічної змінної й можуть бути склеєні) розташовані або поруч, або на протилежних краях карти. Кількість комірок карти дорівнює 2ⁿ, де n – число змінних.

На рис. 5.22 наведені карти Вейча для трьох, чотирьох і п'яти змінних і карти Карно для трьох і чотирьох змінних. У кожній комірці карти проставлений номер набору логічних змінних, котрому ця комірка відповідає. Карти Вейча для п'яти й більше змінних розглядаються як сукупність підкарт для чотирьох змінних, тому кон’юнкції, розташовані на однакових позиціях у підкартах, також є сусідніми. Карти Карно відрізняються від карт Вейча тільки координатною сіткою.

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

Склеювання суміжних кон’юнкцій на картах Вейча й Карно виконується їхнім геометричним об'єднанням у групи, що складаються з 2^k комірок (k = = 1, 2, …)...Така група називається накриттям. Склеюються ті змінні, які входять у накриття й без інверсії й з інверсією.

Результат накриття записується у вигляді кон’юнкцій не склеєних змінних, а МДНФ - у вигляді диз'юнкції результатів накриттів. Чим більше площа накриття, тим менше змінних входить у його результат, а чим менше накриттів, тим менше кон’юнкцій входить у МДНФ. Тому при мінімізації необхідно прагнути накрити всі одиничні (у деяких випадках - нульові) значення ФАЛ мінімальним числом максимальних по площі накриттів.

а) карта Вейча для трьох змінних;

б) карта Карно для трьох змінних;

в) карта Вейча для п'яти змінних;

г) карта Вейча для чотирьох змінних;

д) карта Карно для чотирьох змінних.

Рис. 5.22 - Мінімізуючі карти.

Приклад: Мінімізувати за допомогою карт Вейча логічну функцію трьох змінних -

1. Н аносимо функцію на карту Вейча (рис. 5.23).

Рис. 5.23

2. виконуємо накриття всіх одиничних значень ФАЛ; отримуємо одне накриття площею 4 комірки й 4 накриття площею 2 комірки (виділені пунктиром).

3. Записуємо МДНФ у вигляді логічної суми кон’юнкцій, що відповідають виконаним накриттям:

Метод Квайна – Мак-Класски. Цей метод використовує перебір кон’юнкцій, які можуть бути присутнім у ДНФ, еквівалентної мінімізуемої функції. Вихідна ФАЛ задається у вигляді двійкових наборів, що відповідають кон’юнкціям рангу n, розбитих на підгрупи по числу одиниць у наборі. Алгоритм мінімізації методом Квайна - Мак-Класски полягає в наступному:

1. Набори, що знаходяться у сусідніх підгрупах перевіряються на склеювання.

2. У результаті склеювання утворюються кон’юнкції рангу ( n-1), які знову розбиваються на підгрупи по числу одиниць. На позиції “склеєної” змінної проставляється символ “-“.

3. Якщо які-небудь із кон’юнкцій рангу n не вдалося склеїти, то їх виписують окремо (їх називають первинними імплікантами).

4. Пункти 1-3 повторюють для кон’юнкцій рангу ( n-1); у результаті отримують кон’юнкції рангу ( n-2) і первинні імпліканти рангу ( n-1).

5. Пункти 1-3 повторюють доти, поки можливо хоча б одна операція склеювання. Всі не склеєні кон’юнкції дописують до первинних імплікант.

6. Складається таблиця влучна, у якій по рядках записуються первинні імпліканти, а по стовпцях – набори, на яких функція приймає значення 1 (тобто початкові кон’юнкції рангу n). Для кожного рядка мітки розставляються в тих стовпцях, які мають такі ж елементи в співпадаючих позиціях (тобто рівні значення логічних змінних). При цьому позиціями, у яких первинна імпліканта містить символ “-“, можна зневажити.

7. Знаходиться мінімальне покриття набором первинних імплікант початкової функції, тобто мінімальний набір первинних імплікант, що мають мітки у всіх стовпцях. Цей набір і дасть МДНФ вихідної функції. Послідовність відшукання такого набору простежимо на прикладі.

Приклад: Мінімізувати методом Квайна – Мак-Класски логічну функцію, задану виразом:

• Запишемо двійкові набори, на яких функція дорівнює 1:

• 0000, 0001, 0010, 0011, 0100, 0111, 1001, 1101, 1110, 1111.

• Групуємо набори по числу одиниць у наборах 4-го рангу.

0 група	1 група	2 група	3 група	4 група
0 0 0 0	0 0 0 1 0 0 1 0 0 1 0 0	0 0 1 1 1 0 0 1	0 1 1 1 1 1 0 1 1 1 1 0	1 1 1 1

• Виконуємо (там, де це можливо) операцію склеювання наборів із сусідніх груп. Оскільки всі набори беруть участь у склеюванні, первинних імплікант не виявилося. У результаті одержали набори 3-го ранги, які також розбиваємо на групи.

0 група	1 група	2 група	3 група
0 0 0 - 0 0 - 0 0 – 0 0 	0 0 - 1 – 0 0 1  0 0 1 -	0 – 1 1  1 – 0 1 	– 1 1 1  1 1 – 1  1 1 1 – 

• Виконуючи склеювання переходимо до наборів 2-го ранги; не склеєні набори відзначаємо знаком .

0 група	1 група	2 група
0 0 – – 

• Єдиний отриманий набір 2-го ранги й не склеєні набори 3-го ранги віднесемо до первинних імплікант і внесемо в імплікантну таблицю (табл. 5.9). Заповнимо таблицю мітками.

Таблиця 5.9

	0000	0001	0010	0011	0100	0111	1001	1101	1110	1111
0- 00					
-001							
0-11						
1-01								
-111										
11-1										
111-										
00 --				

• У таблиці викреслюємо стовпці, що мають тільки одну мітку (відповідні наборам 2, 4, 14) і рядка, що дають ці мітки (у таблиці викреслені подвійними лініями). Ці викреслені рядки містять первинні імпліканти, які обов'язково ввійдуть у МДНФ; такі імпліканти називають істотними. У цьому випадку істотними є імпліканти 0-00, 111-, 00 ---і.

• Стовпці, що мають хоча б одну викреслену мітку, також викреслюємо (стовпці, що відповідають наборам 0, 1, 3, 15). У прикладі вони викреслені пунктирною лінією.

• Рядки і стовпці, що залишилися, переносимо в скорочену імплікантну таблицю (табл. 5.10), що також заповнюємо мітками.

• У цій таблиці також шукаємо мінімальне покриття всіх стовпців первинними імплікантами. Тому що імпліканта 1-01 дає мітки у двох стовпцях (а всі інші імпліканти тільки в одному), те її варто ввести в МДНФ, при цьому стовпці, що відповідають наборам 9 і 13 викреслюємо. Залишається стовпець, що відповідає набору 7, що має влучні від двох імплікант 0-11 і -111. При виборі яку з імплікант включити в МДНФ варто керуватися правилом: вибирається та імпліканта, що містить меншу кількість цифр (0 або 1), а при рівній кількості цифр - та, у яку входить більше одиниць (у прикладі - імпліканта -111).

Таблиця 5.10

	0111	1001	1101
-001		
0-11	
1- 01			
-111	
11-1			

• В остаточному виді МДНФ записується у вигляді диз'юнкції елементарних кон’юнкцій, що відповідають істотним і відібраним первинним імплікантам:

4. Синтез схеми методом каскадів.

Як уже згадувалося, набір елементарних логічних функцій, що дозволяє будувати на їхній базі ФАЛ будь-якої складності, називається базисом. Базис, що складається з мінімального набору елементарних ФАЛ, називають повною системою S логічних функцій. Критерій повноти системи ФАЛ задається теоремою Поста-Яблонського, що у найбільш простому формулюванні має такий вигляд:

Система S функцій алгебри логіки f_i є повною тоді й тільки тоді, коли в ній одночасно присутні: функція, що не зберігає константу 0; функція, що не зберігає константу 1; нелінійна функція; не самодвоїста функція й немонотонна функція.

Синтез логічних схем можна виконувати в будь-якому базисі, що забезпечений елементною базою, яка дозволяє реалізувати всі функції, що входять у базис. Основну роль при синтезі електронних схем грають функції логічного множення, додавання й заперечення (Й, АБО, НІ) і логічні елементи, що їх реалізують. Крім того, досить часто використовуються логічні елементи, що реалізують функції Й-НІ, АБО-НІ, АБО, що виключає. Умовні графічні позначення елементів наведені в таблиці 5.11.

Таблиця 5.11 - Умовні графічні позначення логічних елементів

Логічна функція	Позначення
	ДЕРЖСТАНДАРТ 2.743-91	стандарт MIL/ANSI
Л огічне заперечення (НІ; NOT)
Д из'юнкція (АБО; OR)
К он’юнкція (Й; AND)
Заперечення диз'юнкції ( АБО-НІ; NOR)
З аперечення кон’юнкції ( Й-НІ; NAND)
С ума по модулі 2 (АБО, що виключає; XOR)

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

,

необхідні чотири блоки, що реалізують операцію логічного заперечення (інверсії), чотири трьохвходових і один двохвходовий елемент, що реалізують логічне множення, і один п’ятивходовий елемент, що реалізує логічне додавання. Групуючи, відповідно до правил, доданки й співмножники, можна перейти до двохвходовим логічним елементам, наведеним у табл. 5.11.

х₃ х₂ х₁ х₀ = ((х₃ х₂) (х₁ х₀)) ; х₃  х₂  х₁  х₀ = ((х₃  х₂)  (х₁  х₀))

Подібні правила існують і для базису, в основі якого лежать операції Й-НІ, АБО-НІ:

Ці правила справедливі й для більшого числа логічних змінних.

Інший спосіб синтезу логічних схем заснований на використанні розкладання Шенона, що дає можливість описати логічну функцію n змінних через функції (n-m) змінних, називаними залишковими функціями. Наприклад, при m = 1 можна уявити функцію n змінних через функції ( n-1) змінних – нульові й одиничну залишкові функції першого порядку від аргументу x_k:

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

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

Похідна першого порядку f /x_i від ФАЛ по змінної x_i дорівнює сумі по модулю два нульової й одиничної залишкових функцій вихідної логічної функції f:

Як правило, перед узяттям похідної ФАЛ, знаходять її МДНФ.

Похідна першого порядку від ФАЛ визначає умови, при яких функція змінює своє значення при перемиканні x_i (тобто зміні значення змінної x_i на протилежне). Ця умова виражається в тім, що похідна повинна бути дорівнює одиниці. З аналізу наборів змінних, на яких похідна приймає значення «1», визначаються всі умови перемикання функції f. Очевидно, що чим більше наборів, тим більше умов перемикання. Критерій оптимального вилучення полягає в тому, що в першу чергу варто вилучати ті змінні, які викликають максимальне число перемикань функції. Максимальне число перемикань визначається вагою похідної, що розраховується по числу наборів аргументів рангу ( n-1), на яких похідна приймає значення «1».

Таким чином, при синтезі логічної схеми методом каскадів варто взяти похідні ФАЛ по всім змінним, визначити вагу кожної похідної й вилучати ту змінну, похідна по який має найбільшу вагу. Після вилучення змінної отримують нульову й одиничну залишкову функції, до кожної з яких застосовують той же самий алгоритм. Так продовжують доти, поки не будуть отримані досить прості залишкові функції, які легко реалізувати на логічних елементах.

Блок вилучення однієї змінної x_i представлений на рис. 5.24.

1

Рис. 5.24 – Блок вилучення змінної x_i

Розглянемо приклад. Для синтезу візьмемо функцію з попереднього прикладу

.

Визначимо похідні ФАЛ по кожній зі змінних:

• по змінної х₃

;

• по змінної х₂

;

• по змінної х₁

;

• по змінної х₀

.

Тепер варто визначити вагу кожної з похідних. Це доцільно робити одним із двох способів:

1) Побудувати таблиці істинності для кожного з доданків і просумувати по модулю два значення, що відповідають кожному з наборів логічних змінних; кількість одиниць у стовпці суми вкаже вагу похідній P_i.

2) Побудувати таблицю – аналог карти Вейча (Карно), у кожну клітку якої варто внести значення, прийняті кожним з доданків на наборі, що визначається значеннями логічних змінних, зазначених у лівому стовпці й верхньому рядку. При цьому значення, що відповідає першому з доданків поміщається в ліву частину клітки, а значення, що відповідає другому доданку – у праву частину клітки. Якщо в одній клітці виявляються дві одиниці, то вони викреслюються. Кількість одиниць, що залишилися (не викреслених), укаже вагу похідній P_i.

Скористаємося другим способом і складемо таблиці для кожної з похідних

x1x0 x2	0 0	0 1	1 0	1 1		x1x0 x3	0 0	0 1	1 0	1 1
0	1	1 1	1	1		0	1 1	1	1	1 1
1	1	1	1	1		1		1	1	1
		P3 = 6						P2 = 5

x2x0 x3	0 0	0 1	1 0	1 1		x2x1 x3	0 0	0 1	1 0	1 1
0	1 1	1 1	1	1		0	1 1	1	1 1	1
1		1	1	1 1		1	1			1 1
		Р1 = 4						Р0 = 3

Максимальну вагу має похідна ФАЛ по змінної х₃, отже, цю змінну необхідно вилучати на даному етапі. Після вилучення можна записати нульові й одиничну залишкові функції. Ці функції виходять шляхом підстановки у вихідну ФАЛ значення х₃=0 (для нульової залишкової функції) або х₃=1 (для одиничної залишкової функції):

Тепер відповідно до розглянутого вище методикою досліджуємо отримані нульові й одиничну залишкові функції.

Визначимо, яку зі змінних варто виключити з нульової залишкової функції. Для цього знайдемо похідні f (0)/x_i і визначимо їхня вага:

x0 x1	0	1			х2 x0	0	1		x2 x1	0	1
0	1 1				0	1 1	1		0	1 1	1
1		1			1	1 1	1		1	1 1	1
	Р2 (0) = 1					Р1 (0) = 2				Р0 (0) = 2

Тому що вага похідних функції по змінним х₁ і х₀ однакова, виключати можна кожну із цих змінних. Виключаємо з f (0) змінну х₀. Залишкові функції другого порядку мають вид:

Тепер проаналізуємо одиничну залишкову функцію.

х1 x0	0	1			x2 x0	0	1		x2 x1	0	1
0		1			0		1		0	1	1
1	1	1			1	1	1 1		1		1 1
	Р2 (1) = 3					Р1 (1) = 2				Р0 (1) = 2

Виключаємо з f (1) змінну х₂, похідна по який має найбільшу вагу і запишемо залишкові функції другого порядку, що вийшли:

Отримані залишкові функції можна реалізувати за допомогою двохвходових логічних елементів і блоків вилучення змінної (рис. 5.25).

Рис. 5.25 - Схема, отримана методом каскадів