SPANNING TREE

В тази статия ще обсъдим обхващащото дърво и минималното обхващащо дърво. Но преди да преминем директно към обхващащото дърво, нека първо видим кратко описание на графиката и нейните типове.

Графика

Графът може да се дефинира като група от върхове и ръбове за свързване на тези върхове. Видовете графики са дадени, както следва -

Неориентирана графика:Неориентиран граф е график, в който всички ръбове не сочат към определена посока, т.е. те не са еднопосочни; те са двупосочни. Може също да се дефинира като граф с набор от V върхове и набор от E ръбове, като всеки ръб свързва два различни върха.Свързана графика:Свързан граф е граф, в който винаги съществува път от връх до всеки друг връх. Графът е свързан, ако можем да достигнем всеки връх от който и да е друг връх, като следваме ребра в която и да е посока.Насочена графика:Насочените графи са известни също като диграфи. Графът е насочен граф (или диграф), ако всички присъстващи ребра между върхове или възли на графа са насочени или имат определена посока.

Сега нека преминем към обхващащото дърво на темата.

Какво е Spanning Tree?

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

Обхващащото дърво се състои от (n-1) ребра, където 'n' е броят на върховете (или възлите). Краищата на обхващащото дърво могат или не могат да имат присвоени тегла. Всички възможни обхващащи дървета, създадени от дадения граф G, ще имат еднакъв брой върхове, но броят на ръбовете в обхващащото дърво ще бъде равен на броя върхове в дадения график минус 1.

Един пълен неориентиран граф може да има н^n-2 брой обхващащи дървета където н е броят на върховете в графиката. Да предположим, ако n = 5 , броят на максимално възможните обхващащи дървета ще бъде 5^5-2= 125.

Приложения на Spanning Tree

По принцип обхващащото дърво се използва за намиране на минимален път за свързване на всички възли на графиката. Някои от често срещаните приложения на Spanning Tree са изброени както следва -

Клъстерен анализ
Планиране на гражданска мрежа
Протокол за маршрутизиране на компютърна мрежа

Сега нека разберем обхващащото дърво с помощта на пример.

Пример за обхващащо дърво

Да предположим, че графиката е -

Както беше обсъдено по-горе, обхващащото дърво съдържа същия брой върхове като графиката, броят на върховете в горната графика е 5; следователно обхващащото дърво ще съдържа 5 върха. Ребрата в обхващащото дърво ще бъдат равни на броя на върховете в графиката минус 1. Така че ще има 4 ребра в обхващащото дърво.

Някои от възможните обхващащи дървета, които ще бъдат създадени от горната графика, са дадени както следва -

Свойства на spanning-tree

Някои от свойствата на обхващащото дърво са дадени както следва -

Може да има повече от едно обхващащо дърво на свързан граф G.
Обхващащото дърво няма никакви цикли или цикъл.
Spanning Tree е минимално свързан, така че премахването на един ръб от дървото ще направи графиката несвързана.
Spanning Tree е максимално ацикличен, така че добавянето на един ръб към дървото ще създаде цикъл.
Може да има максимум н^n-2 брой обхващащи дървета, които могат да бъдат създадени от пълна графика.
Spanning Tree има n-1 ръбове, където 'n' е броят на възлите.
Ако графиката е пълна графа, тогава обхващащото дърво може да бъде конструирано чрез премахване на максималните (e-n+1) ръбове, където „e“ е броят на ръбовете, а „n“ е броят на върховете.

И така, обхващащото дърво е подмножество на свързан граф G и няма обхващащо дърво на несвързан граф.

Минимално обхващащо дърво

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

Пример за минимално обхващащо дърво

Нека разберем минималното обхващащо дърво с помощта на пример.

Сумата от ръбовете на горната графика е 16. Някои от възможните обхващащи дървета, създадени от горната графика, са -

И така, минималното обхващащо дърво, което е избрано от горните обхващащи дървета за дадената претеглена графика, е -

Приложения на минимално покриващо дърво

Приложенията на минималното обхващащо дърво са дадени както следва -

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

Алгоритми за минимално обхващащо дърво

Минимално обхващащо дърво може да се намери от претеглена графика с помощта на алгоритмите, дадени по-долу -

Алгоритъмът на Прим
Kruskal's Algorithm

Нека видим кратко описание на двата алгоритъма, изброени по-горе.

Алгоритъмът на Prim - Това е алчен алгоритъм, който започва с празно обхващащо дърво. Използва се за намиране на минималното обхващащо дърво от графиката. Този алгоритъм намира подмножеството от ръбове, което включва всеки връх на графиката, така че сумата от теглата на ръбовете да може да бъде минимизирана.

път, зададен в java

За да научите повече за алгоритъма на прим, можете да щракнете върху връзката по-долу - https://www.javatpoint.com/prim-algorithm

Kruskal's algorithm - Този алгоритъм се използва и за намиране на минималното обхващащо дърво за свързан претеглен график. Алгоритъмът на Kruskal също следва алчен подход, който намира оптимално решение на всеки етап, вместо да се фокусира върху глобален оптимум.

За да научите повече за алгоритъма на прим, можете да щракнете върху връзката по-долу - https://www.javatpoint.com/kruskal-algorithm

И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна. Тук обсъдихме обхващащо дърво и минимално обхващащо дърво заедно с техните свойства, примери и приложения.

TechCodeview