4.2. Экстремальные задачи на графовых структурах.

1. Задачи о раскрасках графов.

Задачи о раскрасках графов.

Задача о вершинной раскраске. Каждой вершине графа поставим в соответствие цвет.

Определение 4.25. Вершинная раскраска графа называется правильной, если для любого ребра имеем.

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

Определение 4.26. Хроматическим числом графа называется величина

.

Хроматическому числу соответствует правильная раскраска .

Немецкий математик Мёбиус (1790-1868) высказал в 1840 г. предположение, что для плоских графов ; это предположение получило название гипотезы о четырех красках. Для плоских графов доказано, что ⁸, для деревьев . Гипотеза о четырех красках в течение длительного времени оставалась недоказанной, она стала одной из самых знаменитых нерешенных задач математики. В 1976 г. эту гипотезу удалось доказать с применением компьютера. Было показано, что если для некоторых специальных классов графов, то это условие выполняется для всех графов. Если же хотя бы для одного графа из этих специальных классов , то гипотеза неверна. Все эти специальные классы графов были проанализированы К. Аппелем и В. Хайкеном⁹ на компьютере, для этого потребовалось около 2000 ч машинного времени одной из наиболее мощных ЭВМ того времени; гипотеза была подтверждена [6].

Сформулируем задачу о вершинной раскраске на языке целочисленного линейного программирования.

Пусть ‑ номер цвета, в который окрашена вершина, такая раскраска является правильной, если, например,. Если, то, что можно записать так:

или .

Целевая функция имеет вид

.

Итак, модель описывается соотношениями

, ,

Построенная модель нелинейна по ограничениям и целевой функции. Поэтому рассмотрим другую модель. Введем бинарные переменные

Каждая вершина имеет один цвет, что можно записать в виде

Если , то

Если цвет с номером входит в раскраску, то

,

если цвет в раскраску не входит, то. Поэтому модель имеет вид

(4.5)

(4.6)

, . (4.7)

В самом деле, если ни одна из двух смежных вершин ине окрашена в цвет, то

если одна из них (например, ) окрашена в цвет, то вторая из них () окрашена в другой цвет, поэтому

Итак, модель описывается соотношениями (4.5)-(4.7).

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

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

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

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

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

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

(4.8)

, ,, (4.9)

(4.10)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

Сортировка

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

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

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

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