Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала

Нажмите для полного просмотра!

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №2

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №3

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №4

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №5

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №6

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №7

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №8

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №9

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №10

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №11

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №12

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №13

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №14

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №15

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №16

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №17

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №18

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №19

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №20

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №21

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №22

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №23

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №24

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №25

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №26

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №27

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №28

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №29

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №30

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №31

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №32

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №33

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №34

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №35

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №36

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №37

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №38

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №39

Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала, слайд №40

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 6 Лекция 6 Раздел: Алгоритмы на графах Тема лекции: Минимальное остовное дерево (МОД) Теорема о минимальном ребре Алгоритм Краскала (Жадный алгоритм) Алгоритм ЯПД (Ярника-Прима-Дейкстры) Нижняя граница задачи нахождения МОД

Слайд 2

Описание слайда:

Дерево – связный граф, не содержащий циклов. Дерево – связный граф, не содержащий циклов. Граф связный, если каждая пара различных вершин графа связана маршрутом. Для связного графа G = (V, E) остовным деревом (остовом, каркасом, стягивающим деревом, скелетом) является граф (дерево) T = (V, F), где F E. Ребра дерева – ветви, остальные ребра графа – хорды. В графе много остовов, а именно, число остовов nn-2.

Слайд 3

Описание слайда:

В дереве из n вершин имеется m = n – 1 ребер В дереве из n вершин имеется m = n – 1 ребер Доказательство (по индукции):

Слайд 4

Описание слайда:

Граф G = (V, E). Матрица весов W[v, u]. Граф G = (V, E). Матрица весов W[v, u]. Пусть T = (V, F) – остов графа. Вес остова определяется как

Слайд 5

Описание слайда:

Формулировка 1: Пусть веса всех ребер различны. Тогда оптимальное остовное дерево графа содержит ребро с наименьшим весом. Формулировка 1: Пусть веса всех ребер различны. Тогда оптимальное остовное дерево графа содержит ребро с наименьшим весом. Доказательство (от противного): Пусть {v, u} – кратчайшее из всех ребер – не входит в МОД T. Добавим {v, u} к T. Образуется цикл. Удалим из этого цикла ребро, отличное от {v, u}. Получим T* дерево с весом, меньшим чем вес T, чего не может быть, поскольку T есть МОД (противоречие!).

Слайд 6

Описание слайда:

Формулировка 2: Существует (найдется) оптимальное остовное дерево графа, содержащее ребро с наименьшим весом. Формулировка 2: Существует (найдется) оптимальное остовное дерево графа, содержащее ребро с наименьшим весом. Доказательство (от противного): Пусть {v, u} – кратчайшее из всех ребер – не входит в МОД T. Добавим {v, u} к T. Образуется цикл. Удалим из этого цикла ребро {v’, u’ }, отличное от {v, u}. Получим T* дерево с весом, меньшим или равным, чем вес T. Если W [v, u] = W [v’, u’ ], т.е. W(T*)=W(T), то теорема справедлива. Если W [v, u] < W [v’, u’ ], то W(T*) < W(T), чего не может быть, поскольку T есть МОД (противоречие!).

Слайд 7

Описание слайда:

Пусть G (W) = (V, E, W), а {V1, V2}, есть разбиение V. В G имеется МОД, содержащее кратчайшее из ребер, одна вершина которого принадлежит V1 , а другая V2. Пусть G (W) = (V, E, W), а {V1, V2}, есть разбиение V. В G имеется МОД, содержащее кратчайшее из ребер, одна вершина которого принадлежит V1 , а другая V2. Доказательство (от противного): Как и ранее, пусть кратчайшее ребро {u, v} (uV1 , v V2 ) не входит в МОД …

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

Иллюстрация к теореме Иллюстрация к теореме

Слайд 10

Описание слайда:

Доказательство (от противного): Доказательство (от противного): «Противное»:  ОД (V, F), где F  T и {u, v}  F, которое короче всех остальных ОД, содержащих T и ребро {u, v}. Добавим к F ребро {u, v}. Образуется единственный цикл, не все вершины которого содержаться в V1, например, v  V1.

Слайд 11

Описание слайда:

Алгоритмы построения МОД Бoрувка (O. Bоruvka, 1926) Ярник (V. Jarnik, 1930) Крускал (J.B. Kruskal, Jr., 1956) Прим (R.C. Prim, 1957) Дейкстра (E.W. Dijkstra, 1959) Мы рассмотрим: Алгоритм Крускала (Жадный алгоритм) Алгоритм ЯПД (Ярника-Прима-Дейкстры) Алгоритм Бoрувки (позже)

Слайд 12

Описание слайда:

«Краскал – Крускал» Материал из Википедии «Алгоритм Краскала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Открыт Джозефом Крускалом в 1956 году.» Joseph B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48–50

Слайд 13

Описание слайда:

1. Упорядочить ребра в порядке неубывания весов. 1. Упорядочить ребра в порядке неубывания весов. 2. Поочередно выбирать ребра минимального веса, не образующие циклов с ранее выбранными.

Слайд 14

Описание слайда:

