Растящо дърво - Слайд 26594

Автор: Кононов. За да увеличите слайд, щракнете върху миниатюрата му. За да използвате презентацията в урока, изтеглете безплатно файла Spanning Tree.ppt в zip-архив от 87 KB.

Обширно дърво

Обширни дървета

Минимално обхващащо дърво

Проблем с минимално обхващащо дърво.

Дадено: Графика G, тегло c: E (G)? R. Намерете дървото с най-малко тегло в G или определете какво G? несвързан.

Максимално претеглена гора

Задачата "Максимално претеглена гора".

Дадено: Графика G, тегло c: 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 (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 (D)? ? (° С). Тогава (T * + e) - f е обхващащо дърво. T * оптимално? в (д)? в (е) и (в)? в (е)? в (д). c (f) = c (e) и (T * + e) - f е оптимално обхващащо дърво. Противоречие, тъй като има още един общ ръб с T в (T * + e) - f, отколкото в T * .

Алгоритъм на Крускал

Вход: Свързана графика G, тегло c: E (G)? R. Резултат: Дървото T. с най-малко тегло Ние сортираме ръбовете така, че c (e1)? C (e2)?…? C (em). Задайте T ? (V (G),?). Защото аз ? 1 до m do: Ако T + ei не съдържа цикъл, тогава T ? T + ei.

Алгоритъмът на Крускал намира оптималното решение

Алгоритъм на Крускал (2).

Теорема 4.3 Алгоритъмът на Крускал намира оптималното решение в O (mn).

Алгоритъмът на Крускал може да бъде реализиран

Алгоритъм на Крускал (3).

Теорема 4.4 Алгоритъмът на Крускал може да бъде реализиран в O (m log n).

Свързана графика

Алгоритъмът на Крускал (1956).

Вход: Свързана графика G, тегло c: E (G)? R. Резултат: Дървото Т. с най-малко тегло Ние сортираме ръбовете така, че c (e1)? C (e2)?…? C (em). Задайте T ? (V (G),?). Защото аз ? 1 до m do: Ако T + ei не съдържа цикъл, тогава T ? T + ei.