Î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ă -
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 nn-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 55-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 nn-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.