сла кроків. Таким чином, всі дослідження, пов'язані з розробкою алгоритмів правильної розмальовки графів, слід розвивати у двох напрямках:
) знаходження точних поліноміальних алгоритмів для обмежених класів графів;
В
Рисунок1. Два графа з однаковими n, m і розподілами ступенів вершин, але з різними хроматичними числами, (а)? (G) = 4, (б)? (G) = 2
) отримання наближених алгоритмів (поліноміальних) таких, які гарантують розфарбовування графа для деякого з інтервалу < span align = "justify">, де - число вершин G.
У цьому випускний кваліфікаційної роботі бакалавра для дослідження було обрано наближений алгоритм розмальовки вершин графа з перефарбою двоцвітних подграфов.
Завдання розмальовки вершин графа. Деякі приклади розмальовки графа
Задача про розфарбовування вершин графа, як було наведено вище, полягає в тому, що б розфарбувати вершини графа так, щоб будь-які дві суміжні вершини були розфарбовані в різні кольори, при цьому число використаних кольорів повинно бути найменшим.
Але завдання розмальовки в тому В«чистомуВ» вигляді, в якому вона розглядається в теорії, рідко зустрічається на практиці. Однак її узагальнення та різновиди (незначно відрізняються від неї) знаходять широке застосування у великому числі різних прикладних завдань. Нижче наведені деякі приклади розмальовки, часто зустрічаються на практиці. Природно, що даний список цими прикладами не обмежується. p align="justify"> Складання графіків огляду (перевірки)
У задачах теорії распісанійосмотри представляються, у вигляді тимчасових інтервалів. Кожному огляду можна зіставити вершину деякого графа, причому дві будь-які вершини графа будуть з'єднані ребром лише тоді, коли відповідні їм огляди не можна здійснювати одночасно. Потрібно скласти такий графік огляду, який пов'язаний з найменшими часовими витратами (з урахуванням наведених вище обмежень на В«сумісністьВ» оглядів). Це завдання еквівалентна задачі про розфарбовування вершин графа з використанням найменшого числа кольорів. Хроматичної число графа якраз і відповідає огляду, який вимагає найменших витрат часу. p align="justify"> Розподіл ресурсів
Нехай для виконання якихось n робіт треба розподілити m наявних ресурсів. Вважаємо, що кожна з робіт виконується за деякий (однаковий для всіх робіт) проміжок часу і що для виконання i-й роботи потрібно підмножина ресурсів S i .
Побудуємо граф G: кожній роботі відповідає певна вершина графа, а ребро існує в графі тоді і тільки тоді, коли для виконання і
