Алгоритм 1. Алгоритм Краскала.

Начальная установка. Все рёбра исходного графа являются неокрашенными и ни один из букетов не сформирован.

Шаг 1. Выбрать любое ребро, не являющееся петлёй. Окрасить это ребро в голубой цвет и сформировать букет, включив в него концевые вершины выбранного ребра.

Шаг 2. Выбрать любое неокрашенное ребро, которое не является петлёй. Если в графе такого ребра не найдётся, то закончить процедуру: исходный граф не содержит покрывающего дерева.

После указанного выбора возможны четыре различных случая:

А. Обе концевые вершины выбранного ребра принадлежат одному и тому же букету. В этом случае ребро окрашивается в оранжевый цвет и производится возврат к началу шага 2.

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

В. Ни одна из концевых вершин не принадлежит ни одному из сформированных букетов. Если имеет место такой случай, то необходимо окрасить ребро в голубой цвет и сформировать новый букет из его концевых вершин.

Г. Концевые вершины выбранного ребра принадлежат различным букетам. В этом случае необходимо окрасить выбранное ребро в голубой цвет, а оба букета, которым принадлежат его концевые вершины, слить в один новый букет.

Шаг 3. Если все вершины графа вошли в один букет, закончить процедуру, так как при этом условии голубые рёбра образуют покрывающее дерево. В противном случае вернуться к началу шага 2.

Рассмотрим работу данного алгоритма для графа, изображенного на рис. 3.13.

Будем рассматривать рёбра графа в следующем, произвольно выбранном порядке: (a,b), (d,e), (a,d), (b,e), (e,c), (c,b), (a,c) и (с,d).

Результаты выполнения алгоритма сведены в таблице 3.4.

 

Алгоритм заканчивается просмотром ребра (e,c), поскольку после этого вершины рассматриваемого графа попадают в один букет. Четыре голубых ребра (a,b), (d,e), (a,d) и (e,c) образуют для данного графа покрывающее дерево (см. рис. 5.2.).

 

Таблица. 3.4.

Этапы построения покрывающего дерева графа, изображенного на рис.3.13,

согласно алгоритму 1

Ребро	Цвет	Букет № 1	Букет № 2
		Пуст	Пуст
{a,b}	Голубой	{a,b}	Пуст
{d,e}	Голубой	{a,b}	{d,e}
{a,d}	Голубой	{a,b,d,e}	Пуст
{b,e}	Оранжевый	{a,b,d,e}	Пуст
{e,c}	Голубой	{a,b,d,e,c}	Пуст

 

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

 

 

Часто в практических задачах необходимо учитывать веса на рёбрах и получать покрывающее дерево минимальной или максимальной стоимости.

Приведем пример такой задачи.

Задача 4. В управлении шоссейных дорог рассматривается проект строительства новых дорог, которые должны связать несколько городов некоторого района (причем не обязательно непосредственно каждую пару городов). Стоимость прокладки дороги между каждой парой городов известна.

Для сведения данной задачи к графовой представим каждый из городов вершиной графа, а каждую возможную дорогу ребром с весом, равным стоимости её прокладки. Таким образом, получим полный взвешенный граф.

Составление проекта строительства дороги теперь можно свести к задаче построения покрывающего дерева минимальной стоимости.

Алгоритм построения минимального покрывающего дерева. Данный алгоритм отличается от алгоритма 1 тем, что рёбра просматриваются в порядке возрастания их весов. То есть можно выделить два этапа:

1) сортировка рёбер по весу (если два или более рёбер имеют одинаковые веса, то они упорядочиваются произвольным образом);

2) построение покрывающего дерева по алгоритму 1.

Алгоритм построения максимального покрывающего дерева. Данный алгоритм аналогичен алгоритму построения минимального покрывающего дерева, только рёбра графа рассматриваются в порядке убывания их весов.

Алгоритм Краскала относится к классу градиентных алгоритмов. Еще такие алгоритмы называют «жадными». Общее свойство градиентных алгоритмов состоит в том, что на каждом шаге их работы осуществляется выбор некоторого оптимального варианта, причем этот выбор не учитывает последствий, которые могут иметь место при осуществлении выборов на последующих шагах. Такой подход, как правило, позволяет строить эффективные алгоритмы. Однако возникает естественный вопрос – каковы свойства задач, для которых градиентный алгоритм находит точное решение. Ответ на этот вопрос дает теория матроидов.

