Каркасы графа. Алгоритм построения остовного дерева методом поиска в глубину

Каркас графа Лекция 3 Каркасы графа Каждый граф имеет каркас. Более того, у одного графа может быть несколько каркасов. Связный неориентированный граф называется деревом, если он не имеет циклов. Дерево не имеет петель и кратных ребер Остовное дерево или каркас графа - подграф: 1) содержит все вершины графа, 2) является деревом. Каркасы графа Каркас графа так же называют «Стягивающее дерево» или «Остовное дерево» Ребра графа, вошедшие в каркас будут называться ветвями, а не вошедшие в каркас- хордами. Каркасы можно строить как поиском в глубину, так и поиском в ширину. В любом случае достижение «новой» вершины u из «старой» вершины v означает включение ребра в каркас. Алгоритм построения остовного дерева методом поиска в глубину 1 procedure КАРКАС ГЛУБИНА(v) {поиск в глубину из вершины v, соединенный с нахождением ребра дерева; переменные НОВЫЙ, ЗАПИСЬ, T – глобальные} 2 begin НОВЫЙ[v]:= ложь; 3 for u ЗАПИСЬ[v] do 4 if НОВЫЙ[u] then { (u, v) - новая ветвь} 5 begin T := T + (v, u); КАРКАС ГЛУБИНА(u) end 6 end {вершина v использована}; begin главная программа for u ∈ V do НОВЫЙ[u]:= истина; { инициализация} T := пусто; {T – множество найденных к этому времени ребер каркаса} КАРКАС ГЛУБИНА(r) {r – произвольная вершина графа} end. Докажем корректность этого алгоритма. Алгоритм строит СВЯЗНЫЙ граф, т.к. каждое новое ребро (v-u) продолжает уже существующий путь от к к v. Построенный граф не содержит ЦИКЛОВ. Каждая новая ветвь (v-u) соединяет уже рассмотренную v с НОВОЙ и. Чтобы замкнуть, цикл, требуется ребро, соединяющее две уже РАССМОТРЕННЫЕ вершины. Построенный граф содержит ВСЕ вершины графа G — это свойство поиска в глубину. По этой же причине вычислительная сложность алгоритма O(n+m). Свойства каркаса Любой каркас обладает важным свойством — от корня к до произвольной вершины v существует ровно ОДИН путь, состоящий из ветвей каркаса. Если бы их было два, получился" бы цикл, если бы ни одного, каркас не был бы связным. 2. Кроме того, если каркас D построен поиском в-глубину, то для двух вершин u и v, СОЕДИНЕННЫХ РЕБРОМ, всегда можно сказать: или v — потомок и, или и — потомок v (относительно каркаса D). Первое означает, что и лежит на пути из корня к в вершину v, второе — v на пути из к в и. Это легко доказать. Пусть одна из вершин, например,v просмотрена раньше и. Построен путь от корня к до v. Процесс поиска в глубину начинается с вершины v. Taк как и u v соединены ребром, то, рано или поздно, будет рассмотрена вершина u и построен путь от v до u. Получился путь k—v—u. Если v и и соединены ВЕТВЬЮ каркаса, то одна из них— СЫН, другая — ОТЕЦ. 1. Алгоритм построения остовного дерева методом поиска в ширину Данные: связный граф G=. представленный списками ЗАПИСЬ[v], v e V. Результаты: каркас D = графа G. •begin for u  Запись[V] do НОВЫЙ[u] :=истина; {инициализация} •T:=0 {T - множество найденных ветвей} •ОЧЕРЕДЬ=NIL; ОЧЕРЕДЬ <= k; •НОВЫЙ[k]:=ложь; {к - корень} •while ОЧЕРЕДЬ > NIL do 7 begin v<= ОЧЕРЕДЬ; {вытолкнули из очереди нижний элемент} for u  ЗАПИСЬ[v] do •if НОВЫЙ[u] then {нашли новую ветвь v—u} •beginОЧЕРЕДЬ <=u; НОВЫЙ[u] :=ложъ; • Т:=Т + (v-u) {и присоединили ее к каркасу} •end •end •end. Легко доказать, что этот алгоритм строит каркас произвольного графа за O(n+m) шагов. Построение оптимального каркаса графа В задаче об оптимальном каркасе известна также как задача о кратчайшем остовном дереве. Задан граф G = (V, E) , каждому ребру которого приписано число, называемое весом ребра. Вес ребра (x, y) будем обозначать через w(x, y) . Вес множества D={v,T}, где T ≤ E, определяется как сумма весов составляющих его ребер. Требуется в графе G найти каркас минимального веса. Для решения этой задачи известно несколько алгоритмов. Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. Алгоритм Прима обладает тем свойством, что ребра в множестве А всегда образуют единое дерево. Дерево начинается с произвольной корневой вершины k и растет до тех пор, пока не охватит все вершины в V. На каждом шаге к дереву А добавляется «лёгкое» ребро, соединяющее дерево и отдельную вершину из оставшейся части графа. Данное правило добавляет только безопасные для А ребра; следовательно, по завершении алгоритма ребра в А образуют минимальное остовное дерево. Данная стратегия является жадной, поскольку на каждом шаге к дереву добавляется ребро, которое вносит минимально возможный вклад в общий вес. 1) Выбирается произвольная вершина - она будет корнем остовного дерева; 2) Измеряется расстояние от нее до всех других вершин, т.е. находится минимальное расстояние s от дерева до вершин, которые не включены в дерево; 3) До тех пор пока в дерево не добавлены все вершины делать: - найти вершину u, расстояние от дерева до которой минимально; - добавить ее к дереву; - пересчитать расстояния от невключенных вершин до дерева следующим образом: если расстояние до какой-либо вершины от u меньше текущего расстояния s от дерева, то в s записывается новое расстояние. Алгоритм Прима (другой алгоритм) На каждом шаге вычеркиваем из графа дугу максимальной стоимости с тем условием, что она не разрывает граф на две или более компоненты связности, т.е. после удаления дуги граф должен оставаться связным. Для того, чтобы определить, остался ли граф связным, достаточно запустить поиск в глубину от одной из вершин, связанных с удаленной дугой. Условие окончания алгоритма? Например, пока количество ребер больше либо равно количеству вершин, нужно продолжать, иначе – остановиться. Входные данные: связный граф G и корень r . Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Q. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле prev[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на вершину дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько). Пример 20 м1 23 15 4 1 36 9 25 16 28 17 3 Алгоритм Краскала (Джозеф Краскал, 1956 год) G(V,E) - связный неориентированный граф с заданной функцией стоимости 1. 2. 3. 4. Сортируем ребра графа по возрастанию весов. Полагаем что каждая вершина относится к своей компоненте связности. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем: а)если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву; б)если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения. Если есть еще нерассмотренные ребра и не все компоненты связности объединены в одну, то переходим к шагу 3, иначе выход. Алгоритм Краскала Вход. Неориентированный граф G= (V, Е) с функцией стоимости с, заданной на его ребрах. Выход. Остовное дерево S= (V, Т) наименьшей стоимости для G. Метод: 1. Т ; // остовное дерево (каркас) 2. VS  ; // набор непересекающихся множеств вершин 3. построить очередь с приоритетами Q, содержащую все ребра из Е; 4. Для  vV ВЫПОЛНИТЬ: добавить {v} к VS; Пока |VS|> 1 выполнить: 6. { выбрать в Q ребро (v, w) наименьшей стоимости; 7. удалить (v, w) из Q; 8. если v и w принадлежат различным множествам W1 и W2 из VS то 9. { заменить W1 и W2 на W1W2 в VS; 10. добавить (v, w) к Т; } } Пример 23 4 1 9 3 17 Время работы: Cортировка рёбер - O(|E|×log|E|) Компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E) Получившееся дерево является каркасом минимального веса. Введем массив меток вершин графа Mark. Начальные значения элементов массива равны номерам соответствующих вершин (Mark[i] = i; i  1.. N). Ребро выбирается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. Пример приведен на следующем слайде, изменения Mark показаны в таблице. Алгоритм Краскала с системой непересекающихся множеств Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. в своё множество) с помощью вызова функции MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union - также за O (1). Итого мы получаем: O (M log N + N + M) = O (M log N). Реализация за O (M log N + N2) Отсортируем все рёбра в списках смежности каждой вершины по увеличению веса – O (M log N)). Для каждой вершины заведем указатель, указывающий на первое доступное ребро в её списке смежности. Изначально все указатели указывают на начала списков. На i-ой итерации перебираем все вершины, и выбираем наименьшее по весу ребро среди доступных. Поскольку всё рёбра уже отсортированы по весу, а указатели указывают на первые доступные рёбра, то выбор наименьшего ребра осуществится за O (N). После этого обновляем указатели (сдвигаем вправо), т.к. некоторые из них указывают на ставшие недоступными рёбра (оба конца которых оказались внутри дерева). На поддержание работы указателей требуется O (M) действий. Количество остовных деревьев графа • Количество остовных деревьев(каркасов) графа определяется матрицей Кирхгофа , а именно: алгебраическим дополнением любого элемента матрицы Кирхгофа. Матрица Кирхгофа • Матрица (n*n) • По диагонали – степени вершин • остальные элементы (i,j) при наличии ребра заполняются -1 1 2 3 4 1 1 -1 2 -1 3 -1 -1 3 -1 2 -1 4 -1 -1 2