Лекция 4. Остовное дерево (каркас). Алгоритмы построения остовного дерева (Лекции 2016 года)

Методы дискретной оптимизацииОстовное дерево (каркас). Алгоритмыпостроения остовного дерева1 / 12Терминология, известные фактыОпределение. Остов (каркас) связного графа - дерево, содержащее всевершины графа. Определяется неоднозначно.Определение. Цикломатическое (или циклический ранг) число графа:ν(G) = m − n + c, где n – число вершин, m – число ребер, c –числокомпонент связности графа.Определение. Коциклический ранг (или коранг) графа: ν ∗ (G) = n − cОпределение.

Ребра графа, не входящие в остов, называются хордами.Определение. Цикл, получающийся при добавлении к остову графа егохорды, называется фундаментальным относительно этой хорды.Свойства:1Число ребер неориентированного графа, которые необходимо удалитьдля получения остова, не зависит от последовательности их удаленияи равно цикломатическому числу графа.2Неориентированный граф G является лесом тогда и только тогда,когда ν(G) = 0.3Неориентированный граф G имеет единственный цикл тогда и толькотогда, когда ν(G) = 1.4Остов неориентированного графа имеет ν ∗ (G) ребер.2 / 12СвойстваПусть G1 = (V, E1 ) и G2 = (V, E2 ) – два остовных дерева графа G.Расстоянием между ними называется величина d(G1 , G2 ) = |E1 \E2 |.Множества вершин в деревьях можно поменять ролями, т.к.|E1 | = |E2 | = n − 1.Если d(G1 , G2 ) = 1, то (E1 ∪ E2 )\(E1 ∩ E2 ) = {(e1 , e2 )}, ei ∈ Ei , i = 1, 2,тогда одно дерево получается из другого заменой одной дуги.

Такойпереход называется элементарным переходом от дерева к соседнему.Теорема 1Если для двух деревьев G0 , Gk : d(G0 , Gk ) = k, то второе получается изпервого (и наоборот) за k элементарных переходов.Доказательство. Пусть {e0i ∈ E0 \Ek , eki ∈ Ek \E0 , i = 1, 2, ..., k}. Добавимв множество ребер E 0 ребро ek1 , тогда в G0 возникнет цикл, в которомсуществует ребро e ∈/ Ek , т.к. Gk – дерево. Действительно, если в этомцикле присутствуют ребра исключительно из Ek , то Gk не являетсядеревом. Удалим из цикла это ребро, тогда цикл исчезнет. Таким образомиз G0 будет удалено ребро множества E0 и вместо него помещено ребро изEk , при этом расстояние между деревьями Gk и G10 = (V, (E0 \e) ∪ ek1 )станет равным k − 1. Продолжая процесс далее, получим дерево Gkk = Gk .3 / 12Взвешенные графы.

Задача ШтейнераОпределение. Пусть G = (V, E) – связный простой граф. G называетсявзвешенным графом, если задана функция c(e), называемая весом(длиной) ребра. Обозначение: G = (V, E, c).Для произвольной части H графа G ее весом называется сумма весоввходящих в нее ребер. Обозначение: c(H).Пусть H – остовное дерево (каркас) графа, тогда H = (V, ET ) и задачапоиска остовного дерева минимального веса формулируется какXc(T ) =c(e) → mine∈ETВ теории графов широко известна задача Штейнера: на плоскости заданынесколько точек; нужно соединить их отрезками прямых таким образом,чтобы суммарная длина отрезков была наименьшей.

Главное отличие отзадачи о минимальном остовном дереве при этом заключается в том, чторазрешается добавлять дополнительные точки ветвления с целью ещёсильнее уменьшить сумму длин рёбер. Задача о дереве Штейнераявляется NP-полной.4 / 12Разрезы графаОперация вырезания-вставки ребра в остов является основным элементомпостроения каркаса минимального веса.Определение.

Разбиение (S, V \S) множества вершин называетсяразрезом графа G.Определение. Ребро (u, v) пересекает разрез (S, V \S), или являетсяперешейком данного разреза, если концы этого ребра находятся в разныхчастях разреза.Определение. Ребро (u, v) называется легким ребром для разреза, еслиэто ребро имеет минимальный вес среди всех перешейков данного разреза.Определение.

Множество ребер согласовано с разрезом (S, V \S), еслини одно из ребер A не является перешейком для этого разреза. Если ребраиз A соединяют хотя бы одну вершину из S, то все вершины, инцидентныеребрам из A, лежат в S. Поэтому можно сокращенно обозначать A ⊆ Sфакт согласованности A с разрезом (S, V \S).5 / 12Теорема о минимальном разрезеТеорема 2Пусть (S, V \S) – разрез графа G и множество ребер T в E образуетминимальный каркас G.

При выполнении условий:1. Множество ребер A ⊆ S согласовано с разрезом,2. Легкое для данного разреза ребро (u, ν) ∈/ T.существует минимальный каркас T 0 : (A ∪ (u, ν)) ⊂ T 0 .Доказательство. Считаем, что ребро (u, ν) ∈/ T , в противном случаеT 0 = T . В каркасе T существует ребро (x, y) – перешеек разреза,поскольку T – остов G. При этом по условию A ⊆ S ⇒ (x, y) ∈/ A.0Положим T = (T \(x, y)) ∪ (u, v). Тогда вес данного каркаса непревосходит вес T , поскольку (u, ν) – легкое ребро для разреза (S, V \S),что означает c(u, v) ≤ c(x, y) ⇒ c(T 0 ) ≤ c(T ).

