TechCodeview

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

Граф

Граф се може дефинисати као група врхова и ивица за повезивање ових врхова. Типови графикона су дати на следећи начин -

Неусмерени граф:Неусмерени граф је граф у коме све ивице не указују ни на један одређени правац, тј. нису једносмерне; они су двосмерни. Такође се може дефинисати као граф са скупом В темена и скупом Е ивица, при чему свака ивица повезује два различита темена.Повезани графикон:Повезани граф је граф у коме увек постоји путања од темена до било ког другог темена. Граф је повезан ако можемо доћи до било ког темена из било ког другог темена пратећи ивице у било ком смеру.Усмерени граф:Усмерени графови су такође познати као диграфи. Граф је усмерен граф (или диграф) ако су све ивице присутне између врхова или чворова графа усмерене или имају дефинисан правац.

Сада, пређимо на тему која обухвата дрво.

Шта је раздвојено дрво?

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

Размотано дрво се састоји од (н-1) ивица, где је 'н' број врхова (или чворова). Ивице разапињућег стабла могу или не морају имати додељене тежине. Сва могућа разапињућа стабла створена из датог графа Г имала би исти број врхова, али би број ивица у разапињућем стаблу био једнак броју врхова у датом графу минус 1.

Потпуни неусмерени граф може имати н^н-2 број распонских стабала где н је број врхова у графу. Претпоставимо, ако н = 5 , број максимално могућих разапињућих стабала би био 5^5-2= 125.

Примене разапињућег дрвета

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

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

Сада, хајде да разумемо разапињуће дрво уз помоћ примера.

Пример разапињућег дрвета

Претпоставимо да је графикон -

Као што је горе објашњено, разапињуће дрво садржи исти број врхова као и граф, број врхова у горњем графу је 5; дакле, разапињуће дрво ће садржати 5 врхова. Ивице у разапињућем стаблу биће једнаке броју врхова у графу минус 1. Дакле, у разапињућем стаблу биће 4 ивице.

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

Особине разапињућег дрвета

Нека од својстава разапињућег дрвета су дата на следећи начин -

• Може постојати више од једног разапињућег стабла повезаног графа Г.
• Размотано дрво нема циклусе или петљу.
• Раздвојно дрво је минимално повезан, тако да ће уклањање једне ивице са стабла учинити да граф буде искључен.
• Раздвојно дрво је максимално ациклично, па ће додавање једне ивице стаблу створити петљу.
• Може бити максимум н^н-2 број раздвојених стабала која се могу креирати из комплетног графа.
• Раздвојно дрво има н-1 ивице, где је 'н' број чворова.
• Ако је граф комплетан граф, онда се разапињуће дрво може конструисати уклањањем максималних (е-н+1) ивица, где је 'е' број ивица, а 'н' број врхова.

Дакле, разапињуће стабло је подскуп повезаног графа Г и не постоји разапињуће стабло неповезаног графа.

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

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

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

Хајде да разумемо минимално разапињуће стабло уз помоћ примера.

Збир ивица горњег графа је 16. Сада, нека од могућих стабала која су направљена из горњег графа су -

Дакле, минимално разапињуће стабло које је изабрано из горњих разапајућих стабала за дати пондерисани граф је -

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

Примене минималног разапињућег стабла су дате на следећи начин -

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

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

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

• Примов алгоритам
• Крускалов алгоритам

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

Примов алгоритам - То је похлепни алгоритам који почиње празним разапињућим стаблом. Користи се за проналажење минималног распонског стабла из графа. Овај алгоритам проналази подскуп ивица који укључује сваки врх графа тако да се збир тежина ивица може минимизирати.

мин мак

Да бисте сазнали више о прим алгоритму, можете кликнути на линк испод - хттпс://ввв.јаватпоинт.цом/прим-алгоритхм

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

Да бисте сазнали више о прим алгоритму, можете кликнути на линк испод - хттпс://ввв.јаватпоинт.цом/крускал-алгоритхм

Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан. Овде смо расправљали о разапињућем стаблу и минималном разапињућем стаблу заједно са њиховим својствима, примерима и применама.