În acest articol, vom discuta despre arborele de întindere și arborele de întindere minim. Dar înainte de a trece direct către arborele care se întinde, să vedem mai întâi o scurtă descriere a graficului și a tipurilor acestuia.

Grafic

Un grafic poate fi definit ca un grup de vârfuri și muchii pentru a conecta aceste vârfuri. Tipurile de grafice sunt date după cum urmează -

Grafic nedirecționat:Un grafic nedirecționat este un grafic în care toate muchiile nu indică nicio direcție anume, adică nu sunt unidirecționale; sunt bidirectionale. Poate fi definit și ca un grafic cu un set de vârfuri V și un set de muchii E, fiecare muchie conectând două vârfuri diferite.Graficul conectat:Un graf conectat este un graf în care există întotdeauna o cale de la un vârf la orice alt vârf. Un grafic este conectat dacă putem ajunge la orice vârf de la orice alt vârf urmând muchiile în ambele direcții.Graficul dirijat:Graficele direcționate sunt cunoscute și sub denumirea de digrafe. Un graf este un graf direcționat (sau digraf) dacă toate muchiile prezente între orice vârfuri sau noduri ale grafului sunt direcționate sau au o direcție definită.

Acum, să ne îndreptăm către arborele cuprinzător al subiectului.

Ce este un copac spanning?

Un spanning tree poate fi definit ca subgraful unui graf conectat nedirecționat. Include toate vârfurile împreună cu cel mai mic număr posibil de muchii. Dacă vreun vârf este omis, nu este un arbore care se întinde. Un arbore spanning este un subset al graficului care nu are cicluri și, de asemenea, nu poate fi deconectat.

Un arbore de acoperire este format din (n-1) muchii, unde „n” este numărul de vârfuri (sau noduri). Marginile arborelui spanning pot avea sau nu greutăți atribuite. Toți arborii de întindere posibili creați din graficul dat G ar avea același număr de vârfuri, dar numărul de muchii din arborele de întindere ar fi egal cu numărul de vârfuri din graficul dat minus 1.

Un grafic complet nedirecționat poate avea n^n-2 numărul de copaci spanning unde n este numărul de vârfuri din grafic. Să presupunem, dacă n = 5 , numărul maxim de arbori spanning posibili ar fi 5^5-2= 125.

Aplicații ale arborelui spanning

Practic, un arbore de acoperire este folosit pentru a găsi o cale minimă pentru a conecta toate nodurile graficului. Unele dintre aplicațiile comune ale arborelui spanning sunt enumerate după cum urmează -

• Analiza grupului
• Planificarea rețelelor civile
• Protocol de rutare a rețelei de calculatoare

Acum, să înțelegem arborele întindere cu ajutorul unui exemplu.

Exemplu de Spanning Tree

Să presupunem că graficul este -

După cum sa discutat mai sus, un arbore de acoperire conține același număr de vârfuri ca și graficul, numărul de vârfuri din graficul de mai sus este 5; prin urmare, arborele spanning va conține 5 vârfuri. Muchiile din arborele de întindere vor fi egale cu numărul de vârfuri din grafic minus 1. Deci, vor exista 4 muchii în arborele de întindere.

Unii dintre arborii de întindere posibili care vor fi creați din graficul de mai sus sunt dați după cum urmează -

Proprietățile spanning-tree

Unele dintre proprietățile arborelui spanning sunt prezentate după cum urmează -

• Pot exista mai mult de un arbore de acoperire a unui graf conectat G.
• Un arbore care se întinde nu are cicluri sau buclă.
• Un copac spanning este conectat minim, deci eliminarea unei margini din arbore va face graficul deconectat.
• Un copac spanning este maxim aciclic, deci adăugarea unei margini la arbore va crea o buclă.
• Poate exista un maxim n^n-2 numărul de arbori de întindere care pot fi creați dintr-un grafic complet.
• Un copac spanning are n-1 margini, unde „n” este numărul de noduri.
• Dacă graficul este un grafic complet, atunci arborele de întindere poate fi construit prin eliminarea muchiilor maxime (e-n+1), unde „e” este numărul de muchii și „n” este numărul de vârfuri.

Deci, un arbore de întindere este un subset al graficului conectat G și nu există un arbore de întindere al unui grafic deconectat.

Arborele de întindere minim

Un arbore de întindere minim poate fi definit ca arbore de întindere în care suma greutăților marginii este minimă. Greutatea arborelui spanning este suma greutăților date marginilor arborelui spanning. În lumea reală, această greutate poate fi considerată ca distanță, încărcare de trafic, aglomerație sau orice valoare aleatorie.

Exemplu de arbore de întindere minim

Să înțelegem arborele de întindere minim cu ajutorul unui exemplu.

Suma marginilor graficului de mai sus este 16. Acum, unii dintre posibilii arbori de acoperire creați din graficul de mai sus sunt -

Deci, arborele de acoperire minim care este selectat din arborii de acoperire de mai sus pentru graficul ponderat dat este -

Aplicații ale arborelui de întindere minim

Aplicațiile arborelui de întindere minim sunt date după cum urmează -

• Arborele de acoperire minim poate fi utilizat pentru a proiecta rețele de alimentare cu apă, rețele de telecomunicații și rețele electrice.
• Poate fi folosit pentru a găsi căi pe hartă.

Algoritmi pentru arborele de acoperire minim

Un arbore de acoperire minim poate fi găsit dintr-un grafic ponderat utilizând algoritmii de mai jos -

• Algoritmul lui Prim
• Algoritmul lui Kruskal

Să vedem o scurtă descriere a ambilor algoritmi enumerați mai sus.

algoritmul lui Prim - Este un algoritm lacom care începe cu un arbore spanning gol. Este folosit pentru a găsi arborele de acoperire minim din grafic. Acest algoritm găsește submulțimea muchiilor care include fiecare vârf al graficului astfel încât suma greutăților muchiilor să poată fi minimizată.

extragerea datelor

Pentru a afla mai multe despre algoritmul primului, puteți face clic pe linkul de mai jos - https://www.javatpoint.com/prim-algorithm

algoritmul lui Kruskal - Acest algoritm este folosit și pentru a găsi arborele de acoperire minim pentru un grafic ponderat conectat. Algoritmul lui Kruskal urmează, de asemenea, o abordare lacomă, care găsește o soluție optimă în fiecare etapă, în loc să se concentreze pe un optim global.

Pentru a afla mai multe despre algoritmul primului, puteți face clic pe linkul de mai jos - https://www.javatpoint.com/kruskal-algorithm

Deci, asta e totul despre articol. Sper că articolul vă va fi util și informativ. Aici, am discutat arborele de întindere și arborele de întindere minim împreună cu proprietățile, exemplele și aplicațiile acestora.