Как найти все остовные деревья графа

Построение всех остовных деревьев графа

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

Число различных остовов полного связного неориентированного помеченного графа с n вершинами равно . Число различных остовов неориентированного графа без петель с n вершинами равно значению определителя , где B₀ — матрица инциденций с одной удаленной строкой (т.е. с n-1 независимыми строками), — транспонированная матрица к B₀.

Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева и графа . «Расстояние» между двумя деревьями обозначается через и определяется как число дуг из , которых нет в (или, что эквивалентно, как число дуг из , которых нет в , поскольку оба дерева и имеют дуг). Если , т.е. если

,

где и , то дерево можно получить из дерева удалив из дугу и добавив дугу . Такое преобразование дерева в дерево называется элементарным преобразованием дерева. На рис. 3 приведено дерево T₄, которое получено из дерева T₀ c помощью 4 элементарных преобразований: убрать (x₁, x₈) и добавить (x₅, x₈); убрать (x₅, x₆) и добавить (x₆, x₇); убрать (x₂, x₃) и добавить (x₂, x₄); убрать (x₃, x₅) и добавить (x₄, x₅).

Рис.3. Остовы T₀ и T₄.

Существует теорема, согласно которой дерево T_k может быть получено из дерева T₀ с помощью серий из k элементарных преобразований при =k.

Процедура порождения всех деревьев неориентированного графа

Первый шаг состоит в приписывании номеров ребрам графа G (ребра нумеруются от 1 до m, где m — число ребер в графе G). На каждом этапе (т. е. при каждом ветвлении в дереве решений) выбирается ребро, которое вместе с остальными, выбранными уже на предыдущих этапах, будет образовывать часть конструируемого дерева. Таким образом, прежде чем отобрать такое ребро, выясняют, действительно ли добавление его к частично сформированному дереву (которое на этом шаге является набором поддеревьев) не приводит к появлению цикла. Если цикл появляется, то данное ребро отбрасывается и проверке подвергается следующее ребро, с большим номером. Если цикла нет, то ребро добавляется к другим, уже отобранным, и процесс продолжается до тех пор, пока не будет построено остовное дерево. Ребра перебираются в порядке возрастания их номеров; это приводит к исчерпывающему и без повторений решению задачи.

Для облегчения манипуляций с поддеревьями в каждом поддереве выделяют произвольным образом корень (некоторую вершину поддерева) и затем рассматриваю поддерево уже как древовидность. Для организации проверки на возможность образования (при добавлении ребра) каждую вершину x_j помечают парой (r_j, p_j). Первая пометка r_j указывает «корень» поддерева, содержащего вершину x_j. Первоначально r_j = x_j для всех вершин x_j. На некотором шаге два поддерева T₁, и T₂ сращиваются посредством добавления ребра a_l=(x_a, x_b) с вершиной x_a из T₁ и вершиной x_b из T₂. Если на этом шаге r₁ — «корневая» пометка вершин в T₁, а r₂ — «корневая» пометка вершин в T₂ и для примера r₁ < r₂, то все вершины в T₂, должны «сменить» свои корневые пометки на r₁, и два поддерева T₁ и T₂ «сольются» в единственное новое дерево T₁.

Вторая пометка p_j, приписанная вершине x_j, указывает вершину, предшествующую вершине x_j, т.е. если =(x_k, x_j) — дуга рассматриваемого поддерева, то p_j = x_k. Для корневой вершины дерева такая пометка полагается равной нулю.

А. Замена корня дерева

Если корнем дерева T является вершина r и нужно в качестве корня выбрать новую вершину x_s, то такую «замену» r на x_s можно осуществить простым обращением ориентации дуг, принадлежащих цепи, идущей от r к x_s, не меняя при этом ориентацию других дуг. Соответствующие изменения пометок будут таковы.

Изменение пометок «предшествования»

Пусть x_j = x_s и z = p_j.

Положить x_i = z, a z = p_i.

Шаг обновления: p_i = x_j.

Если x_i = r, то перейти к шагу 5. в противном случае положить x_j = x_i и перейти к шагу 2.

Положить p_s = 0, стоп.

