Основне дерево - Презентація 26594

Автор:Kononov. Щоб збільшити слайд, натисніть його ескіз. Щоб використати презентацію на уроці, скачайте файл «Остовне дерево.ppt» безкоштовно у zip-архіві розміром 87 КБ.

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

Основні дерева

Мінімальне остовне дерево

Завдання «Мінімальне кістякове дерево».

Дано: Граф G, ваги з: E(G) ? R. Знайти остовне дерево в G найменшої ваги або визначити, що G ? нескладний.

Максимальний зважений ліс

Завдання «Максимальний зважений ліс».

Дано: Граф G, ваги з: E(G) ? R. Знайти ліс у G найбільшої ваги.

Еквівалентні завдання

Будемо говорити, що задача P лінійно зводиться до задачі Q, якщо існують функції f і g, що обчислюються за лінійний час, такі що f перетворює приватну задачу x з P на приватну задачу y з Q, і g перетворює рішення f (x) на рішення x. Якщо P лінійно зводиться до Q і Q лінійно зводиться до P то обидві завдання називаються еквівалентними.

Еквівалентність

Пропозиція 4.1 Завдання «Мінімальне дерев'яне дерево» і завдання «Максимальний зважений ліс» еквівалентні.

Доведення

(G, c)? вихідний приклад завдання «Максимальний зважений ліс». Видалимо всі ребра негативної ваги. Покладемо c'(e) = – c(e). Додамо мінімальне безліч ребер F, щоб отриманий граф G' став зв'язковим. (Ваги можна взяти будь-які.) Розв'яжемо задачу «Мінімальне кістякове дерево» на прикладі (G',c'). Видаливши з розв'язання безліч ребер F, отримаємо рішення вихідної задачі. (G, c)? вихідний приклад завдання «Мінімальне кістякове дерево». Покладемо c'(e) = K - c(e), де K = 1 + max e? E(G) c(e). Розв'язання задачі «Максимальний зважений ліс» на прикладі (G',c') дає розв'язання задачі «Мінімальне кістякове дерево» на вихідному прикладі.

Умови оптимальності

Теорема 4.2 Нехай (G, c)? приклад задачі «Мінімальне кістякове дерево», і нехай T ? остовне дерево в G. Тоді такі умови еквівалентні: T? оптимум. Для будь-якого e =? E(G)\ E(T), всі ребра з x-y-шляху в T не дорожчі ніж e. Для будь-якого e? E(T), e? ребро найменшої вартості з? (V (C)), де C? зв'язкова компонента на T-e.

Оптимальне вирішення

(с) Нехай T таке, що для будь-якого e? E(T), e? ребро найменшої вартості з? (V (C)), де C? зв'язкова компонента на T-e. Нехай T * оптимальне рішення, що E(T) ? E(T*) є максимально можливим. Покажемо, що T = T*. Нехай e =? E(T)\ E(T*). Нехай C? зв'язкова компонента на T-e. T* + e містить цикл D. Так як e? E(D) ? ?(C), то існує f? e, f? E(D) ? ? (C). Тоді (T* + e) – f є кістяком. T * оптимум? c(e)? c(f) і (с)? c(f)? c(e). c(f) = c(e) і (T* + e) – f є оптимальним кістяком. Протиріччя, оскільки (T* + e) – f більше одне загальне ребро з T, ніж T* .

Алгоритм Фарбала

Input: Зв'язковий граф G, ваги з: E(G) ? R. Output: Основне дерево T найменшої ваги. Сортуємо ребра так, що c (e1)? c (e2)? ...? c (em). Set T ?? (V(G), ?). For i ?? 1 to m do: If T+ei не містить циклу then T ?? T+ei.

Алгоритм Краскала знаходить оптимальне рішення

Алгоритм Фарбала (2).

Теорема 4.3 Алгоритм Фарбала знаходить оптимальне рішення за O(mn).

Алгоритм Фарбала можна реалізувати

Алгоритм Фарбала (3).

Теорема 4.4 Алгоритм Фарбала можна реалізувати за O(m log n).

Зв'язковий граф

Алгоритм Фарбала (1956).

Як покращити крок

Основна мета кроку 3 перевірити, чи не приведе додавання ребра ei = до утворення циклу. Це еквівалентно перевірки чи лежать v і w в одному зв'язному компоненті. По ходу алгоритму будуватимемо додатковий орлес B з V(B) = V(G), такий, що зв'язкові компоненти B індуковані на тих же вершинах, що і зв'язкові компоненти T.

Спочатку, B = (V(G), ?) і h(v) = 0, для всіх v ?V(G), де h(v) довжина максимального шляху з v до B. 3.1 Для ребра ei = знаходимо коріння rv і rw ордери в B, що містять v і w. 3.2 Якщо rv = rw, то переходимо до наступного ребра і йдемо на 3.1. 3.3 Якщо rv? rw то додаємо ei до T. 3.4. Якщо h(rv)? h(rw) то додаємо дугу (rv, rw) до B, інакше додаємо дугу (rw, rv) до B.

