Задача о реберной раскраске.

Определение. Реберная раскраска называется правильной, если любые два смежных ребра имеют разные цвета. Реберная раскраска с минимальным числом цветов называется минимальной.

Из этого определения следует, что минимальное число цветов в правильной реберной раскраске оценивается снизу степенью графа, т.е. максимальной степенью вершин.

Минимальное число цветов в правильной реберной раскраске называется хроматическим классом графа. Пусть ‑ степень вершины . Для графа без петель и кратных дуг верна оценка[10]

Сформулируем задачу поиска минимального числа цветов в реберной раскраске в терминах целочисленного программирования. Пусть ‑ номер цвета, в который окрашено ребро .

Тогда модель имеет вид:

(4.8)

, , , (4.9)

(4.10)

4.2.2. Построение остовного дерева минимального веса.

Минимальный остов

Задача о минимальном остове [6] состоит в отыскании остова минимального веса во взвешенном графе , где ‑ граф, ‑ вещественнозначная функция, ставящая в соответствие каждому ребру положительное (или неотрицательное) число ‑ вес ребра .

Задача о минимальном остове считается одной из самых «легких» оптимизационных задач па графах. Решение этой задачи можно получить с помощью «жадного» алгоритма, задав процедуру, которая по любому ациклическому множеству ребер и ребру определяет, содержит ли множество ребер цикл графа . В качестве такой процедуры можно использовать поиск в глубину, поскольку выявление цикла в множестве , где , равнозначно отысканию -цепи в порожденном подграфе . В процессе работы «жадного» алгоритма эта процедура выполняется не более раз, и, следовательно, затраты времени составят .

Для упорядочения множества по неубыванию весов известны алгоритмы сложности . Таким образом, даже использование «жадной» стратегии поиска минимального остова приводит (независимо от способа задания графа ) к полиномиальному алгоритму сложности [11].

Рассмотрим алгоритм построения остовного дерева минимального веса, предложенный Примом [2, с. 73]. Алгоритм Прима порождает дерево посредством разрастания только одного поддерева, например , содержащего более одной вершины. «Одиночные» вершины рассматриваются как отдельные поддеревья (т. е. , для всех ). Поддерево постепенно разрастается за счет присоединения ребер , где и , причем добавляемое ребро имеет наименьший вес среди ребер из . Процесс продолжается до тех пор, пока число ребер в не станет равным . Тогда дерево будет требуемым остовом графа .

Алгоритм начинает работу с присвоения каждой вершине пометки , где на каждом шаге есть ближайшая к вершина из а ‑ вес ребра . На каждом шаге алгоритма вершина, например , с наименьшей пометкой присоединяется к посредством добавления ребра . Поскольку к добавлена новая вершина , то, может быть, придется изменить пометки у некоторых вершин , и после этого продолжить процесс.

Алгоритм Прима имеет следующий вид.

Инициализация

Пусть , где — произвольно выбранная вершина из , .

Основной цикл

Шаг 1. Для каждой вершины найти вершину такую, что и приписать вершине пометку . Если такой вершины нет, т. е. при , приписать вершине пометку .

Шаг 2. Выбрать такую вершину , что .

Обновить данные:

.

Если , то останов. Ребра в образуют остов минимального веса. Если , то перейти к шагу 3.

Шаг 3. Для всех таких, что обновить пометки следующим образом:

а) если , то положить , и вернуться к шагу 2;

б) если , то перейти к шагу 2.

Вычислительная сложность алгоритма Прима составляет операций.

Для решения задачи построения остова минимального веса также используется алгоритм Краскала. Рассмотрим шаги этого алгоритма.

Инициализация

Положить — несвязный граф, содержащий вершин.

Сортировка

Упорядочить ребра графа в порядке неубывания их весов.

Основной цикл

Шаг 1. Начать с первого ребра в построенном на шаге Сортировка списке. Добавлять ребра графу , соблюдая условие: добавление ребра не должно приводить к появлению цикла в .

Шаг 2. Повторять шаг 1 до тех пор, пока число ребер в не станет равным .