Изменение корневых пометок

У всех вершин, имеющих корневую пометку r, заменить ее на пометку x_s.

Б. Сращивание двух поддеревьев

Если осуществлено сращивание двух поддеревьев T₁ и T₂ (путем добавления ребра (x_a, x_b)), то в пометки необходимо внести следующие изменения:

(1) У вершин с корневой пометкой r₂ заменить эту пометку на r₁.

(2) Заменить в дереве T₂ корень r₂ на x_b (пункт А), после чего изменить пометку «предшествования» у вершины x_b с p_b = 0 на p_b = x_a.

B. Расщепление дерева на две части

Поскольку метод порождения деревьев, рассматриваемый ниже, является поиском, использующим дерево решений, то возникает необходимость удаления некоторых ребер (на шагах возвращения), чтобы испытать затем другие ребра. В такой ситуации удаление ребра приводит к расщеплению некоторого дерева на две части, например на T₁ и T₂, и в пометки одного из этих поддеревьев должны быть внесены изменения. Пусть удаляется ребро (x_a, x_b), где x_aÎT₁ и x_bÎT₂. Тогда при p_b = x_a (т. е. если ребро (x_a, x_b) в первоначальном дереве ориентировано от x_a к x_b) пометки в дереве T₁, можно оставить прежними, а пометки в дереве T₂ должны быть изменены. Если же p_a = x_b (т. е. ребро (x_a, x_b) ориентировано от x_b к x_a), то можно не менять пометки в дереве T₂, но нужно изменить пометки в T₁. Предполагая, что пометки меняются в дереве T₂, покажем, как надо «восстанавливать» корень в этом дереве.

Положить S = <x_b> и p_b = 0 (x_b будет корнем дерева T₂).

Найти все вершины x_j с p_jÎS и изменить их корневые пометки на r_j = x_b. Если таких вершин нет, остановиться.

Шаг обновления: S = S È <x_j | p_jÎS>; вернуться к шагу 2.

Следует отметить, что ни у одной вершины, кроме нового корня x_b, пометки предшествования менять не нужно. Заметим также, что число описанных выше шагов 2 и 3, которое необходимо для восстановления корня, равно длине самой длинной цепи в T₂ исходящей из вершины x_b.

Описание алгоритма. Возьмем произвольную вершину x * графа G. Пусть ее степень равна d * . Перенумеруем ребра, инцидентные этой вершине: a₁, a₂, …, a_d*. Затем перенумеруем остальные ребра графа G: a_d*+1, a_d*+2, …, a_m. При порождении деревьев ребра будут перебираться в соответствии с введенной нумерацией.

Шаг 1. Приписать вершинам пометки: (r_i, p_i), где r_i=x_i и p_i=0, «x_iÎX. Положить k=1.

Шаг 2. Выбрать для исследования некоторое ребро. Например, a_k=(x_i, x_j). Если k≤m, где m — число ребер графа, то перейти к 2 (1). При k=m+1, т. е. если «неисследованных» ребер нет, перейти к шагу 5.

(1) Если r_i=r_j, то это означает, что вершины x_i и x_j принадлежат одному и тому же поддереву и добавление ребра a_k приведет к появлению цикла. Отбросить ребро a_k, т. е. положить k=k-1 и вернуться к шагу 2.

(2) Если r_i≠r_j то ребро a_k можно добавить к ребрам построенных поддеревьев. Перейти к шагу 3.

Шаг 3. Срастить два поддерева, у которых вершины имеют корневые пометки r_i и r_j, применив для этого метод, описанный выше в пункте Б.

Шаг 4. Отобрав n-1 ребер, мы получаем некоторое дерево. Заполнить это дерево и перейти к шагу 5. Если отобрано меньше, чем n-1 ребер, то положить k=k+1 и вернуться к шагу 2.

Шаг 5. (Возвращение.) Удалить ребро, добавленное последним. Предположим, что таким ребром является a_l. Если a_l — единственное оставшееся для добавления ребро, l=d * то остановиться. Все остовные деревья, таким образом построены, т. к. при любом дальнейшем ветвлении дерева решений вершина x * останется изолированной.

