5. Связность

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

Задача 3. В небольшой деревушке некоторые из жителей имеют каждодневные встречи друг с другом. Может ли в этой деревне распространиться какой-либо слух?

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

В данном разделе будут рассмотрены алгоритмы для решения таких и других подобных задач.

5.1. Построение покрывающих деревьев

Исходя из определения покрывающего дерева (см. гл.3), можно сделать вывод, что оно существует только для связных графов. То есть если нам удалось построить хотя бы одно покрывающее дерево для данного графа, можно сделать вывод, что он связный.

Рассмотрим алгоритм построения покрывающего дерева, предложенный Дж. Краскалом в 1957 г.

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

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

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

В процессе работы алгоритма рёбра, включенные в дерево, составляют граф, имеющий один или несколько связных компонентов. Множество вершин, принадлежащих отдельному связному компоненту, для сокращения речи будем называть “букетом”. Некоторое ребро образует цикл с рёбрами, уже включенными в дерево, если обе его концевые вершины принадлежат одному и тому же связному компоненту (одному и тому же букету).

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

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

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

Сформулируем алгоритм построения покрывающего дерева.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица. 5.1. Этапы построения покрывающего дерева графа, изображенного на рис.5.1, согласно алгоритму 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.

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

Упражнения:

1. Реализуйте алгоритм Краскала, то есть выберите способ хранения графа, удобный для реализации алгоритма Краскала, разработайте структуры для хранения рабочих переменных (букетов, цветов рёбер), обоснуйте свой выбор с точки зрения занимаемой памяти, быстродействия, универсальности и др., напишите программу, реализующую данный алгоритм и подберите тесты для её проверки. Оцените трудоемкость программы.

2. Дополните алгоритм возможностью выдавать все деревья покрывающего леса в случае несвязного исходного графа.

3. Реализуйте различные методы сортировок и используйте алгоритм Краскала для построения минимального (максимального) покрывающего дерева. Оцените трудоемкость программ.

4. Для построения минимальных (максимальных) покрывающих деревьев также часто используется алгоритм, предложенный Р.Примом в 1957 г. Алгоритм Прима не требует сортировки рёбер. Алгоритм заключается в следующем:

Начинаем с некоторой произвольной вершины aв заданном графе. Пусть {a,b} - ребро с наименьшим весом, инцидентноеa; ребро {a,b} включается в дерево. Затем среди всех рёбер, инцидентных либоa, либоb, выбираем ребро с наименьшим (наибольшим) весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, скажемc. Повторяя процесс, ищем наименьшее ребро, соединяющееа,b илисс некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины не будут включены в дерево, то есть пока дерево не станет покрывающим.

Реализуйте алгоритм Прима, оцените его трудоемкость и сравните с алгоритмом Краскала. Обоснуйте, когда и какой алгоритм выгоднее применять.

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

Построение эффективного алгоритма для нахождения всех покрывающих деревьев графа невозможно, так как само перечисление решений требует экспоненциального времени. Число покрывающих деревьев полного графа порядка 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вершин не отождествятся (сольются в одну вершину), либо все графы станут несвязными и не имеющими покрывающих деревьев.

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