МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ університет “Львівська політехніка”
ДИСКРЕТНА МАТЕМАТИКА
МЕТОДИЧНІ ВКАЗІВКИ
до виконання лабораторних робіт
для студентів першого бакалаврського рівня вищої освіти спеціальності 123 “Комп’ютерна інженерія”.
Укладач: Попович Р. Б., д.ф.-м.н., доц.
Львів – 2019
ЗМІСТ
ЗМІСТ 2
ВСТУП 3
1.1. Теоретичні відомості 4
Операції над множинами 6
2.1. Теоретичні відомості 10
3.1. Теоретичні відомості 13
4.1. Теоретичні відомості 15
5.1. Теоретичні відомості 19
СПИСОК ЛІТЕРАТУРИ 24
ВСТУП
Методичні вказівки до лабораторних робіт укладені відповідно до навчальної програми з дисципліни “Дискретна математика” та містять п’ять лабораторних робіт.
Виконання лабораторних робіт має на меті засвоєння основних понять дискретної математики, програмно реалізуючи їх.
В лабораторній роботі 1 досліджуються основні поняття з розділу елементи теорії множин. У лабораторній роботі 2 досліджуємо властивості відображень, а в лабораторній роботі 3 − властивості відношень. У лабораторній роботі 4 розглядаємо алгоритм Пріма побудови кістякового дерева зв’язаного графа. Лабораторна робота 5 присвячена питанню розфарбування графів.
Результатом виконання робіт також є отримання студентом знань та навичок, необхідних для виконання розрахункової графічної роботи.
В лабораторних роботах використовується наявна на кафедрі обчислювальна техніка. Методичні вказівки допоможуть студенту засвоїти матеріал дисципліни, отримати необхідні навички з програмної реалізації основних понять дискретної математики, вчасно виконати завдання розрахункової графічної роботи.
Поняття з теорії множин [ ] є основою для всієї математики. Поняття з абстрактної алгебри [ ] на сьогодні широко використовують у прикладних застосуваннях, зокрема в захисті інформації від зловмисника (криптологія) та від завад (завадостійке кодування). Також широко застосовують поняття з теорії графів [ ].
1. Лабораторна робота № 1
Тема. Операції над множинами.
Мета. Засвоїти способи задання множин та операції над множинами.
1.1. Теоретичні відомості
Множина − це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені за допомогою правила, що задає належність до множини.
Для наших цілей достатньо буде викладення основ так званої інтуїтивноїабо наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора.
В інтуїтивній теорії множин поняття “множина” належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або об’єкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуїції. Такими поняттями в математиці є також поняття “число”, “пряма”, “точка”, “площина” тощо.
Канторівський вираз: “Множина − це зібрання в єдине ціле визначених об’єктів, які чітко розрізняються нашою інтуїцією або нашою думкою” − безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін “множина” на термін “збірка”. Іншими синонімами основного слова “множина” є “сукупність”, “набір”, “колекція”, “об’єднання” тощо.
Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Львова, множина парних чисел, множина розв’язків деякого рівняння та ін.
На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, N − множина натуральних чисел, Z − множина цілих чисел, Q − множина раціональних чисел, R − множина дійсних чисел, C − множина комплексних чисел тощо.
Об’єкти, з яких складається задана множина, називають її елементами. Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об’єкт a є елементом множини M записується так: aM. Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення aM. Запис a, b, c,...M використовують для скорочення запису aM, bM, cM,....
Множину називають скінченною, якщо кількість її елементів скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В іншому разі множина є нескінченною.
Множина є визначеною, коли можна встановити, чи є будь-який об’єкт її членом чи ні. Для задання множини, утвореної з будь-яких елементів, будемо використовувати два такі способи. В основі обох із них лежить позначення множини за допомогою фігурних дужок.
1. Якщо a1,a2,...,an - деякі об’єкти, то множина цих об’єктів позначається через {a1,a2,...,an}, де у фігурних дужках міститься перелік усіх елементів відповідної множини. З останнього зауваження випливає, що в такий спосіб можуть бути задані тільки скінченні множини. Порядок запису елементів множини при цьому позначенні є неістотним. Так, множина десяткових цифр записується {0,1,2,3,4,5,6,7,8,9}, множина основних арифметичних операцій − {+,-,*,/} або {*,/,+,-}, множина розв’язків нерівності (x-1)2 0 − {1}.
Слід підкреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного об’єкта математичного дослідження. Тому необхідно розрізняти такі два різні об’єкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.
2. Другий спосіб задання множин грунтується на зазначенні загальної властивості або породжувальної процедури для всіх об’єктів, що утворюють описувану множину.
У загальному випадку задання множини M має вигляд: M = {a | F(a)}. Цей вираз читається так: "множина M − це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони.
S = { n | n − непарне число } або S = { n | n = 2k+1, kZ},
X = { x | x = k, kZ},
F = { fi | fi+2 = fi+1 + fi, iN, f1 = f2 = 1 }.
Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх невпорядкованих пар з елементів a, b і c можна задати так: D = { {x,y} | x{a,b,c}, y{a,b,c} і x y}.
У теорії множин використовують поняття порожньої множини. Її позначають символом . Дійсно, множина може взагалі не містити елементів, наприклад
S = {x| x– непарне число, що ділиться на 2} = ;
K = {x| x R, x2 + 1 = 0} = .
Власне для позначення цього факту і вводиться поняття порожньої множини.
Це поняття відіграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників студентської групи або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не турбуючись про те, чи є відмінники в групі, яка розглядається. Порожню множину умовно відносять до скінченних множин. Число елементів у ній рівне 0.
Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
Операції над множинами
Розглянемо дві множини А і В та введемо низку операцій над ними. Для графічної ілюстрації використовують діаграми (кола) Ейлера. Для зображення множини на площині креслять замкнену лінію із заштрихованою внутрішньою областю (найчастіше – це коло, звідси й назва відповідного інструмента, що широко застосовується в теорії множин).
Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис. 1.1), тобто
А В = {x | x А або x В}.
Рис. 1.1. Об’єднання множин
Перетин А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис. 1.2), тобто
А В = {x | x А і x В}.
Рис. 1.2.Перетин множин
Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис. 1.3), тобто
А \ В = {x | x А і x В}.
Рис. 1.3. Різниця множин
Диз’юнктивна сума А і В (симетрична різниця) – множина, що складається усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів (рис. 1.4), тобто
А В = {x | (x А і x В) або (x В і x А)}.
Рис. 1.4. Диз’юнктивна сума множин
Звичайно, вже в означенні конкретної множини явно або неявно обмежується сукупність об’єктів, що є допустимими (слони – серед тварин, натуральні числа – серед цілих або дійсних залежно від контексту). Зручно сукупність допустимих об’єктів зафіксувати явно та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають U. Універсум U арифметики – числа, універсум U зоології – тварини і т.д. Будь-яку множину розглядатимемо у зв’язку з універсумом, який на діаграмах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 1.5).
Рис. 1.5. Універсальна множина
Доповнення множини А – це множина, що містить усі елементи універсуму, за винятком елементів А (рис. 1.6), тобто
.
Рис.1.6. Доповнення множини
Множина А називається підмножиною множини В, якщо кожен елемент А є елементом В. Для позначення цього факту вводиться знак - символ строгого включення (або - символ нестрогого включення) (рис. 1.7). Якщо необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення А В.
Дві множини рівні, якщо вони складаються з одних і тих самих елементів. Справджується таке: А = В тоді і тільки тоді, коли А В і В А.
Рис. 1.7. Підмножина множини
Окремо розглянемо ще одну дуже важливу операцію над множинами. Декартовим (прямим) добутком множин A і B (записується AB) називають множину всіх пар (a,b), в яких перша компонента належить множині A (aA), а друга − множині B (bB), тобто AB = {(a,b) | aA і bB }.
Наприклад, якщо A = {a,b} і B = {b,c,d}, то
AB = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},
A2 = AA = {(a,a),(a,b),(b,a),(b,b)}.
Якщо R − множина дійсних чисел або множина точок координатної прямої, то R2 − це множина пар (a,b), де a,bR, або множина точок координатної площини. Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена операція над множинами і називається декартовим добутком.
Множину, елементами якої є всі підмножини множини А, називають множиною підмножин множини А (або булеаном множини А) і позначають Р(А). Так, для триелементної множини А = {a, b, c} маємо P(A)={, {a}, {b}, {c}, {a, b},{b, c}, {a, c}, {a, b, c}}. У разі скінченної множини А з n елементів, множина підмножин Р(А) містить 2n елементів.
1.2. Порядок виконання роботи
1. Складіть програму, яка як вхідні дані одержує дві множини і визначає, чи рівні ці множини, чи є одна з них підмножиною іншої.
2. Складіть програму, яка як вхідні дані одержує множину і утворює список всіх можливих підмножин даної множини.
3. Складіть програму, яка як вхідні дані одержує дві множини A, B і утворює декартові добутки AB та BA.
4. Складіть програму, яка моделює операції
, 
, 
, 
, 
над множинами у графічному режимі.2. Лабораторна робота № 2
Тема. Властивості відображень.
Мета. Ознайомитися з властивостями відображень та їх дослідженням.
2.1. Теоретичні відомості
Нехай задано дві множини Х і Y. Відображення f з множини Х в множину Y кожному елементу х з множини Х ставить у відповідність деякий (один) елемент f (х) з множини Y. Елемент f (х) називають образом елемента х при відображенні f. Символічно відображення записується так: f : Х Y чи X
Y. У випадку Y = Х кажуть ще про відображення f множини Х в (на) себе.Якщо Х = {x1, x2, …, xn} – скінченна множина, тo відображення f : Х Y, можна задати записом з двох рядків f =
, де f(хi) Y, i = 1, 2, …, n. Наприклад, f: Х → Y, Х= {l, 2, 3, 4, 5}, Y = {а, b, c}, f = 
.Відображення часто ілюструють за допомогою діаграм (рис. 2.1), де відповідність між елементами показують стрілками. Відображення, задане в попередньому прикладі, зображене на рис. 2.1 а. Відповідності рис. 2.1 б та рис. 2.1 в відображеннями не є, оскільки на рис. 2.1 б елемент 1 X не має образу в множині Y, а на рис. 2.1 в елементу 3 X ставиться у відповідність два елементи з множини Y: b та c.
Рис. 2.1. Поняття відображення.
Відображення f множини Х в множину Y називають ін’єктивним, чи ін’єкцією, якщо двом різним елементам з множини Х відповідають два різних елементи з множини Y (рис. 2.2 а та 2.2 в). Іншими словами, f : X → Y ін’єктивне, якщо для будь-яких x, x1 Х та x ≠ x1 виконується f (x) ≠ f (x1).
Відображення f називають сюр’єктивним, чи сюр’єкцією, якщо для кожного елемента y з множини Y існує принаймні один елемент x з множини X такий, що f(x)=y. (рис. 2.2 б та 2.2 в).
Відображення називають бієктивним, чи бієкцією, якщо воно одночасно ін’єктивнe та сюр’єктивнe. Відображення f є бієктивним, якщо кожен елемент із Y є образом при відображенні f деякого, і при тому єдиного, елемента з X (рис. 2.2 в). Кажуть, що бієктивне відображення встановлює взаємно однозначну відповідність між множинами X та Y. Бієкція множини на себе називається також перестановкою чи перетворенням.
Рис. 2.2. Властивості відображення.
2.2. Порядок виконання роботи
1. Складіть програму, яка як вхідні дані одержує дві скінченні множини та відповідність між елементами цих множин і досліджує чи ця відповідність є відображенням (коректно заданою).
2. Складіть програму, яка як вхідні дані одержує дві скінченні множини та задає відображення з однієї в іншу із заданими властивостями (ін’єктивність, сюр’єктивність, бієктивність).
3. Лабораторна робота № 3
Тема. Властивості відношень.
Мета. Ознайомитися з властивостями відношень та їх дослідженням.
3.1. Теоретичні відомості
Розглянемо декартовий добуток другого степеня множини Х, тобто Х2 = Х Х. Довільну підмножину L множини Х2 (L Х2) будемо називати бінарним відношенням (або просто відношенням), заданим на множині Х. Вважатимемо, що впорядковані елементи x, х' Х знаходяться між собою у відношенні L, коли (x, х') L. Якщо на Х задано відношення L X2, то запис x L х' означає, що x і х' знаходяться у відношенні l, тобто(x, х') L.
Розглянемо кілька прикладів відношень:
1) на множині N відношення . Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить;
2) на множині Р(Х) всіх підмножин множини Х = {1, 3, 5, 7, 9} відношення . Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить.
Відношення L на множині X називають:
1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого х Î Х виконується х L х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел;
2) антирефлективним, якщо для будь-якого х Î Х пара (х, х) не належить до відношення L. Прикладами антирефлективних відношень можуть бути <, >, ≠ на множині раціональних чисел;
3) симетричним, якщо для довільних x, х' Î Х з того, що x L х' випливає х' L x. Наприклад, на множині Р(Х) відношення задане так: A, BÎ P(Х) перебувають у відношенні, якщо
. Зокрема, якщо Х = {1, 3, 5, 7, 9}, то пара підмножин ({1, 3}, {5, 7, 9}) належить цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить;4) антисиметричним, якщо для довільних x, х' Î Х з того, що x L х' і х' L x, випливає x = х' (наприклад, на N, тому що з x х' і х' x випливає х= х');
5) транзитивним, якщо для довільних x, х', х'' Î Х з того, що x L х' і х' L х'', випливає x L х'' (наприклад, відношення на множині Р(Х) чи відношення на множині N).
3.2. Порядок виконання роботи
1. Складіть програму, яка як вхідні дані одержує скінченну множину з n>30 елементами та задане на ній відношення й досліджує його властивості (рефлективність, симетрію, транзитивність).
2. Складіть програму, яка як вхідні дані одержує скінченну множину з n>30 елементами та задає на ній відношення із заданими властивостями (рефлективність, симетрію, транзитивність). Кількість пар елементів початкової множини, які належать до відношення, повинна бути не меншою, ніж
.4. Лабораторна робота № 4
Тема. Кістякове дерево графа.
Мета. Ознайомлення з алгоритмом Пріма побудови кістякового дерева екстремальної (мінімальної або максимальної) ваги для довільного скінченного неорієнтованого зв’язаного графа.
4.1. Теоретичні відомості
При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі. Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто на кожному кроці перевіряти наявність циклів у графі, що виникає.
Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда). Він дозволяє збудувати кістякове дерево скінченного неорієнтованого зв’язаного графа. Множину вершин графа позначаємо
, а множину його ребер 
. Зрозуміло, що ці множини є скінченними.Крок 1. Присвоєння початкових значень.
− множина вершин кістякового дерева, що формується,
, де 
− довільна вершина графа (скажімо, перша за номером);
;
− множина ребер кістякового дерева, що формується,
.Крок 2. Оновлення даних.
Знаходимо в графі таке ребро
, що 
, 
та 
Тоді покладаємо
, , 
.Крок 3. Перевірка на завершення.
Якщо
, то граф з множиною вершин і з множиною ребер є шуканим графом.У випадку
переходимо на Крок 2.4.2. Порядок виконання роботи
Завданням роботи є створення програми, що реалізує алгоритм Пріма (найближчого сусіда) знаходження кістякового дерева екстремальної (найбільшої або найменшої) ваги для довільного скінченого неорієнтованого зв’язаного графа.
Далі наведено приклад виконання алгоритму Пріма для зв’язаного графа. Множина вершин цього графа складається з п’яти елементів
. Список ребер з вказанням їх ваг (після вертикальної риски) наведено далі:
Заданий граф зображено на рис. 4.1.
Рис. 4.1. Зв’язаний граф, для якого шукаємо кістякове дерево
Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування:
Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги).
Крок 1.
, 
, Крок 2.
, 
,
Крок 3.
Крок 2.
,
,
Крок 3.
Крок 2.
,
,
Крок 3.
Крок 2.
,
,
Крок 3.
Таким чином, отримали кістякове дерево мінімальної ваги для початкового графа (множина вершин
, а множина ребер 
), яке зображено на рис. 4.2.
Рис. 4.2. Кістякове дерево для графа з рис. 4.1.
Вага отриманого кістякового дерева (тобто сума ваг всіх його ребер) мінімальної ваги дорівнює 10. Зауважимо, що отримане кістякове дерево не єдине. Інше можливе кістякове дерево (і також ваги 10) наведене на рис. 4.3.
Рис. 4.3. Інше кістякове дерево для графа з рис. 4.1.
5. Лабораторна робота № 5
Тема. Правильне розфарбування графів.
Мета. Ознайомитись із правильним розфарбуванням графів за допомогою евристичного алгоритму.
5.1. Теоретичні відомості
Різноманітні завдання, що виникають при плануванні виробництва, складанні графіків огляду техніки, зберіганні і транспортуванні товарів тощо, можуть бути представлені часто як задачі теорії графів, тісно пов'язані з так званою “задачею розфарбування”. Графи, які розглядаємо в цій роботі, є неорієнтованими і без петель.
Граф G називають r-хроматичним, якщо його вершини можна розфарбувати з використанням r кольорів (фарб) так, що будь-які дві суміжні вершини мають різні кольори. Найменше число r таке, що граф G є r-хроматичним, називають хроматичним числом графа G і позначають
. Задачу знаходження хроматичного числа графа називають задачею про (правильне) розфарбовування графа. Відповідне цьому числу розфарбування вершин розбиває множину вершин графа на r підмножин, кожна з яких містить вершини одного кольору.Приклад розфарбування графа показано на рис. 5.1 . Числа 1 і 2 позначають кольори вершин.
Рис. 5.1. Приклад розфарбування графа.
Зрозуміло, що повний граф з n вершинами розфарбовуємо з використанням рівно n кольорів.
Проблема визначення, чи є заданий граф k-хроматичним для певного k, та проблема знаходження мінімального правильного розфарбування для заданого графа належать до класу задач, для яких на сьогодні не існують (і є всі підстави вважати, що не існують взагалі) ефективні точні алгоритми їх розв’язку. Тому важливими є результати, які дозволяють оцінити значення хроматичного числа
, виходячи з певних характеристик та властивостей графа G. Зокрема, знаючи число вершин n, число ребер m і степені d(vi) (i=1,…,n) всіх вершин графа, можна отримати нижню й верхню оцінки для хроматичного числа. Нижня оцінка для хроматичного числа виглядає так:
.Верхні оцінки для хроматичного числа графа:
або
.Застосування оцінок для хроматичного числа значно звужує межі рішення. Для визначення оцінки хроматичного числа також можна використовувати інші топологічні характеристики графа, наприклад, властивість планарності. Граф, який можна зобразити на площині так, що ніякі два його ребра не перетинаються між собою, називають планарним. Наведена далі теорема стверджує, що коли граф G − планарний, то
.Теорема (про п'ять фарб) . Кожен планарний граф можна розфарбувати за допомогою щонайбільше п'яти кольорів так, що будь-які дві суміжні вершини будуть пофарбовані в різні кольори.
У наведеній далі гіпотезі йдеться про те, що коли граф G − планарний, то
.Гіпотеза (про чотири фарби). Кожен планарний граф можна розфарбувати за допомогою щонайбільше чотирьох кольорів так, що будь-які дві суміжні вершини будуть пофарбовані в різні кольори.
Ця гіпотеза (в еквівалентному формулюванні для географічних карт) з’явилася ще в середині 19-го століття. Її непрямо підтверджує час (більше століття), протягом якого численні спроби побудувати контрприклади залишалися марними. Гіпотезу чотирьох фарб доведено для окремих класів графів, наприклад, для графів, що мають не більше 41 вершини. В 1969 році Х. Хеєш звів проблему чотирьох фарб до дослідження великої, але скінченної множини графів. Пізніше кількість графів цієї множини було зведено до 1482 і вже в 1976 році колективу математиків і программістів під керівництвом К. Аппеля і В. Хейкена за допомогою ЕОМ вдалося розфарбувати всі ці графи. У 1996 році Н. Робертсон, Д. Сендерс, П. Сеймур, Р. Томас запропонували нове, простіше доведення гіпотези чотирьох фарб, але знову з використанням комп’ютера. Проте з повною мірою математичної строгості її не доведено, оскільки, наприклад, не доведено коректність компілятора та коректність виконання побудованого програмного коду, за допомогою якого будувалося розфарбування, крім того, і зведення загального випадку до перебору скінченної множини графів, і розфарбування останніх складно повторити.
Такий “фізичний” експериментальний спосіб доведення не влаштовує багатьох професійних математиків, і вони продовжують пошуки аналітичного доведення гіпотези.
Евристичний алгоритм розфарбовування
В інформатиці евристичний алгоритм− це алгоритм, спроможний видати прийнятне рішення проблеми серед багатьох рішень, але неспроможний гарантувати, що це рішення буде найкращим. Отже, такі алгоритми є приблизними і неточними. Зазвичай такі алгоритми знаходять рішення, близьке до найкращого і роблять це швидко. Іноді такий алгоритм може бути точним, тобто він знаходить дійсно найкраще рішення, але він все одно буде називатися евристичним доти, доки не буде доведено, що рішення дійсно найкраще.
Два фундаментальні завдання в інформатиці − знаходження алгоритмів з імовірно найкращим часом виконання та з доброю якістю. Евристичний алгоритм відмовляється від одного або обидвох завдань; наприклад, він зазвичай знаходить дуже добре рішення, але немає доказів, що рішення насправді не є поганим; або працює досить швидко, але не має гарантії, що він завжди видасть рішення.
Часто можна знайти таку задачу, в якій евристичний алгоритм буде працювати або дуже довго, або видавати невірні результати, однак, такі парадоксальні приклади можуть ніколи не зустрітись на практиці через свою специфічну структуру. Таким чином, використання евристики дуже поширене в реальному світі. Для багатьох практичних проблем евристичні алгоритми, можливо, єдиний шлях для отримання задовільного рішення за прийнятний час.
Точні методи розфарбування графа складні для програмної реалізації. Однак існує багато евристичних процедур розфарбовування, що дозволяють знаходити хороші наближення для визначення хроматичного числа графа. Такі процедури можна з успіхом використовувати при розфарбовуванні графів з великою кількістю вершин, де застосування точних методів не виправдане з огляду на великий обсяг потрібних обчислень.
З евристичних процедур розмалювання слід відзначити послідовні методи, засновані на упорядкуванні множини вершин. В одному з найпростіших методів вершини спочатку розташовуються в порядку зменшення їх степенів. Перша вершина забарвлюється в колір 1; потім список вершин проглядається за спаданням степенів і в колір 1 забарвлюється кожна вершина, яка не є суміжною з вершинами, забарвленими в цей колір. Потім повертаємося до першої в списку незафарбованої вершини, зафарбуємо її в колір 2 і знову переглядаємо список вершин, фарбуючи в колір 2 будь-яку незабарвлену вершину, що не з'єднана ребром з іншою, вже пофарбованою в колір 2 вершиною. Аналогічно діємо з кольорами 3, 4 і т. д., поки не будуть пофарбовані всі вершини. Число використаних кольорів буде тоді наближеним значенням хроматичного числа графа.
Більш точно, евристичний алгоритм розфарбування вершин графа має такий вигляд.
Крок 1. Посортувати вершини графа в порядку зменшення їх степенів:
, де 
для 
. Встановити колір 
.Крок 2. Встановити
, 
− множина вершин, вже розфарбованих в колір p.Крок 3.
. Якщо вершина 
не розфарбована і не є суміжною ні з однією вершиною з множини 
, то присвоїти їй колір 
та доповнити множину 
.Крок 4. Якщо
, то перейти на крок 3.Крок 5. Якщо всі вершини графа розфарбовані, то кінець алгоритму; інакше:
та перейти на крок 2.4.2. Порядок виконання роботи
Завданням роботи є створення програми, що реалізує евристичний алгоритм правильного розфарбування для довільного скінченного неорієнтованого графа без петель.
Далі наведено приклад виконання описаного евристичного алгоритму розфарбування для графа G, зображеного на рис. 5.2.
Рис. 5.2. Граф, який розфарбовуємо.
Проміжні дані для вирішення задачі будемо записувати в табл. 5.1. Відсортуємо вершини графа за спаданням їх степенів. У результаті отримуємо
. Відповідні даним вершинам степені дорівнюють: {5,4,4,3,2,2}. У першому рядку таблиці запишемо номери посортованих вершин; а в другому − відповідні вершинам степені. Наступні рядки відображають етапи присвоєння кольорів вершинам. Значення 0 означає, що вершина ще не пофарбована.| Таблиця 5.1. Етапи розфарбування | ||||||
| номери вершин | v1 | v5 | v6 | v4 | v2 | v3 |
| степені вершин | 5 | 4 | 4 | 3 | 2 | 2 |
| p: = 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| p: = 2 | 1 | 2 | 0 | 0 | 0 | 2 |
| p: = 3 | 1 | 2 | 3 | 0 | 3 | 2 |
| p: = 4 | 1 | 2 | 3 | 4 | 3 | 2 |
Результат розфарбування показано на рис. 5.3. Таким чином, даний граф можна розфарбувати щонайбільше чотирма кольорами, тобто
.
Рис. 5.3. Розфарбування графа з рис. 5.2.
Завдання для лабораторної роботи
1. Одержати завдання у викладача у вигляді початкового неорієнтованого графа.
2. Створити програму, що реалізує евристичний алгоритм розфарбування графа. Початковий граф задавати матрицею суміжності, яку слід вводити через рядок за допомогою консолі. Програма повинна вивести список отриманих кольорів для всіх вершин графа.
СПИСОК ЛІТЕРАТУРИ
Андрiйчук В.I., Комарницький М.Я., Iщук Ю.Б. Вступ до дискретної математики – Львiв: Видавничий центр ЛНУ, 2003.– 254с.
Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика: Підручник – К.: Вища школа, 2002. – 287с.
Бондаренко М.Ф., Білоус Н.В., Руткас А.Г. Комп’ютерна дискретна математика: Підручник – Харків: Компанія СМІТ, 2004. – 480с.
Ємець В., Мельник А., Попович Р. Сучасна криптографія: основні поняття – Львів, БаК, 2003.- 144 с.
Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник – К.: Наукова думка, 2002. – 568с.
Манзій О. С., Тесак І. Є., Кавалець І. І., Чарковська Н. В. Дискретна математика. Практикум: Навчальний посібник – Львів: Видавництво Львівської політехніки, 2016. – 212 с.
Матвієнко М. П. Дискретна математика: Підручник. Вид. 2-ге перероб. і доп. – Київ: Видавництво Ліра-К, 2017. – 324 с.
Нікольський Ю.І., Пасічник В.А., Щербина Ю.Р. Дискретна математика: Підручник – Київ: Видавнича група BHV, 2007. – 368 с.
Стрелковська І.В., Буслаєв А.Г., Харсун О.М., Пашкова Т.Л., Баранов М.І., Григор’єва Т.І., Вишневська В.М., Кольцова Л.Л. Дискретна математика: Навч. посіб. − Одеса: ОНАЗ ім. О. С. Попова, 2010. −196 с.