Редица задачи от теорията на графите се наричат минимално простиращо се дърво. В теорията на графите дървото е начин за свързване на всички върхове заедно, така че да има точно един път от всеки един връх до всеки друг връх на дървото. Ако графът представлява няколко града, свързани с пътища, може да се избере такъв брой пътища, че до всеки град да може да се стигне от всеки друг, но да няма повече от един път за пътуване от един град до друг.

Графът може да има повече от едно простиращо се дърво, точно както може да има повече от един начин за избор на пътища между градовете.

В повечето случаи графиките са претеглени; всяка връзка между два града има тегло: пътуването по даден път може да струва нещо или една връзка може да е по-дълга от друга, което означава, че пътуването по нея отнема повече време. На езика на теорията на графите връзките се наричат ребра.

Минималното простиращо се дърво е дърво. То се различава от другите дървета по това, че минимизира сбора от теглата, прикрепени към ребрата. В зависимост от това как изглежда графът, може да има повече от едно минимално простиращо се дърво. В граф, в който всички ребра имат еднакво тегло, всяко дърво е минимално простиращо се дърво. Ако всички ребра имат различни тегла (т.е. няма две ребра с еднакво тегло), има точно едно минимално простиращо се дърво.

Формално определение

Нека G = (V, E, w) е свързан, ненасочен граф, където V е множеството от върхове, E е множеството от ребра и w: E → R е функцията, даваща тегло (реално число) на всяко ребро. Простиращо се дърво (spanning tree) на G е подграф T = (V, E_T), където E_T ⊆ E, който е дърво и съдържа всички върхове V. Минималното простиращо се дърво (MST) е такова T, че сумата на теглата Σ_{e∈E_T} w(e) е минимална сред всички простиращи се дървета на G.

Основни свойства

  • Всяко MST съдържа точно |V| − 1 ребра.
  • Ако графът не е свързан, минимално простиращо се дърво не съществува, но можем да дефинираме минимална простираща гора (minimum spanning forest) — MST за всяка свързана компонента.
  • Свойство на разреза (cut property): за всеки разрез на върховете, най-лекото ребро, което пресича този разрез, принадлежи на някоe MST.
  • Свойство за цикъл (cycle property): за всеки цикъл в графа най-тежкото ребро в този цикъл не принадлежи на никакво MST.
  • Уникалност: ако всички ребра имат различни тегла, MST е единствено. При равни тегла може да има няколко различни MST със същата сумарна тежест.

Алгоритми за намиране на MST

Най-популярните алгоритми са:

  • Крускал (Kruskal): сортира ребрата по тегло (възходящо) и последователно добавя ребра към текущия гор (forest), ако не образуват цикъл. Обикновено се реализира с помощта на структурата Union-Find (disjoint-set). Времева сложност: O(E log E) ≈ O(E log V).
  • Прим (Prim): започва от произволен връх и на всяка стъпка добавя най-евтиното ребро, което свързва достигнатата част със съседен недостигнат връх. Често се реализира с приоритетна опашка (heap). Времева сложност: O(E log V) при използване на binary heap, или O(E + V log V) при Fibonacci heap.
  • Borůvka: паралелен алгоритъм, който в няколко итерации за всяка компонента избира най-евтиното изхождащо ребро и ги свързва; полезен при паралелни/разпределени среди и за аналитични цели.

Кратка схема на Kruskal (стъпки):

  • 1) Сортирай ребрата по нарастващо тегло.
  • 2) Инициализирай горта с всички върхове като отделни компоненти.
  • 3) За всяко ребро в сортирания ред: ако свързва две различни компоненти, добави го и ги обедини.
  • 4) Продължи докато имаш |V| − 1 ребра или докато не пресечеш всички ребра.

Пример

Нека имаме четири върха A, B, C, D и следните ребра с тегла:

  • A–B: 1
  • A–C: 5
  • B–C: 2
  • B–D: 4
  • C–D: 3

Използвайки Kruskal: първо допадаме A–B (1), после B–C (2) — сега имаме A,B,C свързани. След това най-евтиното, което не образува цикъл, е C–D (3). Резултатното MST съдържа ребрата A–B, B–C, C–D с обща тежест 1+2+3=6. Това е минималната възможна сумарна тежест за свързване на всички четири върха.

Приложения

  • Проектиране на мрежи (електрически, теле-ком, пътища) с минимални разходи.
  • Клъстериране и агломеративни методи в машинното обучение.
  • Приближени алгоритми за задачи като проблема на пътя на търговеца (TSP) и други комбинаторни задачи.
  • Обработка на изображения — сегментация чрез граф-базирани методи.

Допълнителни бележки и вариации

  • Ако графът съдържа ребра със същата тегловна стойност, може да има множество различни MST; всички те имат една и съща обща тежест.
  • За графове с отрицателни тегла алгоритмите Kruskal и Prim работят без промяна, тъй като те не зависят от неотрицателността на теглата (за разлика от най-късите пътища с Dijkstra).
  • За големи входни данни прилагайте ефективни структури (Union-Find с пътна компресия, оптимизиран heap) и внимавайте с представянето на ребрата, за да постигнете добър реален performance.

Минималното простиращо се дърво е фундаментална структура в теорията на графите с богата теория и много практични приложения. Понятието комбинира лесна за формулиране цел (минимизиране на сумата от тегла) с мощни свойства (разрези и цикли), които позволяват бързи, коректни и често оптимални алгоритми за намиране.