Graficul G = (X.A) se numește încărcat. dacă pentru fiecare margine (xi, xj) este definită lungimea (sau greutatea) cij.
Fie G un grafic încărcat conectat. Sarcina de a construi un arbore minim de spanning este de a găsi un copac din setul de arbori care se întind, pentru care suma lungimilor marginilor este minimă.
Dăm câteva cazuri tipice atunci când devine necesar să construim un arbore minim al unui grafic.
a) Este necesar să se conecteze n orașe cu linii de cale ferată (drumuri, linii electrice, o rețea de conducte etc.), astfel încât lungimea totală a liniilor sau costul să fie minim.
b) Este necesar să se construiască un circuit al unei rețele electrice în care bornele trebuie să fie conectate prin fire de lungime cel puțin comună.
Problema construirii unui arbore minim spanning poate fi rezolvată folosind următorul algoritm.
Algoritmul 3.2 (algoritm Kruskal).
Pasul 1. Setarea valorilor inițiale.
Introducem matricea lungimilor marginilor C ale graficului G.
Pasul 2. Selectați marginea lungimii minime din graficul G. Construiți graficul G2. Se compune dintr-o anumită margine și vârfuri incidente. Pune i = 2.
Pasul 3. Dacă i = n. unde n este numărul de margini ale graficului, apoi terminați lucrarea (problema este rezolvată), altfel treceți la pasul 4.
Pasul 4. Construiți graficul Gi +1 prin adăugarea la graficul Gi a unei noi margini de lungime minimă aleasă între toate marginile lui G. Fiecare dintre ele este incident către un anumit vârf al lui Gi și simultan incidentă la un anumit vertex al lui G. Nu este conținut în Gl. Împreună cu această margine, includem în Gi + 1 și un vârf incident care nu conținea Gi. Aloca i: = i + 1 și mergeți la pasul 3.
Găsim copacul minim de spanning pentru graficul prezentat în Fig. 3.14.
Pasul 1. Setarea valorilor inițiale.
Introducem matricea lungimilor marginilor C:
Pasul 2. Alegeți o margine de lungime minimă. Lungimea minimă a unei muchii este una. Există trei astfel de margini: (x1, x2), (x1, x4), (x2, x4). În acest caz, puteți lua orice. Luăm (x1, X2). Să construim graficul G2. constând dintr-o anumită margine și vârfuri incidente x1 și x2. Am setat i = 2.
Pasul 3. Deoarece n = 5, atunci i ¹ n. mergeți la pasul 4.
Pasul 3. Din moment ce i ¹ n. mergeți la pasul 4.
Pasul 3. Din moment ce i ¹ n. mergeți la pasul 4.
Pasul 3. Deoarece i = n. atunci G5 este arborele minim necesar. Lungimea totală a marginilor este 1 + 1 + 2 + 3 = 7.
Procesul de construire a unui copac minim de spanning este prezentat în Fig. 3.15.
TOPIC 4. POȘTURI DE FUNCȚIE
Articole similare
Trimiteți-le prietenilor: