Минимално обхващащо дърво
Редица задачи от теорията на графите се наричат минимално простиращо се дърво. В теорията на графите дървото е начин за свързване на всички върхове заедно, така че да има точно един път от всеки един връх до всеки друг връх на дървото. Ако графът представлява няколко града, свързани с пътища, може да се избере такъв брой пътища, че до всеки град да може да се стигне от всеки друг, но да няма повече от един път за пътуване от един град до друг.
Графът може да има повече от едно простиращо се дърво, точно както може да има повече от един начин за избор на пътища между градовете.
В повечето случаи графиките са претеглени; всяка връзка между два града има тегло: пътуването по даден път може да струва нещо или една връзка може да е по-дълга от друга, което означава, че пътуването по нея отнема повече време. На езика на теорията на графите връзките се наричат ребра.
Минималното простиращо се дърво е дърво. То се различава от другите дървета по това, че минимизира сбора от теглата, прикрепени към ребрата. В зависимост от това как изглежда графът, може да има повече от едно минимално простиращо се дърво. В граф, в който всички ребра имат еднакво тегло, всяко дърво е минимално простиращо се дърво. Ако всички ребра имат различни тегла (т.е. няма две ребра с еднакво тегло), има точно едно минимално простиращо се дърво.
Минималното разклоняващо се дърво на плосък граф. Всяко ребро е обозначено с теглото си, което тук е приблизително пропорционално на дължината му.
Намиране на минималното простиращо се дърво
Първи опит
Може да бъде много лесно да се създаде алгоритъм, който да открие минимално простиращо се дърво:
функция MST(G,W): T = {} докато T не образува разклоняващо се дърво: намерете минималния претеглен ръб в E, който е безопасен за T T T = T union {(u,v)} return TВ този случай "безопасно" означава, че включването на реброто не образува цикъл в графа. Цикъл означава да се започне от даден връх, да се премине през редица други върхове и да се завърши отново в началната точка, без да се използва два пъти едно и също ребро.
История
През 1926 г. чешкият учен Отокар Борувка разработва първия известен алгоритъм за намиране на минимално простиращо се дърво. Той иска да реши проблема с намирането на ефективно покритие на Моравия с електричество. Днес този алгоритъм е известен като алгоритъм на Борувка. Два други алгоритъма се използват често днес. Единият от тях е разработен от Войтех Ярник през 1930 г., а на практика е приложен от Робърт Клей Прим през 1957 г. Едсгер Уайб Дийкстра го преоткрива през 1959 г. и го нарича алгоритъм на Прим. Другият алгоритъм се нарича алгоритъм на Крускал и е пулбикуван от Джоузеф Крускал през 1956 г. И трите алгоритъма са алчни и се изпълняват за полиномиално време.
Най-бързият до момента алгоритъм за минимално простиращо се дърво е разработен от Бернар Шазел. Алгоритъмът се основава на меката купчина - приблизителна приоритетна опашка. Времето му за изпълнение е O(m α(m,n)), където m е броят на ребрата, n е броят на върховете, а α е класическата функционална инверсия на функцията на Акерман. Функцията α расте изключително бавно, така че за всички практически цели може да се счита за константа, не по-голяма от 4; по този начин алгоритъмът на Chazelle отнема много близо до линейното време.
Кой е най-бързият възможен алгоритъм за тази задача? Това е един от най-старите отворени въпроси в информатиката. Ясно е, че има линейна долна граница, тъй като трябва да разгледаме поне всички тегла. Ако теглата на ребрата са цели числа с ограничена дължина на битовете, тогава са известни детерминистични алгоритми с линейно време за изпълнение. За общи тегла съществуват рандомизирани алгоритми, чието очаквано време за изпълнение е линейно.
Към проблема може да се подходи и по разпределен начин. Ако всеки възел се разглежда като компютър и никой възел не знае нищо друго освен собствените си свързани връзки, все пак може да се изчисли разпределеното минимално простиращо се дърво.
Въпроси и отговори
Въпрос: Какво представлява минималното простиращо се дърво в теорията на графите?
О: В теорията на графите минимално обхващащо дърво е дърво, което минимизира общите тегла, приложени към ребрата.
В: Какво е дърво в теорията на графите?
О: Дървото е начин за свързване на всички върхове заедно в теорията на графите, така че да има само един път от всеки един връх до всеки друг връх на дървото.
В: Каква е целта на избирането на пътища в сценарий на теория на графите, който представя градове?
О: Целта на избора на пътища в сценарий на теория на графите, който представя градове, е да се даде възможност всеки град да бъде достигнат от всеки друг град, но без да има повече от един възможен път за пътуване от един град до друг.
Въпрос: Може ли един граф да има повече от едно разтегателно дърво?
О: Да, графът може да има повече от едно дърво на простиране.
В: Каква е разликата между минималното дърво на простиране и други дървета в теорията на графите?
Отговор: Минималното дърво минимизира общите тегла, прикрепени към ребрата, докато другите дървета нямат тази характеристика.
В: Какво представляват ребрата в теорията на графите?
О: В теорията на графите ребрата са връзките между два върха.
Въпрос: Може ли да има повече от едно минимално простиращо се дърво в граф с различно претеглени ребра?
О: Да, в зависимост от това как изглежда графът, може да има повече от едно минимално простиращо се дърво.
