Описывается новый метод раскраски графа. Доказана его корректность. Приводится пример, иллюстрирующий метод.

1 УДК 8011 САКАНЦЕДАЛ МВКОСТИКОВА ПРОСТОЙ МЕТОД РАСКРАСКИ ГРАФА Описывается новый метод раскраски графа Доказана его корректность Приводится пример иллюстрирующий метод 1 Постановка задачи Разнообразные задачи планирования производства хранения и транспортировки грузов составления графиков осмотра оборудования и тп могут быть сформулированы как задачи оптимальной раскраски графа G = ( V E) с множеством вершин V и рёбер E В свою очередь суть оптимальной раскраски G состоит в выборе для окрашивания его вершин наименьшего количества цветов 1 так чтобы никакие смежные вершины графа не были окрашены в один цвет Полученный граф принято называть r -хроматическим (раскрашенным) а минимальное число цветов (красок) r хроматическим числом графа G [1] Рассмотрим следующую задачу Для выполнения n видов работ используется m типов ресурсов Все работы выполняются за одинаковое время но присеняют различные типы ресурсов Сокращение общего времени выполнения всех n работ может быть доступно тогда когда большинство из них выполняется параллельно (одновременно) Требуется так распределить типы ресурсов чтобы минимизировать общее время выполнения работ Сформулируем задачу в терминах графов Для этого каждой работе поставим в соответствие его вершины ϑ i i = 1 n Вершины ϑ i ϑ j соединим ребром тогда и только тогда когда для выполненияi -й и j -й работ требуется один и тот же тип ресурса Это говорит о том что указанные работы не могут выполняться одновременно Раскраска вершин полученного графа при помощи наименьшего количества красок будет означать что выделено наименьшее число его рёбер те тех пар работ которые не могут выполняться одновременно В свою очередь это будет означать что остальные работы могут выполняться параллельно и следовательно решение задачи о раскраске графа даст оптимальное решение поставленной задачи Цель исследования разработка нового алгоритма раскраски графа Задача для достижения цели изучение существующих алгоритмов Метод раскраски Задача о раскраске графов изучалась примерно с середины XIX века Для планарных графов строго доказано что их оптимальная раскраска требует не больше пяти цветов Гипотеза о том что такие графы могут быть раскрашены не больше чем четырьмя цветами доказана при помощи ЭВМ в 197 г Для решения задачи о раскраске обычных графов предложены как точные так и приближённые методы В связи с тем что задача о раскраске графа может быть представлена как задача целочисленного линейного программирования с булевыми переменными или сведена к задаче о наименьшем покрытии она может быть решена методами решения задач целочисленного линейного программирования отсечения либо по схеме ветвей и границ либо теми методами которые применяются для решения задачи о наименьшем покрытии Кроме этих методов для решения задачи о раскраске предложен метод динамического программирования и прямого перебора (исчерпывающий поиск) использующий дерево поиска [] Мы предлагаем один из самых простых методов решения задачи о раскраске графа G = ( V E) Он основан на последовательном окрашивании предварительно упорядоченных вершин графа состоит из тактов и на каждом такте окрашивания реализует идею максимально возможного окрашивания вершин G в один цвет