В противном случае надо обновить пометки, действуя так, как указано в пункте B, положить k=l-1 и возвратиться к шагу 2.

Построим все остовные деревья графа, изображенного на рис.4. Выберем в качестве x * вершину x₁.

Рис.4. Граф G.

На рис.5 изображено соответствующее дерево решений, которое порождено в процессе работы алгоритма. Если взять ребра, указанные в кружочках какой-либо цепи, выходящей из верхнего узла этого дерева и оканчивающейся в самом нижнем узле, то из них можно построить некоторый остов данного графа. Эти остовы перенумерованы числами от 1 до 21 и приведены на рис.6.

Рис.5. Полное дерево поиска.

Рис.6. Все остовы графа G.

Кратчайший остов графа

Рассмотрим взвешенный связный неориентированный граф G=(X, A); вес ребра (x_i, x_j) обозначим c_ij. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая. Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической сети, которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок). Другой пример: вершины представляют города, которые нужно связать сетью трубопроводов; тогда наименьшая общая длина труб, которая должна быть использована для строительства (при условии, что вне городов «разветвления» трубопроводов не допускаются), определяется кратчайшим остовом соответствующего графа.

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

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

, i≠j. (1)

Зададим следующую операцию: Для поддерева T_s найти такое поддерево T_j*, чтобы . Пусть будет тем ребром, вес которого соответствует величине в выражении (1). Тогда ребро принадлежит кратчайшему остову и может быть добавлено к другим ребрам частично сформированного кратчайшего остова.

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

Как найти все остовные деревья графа

В некоторых ситуациях возникает необходимость в построении полного списка остовных деревьев графа Например, в том случае, когда надо отобрать «наилучшее» дерево, а критерий, позволяющий осуществить такой отбор, является очень сложным (или даже частично субъективным), так что непосредственное решение задачи оптимизации (не использующее перечисление всех остовных деревьев) оказывается невыполнимым. В других ситуациях, например при нахождении передаточной функции системы [42,6] или при вычислении определителей некоторых матриц в макроэкономической теории [2], с помощью порождения всех остовов соответствующих графов можно добиться упрощения вычислительных процедур.

Число различных остовов полного связного неориентированного помеченного графа с вершинами было найдено впервые Кэли [4]. Оно равно . У Муна [45] приводится список из более чем 25 работ, содержащих разнообразные доказательства этой формулы. (См. также задачу 6.) Формулы для числа остовов в более общих графах можно найти у Риордана [49]. Хотя эти формулы, как правило, очень сложные и их вывод для наших целей не нужен, но стоит, пожалуй, привести следующий результат.

Теорема 1. Пусть -вершинный граф без петель и его матрица инциденций с одной удаленной строкой (т. е. с независимыми строками). Пусть транспонированная матрица к Тогда определитель равен числу различных остовных деревьев графа

Доказательство этой теоремы можно найти в [53] и в [1] (см. также задачу 5).

2.1. Элементарные преобразования деревьев

Рассмотрим два (ориентированных или неориентированных) остовных дерева и графа «Расстояние» между двумя деревьями обозначается через и определяется как число дуг из которых нет в (или, что эквивалентно, как число дуг из которых нет в поскольку оба дерева имеют дуг). Если т. е. если

где то дерево можно получить из дерева удалив из дугу и добавив дугу Такое преобразование дерева в дерево называется элементарным преобразованием дерева.

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

Доказательство. Пусть дуг из которых нет в Тк, и к дуг из Тк, которых нет в Если в дерево добавить дугу то в получившемся графе, согласно определению дерева, найдется цикл. (На рис. жирными линиями показано неориентированное дерево а пунктирной линией — дуга дерева приведенного на рис. 7.5(д).) В полученном цикле содержится по крайней мере одна дуга, не принадлежащая дереву Тк. Следовательно, ее можно удалить, разорвав тем самым цикл, и это даст новое дерево Поскольку в число дуг, общих с дугами из Тк, на единицу больше (чем в ), то Применяя элементарные преобразования дальше, получим последовательность деревьев , в которой для каждого . На рис. 7.5(б) — (д) показано, как с помощью 4 элементарных преобразований из дерева получается дерево

