Відомості з теорії графів, методи отримання точних розв"язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп"ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
У даній курсовій роботі розглядаються прикладні задачі, які зводяться в теорії графів до оптимального розфарбування планарних графів та знаходження їх хроматичного числа. Метою роботи є систематизувати та поглибити знання з дискретної математики, теорії алгоритмів, зокрема застосування теорії графів у дослідженні прикладних задач, повязаних із розфарбуванням графів; вивчити можливості інформаційних технологій у полегшенні процесу цього дослідження. дослідити типи прикладних задач, що зводяться до задачі розфарбування графів та існуючи методи їх розвязання;В математиці теорема про чотири кольори говорить, що будь-яку розташовану на сфері карту можна розмалювати чотирма кольорами так, щоб дві любі області, які мають спільні зони границі, були розмальовані в різні кольори. Теорема Хівуда (полягає в тому, що будь-який граф можна розмалювати 5 різними кольорами) була доведена в 1890 р. Понизити верхню планку для хроматичного числа будь-якого планарного графа з 5 до 4, тобто підтвердити гіпотезу про чотири кольори не вдавалося майже 90 років. У 1969 р. задача була зведена до розгляду кінцевого, але досить великого числа конкретних випадків, пізніше їх число було скорочене до "всього лиш" 1482.Обєкти - вершини графу, а звязки - дуги та ребра графу. Для різних областей використання видів графів можуть відрізнятися орієнтованістю, обмеженнями на кількість звязків і додатковими даними про вершини або ребра. Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представленні графами. Наприклад, будову Вікіпедії можна змоделювати за допомого орієнтованого графа, в якому статті це вершини, а посилання на інші статті це дуги (орієнтовані ребра). граф G - це впорядкована пара G: = (V,E), для якої виконуються наступні умови: V - множина вершин або вузлів, E - множина пар (у випадку неорієнтованого графу - невпорядкованих) вершин з V, які називають ребрами.Необхідно призначити кожній вершині v ? V колір так, щоб загальна кількість кольорів була мінімальним. Нехай: · k - кількість кольорів, в які можна розфарбувати граф, причому k ? | V |. розумніше спочатку знайти будь-яку розмальовку за допомогою швидкої евристики з деяким числом кольорів col і покласти k = col, інакше необхідно покласти k =| V |.IMG_d2b15a38-5bb6-465b-89d7-60f3ec757aac
IMG_64aa92f4-e243-4657-8f19-fabeef9f3510
IMG_340f87c3-5b36-48c7-a67c-66765cf8bf3c
IMG_25a0c8bd-3535-463b-84c0-a7fc3aa925e3
IMG_411b3b7a-5eea-48cc-b47b-12ebd322d1d0
IMG_8411f181-74af-4115-918b-e69390e48627
IMG_3b31de06-21e5-48a4-99f2-e16a7e8ecaed
IMG_fcf80e51-9f3a-4f75-a74b-1629216cb333
IMG_8226790f-70c9-4336-8063-dc56c375b608
IMG_8d32d67f-05ef-4677-9d68-cea9af2916ab
IMG_c1cab09f-5909-45b7-af84-0a9a20521ad9
IMG_89425029-d98e-4ea8-b23f-6b8de9efd132
IMG_ee1d2518-8f0b-4bec-8b5d-0f0efb7c4d0d
IMG_ee94519d-16e9-4885-b99f-ec1de70112f3
IMG_55258e02-16ca-4e07-9dc9-876e380c4c3f
IMG_adae5699-7fb6-49d4-9c63-6c3a2d112a81
IMG_e9176da0-5253-4505-a060-bf64a36b4f92
IMG_7fa0340a-781e-4ab4-929d-5be4bbdc0b72Р-задача - це задача, для розвязку якої існує поліноміальний алгоритм. NP-задачею називається задача, яка може бути розвязана на детермінованій машині Тьюринга за поліноміальний час O (nm), де n - розмір задачі. Якщо ж обмежитися детермінованими алгоритмами, то для вирішення будь-якої NP-задачі можна використовувати схему перебору з поверненням або подібні до неї перебірні схеми. Подібні алгоритми є експоненційними по своїй суті, і задачі, які вимагають застосування таких алгоритмів, відносяться до класу важко вирішуваних. Позначимо через P клас Р-задач, а через NP - клас NP-задач Ясно, що P - підмножина NP.Для NP-повних задач не відомо кращого методу рішення, ніж повний перебір всіх можливих варіантів, і, на думку більшості математиків, малоймовірно, щоб кращий метод був колись знайдений.Цей алгоритм використовується для стійкого розфарбування і є NP-складною задаче комбінаторної оптимізації. В ідеї алгоритму лежить здатність колонії мурах знаходити найкоротший шлях між мурашником та їжею. Кожна мураха залишає за собою слід секрету (феромонів) і, рухаючись в навколишньому середовищі, намагається дотримуватися стежок із секрету, що залишили інші мурахи. Чим більше мурах проходить цією дорогою, тим більше секретів залишається, тож імовірність що мураха вибере саме цей шлях значно зростає. Стежини по яких рухаються мурахи можна представити у вигляді ребра графа, що має назву конструкційного.Під час першої будується початкова допустима розфарбування графа за наступним правилом: перша вершина фарбується в перший колір, а далі для кожної вершини вибирається мінімальний за номером колір, такий щоб ніяка із суміжних з даною раніше забарвлених вершин не мала цього кольору. На першому кроці другої фази відшукується перша за номером вершина, пофарбована у колір, від якого ми хочемо позбутися.До задачі правильного розфарбування графів зводиться багато типових задач, наприклад: Задача про розфарбуванн
План
Зміст
Вступ
Розділ 1. Задача розфарбування графів: постановка задачі
1.1 Історія виникнення задачі
1.2 Деякі відомості з теорії графів
1.3 Математична модель задачі
2. Задача розфарбування графів як типовий приклад задачі np класу
2.1 Алгоритмічна складність задачі
2.2 Методи отримання точних розвязків задачі розфарбування графів
2.2.1 Алгоритм мурашиної колонії для розфарбування графів
2.2.2 Алгоритм розфарбування графу методом неявного перебору
