Тема 3. Багатозначна логіка

Багатозначна (k-значна) логіка – це логіка, в якій змінна може приймати одне з k значень істинності, де k – будь-яке ціле число, більше 1. Функції k-значної логіки визначені і приймають значення, які входять до деякої множини В_k={0,1,..., k-1}, що називається алфавітом цієї логіки.

Функцію k-значної логіки однозначно визначає її таблиця значень (істинності). Множину всіх функцій k-значної логіки позначають Р_k. Кількість функцій Р_k, що залежить від n змінних, дорівнює . Як і у двозначній логіці, висловлення зображуються у вигляді формул k-значної логіки. Елементарні функції зображують узагальнення аналітичних функцій двозначної логіки.

Розглянути основні поняття і функції k-значної логіки [1, c. 230-239; 2, c. 231-238].

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

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

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

Розглянути задачу комівояжера та деякі інші алгоритми знаходження ейлерова та гамільтонового циклу [1, c. 314-321; 2, c. 314-321; 4, c. 320-335; 14, c. 53-70].

Тема 5. Розфарбування графів

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

Граф G називається k-розфарбовуваним, якщо існує правильне розфарбування ребер у k кольорів. Граф G називається реберно k-хроматичним, якщо хроматичний індекс дорівнює k.

Гіпотеза п'яти фарб формулюється так: «Для кожного планарного графа G справедлива нерівність h(G)5».

Гіпотеза чотирьох фарб формулюється так: «Будь-який планарний граф може бути розфарбований за допомогою чотирьох фарб».

Навчитися розфарбовувати графи та визначити основні галузі застосування алгоритмів розфарбовування [1, c. 314-321; 2, c. 314-321; 4, c. 320-335; 14, c. 53-70].

Тема 6. Цикломатика графів

Для графа G на n вершинах і m ребрах, що містить k компонент зв’язності ранг (позначається через p(G)) визначається як n-k.

Цикломатичне число графа G (µ(G)) визначається як m-n+k.

Справедливо, що p(G)+µ(G)=m. З визначення лісу і ко-лісу випливає, що ранг p(G) графа дорівнює кількості ребер лісу графа G, а цикломатичне число µ(G) – кількості ребер ко-лісу графа G. Ранг і цикломатичне число є одними з найбільш важливих характеристик графа – вони визначають розмірність підпросторів циклів і розрізів графа.

Розглянути поняття цикломатики графів. Навчитися будувати базис циклів [1, c. 286-292; 2, c. 286-292; 3, с. 102-106; 14, c. 87-88].