2 изображенный на рис 1 Вершины графа отмечены символами ϑ 1 Рядом представлен список множеств несмежных вершин всех вершин G Суть метода объясним на примере Пусть задан граф G = ( V E) ϑ 8 (ç) ϑ 7(æ) ϑ 1(ê) ϑ (ñ) ϑ (ç) ϑ (ç) ϑ 3 (ñ) ϑ (ê) < ϑ ϑ >ϑ < >1 7 : ϑ 3 < ϑ ϑ 7 > < ϑ 1 ϑ 8 > < ϑ 1 ϑ ϑ 3 ϑ 7 8 > < ϑ ϑ 3 8 > < ϑ 1 ϑ 3 > < ϑ ϑ ϑ >7 ϑ : ϑ Рис 1 Граф G и список множеств несмежных вершин Таким образом предлагаемый метод раскраски G предусматривает предварительное составление указанных множеств После этого вершины G упорядочиваются по невозрастанию мощностей множеств несмежных вершин В том случае когда мощности некоторых множеств одинаковы они относительно друг друга располагаются в произвольном порядке В результате для рассматриваемого примера получаем последовательность вершин ϑ ϑ ϑ 8 ϑ 1 ϑ 3 ϑ ϑ ϑ 7 которую обозначим γ Теперь приступим к окраске вершин G Для этого первой вершинеϑ последовательности γ назначим цвет 1 например зелёный и обозначим её ϑ (ç) Далее в множестве вершин < ϑ 1 ϑ ϑ 3 ϑ 7 ϑ 8 >несмежных вершине ϑ (ç) найдём вершину ближайшую к вершинеϑ в последовательности γ Такой является вершина ϑ Этой вершине также назначим цвет 1 и обозначим её ϑ (ç) После этого из множеств вершин < ϑ 1 ϑ ϑ 3 ϑ 7 ϑ 8 > < ϑ ϑ ϑ ϑ 8 >несмежных вершинам ϑ ϑ исключаем окрашенные вершины ϑ ϑ и находим множество несмежных вершин для суммы ϑ + Если множество таких вершин для ϑ + не пусто найдём ближайшую к началу γ вершину этого множества и назначим ей также цвет 1 Такие действия выполняем до тех пор пока множество несмежных вершин накапливающейся суммы окрашиваемых вершин G не окажется пустым Когда это произойдёт в последовательности γ найдём ближайшую к её началу неокрашенную вершину и назначим ей цвет Теперь описанные действия выполним с цветом После окраски вершин цветом переходим к цвету 3 и тд Процесс окраски графа завершаем тогда когда будет окрашена последняя вершина последовательности γ Множество несмежных вершин для ϑ + это пересечение множеств вершин < ϑ 1 ϑ 3 ϑ 7 ϑ 8 >и < ϑ ϑ ϑ 8 >несмежных вершинам ϑ ϑ из которых исключены вершины ϑ ϑ Оно равно < ϑ 8 >Следовательно вершине ϑ 8 также назначим цвет 1 и обозначим её ϑ 8(ç) Теперь определим множество несмежных вершин для суммы ϑ + + Из < ϑ 8 >исключаем окрашенную вершину ϑ 8 В результате получаем пустое множество А из множества вершин < ϑ ϑ ϑ ϑ >несмежных вершине ϑ 8 исключаем окрашенные вер- 8 3

3 шины ϑ ϑ ϑ Так как пересечение пустого множества с любым множеством пустое множество окраску вершин цветом 1 завершаем и назначаем цвет красный ближайшей к началу последовательности γ неокрашенной вершине ϑ 1 Обозначим её ϑ 1(ê) Из множества вершин < ϑ ϑ ϑ 7 >несмежных вершине ϑ 1(ê) исключаем окрашенную вершину ϑ и в полученном множестве < ϑ ϑ 7 >в цвет окрасим ближайшую к началу последовательности γ вершину ϑ Обозначим её ϑ (ê) Определим множество несмежных вершин для суммы ϑ 1 + ϑ Для этого из множества < ϑ ϑ 7 >исключаем окрашенную вершину ϑ и получаем множество < ϑ 7 >а из множества вершин < ϑ 1 ϑ ϑ 8 >несмежных вершине ϑ исключаем окрашенные вершины ϑ 1 и получаем пустое множество Так как пересечение полученных множеств пусто ближайшей к началу последовательности γ неокрашенной вершинеϑ 3 назначим цвет 3 синий и обозначим её ϑ 3(ñ) Из множества вершин < ϑ ϑ ϑ 7 >несмежных вершине ϑ 3 исключим окрашенную вершину ϑ и в полученном множестве < ϑ ϑ 7 >назначим ближайшей к началу последовательности γ вершинеϑ тоже цвет 3 Обозначим её ϑ (ñ) Далее определим множество несмежных вершин для суммы ϑ 3 + ϑ Для этого из множества < ϑ ϑ 7 >исключаем окрашенную вершину ϑ а из множества несмежных вершин < ϑ ϑ 3 ϑ 8 >окрашенные вершины ϑ ϑ 3 ϑ 8 Так как пересечение полученных множеств пусто назначим ближайшей к началу последовательности γ неокрашенной вершине ϑ 7 цвет жёлтый и обозначим её ϑ 7(æ) Из множества вершин < ϑ 1 ϑ 3 ϑ >несмежных вершине ϑ 7 исключим окрашенные вершины ϑ 1 ϑ 3 ϑ В результате получим пустое множество Это означает что нет вершины которую следует окрасить в цвет те все вершины последовательности γ а следовательно графа G окрашены Для этого понадобилось четыре цвета и таким образом хроматическое число графа r = Правильность описанного метода окраски графа и определения наименьшего его хроматического числа вытекает из следующего Метод реализует последовательную окраску вершин графа не пропуская ни одной его вершины В связи с тем что число вершин G конечно метод также конечен так как останавливается после их окраски С другой стороны метод выполняет последовательность этапов окраски вершин Начало каждого этапа задание очередного нового цвета вершине G а содержимое этапа включает действия направленные на окраску одним цветом по возможности наибольшего числа несмежных вершин G причём эти действия выполняются с позиций не одной вершины инициировавшей окраску а накапливаемой суммы окрашенных одним цветом вершин Тем самым гарантируется выполнение условия: никакие смежные вершины не окрашиваются в один цвет Поскольку число вершин G конечно и на каждом этапе в один цвет окрашивается максимальное число несмежных вершин число этапов окраски и следовательно цветов будет минимальным Полученные цвета окраски вершин G показаны на рис 1 в скобках возле обозначения каждой вершины Легко проследить что в результате раскраски G никакие пары смежных ему вершин не окрашены в один цвет В заключение решим задачу раскраски графа хроматическое число которого r = известно [] 3 Пример Граф G = ( V E) ϑ и получаем < >взятый из [] изображён на рис Рядом приведены множества вершин несмежности перечня его вершин

