Разапињуће стабло минималног степена

Минимално разапињуће стабло је разапињуће стабло неког повезаног, тежинског и неусмереног графа које садржи све чворове тог графа, а збир тежина његових грана је минималан.

Планаран граф на коме је подебљаном линијом означено његово минимално разапињуће стабло

Један граф може имати више оваквих стабала, зависно од своје конфигурације. Уколико свакој грани доделимо одређену тежину онда је збир тежина грана у неком разапињућем стаблу у ствари тежина тог стабла. Минимално разапињуће стабло или минимално тежинско разапињуће стабло је разапињуће стабло чија је тежина мања или једнака у односу на остала разапињућа стабла неког графа. Уопштеније, сваки неусмерен граф (не нужно повезан) има минималну разапињућу шуму, која је унија минималних разапињућих стабала.

Постоји доста случајева када се користе минимална разапињућа стабла. Типичан проблем који се везује за ово стабло је достављање услуга телекомуникационе компаније на више локација на што исплатљивији начин. Ако се претпостави да се каблови закопавају дуж одређених путева (нпр. дуж коловоза) онда бисмо могли направити граф који представља које локације су повезане тим путевима. Неки од путева су дужи, или захтевају да каблови буду дубље закопани, због чега су и скупљи; ти путеви су представљени гранама веће тежине. Тежина гране одговара трошковима постављања каблова - није неопходно да се дужине грана придржавају правила геометрије као што је неједнакост троуглова. Разапињуће стабло тог графа је подскуп оних путева који не образују циклус, а ипак повезују све локације; могуће је да постоји неколико разапињућих стабала. Минимално разапињуће стабло је оно разапињуће стабло које има најмању тежину, односно чији је трошак постављања каблова најмањи.

Особине

Могућност многобројности

Ова слика показује да граф може имати више од једног минималног разапињућег стабла. На слици, два стабла испод графа су у ствари две могућности минималног разапињућег стабла за дати граф.

Могуће је да у неком графу постоји неколико минималних разапињућих стабала исте тежине са минималним бројем грана; посебно, ако су све гране задатог графа исте тежине, онда је свако разапињуће стабло тог графа минимално.

Ако граф има ${\displaystyle n}$ чворова, тада свако разапињуће стабло има ${\displaystyle n-1}$ грана.

Јединственост

Уколико свака грана има различиту тежину, тада граф садржи само једно јединствено минимално разапињуће стабло. Ово је најчешћи случај у реалним ситуацијама, као што је горенаведени пример телекомуникационе компаније, где је мало вероватно да два пута сносе потпуно исте трошкове. Општије гледано ово важи и за разапињуће шуме.

Ако тежине грана нису јединствене, онда је само мултискуп тежина у минималном разапињућем стаблу јединствен, то је заједничко за сва минимална разапињућа стабла.^[1]

Доказ:

1. Претпоставимо супротно, да постоје два различита минимална разапињућа стабла ${\displaystyle A}$ и ${\displaystyle B}$.
2. Нека је ${\displaystyle e_{1}}$ грана најмање тежине која се налази само у једном минималном разапињућем стаблу. Без губитка општости, претпоставимо да се ${\displaystyle e_{1}}$ налази у ${\displaystyle A}$ и не налази у ${\displaystyle B}$.
3. Како ${\displaystyle B}$ јесте минимално разапињуће стабло ${\displaystyle {e_{1}}\cup B}$ мора садржати циклус ${\displaystyle C}$.
4. Тада ${\displaystyle C}$ садржи неку грану ${\displaystyle e_{2}}$ чија је тежина већа од тежине гране ${\displaystyle e_{1}}$, с обзиром да све гране које су мање од {${\displaystyle e_{1}}$} и налазе се у ${\displaystyle B}$ садрже се и у ${\displaystyle A}$, и циклус ${\displaystyle C}$ мора имати барем једну грану која није у ${\displaystyle A}$ јер у супротном ${\displaystyle A}$ би садржало циклус што је контрадикција са тим да је оно и минимално разапињуће стабло.
5. Заменом ${\displaystyle e_{2}}$ са ${\displaystyle e_{1}}$ у ${\displaystyle B}$ добија се разапињуће стабло мање тежине.
6. Ово је у супротности са претпоставком да је ${\displaystyle B}$ минимално разапињуће стабло.

Подграф минималне тежине

Ако су све тежине позитивне тада је минимално разапињуће стабло у ствари подграф минималне тежине који садржи све чворове, како подграфови садрже циклусе углавном су и веће тежине.

Особина циклуса

За сваки циклус ${\displaystyle C}$ у неком графу важи да ако је грана ${\displaystyle e}$ која се налази у циклусу ${\displaystyle C}$ веће тежине од свих других грана тог циклуса, онда та грана не може припадати минималном разапињућем стаблу.

Доказ: Претпоставимо супротно, тј. да ${\displaystyle e}$ припада минималном разапињућем стаблу ${\displaystyle T_{1}}$. Тада брисањем гране ${\displaystyle e}$ ${\displaystyle T_{1}}$ се дели на два подстабла код којих се један крај гране ${\displaystyle e}$ налази у једном, а други крај у другом подстаблу. Остатак циклуса ${\displaystyle C}$ поново повезује подстабла, пошто постоји грана ${\displaystyle f}$ из ${\displaystyle C}$ која има крајеве у различитим подстаблима, тј. она поново повезује подстабла у стабло ${\displaystyle T_{2}}$ тежине мање него ${\displaystyle T_{1}}$, јер је тежина ${\displaystyle f}$ мања од тежине ${\displaystyle e}$.

Особина одсецања

На слици се види особина одсецања за минимално разапињуће стабло.

За сваки одсечак ${\displaystyle C}$ из неког графа важи да ако је тежина гране ${\displaystyle e}$ (која се налази у том одсечку ${\displaystyle C}$) стриктно мања од тежина свих грана из тог одсечка, онда та грана ${\displaystyle e}$ припада свим минимално разапињућим стаблима тог графа.

Грана минималне тежине

Ако је грана ${\displaystyle e}$ јединствена грана минималне тежине неког графа, онда се она налази у свим минималним разапињућим стаблима тог графа.

Доказ: Претпоставимо да се ${\displaystyle e}$ не налази у минималном разапињућем стаблу, тада уклањањем било које гране (веће тежине) из циклуса ${\displaystyle C}$ који је формиран након што је грана ${\displaystyle e}$ додана у минимално разапињуће стабло се формира ново разапињуће стабло мање тежине.

Контракција

Ако је ${\displaystyle T}$ стабло састављено од грана из минималног разапињућег стабла, онда можемо контраховати ${\displaystyle T}$ у један чвор док одржавамо инваријанту да минимално разапињуће стабло контрахованог графа заједно са ${\displaystyle T}$ даје минимално разапињуће стабло графа пре контракције.

Алгоритми

У свим алгоритмима испод ${\displaystyle m}$ представља број грана у графу док ${\displaystyle n}$ представља број чворова.

Класичани алгоритми

Први алгоритам за тражење минималног разапињућег стабла је развио Чешки научник Отакар Борувка 1926. године (видети Борувкин алгоритам). Његова сврха је била изградња електричне мреже за Моравску. Алгоритам се извршава у неколико фаза. У свакој фази, названој Борувкин корак, идентификује се шума ${\displaystyle F}$ која се састоји од грана инцидентних са сваким чвором у графу ${\displaystyle G}$, затим формира граф ${\displaystyle G1=G\setminus F}$ као улаз у следећем кораку. Овде ${\displaystyle G\setminus F}$ означава граф добијен од ${\displaystyle G}$ одсецањем грана у ${\displaystyle F}$ (Особина одсецања). Сваки Борувкин корак је линеарне сложености. Пошто је број чворова редукован за барем половину у сваком кораку, Борувкин алгоритам је сложености ${\displaystyle O(m\log n)}$.

Други алгоритам је Примов алгоритам, који је 1930. године изумео Војтех Јарник, а касније независно од њега информатичар Роберт Прим 1957, и поново Едсгер Дајкстра 1959. Алгоритам постепено повећава величину стабла почевши од једног чвора, док не повеже све чворове. Сложеност Примовог алгоритма је ${\displaystyle O(m\log n}$) или ${\displaystyle O(m+n\log n)}$ у зависности од структуре података која се користи.

Трећи алгоритам који се често користи је Крускалов алгоритам који такође има сложеност ${\displaystyle O(m\log n)}$.

Четврти не тако често коришћен алгоритам је Алгоритам обрнутог брисања који је супротан Крускаловом алгоритму. Његова сложеност је ${\displaystyle O(m\log n(\log \log n)^{3})}$.

Сва четири алгоритма спадају у похлепне алгоритме.

Бржи алгоритми

Неколико истраживања су покушала да пронађу више рачунски-ефикаснијих алгоритама.

У моделу поређења, у ком су једине дозвољене операције над тежинама грана операције поређење парова, Каргер, Клејн и Тарџан 1995. године пронашли су насумични алгоритам у линеарном времену базиран на комбинацији Борвукиног алгоритма и алгоритма обрнутог брисања.^[2][3]

Најбржи ненасумични базиран на поређењу алгоритам са познатом сложеношћу направљен од стране Бернард Шазела је базиран на приближном приоритету софт хипа.^[4][5] Његово време извршавања је ${\displaystyle O(m\alpha (m,n))}$, где ${\displaystyle \alpha }$ представља класичну инверзну функцију Акерманове функције. Функција ${\displaystyle \alpha }$ расте екстремно споро, тако да се за све практичне сврхе може посматрати као константа не већа од 4; стога је Шазелов алгоритам веома близу линеарне сложености.

Алгоритам линеарне слоеонсти у специјалним случајевима

Густи графови

Ако је граф густ тј. ${\displaystyle (m{/}n\geq \log \log \log n)}$, oнда Фредманов и Тарџанов детерминистички алгоритам проналази минимално разапињуће стабло за време ${\displaystyle O(m)}$.^[6] Алгоритам извршава низ фаза. Свака фаза извршава Примов алгоритам много пута, сваки пут за ограничен број корака. Време извршавања сваке фазе је ${\displaystyle O(m+n)}$. Ако је број чворова пре извршавања фазе ${\displaystyle n'}$, онда је број чворова након извршавања фазе ${\displaystyle n'/2^{m/n'}}$. Стога је потребно да се изврши највише ${\displaystyle \log *{n}}$ фаза, што нам даје линеарно време извршавања за густе графове.

Постоје и други алгоритми који раде са густим графовима.^[7]

Целобројне тежине

Ако је тежина гране цео број представљен у бинарном запису, онда је познато да детерминистички алгоритми решавају проблем у ${\displaystyle O(m+n)}$ целобројних операција. Иако се проблем може решити детерминистички за општи граф у линеарној сложености, за алгоритме базиране на поређењу то остаје отворено питање.

Стабла одлучивања

За задат граф ${\displaystyle G}$ код кога су чворови и гране фиксиране али је тежина непозната, могуће је конструисати бинарно стабло одлучивања за рачунање минималног разапињућег стабла за било коју пермутацију тежина. Сваки унутрашњи чвор из стабла одлучивања садржи поређење између две гране, нпр. „ Да ли је тежина гране између чворова ${\displaystyle x}$ и ${\displaystyle y}$ већа од тежине гране између чворова ${\displaystyle w}$ и ${\displaystyle z}$?“. Два детета чвора одговарају одговорима „да“ или „не“. У сваком листу стабла одлучивања постоји листа грана која одговара минималном разапињућем стаблу. Сложеност извршавања стабла одлучивања једнака је највећем броју упита потребним да се нађе минимално разапињуће стабло, што је у ствари дубина стабла одлучивања. Стабло одлучивања за граф ${\displaystyle G}$ је оптимално ако има најмању дубину у односу на сва исправна стабла одлучивања из графа ${\displaystyle G}$.

За сваки цео број ${\displaystyle r}$, могуће је пронаћи оптимална стабла одлучивања за све графове са ${\displaystyle r}$ чворова, помоћу исцрпне претраге.

А. Генерисање свих потенцијалних стабала одлучивања

• Постоји ${\displaystyle 2^{r \choose 2}}$ различитих графова са ${\displaystyle r}$ чворова.
• За сваки граф, минимално разапињуће стабло се може наћи помоћу ${\displaystyle r\cdot (r-1)}$ поређења, нпр. помоћу Примовог алгоритма.
• Стога, дубина оптималног стабла одлучивања је ${\displaystyle r^{2}}$.
• Дакле, број чворова у оптималном стаблу одлучивања је мањи од ${\displaystyle 2^{r^{2}}}$.
• Сваки унутрашњни чвор пореди две гране. Број грана је највише ${\displaystyle r^{2}}$, тако да постоји највише ${\displaystyle r^{4}}$ различитих поређења.
• Дакле, број потенцијалних стабала одлучивања је мањи од: ${\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}}$.

Б. Проналажење исправних стабала одлучивања

Да бисмо проверили да ли је стабло одлучивања исправно, потребно је проверити га за све могуће пермутације тежина грана.

• Број таквих пермутација је највише ${\displaystyle (r^{2})!}$.
• За сваку пермутацију решава се проблем минималног разапињућег стабла за дат граф користећи било који постојећи алгоритам, и резултат се пореди са одговором добијеним из стабла одлучивања.
• Време извршавања било ког алгоритма за минимално разапињуће стабло је највише ${\displaystyle (r^{2})}$, тако да је укупно време да се провере све пермутације највише ${\displaystyle (r^{2}+1)!}$.

Стога, укупно време које је потребно да се пронађе оптимално стабло одлучивања за све графове са ${\displaystyle r}$ чворова износи: ${\displaystyle 2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!}$ што је мање од: ${\displaystyle 2^{2^{r^{2}+o(r)}}}$.

Оптималан алгоритам

Сетх Петит и Виџаја Рамачандран су пронашли оптимални детерминистички базиран на компарацији алгоритам који проналази минимално разапињуће стабло. У наставку је описан поједностављен приказ алгоритма.

1. Нека је ${\displaystyle r=\log \log \log n}$, где ${\displaystyle n}$ представља број чворова. Потребно је пронаћи сва оптимална стабла одлучивања са ${\displaystyle r}$. Ово се може урадити за време ${\displaystyle O(n)}$.
2. Поделити граф на компоненте, тако да у свакој компоненти има највише ${\displaystyle r}$ чворова. Ова подела се може извршити за ${\displaystyle O(m)}$ времена.
3. Користимо оптимално стабло одлучивања да бисмо нашли минимално разапињуће стабло у свакој компоненти.
4. Контрахујемо сваку повезану компоненту обухваћену минималним разапињућим стаблом у по један чвор.
5. Могуће је доказати да добијени граф има највише ${\displaystyle n{/}r}$ чворова. Дакле, граф је густ и ми можемо користити било који алгоритам који се користи код густих графова у времену ${\displaystyle O(m)}$.

Време извршавања свих корака у алгоритму је ${\displaystyle O(m)}$, изузев корака где се користе стабла одлучивања. Ми не знамо време извршавања овог корака, али знамо да је оптимално - ниједан алгоритам не може дати бољи резутат од оптималног стабла одлучивања.

Према томе, овај алгоритам има чудну особину да је доказиво оптималан иако је његова сложеност непозната.

Паралелни и расподељени алгоритми

При истраживању проблема минималног разапињућег стабла узети су у обзир и паралелни алгоритми. Са линеарним бројем процесора могуће је решити овај проблем за ${\displaystyle O(\log n)}$ времена. Бадер и Чонг 2006. године су демонстрирали алгоритам који може да пронађе минимална разапињућа стабла 5 пута брже на 8 процесора него оптимизовани секвенцијални алгоритам.

Остали специјализовани алгоритми дизајнирани за налажење минималног разапињућег стабла су толико велики да већим делом морају бити чувани на диску све време. Ови алгоритми са спољашњим складиштењем, као на пример они који су описани у раду „Конструкција алгоритма за проналажење минималног разапињућег стабла који користи екстерну меморију“ од Романа Дементијева могу, се извршавати, како аутор тврди, 2 до 5 пута спорије него традиционални алгоритми који користе унутрашњу меморију. Они се ослањају на ефикасно спољашње сортирање и на контракцију графа - технику за ефикасно смањење величине графа.

Проблему се такође може приступити помоћу расподељеног израчунавања. Ако се сваки чвор посматра као рачунар и ниједан чвор не зна ништа сем веза са којима је повезан, један сигурно може пронаћи дистрибуирано минимално разапињуће стабло.

Минимално разапињуће стабло у комплетним графовима

Алан М. Фриз је показао да задат комплетан граф са ${\displaystyle n}$ чворова, који има гране чије су тежине независне идентично распоређене случајне променљиве са функцијом расподеле ${\displaystyle F}$ задовољава ${\displaystyle F'(0)>0}$, и како ${\displaystyle n}$ прилази +∞ очекивана тежина минималног разапињућег стабла се приближава ${\displaystyle \zeta (3)/F'(0)}$, где ${\displaystyle \zeta }$ представља Риманову зета-функцију. Фриз и Стил су такође доказали конвергенцију у вероватноћи. Сванте Јансон је доказао централну граничну теорему за тежину минималног разапињућег стабла.

За насумично одабране тежине из интервала ${\displaystyle [0,1]}$,тачна очекивана величина минималног разапињућег стабла је израчуната за мале комплетне графове.

Чворови	Очекивана величина	Приближна очекивана величина
2	1 / 2	0.5
3	3 / 4	0.75
4	31 / 35	0.8857143
5	893 / 924	0.9664502
6	278 / 273	1.0183151
7	30739 / 29172	1.053716
8	199462271 / 184848378	1.0790588
9	126510063932 / 115228853025	1.0979027

Апликације

Сродни проблеми

Референце

1. Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
2. Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), „A randomized linear-time algorithm to find minimum spanning trees”, Journal of the Association for Computing Machinery, 42 (2): 321—328, MR 1409738, doi:10.1145/201019.201022
3. Pettie, Seth; Ramachandran, Vijaya (2002), „Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms”, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, стр. 713—722.
4. Chazelle, Bernard (2000), „A minimum spanning tree algorithm with inverse-Ackermann type complexity”, Journal of the Association for Computing Machinery, 47 (6): 1028—1047, MR 1866456, doi:10.1145/355541.355562.
5. Chazelle, Bernard (2000), „The soft heap: an approximate priority queue with optimal error rate”, Journal of the Association for Computing Machinery, 47 (6): 1012—1027, MR 1866455, doi:10.1145/355541.355554.
6. Fredman, M. L.; Tarjan, R. E. (1987). „Fibonacci heaps and their uses in improved network optimization algorithms”. Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874.
7. Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). „Efficient algorithms for finding minimum spanning trees in undirected and directed graphs”. Combinatorica. 6 (2): 109. doi:10.1007/bf02579168.