Жадный алгоритм построения МОД (Kruskal, 1956) Vs - множество множеств узлов (множество деревьев остовного леса) begin {алгоритм МОД } Vs := { }; T:= { }; for  v  V do добавить {v} к Vs; Построить очередь Q из всех ребер e  E, упорядочив их по возрастанию весов; while Card(Vs) > 1 do begin Выбрать из Q ребро e = {u,v} с минимальным весом; Удалить e из Q; If u и v принадлежат разным подмножествам W1 и W2 из Vs then begin Заменить W1 и W2 на W1  W2 в Vs; T := T  {e} end end {while} end {алгоритма МОД };

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

Корректность алгоритма (Теорема+индукция). Корректность алгоритма (Теорема+индукция). Сложность алгоритма O(m log m) при соответствующей реализации набора непересекающихся подмножеств Vs. Сортировка O(m log m). Очередь с приоритетами – пирамида  O(k log m). В худшем случае O(m log m). Базовые операции с набором непересекающихся подмножеств: принадлежность заданной вершины к одному из подмножеств; объединить подмножества. (См. следующую лекцию)

Слайд 17

Описание слайда:

Слайд 18

Описание слайда:

Корректность алгоритма: из теоремы, при этом (V1, T1) – дерево, а остальные (Vi, Ti) – изолированные вершины, т.е. Vi = {vj(i)} и Ti = . Корректность алгоритма: из теоремы, при этом (V1, T1) – дерево, а остальные (Vi, Ti) – изолированные вершины, т.е. Vi = {vj(i)} и Ti = . Предполагаемая сложность: пусть G – полный граф, тогда на i-ом шаге при выборе «ближайшей» для всех i вершин текущего дерева необходимо просмотреть все остальные (n – i) изолированные вершины, т.е. всего i (n – i) вариантов. Суммарно по всем шагам получим

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Вход : V - множество вершин графа G=(V,E), а D [1..n,1..n] – матрица весов Вход : V - множество вершин графа G=(V,E), а D [1..n,1..n] – матрица весов Выход: множества Vt - вершин, Et - ветвей МОД, Wt - общий вес МОД Рабочие: Near[1..n] - массив вершин begin {алгоритм МОД } {выбор произвольной вершины v0} Vt := {v0}; Et := { } ; Wt := 0; for  v (V \ Vt) do Near[v] := v0; {инициализация Near[*] } while Card(Vt) < n do begin {ф1:} v:=вершина из V\Vt с минимальным значением D[v,Near[v]]; Vt := Vt +{v}; Et := Et + { {v,Near[v]} } ; Wt := Wt + D [v,Near[v]]; {коррекция массива Near[*] после включения v в T : } for  x  (V \ Vt) do if D [x,Near[x]] > D [x,v] then Near[x] := v; end {while} end {алгоритма МОД };

Слайд 21

${Детализация фрагмента ф1:} {Детализация фрагмента ф1:} min := + ; for  x (V \ Vt) do if D [x,Near[x]] < min then begin min := D [x,Near[x]] ; v...$

Описание слайда:

{Детализация фрагмента ф1:} {Детализация фрагмента ф1:} min := + ; for  x (V \ Vt) do if D [x,Near[x]] < min then begin min := D [x,Near[x]] ; v := x end; {Можно наряду с Near[*] использовать рабочий массив расстояний Dist[x] = D [x,Near[x]] }

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

Худший случай: полный граф m = n(n  1)/2. Худший случай: полный граф m = n(n  1)/2. Алгоритм ЯПД – асимптотически оптимальный. Действительно, симметричная матрица весов содержит n(n  1)/2 элементов. В том числе и вес минимального ребра. Сопоставим задачу МОД с задачей нахождения минимума из n(n  1)/2 элементов, которая решается за n(n  1)/2 шагов и не менее. Пусть для заданной матрицы решили задачу МОД. Из остовного дерева, содержащего (n  1) ребро, за (n  1) шаг извлекаем минимальный элемент матрицы. Если задача МОД решается за менее, чем n(n  1)/2  (n  1) шагов, то и задачу нахождения минимума из n(n  1)/2 элементов можно решить за менее, чем n(n  1)/2 шагов, что неверно. Итак, нижняя граница задачи МОД: O(n2).

Слайд 24

Описание слайда:

Задачи A: Min(n(n1)/2) и B: МОД(n) Задачи A: Min(n(n1)/2) и B: МОД(n)

Слайд 25

Описание слайда:

Пусть наряду с Near[*] используется рабочий массив расстояний Dist[x] = D [x,Near[x]]. Реализуем из данных (x, Near[x], Dist[x]) очередь с приоритетами по ключу Dist[x]. Пусть наряду с Near[*] используется рабочий массив расстояний Dist[x] = D [x,Near[x]]. Реализуем из данных (x, Near[x], Dist[x]) очередь с приоритетами по ключу Dist[x]. Минимальный элемент извлекается (с восстановлением пирамиды) за O (log n) действий. При помещении вершины v в остовное дерево производим коррекцию данных о вершинах, смежных с v и находящихся в очереди. Коррекция каждой такой вершины x (ребра {v, x}) требует O (log n) действий, но при этом такое ребро «возникает» и «исчезает» лишь один раз за все время. Т.о. суммарно требуется O ((n+m) log n) операций, или, что то же O (m log n). Ср. с O (n2) (например, при m =O (n))

Слайд 26

Описание слайда:

Алгоритм Ярника-Прима-Дейкстры построения МОД Примеры выполнения. Варианты: Стандартный - для «плотных» графов (m =O(n)) Для разреженных графов (m = O(n))