Матроидом называется пара множеств M=(D,Â), где D={d₁,…,d_m} – некоторое конечное множество, а Â={F₁,…,F_k} – множество подмножеств множества D, которое обладает следующими двумя свойствами:

1) из того, что FÎÂ и HÍF, следует, что HÎÂ;

2) пусть F,TÎÂ, |F|=u, |T|=u+1, тогда в T найдется элемент t, такой, что FÈtÎÂ и |FÈt|=u+1.

Эти свойства обычно называют аксиомами матроида. Максимальные по включению элементы множества Â называют базами. Все базы матроида равномощны.

Рассмотрим следующую задачу дискретной оптимизации. Пусть D – непустое конечное множество, w: D®R⁺ - функция, ставящая в соответствие каждому элементу dÎD неотрицательное действительное число w(d) – вес элемента d. Пусть также задано непустое множество Â подмножеств множества D. Вес FÎÂ определяется как сумма весов всех элементов, составляющих F, то есть

w(F) = å w(d)

dÎF

Задача состоит в поиске FÎÂ максимального веса.

Сформулируем градиентный алгоритм решения этой задачи.

Шаг 1. Находим такой элемент d₁ÎD, что

w(d₁) = max w(d)

{d}ÎÂ

Шаг k (k³2). Находим такой элемент d_kÎD, что

w(d_k) = max w(d)

{d₁,…,d_k-1,d}ÎÂ

d¹d_i, i=1,…,k-1

Если такого элемента нет, то конец алгоритма.

Очевидно, что выходом градиентного алгоритма всегда является множество FÎÂ, причем мощность множества F больше или равна мощности любого множества F¢ÎÂ, то есть выходом градиентного алгоритма является одна из баз. Однако вес F может оказаться меньше, чем вес некоторого F¢.

Например, для D={1,2,3}, Â={{1}, {1,2}, {2,3}}, w(1)=3, w(2)=2, w(3)=4 алгоритм найдет множество {1,2}, однако множество {2,3} имеет больший вес.

Если же в рассмотренной задаче (D,Â) – матроид, то градиентный алгоритм найдет множество FÎÂ максимального веса, то есть найдет точное решение задачи.

Что касается задачи построения максимального (минимального) покрывающего дерева, то её точное решение также дает градиентный алгоритм (алгоритм Краскала). Это следует из того, что задача построения максимального покрывающего дерева ничем не отличается от рассмотренной задачи. При этом D – множество рёбер исходного графа G; Â - множество деревьев, вершинами и рёбрами которых являются вершины и рёбра графа G; пара (D,Â) – матроид, базами которого являются покрывающие деревья графа G.

return false">ссылка скрыта

Итак, точное решение градиентный алгоритм дает лишь в задачах на матроидах (D,Â) при любом положительном взвешивании элементов множества D. Однако в силу своей простоты он часто используется для построения приближенных алгоритмов.

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

Построение эффективного алгоритма для нахождения всех покрывающих деревьев графа невозможно, так как само перечисление решений требует экспоненциального времени. Число покрывающих деревьев полного графа порядка n равно n^n-2.

Рассмотрим наиболее удачный алгоритм нахождения всех покрывающих деревьев.

Основной шаг алгоритма состоит в том, что множество всех покрывающих деревьев графа G делится на два класса: класс, содержащий выделенное ребро {u,v}, и класс, его не содержащий.

Покрывающие деревья, которые содержат {u,v}, состоят из ребра {u,v} и покрывающего дерева графа G_u,v, получающегося из G отождествлением вершин u и v (стягиванием ребра {u,v}) и удалением всех петель, которые могут получиться в результате такой операции.

Другой класс покрывающих деревьев составляют покрывающие деревья графа G–{u,v}, получаемого удалением из графа G ребра {u,v}.

Заметим, что каждый из графов G_u,v и G-{u,v} меньше, чем граф G. Поэтому последовательное применение (скажем, путем рекурсии) такого основного шага уменьшает графы до тех пор, пока либо все n вершин не отождествятся (сольются в одну вершину), либо все графы станут несвязными и не имеющими покрывающих деревьев.

Пример работы данного алгоритма проиллюстрирован на рис. 3.15.