Растезно дрво и минимално распрострањено дрво

У овом упутству ћете научити о растућем дрвету и минималном растућем дрвету помоћу примера и слика.

Пре него што научимо о распону дрвећа, морамо да разумемо два графика: неусмерени и повезани графови.

Ундирецтед грапх представља графикон у којем се ивице не упути у било ком правцу (нпр. Ивице су бидирецтионал).

Неусмерени графикон

Повезан граф је граф у коме увек постоји пут од врха до осталих чворова.

Повезани граф

Распрострањено дрво

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

На ивицама им могу бити додељене тежине, али не морају.

Укупан број распрострањених стабала са nврховима који се могу створити из комплетног графикона једнак је .n(n-2)

Ако имамо n = 4, максималан број могућих распрострањених стабала је једнак . Тако се из целовитог графикона са 4 темена може формирати 16 распрострањених стабала.44-2 = 16

Пример распрострањеног дрвета

Хајде да разумемо распрострањено стабло са примерима у наставку:

Нека оригинални графикон буде:

Нормални граф

Нека од могућих распрострањених стабала која се могу створити из горњег графикона су:

Растезно дрво Растезно дрво Растезајуће дрво Растезајуће дрво Растезно дрво Растезно дрво

Минимално дрвеће у распону

Минимално затезно дрво је затезно дрво код којег је збир тежине ивица што је могуће мањи.

Пример распрострањеног дрвета

Да разумемо горњу дефиницију уз помоћ примера у наставку.

Почетни графикон је:

Пондерисани граф

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

Минимално растегљиво дрво - 1 Минимално распростируће се дрво - 2 Минимално распростируће се дрво - 3 Минимално распонично дрво - 4

Минимално дрвеће које се протеже од горе наведеног дрвећа је:

Минимално распрострањено дрво

Минимално стабло распона из графа налази се помоћу следећих алгоритама:

1. Примов алгоритам
2. Крускалов алгоритам

Спаннинг Трее апликације

• Протокол за усмеравање рачунарске мреже
• Кластер анализа
• Планирање цивилне мреже

Минимално примање стабла распона

• Да бисте пронашли путање на мапи
• За пројектовање мрежа попут телекомуникационих мрежа, водоводних мрежа и електричних мрежа.