SPANNING TREE - VÝUKA DS

V tomto článku se budeme zabývat kostrou a minimální kostrou. Než se však přesuneme přímo ke kostrě, podívejme se nejprve na stručný popis grafu a jeho typů.

Graf

Graf lze definovat jako skupinu vrcholů a hran pro spojení těchto vrcholů. Typy grafů jsou uvedeny následovně -

Neorientovaný graf:Neorientovaný graf je graf, ve kterém všechny hrany nesměřují k žádnému konkrétnímu směru, tj. nejsou jednosměrné; jsou obousměrné. Může být také definován jako graf se sadou V vrcholů a sadou E hran, přičemž každá hrana spojuje dva různé vrcholy.Připojený graf:Souvislý graf je graf, ve kterém vždy existuje cesta z vrcholu do jakéhokoli jiného vrcholu. Graf je souvislý, pokud můžeme dosáhnout libovolného vrcholu z jakéhokoli jiného vrcholu sledováním hran v obou směrech.Orientovaný graf:Orientované grafy jsou také známé jako digrafy. Graf je orientovaný graf (nebo digraf), pokud všechny hrany přítomné mezi libovolnými vrcholy nebo uzly grafu směřují nebo mají definovaný směr.

Nyní pojďme k tématu kostry.

Co je to kostra?

Spanning tree lze definovat jako podgraf neorientovaného souvislého grafu. Zahrnuje všechny vrcholy spolu s co nejmenším počtem hran. Pokud některý vrchol chybí, nejedná se o kostru. Kostra je podmnožina grafu, která nemá cykly a také ji nelze odpojit.

Kostra se skládá z (n-1) hran, kde 'n' je počet vrcholů (nebo uzlů). Hrany kostry mohou nebo nemusí mít přiřazeny váhy. Všechny možné kostry vytvořené z daného grafu G by měly stejný počet vrcholů, ale počet hran kostry by se rovnal počtu vrcholů v daném grafu mínus 1.

Může mít úplný neorientovaný graf n^n-2 počet kostrových stromů kde n je počet vrcholů v grafu. Předpokládejme, že pokud n = 5 , počet maximálních možných kostrových stromů by byl 5^5-2= 125.

Aplikace kostry

V zásadě se kostra používá k nalezení minimální cesty k propojení všech uzlů grafu. Některé z běžných aplikací kostry jsou uvedeny následovně -

Shluková analýza
Plánování civilní sítě
Směrovací protokol počítačové sítě

Pojďme nyní pochopit kostru pomocí příkladu.

Příklad Spanning tree

Předpokládejme, že graf je -

Jak bylo diskutováno výše, kostra obsahuje stejný počet vrcholů jako graf, počet vrcholů ve výše uvedeném grafu je 5; kostra tedy bude obsahovat 5 vrcholů. Hrany kostry se budou rovnat počtu vrcholů v grafu mínus 1. V kostru tedy budou 4 hrany.

Některé možné kostry, které budou vytvořeny z výše uvedeného grafu, jsou uvedeny následovně -

Vlastnosti kostry

Některé vlastnosti kostry jsou uvedeny následovně -

V souvislém grafu G může být více než jedna kostra.
Spanning tree nemá žádné cykly ani smyčku.
Je to kostra minimálně připojeno, takže odstranění jedné hrany ze stromu způsobí odpojení grafu.
Je to kostra maximálně acyklické, takže přidání jedné hrany do stromu vytvoří smyčku.
Může být maximálně n^n-2 počet kostrových stromů, které lze vytvořit z kompletního grafu.
Kostým má n-1 hrany, kde 'n' je počet uzlů.
Pokud je graf úplný graf, pak kostru lze sestavit odstraněním maximálních (e-n+1) hran, kde 'e' je počet hran a 'n' je počet vrcholů.

Takže kostra je podmnožinou spojeného grafu G a neexistuje žádná kostra nespojeného grafu.

Minimální kostra

Minimální kostru lze definovat jako kostru, ve které je součet vah hrany minimální. Hmotnost kostry je součtem vah daných okrajům kostry. V reálném světě lze tuto váhu považovat za vzdálenost, dopravní zátěž, zácpu nebo jakoukoli náhodnou hodnotu.

Příklad minimální kostry

Pojďme pochopit minimální kostru pomocí příkladu.

Součet hran výše uvedeného grafu je 16. Nyní některé možné kostry vytvořené z výše uvedeného grafu jsou -

Takže minimální kostra, která je vybrána z výše uvedených kostry pro daný vážený graf, je -

Aplikace minimální kostry

Aplikace minimální kostry jsou uvedeny následovně -

Minimální kostru lze použít pro návrh vodovodních sítí, telekomunikačních sítí a elektrických sítí.
Lze jej použít k vyhledání cest v mapě.

Algoritmy pro minimální kostru

Minimální kostru lze nalézt z váženého grafu pomocí níže uvedených algoritmů -

Primův algoritmus
Kruskalův algoritmus

Podívejme se na stručný popis obou výše uvedených algoritmů.

Primův algoritmus - Je to chamtivý algoritmus, který začíná prázdným kostrou. Používá se k nalezení minimální kostry z grafu. Tento algoritmus najde podmnožinu hran, která zahrnuje každý vrchol grafu, takže součet vah hran lze minimalizovat.

jaké měsíce jsou q1

Chcete-li se dozvědět více o primově algoritmu, klikněte na níže uvedený odkaz - https://www.javatpoint.com/prim-algorithm

Kruskalův algoritmus - Tento algoritmus se také používá k nalezení minimální kostry pro spojený vážený graf. Kruskalův algoritmus také sleduje chamtivý přístup, který nalézá optimální řešení v každé fázi místo toho, aby se zaměřoval na globální optimum.

Chcete-li se dozvědět více o primově algoritmu, klikněte na níže uvedený odkaz - https://www.javatpoint.com/kruskal-algorithm

Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní. Zde jsme diskutovali spanning tree a minimální spanning tree spolu s jejich vlastnostmi, příklady a aplikacemi.