5 Находим несмежную вершину суммы ϑ + ϑ Для этого из множества < ϑ удаляем вершину ϑ а из множества вершин < ϑ ϑ3 ϑ несмежных вершине ϑ предварительно окрашенные вершины ϑ ϑ 3 ϑ 9 ϑ 11 Пересечение полученных множеств < ϑ < ϑ даёт множество < ϑ Ближайшей к началу последовательности γ вершиной в этом множестве является вершина ϑ 10 Окрашиваем её во второй цвет и обозначаем ϑ 10(ê) Определяем вершину несмежную сумме ϑ + ϑ Для этого из пересечения < ϑ удаляем вершину ϑ 10 а из множества вершин < ϑ 1 ϑ3 ϑ несмежных вершине ϑ 10 предварительно окрашенные вершины ϑ 1 ϑ ϑ 3 ϑ ϑ ϑ 9 ϑ 10 ϑ 11 Находим пересечение множеств < ϑ < ϑ в результате чего получаем < ϑ Ближайшей вершиной к началу последовательности γ в этом множестве является вершина ϑ 1 Её окрашиваем во второй цвет и обозначаем ϑ 1(ê) Находим вершину несмежную сумме ϑ + ϑ + ϑ1 Для этого из пересечения < ϑ удаляем вершину ϑ 1 а из множества вершин < ϑ 1 ϑ3 ϑ ϑ10>несмежных вершине ϑ 1 предварительно окрашенные вершины ϑ 1 ϑ ϑ 3 ϑ ϑ ϑ 9 ϑ 10 ϑ 11 ϑ 1 Пересечение полученных множеств < ϑ ϑ 7 ϑ 8 > < ϑ ϑ 7 >даёт множество < ϑ ϑ 7 >Вершиной ближайшей к началу последовательности γ в этом множестве является ϑ Окрашиваем её во второй цвет и обозначаем ϑ (ê) Находим вершину несмежную сумме ϑ + ϑ + ϑ1 + ϑ Для этого из пересечения < ϑ ϑ 7 >удаляем вершину ϑ а из множества вершин < ϑ 1 несмежных вершине ϑ предварительно окрашенные вершины ϑ 1 ϑ ϑ 3 ϑ ϑ ϑ 9 ϑ 10 ϑ 11 ϑ 1 ϑ Пересечение полученных множеств < ϑ 7 > < >пустое множество Поэтому неокрашенной вершине ϑ 7 ближайшей к началу последовательности γ назначим третий цвет и обозначим её ϑ 7(ñ) Множество вершин несмежных вершине ϑ 7 пусто так как все они окрашены Поэтому оставшейся неокрашенной вершине ϑ 8 назначаем четвертый цвет жёлтый и обозначаем её ϑ 8(æ) Таким образом для окраски вершин графа потребовалось четыре цвета те хроматическое его число r = Это совпадает с данными [ с 7] На рис назначенные цвета проставлены в скобках возле обозначения вершины графа Выводы Научная новизна работы состоит в том что разработан новый эффективный алгоритм окраски графа Практическая значимость исследований состоит в том что алгоритм легко программируем и может успешно применяться для различных задач окраски графа Список литературы: 1 Берж К Теория графов и ее применения М: ИЛ с Кристофидес Н Теория графов Алгоритмический подход М: Мир с Поступила в редколлегию Канцедал Сергей Андреевич д-р техн наук профессор кафедры прикладной математики и информатики Западнодонбасского института экономики и управления Научные интересы: математическое моделирование теория расписаний и её применение Адрес: Украина Павлоград ул Днепровская 00 Костикова Марина Владимировна канд техн наук доцент кафедры информатики Харьковского национального автомобильно-дорожного университета Научные интересы: математическое моделирование теория расписаний и её применение Адрес: Украина 100 Харьков ул Петровского тел

Тема 10. Раскрашивание графов 10.1. Хроматическое число Определение. Граф G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные