Лекция 4. Остовное дерево (каркас). Алгоритмы построения остовного дерева (1162200)
Текст из файла
Методы дискретной оптимизацииОстовное дерево (каркас). Алгоритмыпостроения остовного дерева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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
