1 Отчет за проблема
Нека свързан ненасочена графика [математика] G = (V, E) [/ математика] с тегло ръбове [математика] е (д) [/ математика]. Подграф, който е дърво и преминава през всички върхове [математика] G [/ математика]. Тя се нарича първичен дървото. Spanning дърво се нарича минимално. ако общото тегло на ръбовете му е минимален сред всички обхващащи дървета.
2 варианта на проблема
Ако оригиналният графиката [математика] G [/ математика] изключен, набор от минимум обхваща дърво за всички свързани компоненти се нарича минималната обхваща гората (Минимална Spanning Гора, MSF).
За графика с целочислени тегло е възможно да се използват специални техники, като например корен вид. което води до решаване на проблема за линейно време алгоритъм.
В разпространена проблем може да представлява допълнително изискване, че обменът на данни се извършва само по ръбовете на графиката.
3 работни имоти
Тегло. Solution не зависи от мащаба на ценности, и в какъв ред. По този начин, вместо тегла може да се настрои за прехвърляне - предикат "по-малко или равно" на набор от двойки краища на графиката. Поради тази причина е възможно, без ограничение на общността, да предположим, че цялата тежест на краищата са различни - тя трябва да бъде опростена ръбове за първи път от теглото и след това от броя. В допълнение към първоначалните тегла може да се прилага всяка нарастваща функция и тя не доведе до решение да се промени. Като последица от това, може да се приеме, че всички тегла са в рамките на предварително определен обхват, например, [математика] [0, 1] [/ математика].
Съществуването и уникалността. Минимална поддръжка гора винаги там, и ако всички тегла на ръбове са различни, тогава тя е уникална. Както вече споменахме, че винаги е възможно да се направи най-различни тегла на ръбове. Ако състоянието на различни тегла не е доволен, че е лесно да се изгради един пример, в който ще има по-ниска от минималната, обхващаща дървото.
Крахът на фрагментите. Нека [математика] F [/ математика] - фрагмент от минималната обхваща дървото на графика [математика] G [/ математика]. и броят [математика] G '[/ математика] получава от [математика] G [/ математика] залепване върховете принадлежащи [математика] F [/ математика]. Тогава съюз [математика] F [/ математика] и минималната обхваща дървото на графиката [математика] G '[/ математика] дава минималната обхваща дървото на графиката от [математика] G [/ математика].
Минимална ръб фрагмент. Нека [математика] F [/ математика] - остатък и минимална обхваща дърво [математика] e_F [/ математика] - ребро малко тегло, излъчвана от [математика] F [/ математика] (т.е. точно единия край е на върха на [математика] F [/ математика]). Ако ръба [математика] e_F [/ математика] е уникална, а след това той принадлежи към минималната обхваща дървото. На този имот въз основа алгоритъм и алгоритъм Борувка Prima.
Минимална ръб на графиката. Ако [математика] д ^ * [/ математика] - само един ръб с минимално тегло, той принадлежи към минималната обхваща дървото. На този имот алгоритъм, основан на Kruskal.
Асоциативност на ребрата. Нека MSF [математика] (Е) [/ математика] - минимум обхваща гора от графиката с ръбове [математика] E [/ математика]. след това
[Math] MSF (чаша \ точки E_1 \ чаша E_2 \ \ чаша E_k) = MSF (MSF (E_1) \ чаша MSF (E_2) \ чаша \ точки \ чаша MSF (E_k)). [/ Math]
Броят на ребра, обхващащи гора за графиката с [математически] п [/ математика] върхове и [математика] в [/] математика свързани компоненти е равно на [математика] п-с [/ математика]. Този имот може да се използва за по-бързото приключване на алгоритми, ако броят на свързаните компоненти се знае предварително.
4 Описание на входните и изходните данни
Input. претеглена графика [математика] (V, Е, W) [/ математика] ([математика] п [/ математика] върховете [математика] v_i [/ математика] и [математика] m [/ математика] ребро [математика] e_j = ( о ^ _, о ^ _) [/ математика] с тегло [математика] f_j [/ математика]).
Обемът на входни данни. [Math] O (m + п) [/ математика].
Imprint. списък на ръбове минимум обхваща дърво (за изключен графика - списък на минималната обхваща дървото за всички свързани компоненти).
Обем на изходни данни. [Math] О (п) [/ математика].
5 алгоритми за решаване на проблема
Има три класически подходи за решаване на проблема:
Във всички случаи, в съответствие сложност алгоритъм [математика] O (m \ LN т) [/ математика] използват конвенционални структури от данни. (Легенда:. [Математика] m [/ математика] - брой ръбове, [математически] н [/ математика] - броят на върховете)
Всички други алгоритми обикновено са комбинация на един от трите списъка, или комбинация от тях.
- GHS алгоритъм (Gallager, Humblet, Spira) [6] и последващите версии [7] [8] са разпределени алгоритъм един Борувка на. Този алгоритъм се използва често, за да разпределят автоматично обхваща дърво мрежови комутатори.
- Алгоритъм Gabova и сътр. [9] за използване купчина Фибоначи подреждане на ръбове в алгоритъм Борувка на. Сложността [математика] O (m \ LN \ бета (m, п)) [/ математика].
- Fredmana и Willard алгоритъм [10] за графики с целочислени тегла и линейна цената на сложност [математика] O (т) [/ математика]. Прим алгоритъм се използва във връзка със специално предназначена алгоритъм купчина (AF-куп).
- Алгоритъм Karger и сътр. [11] решава средната О линейно време [математика] (т) [/ математика]. (Наличието на детерминиран алгоритъм с линейна сложност обвързан е отворен въпрос.)
Трябва да се отбележи, че алгоритмите имат асимтотична сложност по-добре от [математика] O (m \ Въ н) [/ математика]. Обикновено, на практика, са по-бавно класическите алгоритми: константа в оценката е толкова голяма, че печалбата от асимптотичния поведението на най-доброто, ще бъде видима само за много големи графики.
6 Resource паралелизъм
- Имоти колапс фрагменти и минимални фрагмент ребра позволяват обработват независимо фрагменти. Въз основа на тези свойства, алгоритъмът има най-голям ресурс Борувка паралелност между трите класически алгоритми.
- Асоциативност на ребрата може да се използва за паралелизация алгоритми и Kruskal Прима, които първоначално са по същество в съответствие.
- Използване на паралелни сортиране алгоритми ръбове на графиката, или паралелно сортиране ръбове на всеки връх или всеки фрагмент.