 |
Разновидности остовных деревьев
|
|
|
|
Некоторые задачи приводят к необходимости построить остов не минимального, а максимального веса, например, к нахождению максимального остовного дерева сводится проблема активации задач.
Рассмотрим ситуацию, когда на входе ЭВМ имеется некоторое множество задач, имеющих общие страницы в памяти. Требуется определить такую последовательность пропуска этих задач, чтобы минимизировать пересылки страниц в памяти. Для решения построим граф, вершинами которого будут служить задачи, а две вершины будут соединены ребром тогда и только тогда, когда они соответствуют задачам, имеющим общие страницы памяти. Каждому ребру сопоставляется вес, зависящий от числа общих страниц. Искомая последовательность выполнения задач будет задаваться остовным деревом максимального веса. К этой задаче также применимы алгоритмы Краскала и Прима, если изменить знак веса каждого ребра на противоположный.
Заметим, что большинство алгоритмов на графах нельзя так легко адаптировать на работу с отрицательными числами.
Если требуется найти остовное дерево с минимальным произведением весов ребер, то учитывая, что log(ab) = log(a) + log(b), минимальное остовное дерево графа, в котором веса ребер заменены их логарифмами дает нужное нам решение. Правда, вес ребер обязательно должен быть положительным.
C задачей об остове минимального веса тесно связана задача Штейнера. На практике эта задача возникает при проектировании коммуникационных сетей, когда необходимо соединить данное множество станций, используя кабель наименьшей протяженности. Естественно сопоставить станции – вершинам графа, а кабели между станциями – ребрам. Задача Штейнера отличается от задачи построения остова минимального веса в графе тем, что в этот граф разрешается вносить новые вершины – точки Штейнера. Их можно добавлять столько, сколько потребуется, чтобы дерево, их соединяющее, имело минимальный вес.
|
|
|
На рисунке 16а представлен исходный граф, представляющий собой равносторонний треугольник с длиной стороны равной единице, рядом (рис. 16б) – его минимальное остовное дерево. Его длина равна 2. И на рисунке 16в – дерево Штейнера исходного графа, которое соединяет все вершины графа, при помощи еще одной, дополнительной. Его длина равна 
.
Рис. 16. Граф, его остовное дерево и дерево Штейнера
Какие-либо эффективные алгоритмы, решающие задачу Штейнера, неизвестны.
Упражнения.
1. Объясните, могут ли алгоритмы Краскала и Прима выдавать разные минимальные остовные деревья.
2. Дан взвешенный граф G и его минимальное остовное дерево T. В G добавили ребро E с весом W. Разработайте алгоритм, который за минимальное число операций строит остовное дерево графа G + E.
3. Дан взвешенный граф G и его минимальное остовное дерево T. В G вес всех ребер увеличили на d. Объясните, останется ли T минимальным остовом графа G.
4. Укажите эффективный алгоритм для такой задачи: для данного взвешенного графа G =(V, E, W) найти наилучшее покрывающее дерево, критерий «качества» дерева – вес его самого тяжелого ребра (который д.б. как можно меньше).
5. Пусть минимальный остов уже построен. Как быстро можно найти новый минимальный остов, если добавить к графу новую вершину и инцидентные ей ребра? Напишите алгоритм, решающий эту задачу.
6. Укажите эффективный алгоритм поиска второго по величине покрывающего дерева.
7. Разработайте алгоритм решения следующей задачи: Имеется N городов. Для каждой пары городов (i, j) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A (i, j). Вне городов дороги не пересекаются. Требуется найти самую дешевую систему дорог, позволяющую попасть из любого города в любой другой. Результаты задавать таблицей B, где B [ i, j ]=1 тогда и только тогда, когда дорогу, соединяющую города i и j, следует строить.
|
|
|
Циклы в графах
В этой лекции рассматриваются вопросы, связанные с существованием в графе самых различных циклов. Задачи, связанные с циклическим обходом графа очень часто встречаются на практике, например, при проверке оборудования, профилактических работах в коммуникационных сетях и т.д.
Эйлеров цикл
Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом.
Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Определить, содержит ли граф эйлеров цикл достаточно просто. Полную характеристику эйлерова графа дает теорема, доказанная Л. Эйлером еще в 1736 г.
Теорема. Связный неориентированный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
Естественно возникает вопрос: как найти хотя бы один эйлеров цикл в эйлеровом графе G, т. е. как занумеровать ребра графа числами 1, 2,..., m (G) с тем, чтобы номер, присвоенный ребру, указывал, каким по счету это ребро проходится в эйлеровом цикле? Ответ на этот вопрос дает алгоритм Флери. Ребра нужно нумеровать, придерживаясь следующих двух правил:
1. Начиная с произвольной вершины u, присваиваем произвольному ребру { u, v } номер 1. Затем вычеркиваем ребро { u, v } и переходим в вершину v.
2. Пусть w – вершина, в которую мы пришли в результате выполнения предыдущего шага, и k – номер, присвоенный некоторому ребру на этом шаге. Выбираем любое ребро, инцидентное вершине w, причем мост выбираем только в том случае, когда нет других возможностей; присваиваем выбранному ребру номер k +1 и вычеркиваем его.
Этот процесс заканчивается, когда все ребра графа вычеркнуты, т.е. занумерованы.
Дадим теперь обоснование алгоритма. Прежде всего заметим, что поскольку степень каждой вершины графа G четна, то алгоритм может закончить работу только в той вершине, с которой начал. Поэтому он строит некоторый цикл C, и надо только доказать, что этот цикл включает все ребра графа G.
|
|
|
Предположим, что это не так, и пусть G ' – связная компонента графа G \ E (C), не являющаяся изолированной вершиной. Рассмотрим множество A ребер цикла C, инцидентных вершинам, вошедшим в G '. Ясно, что A ≠Ø. Пусть а – ребро из A, получившее в процессе работы алгоритма наибольший номер, т. е. вычеркнутое последним среди ребер A. Тогда, как легко видеть, ребро a к моменту вычеркивания было мостом в графе. Однако это противоречит правилу выбора очередного ребра.
Реализация алгоритма Флери основана на поиске в глубину. Пусть граф G, удовлетворяющий условию теоремы, задается матрицей смежности. Будем обходить граф методом поиска в глубину, при этом каждое просмотренное ребро удаляется. При обнаружении вершины, все ребра которой удалены, ее номер записывается в стек, и просмотр продолжается от предыдущей вершины. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, четность степеней вершин при этом не изменится. Процесс продолжается до тех пор, пока есть ребра. В стеке после этого будут записаны номера вершин графа в порядке, соответствующем эйлерову циклу.
Код алгоритма приведен в листинге 11.
public class EulerCycleSearch
{ // алгоритм Флёри поиска Эйлерова цикла в графе
Stack<int> cycleVertex; // стек для хранения вершин цикла
public EulerCycleSearch(graph g)
{
cycleVertex = new Stack<int>();
DFS_traversal(g, 0); // начало обхода графа
Console.WriteLine("Вершины эйлерова цикла");
while(cycleVertex.Count>0)
{
Console.Write("{0} ",cycleVertex.Pop());
}
Console.WriteLine();
}
void DFS_traversal(graph g, int v)
{// рекурсивный метод обхода
for(int i = 0; i < g.kol_vershn; i++)
{// если вершины смежны и в i еще не были
if (g.matr_smeznosti[v, i]!= 0)
{ // удаление пройденного ребра
g.matr_smeznosti[v,i]=0;
g.matr_smeznosti[i,v]=0;
DFS_traversal(g, i); //рекурсивный вызов
}
}
cycleVertex.Push(v);// сохранение вершины в стеке
}
}
Листинг 11. Реализация алгоритма Флери поиска эйлерова цикла в графе
Временная сложность алгоритма Флери совпадает с сложностью алгоритма поиска в глубину и равна O (n 2). На рисунке 17 изображен граф G и приведена последовательность вершин, составляющих эйлеров цикл, которую находит алгоритм.
Рис. 17. Граф G и его эйлеров цикл.
Все сказанное в этом параграфе о графах может быть перенесено и на мультиграфы.
|
|
|
