Анотація
Випускна кваліфікаційна робота присвячена алгоритмічним проблемам завдання про правильну розфарбуванні вершин графа, яка відноситься до класу NP-повних задач. У роботі вивчається евристичний алгоритм розмальовки вершин графа з перефарбою двоцвітних компонент. Алгоритм запрограмований на мові Сі + + в середовищі програмування MicrosoftVisualStudio 2010, отримані чисельні результати. br/>
Введення
довільний граф алгоритм
Різноманітні завдання, що виникають при плануванні виробництва, складанні графіків огляду, зберіганні та транспортуванні товарів і т. д., можуть бути представлені часто як задачі теорії графів, тісно пов'язані з так званою В«завданням розмальовкиВ».
Нехай G = (V, E) - звичайний граф, тобто неорієнтовані граф без кратних ребер і петель. Розфарбуванням вершин графа називається призначення квітів його вершінам.Обично кольору - це числа . Розмальовка називається правильною, якщо кожен кольоровий клас є незалежною безліччю (незалежне множествовершін графа-це будь безліч попарно не суміжні вершин, тобто безліч вершин, що породжує порожній подграф). Інакше кажучи, в правильній розмальовці будь-які дві суміжні вершини повинні мати різні кольори. Завдання про розфарбовування полягає в знаходженні правильної розмальовки даного графа Gс найменшим числом цветов.Ето число називається хроматичним числом графа G, тобто це мінімальне число кольорів, що вимагається для розмальовки G.
Хроматичні число графа не можна знайти, знаючи тільки числа вершин і ребер графа. Недостатньо також знати ступінь кожної вершини, щоб обчислити хроматичної число графа. У цьому можна переконатися, розглядаючи графи, наведені на рис. 1 (a) та 1 (6). Ці графи мають по вершин, ребер і однакові розподілу ступенів вершин . Однак хроматичні числа даних графів дорівнюють 4 і 2 відповідно. При відомих величинах n (число вершин), m (число ребер) і (ступеня вершин графа) можна отримати верхню і нижню оцінки для хроматичного числа графа. Деякі оцінки хроматичного числа ми розглянемо нижче.
Задача знаходження хроматичного числа довільного графа з'явилася предметом багатьох досліджень наприкінці XIX і в наступних століттях. Зараз з цього питання відомо велика кількість цікавих результатів. Але ми не будемо заглиблюватися в ці результати. p align="justify"> Так само завдання знаходження хроматичного числа графа увійшла в знаменитий список з 21 NP - повної задачі, запропонований в 1972 році Р. Карпом. Тому, всі відомі алгоритми, які знаходять мінімальну розмальовку для будь-якого графа, вимагають експоненціального чи...