Графы — определения, деревья, хранение и поиск в глубину

Графом \(G\) называется пара множеств \(G = (V, E\) , где \(V(G)\) — непустое конечное множество элементов, называемых вершинами графа, а \(E\) — множество пар элементов из \(V\) (необязательно различных), называемых ребрами графа. \(E = \<(u , v)\ | u, v \in V\>\) — множество ребер графа \(G\) , состоящее из пар вершин \((u, v)\) . Ребро \((u, v)\) соединяет вершины \(u\) и \(v\) .

Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).

Примеры графа

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах \(N\) — количество вершин, а \(M\) — ребер. Количество ребер, исходящее из вершины называют степенью вершины \(d(v)\) . Для вершины \(a\) ребро \((a, b)\) называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

Теоретическое задание

Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.

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

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

Теоретическое задание

Сколько может быть рёбер в простом графе в \(N\) вершинами?

Теоретическое задание

Найдите цикл размера 4 и петлю в этом непростом графе.

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Хранение графа в программе

Чаще всего в задачах по программмированию вершины графа — это числа от \(0\) до \(N-1\) , чтобы удобно было обращаться к ним как к индексам в разных массивах.

Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.

Для графа существуют несколько основных способов хранения:

1. Матрица смежности. Давайте хранить двумерную матрицу \(A_\) , где для данного графа G верно, что если \(A_\) = 1, то две вершины \(i\) и \(j\) являются смежными, иначе вершины \(i\) и \(j\) смежными не являются.

Мы храним для каждой из \(N\) вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним \(N^2\) ячеек, а следовательно асимптотика по памяти — \(O(N^2)\) .

1. Список смежности. Давайте для каждой из \(N\) вершин хранить все смежные с ней, для этого нам потребуется любая динамическая структура, например vector в с++.

Здесь асимптотика по памяти и времени считывания — \(O(N + M)\) , так как мы храним для каждой вершины, куда есть ребра, то есть \(2 M\) ребер, а также суммарно \(N\) векторов.

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

1. Список рёбер. Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.

Заметьте, что все эти способы обощаются на случай ориентированных графов — при этом матрица смежности становится неориетированной: если есть ребро из вершины \(i\) в вершину \(j\) , то сделаем \(A_ = 1\) , а \(A_ = 0\) , если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра \((u, v)\) будем добавлять только \(v\) в список соседей \(u\) , но не наоборот.

Практическое задание

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

Деревья

Дерево — это связный неориентированный граф без циклов.

Пример дерева

1. У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.

Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины — ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) — ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.

1. У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.

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

1. У дерева с \(N\) вершинами всегда ровно \(N-1\) ребро.

Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока \(N > 1\) . В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.

1. Между любыми двумя вершинами в дереве есть ровно один простой путь.

Действительно, если их два, то в графе есть цикл. Быть ноль их не может — ведь граф связный.

1. Дерево — это минимальный по числу рёбер связный граф на \(N\) вершинах.

Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.

DFS (Алгоритм обхода графа в глубину)

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

При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.

Красивая визуализация: https://visualgo.net/en/dfsbfs

Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку \(O(N + M)\) .

Практическое задание

Задачи 3-5 в контесте.

Поиск компонент связности графа

Путем в графе называется последовательность вершин \(v_i \in ��\) , \(i = 1. k\) таких, что две последовательные вершины в пути соединены ребром, \(k\) — длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.

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

Практическое задание

На данную тему задачи 6 и 10 в контесте.

Остовное дерево

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

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

Практическое задание

7 задача в контесте на выделение остовного дерева в графе.

Раскраска графа в два цвета

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

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

Практическое задание

8 задача в контесте на раскраску графа в два цвета

Поиск циклов в графе

Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.

В обычном dfs мы используем два цвета (1 — вершина посещена, 0 — не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:

• 0 — вершина не просмотрена
• 1 — мы входили DFS-ом в эту вершину, но еще не вышли (а значит из нее есть путь до текущей),
• 2 — мы входили DFS-ом в эту вершину

Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.

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