Теорема доказана.6 / 12ЗадачаПусть (S, V \S) – разрез графа G, множество ребер T в E образуетминимальный каркас G, множество ребер A ⊆ S ∩ T и существуетминимальный каркас T 0 : (A ∪ (u, ν)) ⊂ T 0 . Следует ли отсюда, что (u, ν) –легкое ребро для данного разреза? Привести контрпример.Решение. Рассмотрим граф, задаваемый матрицей расстояний:бесконечность означает отсутствие ребра, 0 означает расстояние отвершины до нее самой.01 ∞ 321 104 ∞ ∞ ∞  ∞ 401 ∞ ∞ A= 3 ∞ 10 ∞ ∞  2 ∞ ∞ ∞ 0 ∞ 1 ∞ ∞ ∞ ∞ 0Зададим S = {1, 2}, A = (1, 2).

Минимальный остов состоит из ребер{(1, 2), (3, 4), (1, 4), (1, 5), (1, 6)}. При этом (1, 4) – перешеек длины 3 – частьминимального остова, но минимальный перешеек (1, 6) имеет длину 1,перешеек (1, 5) длины 2.7 / 12ПримерСледствие. Пусть GA = (V, A) – лес для связного неориентированногографа G = (V, E), C = (VC , EC ) – компонента леса, – подмножество ,входящее в минимальный каркас T для G. Если (u, v) – легкое ребро,соединяющее C с другим компонентом леса, то существует минимальныйкаркас T1 , содержащий A ∪ (u, v).

В принятой терминологии ребро (u, v) –безопасное ребро для .8 / 12Алгоритм Краскала (1956)1. Пусть On – граф с n вершинами и пустым количеством ребер. Строимграф T1 = e1 , e1 – ребро минимального веса в E. Это реброопределяется неоднозначно и решение самой задачи не единственно.2. Пусть построен граф Ti , i < n − i. Строим граф Ti+1 = Ti + ei+1 , гдеребро ei+1 является ребром минимального веса среди ребер, невходящих в Ti и не составляющих циклов с ребрами из Ti .

Этоозначает: алгоритм находит безопасное ребро для добавления врастущий лес с помощью поиска ребра (u, v) с минимальным весомсреди всех ребер, соединяющих 2 дерева в лесу.9 / 12Алгоритм КраскалаТеорема 3При i < n − 1 граф Ti+1 = Ti + ei+1 определен корректно, а Tn−1 –остовное дерево минимального веса.Доказательство.1. Граф Ti имеет i < n − 1 ребер и не может быть связным. Значит, вграфе G имеется ребро, обозначим его ei+1 , не составляющее циклов сребрами графа Ti . Следовательно, определение Ti+1 = Ti + ei+1корректно.2. Рассмотрим Tn−1 , по построению это дерево, надо показать егоминимальность.

Если предположить, что это не так, то: среди всехостовных деревьев минимального веса графа G выберем остов T ,который имеет с деревом Tn−1 максимальное число общих ребер.Рассмотрим номер ребра i = min{k|ek ∈ Tn−1 \T }, пусть ei = (a, b).3. Рассмотрим в дереве T цепь, соединяющую вершины a, b. Добавим кэтому пути ребро ei = (a, b), получим цикл, в котором есть реброe ∈ T \Tn−1 .

Такое ребро существует, поскольку в противном случаеTn−1 содержит цикл.10 / 12Алгоритм Краскала4. Заменим в дереве T ребро e на ei , получим новый остовT 0 = T − e + ei . По предположению остов T – остов минимальноговеса, откуда c(T 0 ) = c(T ) + c(ei ) − c(e) ≥ c(T ) ⇒ c(ei ) ≥ c(e).5. С другой стороны, если проследить процесс построения дерева Tn−1 ,то нетрудно заметить, что после выбора ребер e1 , e2 , ..., ei−1 алгоритмКраскала в случае c(ei ) > c(e) выбрал бы не ei = (a, b), а e, посколькутакой выбор не привел бы к появлению цикла и вес остова был быменьше. Отсюда следует, что c(T 0 ) = c(T ), т.е. T 0 – также остовминимального веса.6. При этом |T 0 ∩ Tn−1 | > |T ∩ Tn−1 |, что противоречит выбору T .Полученное противоречие доказывает теорему.11 / 12Алгоритм Прима-ДейкстрыДанный алгоритм отличается от предыдущего только тем, что не простоациклический граф, но дерево строится на каждом шаге.

Укажем шагиалгоритма.1. Выбирается ребро e1 = (a, b) минимального веса и строится деревоT1 : V1 = {a, b}, E1 = {e1 }.2. Если дерево Ti уже построено и i < n − 1, то среди ребер,соединяющих вершины этого дерева с вершинами графа G, невходящими в Ti , выбираем ребро ei+1 минимального веса. ПолагаемTi+1 : Vi+1 = {Vi ∪ v : ei+1 = (v, c), v ∈/ Vi , c ∈ Vi }, Ei+1 = {Ei ∪ {ei+1 }}Доказательство корректности данного алгоритма аналогичнопредыдущему случаю. Если число ребер графа G равно n, то числоопераций пропорционально(n − 1) + (n − 2) + ...

+ 2 + 1 =n(n − 1).2Таким образом, алгоритм Прима-Дейкстры применим к связномувзвешенному графу и имеет сложность O(n2 ).12 / 12.