Час роботи кроку

Час роботи пропорційно довжині rv-v-шляху B. Покажемо, що будь-яке ордерево B з коренем r має принаймні 2h(r) вершин. Коли B = (V(G), ?) твердження очевидне. Нехай алгоритм додає дугу (x, y) в B. Отримуємо нове ордерево з коренем x і числом вершин ? 2h(x) + 2h(y). Якщо h(x) > h(y), значення h(x) не змінюється і твердження справедливе. Якщо h(x) = h(y), то значення h(x) збільшується на 1. Число вершин у новому ордереві? 2h(x) + 2h(y) = 2h(x)+1. h(r)? log n, і трудомісткість кроку 3? mlog n.

Алгоритм Пріма

Input: Зв'язковий граф G, ваги з: E(G) ? R. Output: Основне дерево T мінімальної ваги. Вибрати v? V(G). T ?? (?). While V(T) ?V(G) do: Вибрати ребро e? ?G(V(T)) мінімальної вартості. T ?? T+e.

Алгоритм Пріма знаходить рішення

Алгоритм Пріма (2).

Теорема 4.5 Алгоритм Пріма знаходить рішення за O(n2) елементарних операцій.

Як реалізувати крок

While V(T) ?V(G) do: Вибрати ребро e? ?G(V(T)) мінімальної вартості. T ?? T+e. Для кожної вершини v?V(T) будемо зберігати найдешевше ребро (кандидата) з v до V(T). Тоді вибір ребра мінімальної вартості та заміна кандидатів може бути виконана за O(n) елементарних операцій.

Максимальний виважений орієнтований ліс

Завдання «Максимальний виважений орієнтований ліс».

Дано: Орграф G, ваги з: E(G) ? R. Знайти орієнтований ліс у G найбільшої ваги.

Мінімальне остовне орієнтоване дерево

Завдання «Мінімальне кістякове орієнтоване дерево».

Дано: Орграф G, ваги з: E(G) ? R. Знайти скелетне орієнтоване дерево в G найменшої ваги або визначити, що воно не існує.

Кореневе орієнтоване дерево

Завдання «Мінімальне кістякове кореневе орієнтоване дерево».

Дано: Орграф G, вершина r? V (G), ваги c: E (G)? R. Знайти остовне орієнтоване дерево з коренем r G найменшої ваги або визначити, що воно не існує.

Еквівалентність трьох завдань

Пропозиція 4.6. Завдання «Максимальний зважений орієнтований ліс», «Мінімальне кістякове орієнтоване дерево» і «Мінімальне кістякове кореневе орієнтоване дерево» еквівалентні. Вправа 4.1 Довести пропозицію 4.6.

Орієнтований ліс

Орграф називається орієнтованим лісом, якщо відповідний йому граф є лісом і кожна вершина v має трохи більше вхідного ребра.

Орієнтований ліс та цикли

Пропозиція 4.7. Нехай B? орграф з усім x ? V(B). Тоді B має цикл і тоді, коли відповідний йому граф має цикл. Лемма 4.8. (Karp [1972]) Нехай B0? підграф G максимальної ваги для всіх v ? V(B0). Тоді існує оптимальний орієнтований ліс B G такий, що для кожного циклу C B0, E(C)\ E(B) = 1.

Доказ леми

Нехай B – оптимальний орлес у G має макси-мально багато ребер з B0.

Покажемо, що B є bi-bi-1-шлях для всіх i.

що у B є bi-bi-1-шлях для всіх i.

Основна ідея

Знайти B0 орієнтований підграф G максимальної ваги, в якому кожну вершину входить не більше однієї дуги. Стягнути кожен цикл B0 у вершину. Перерозподілити ваги в новому графі G1, так щоб будь-який оптимальний орлес G1 відповідав оптимальному орлесу G.

Алгоритм Едмондса

побудови орієнтованого лісу максимальної ваги (1967).

Input: орграф G, ваги з: E(G) ? R+. Output: орлес максимальної ваги B of G. Set i ??0, G0 ?? G, і c0 ?? c. Нехай Bi підграф G максимальної ваги для всіх v? Bi. If Bi не містить циклів then B ?? Bi та go to (5). Побудуємо (Gi+1, ci+1) (Gi, ci): do для кожного циклу C з Bi . Стягнемо C до однієї вершини vC Gi+1. Для кожного ребра e = (z, y) ?E(Gi) з z?V(C), y?V(C) do: Set ci+1 (e?) ?? ci(e) – ci(?(e,C)) + ci(eC) та ?(e?) ??e, де e? ?? (z, vC), ?(e,C)=(x,y) ?E(C), і eC найдешевше ребро C. If i = 0 then stop. Для кожного циклу C з Bi-1 do: If є ребро e? ? (z, vC)? E(B) then E(B) ?? (E(B)\) ??(e?) ?(E(C)\) else E(B) ?? E(B) ?(E(C)\). Set V(B) ?? V(Gi-1), i ?? i–1 та go to (5).