Grafuri ponderate [604916]

Grafuri ponderate

Definiție :
Considerăm ungraf G=(X, U)șiofuncție cost :UR+care asociază fiecărei muchii
(arc) unnumăr realpozitiv (care poate avea semnificația decost, distanță, timp, durată) .
Definiție :
UngrafG=(X,U) pentru care s-adefinit ofuncție costsenumește graf ponderat .
51
Graf
51
Graf ponderat2
36
2415

Matricea ponderilor (matricea costurilor )
c M n x n
c𝑖,𝑗= 0,𝑑𝑎𝑐ă𝑖=𝑗
𝑐𝑜𝑠𝑡𝑖,𝑗,𝑑𝑎𝑐ă𝑖≠𝑗ș𝑖𝑒𝑥𝑖𝑠𝑡ă𝑚𝑢𝑐ℎ𝑖𝑒 𝑎𝑟𝑐𝑑𝑒𝑙𝑎𝑖𝑙𝑎𝑗
∞,î𝑛𝑐𝑎𝑧𝑐𝑜𝑛𝑡𝑟𝑎𝑟
12345
102∞∞3
220615
3∞6024
4∞120∞
5354∞0
51
Graf ponderat2
36
2415
Matricea ponderilor
(costurilor)

Arbore parțial de cost minim

Definiție :
FieG=(X, U)ungrafneorientat conex, cucosturi asociate muchiilor .
Ungrafparțial alluiGcare estearbore (arbore= grafconex șifărăcicluri)senumește arboreparțial .
Unarbore parțial pentru care suma costurilor muchiilor este minimă senumește arbore
parțial decostminim .
Pentru adetermina arborele parțial decostminim asociat unui grafsepoate folosi :
•ALGORITMUL LUI PRIM -dacă graful estememorat subformă dematrice acosturilor
•ALGORITMUL LUI KRUSKAL -dacă graful estememorat prinlista demuchii .

ALGORITMUL LUI PRIM
Sepornește delaunnodoarecare considerat rădăcină șiseconstruiește arborele parțial
decostminim .
Algoritmul esteurmătorul :
Sealege nodul deplecare (acesta vafirădăcina arborelui parțial decostminim)
Înmod repetat sealege unnodneadăugat înarbore care areproprietatea căestelegat de
unul dintre nodurile deja selectate înarbore printr -omuchie decostminim .
Atunci când numaiputem alege noduri atunci :
Aufostadăugate toate nodurile șialgorimul s-aterminat .
Graful nueste conex șiaufostadăugate înarbore toate nodurile dincomponenta conexă a
nodului inițial .Înacest cazsecontinuă cuurmătoarea componentă conexă .
Observație :
Arborele parțial decost minim alunui graf neorientat nueste unic,însă toțiarborii
parțiali decostminim voravea același cost.

51
2
36
2415
12345
102∞∞3
220615
3∞6024
4∞120∞
5354∞0Exemplu :
Considerăm nodul deplecare 4(rădăcina
arborelui)
Cost arbore =0
Alegem muchia decost minim care există între
4șiunaltnod care nueste adăugat înarbore
(muchia( 4,2)=1),deci adăugăm nodul 2.
Cost arbore =1
Alegem muchia decost minim care există între
4sau2șiunaltnod care nueste adăugat în
arbore (muchia( 4,3)=2),deci adăugăm nodul 3.
Cost arbore =1+2=3
Alegem muchia decost minim care există între
4,2sau3șiunaltnodcare nueste adăugat în
arbore (muchia( 2,1)=2),deci adăugăm nodul 1.
Cost arbore =1+2+2=5
Alegem muchia decost minim care există între
4,2,3sau1șiunaltnodcare nueste adăugat
înarbore (muchia( 1,5)=3),deci adăugăm nodul
5.
Cost arbore =1+2+2+3=8
1
2
2
3

Pentru a implementa algoritmul vomutiliza treivectori :
Vectorul caracteristic S definit astfel:
S[i]= 0,𝑑𝑎𝑐ă𝑛𝑜𝑑𝑢𝑙𝑖𝑛𝑢𝑎𝑝𝑎𝑟ț𝑖𝑛𝑒 𝑎𝑟𝑏𝑜𝑟𝑒𝑙𝑢𝑖 𝑑𝑒𝑗𝑎𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑖𝑡
1,𝑑𝑎𝑐ă𝑛𝑜𝑑𝑢𝑙𝑖𝑎𝑝𝑎𝑟ț𝑖𝑛𝑒 𝑎𝑟𝑏𝑜𝑟𝑒𝑙𝑢𝑖 𝑑𝑒𝑗𝑎𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑖𝑡
Vectorul T –definit astfel:
T[i]= valoarea nodul uipărinte al lui i (reconstituirea
arborelui se face pebaza acestui vector);
Vectorul P–vector ceconține pentru fiecare nod costul
arcului de la părinte la el
P[i]=cost( T[i], i).

ALGORITMUL LUI KRUSKAL
Seconstruiește arborele decost minim pornind delanarbori disjuncți (fiecare nodal
grafului esteconsiderat inițial subarbore) .
Subarborii seunesc perând până când seobține unsingur arbore (dacă graful este
conex )saupână când acest lucru numaiesteposibil (dacă graful nuesteconex .
Algoritmul esteurmătorul :
Ordonăm muchiile grafului crescător după cost;
Analizăm perând, înordinea crescătoare a costurilor ,muchiile grafului ;
pentru fiecare muchie analizată :
dacă extremitățile muchiei facparte din același subarbore , muchia se ignoră
dacă extremitățile muchiei facparte din subarbori diferiți , aceștia se vorreuni , iarmuchia
respectivă face parte dinarborele parțial de cot minim

51
2
36
2415
Muchie Cost
1, 2 2
1, 5 3
2, 3 6
2, 4 1
2, 5 5
3, 4 2
3, 5 4Muchiile
grafului sunt:Exemplu :
Fiecare nodalgrafului esteconsiderat inițial subarbore
Cost arbore =0
Alegem muchia (2,4)șiunim ceidoisubarbori .
Cost arbore =1
Alegem muchia (1,2)–cum nodurile 1și2sunt însubarbori diferiți le
putem uni.
Cost arbore =1+2=3
Alegem muchia (3,4)–cum nodurile 3și4sunt însubarbori diferiți le
putem uni.
Cost arbore =1+2+2=5
Alegem muchia (1,5)–cum nodurile 1și5sunt însubarbori diferiți le
putem uni.
Cost arbore =1+2+2+3=8Muchie Cost
2, 4 1
1, 2 2
3, 4 2
1, 5 3
3, 5 4
2, 5 5
2, 3 6Muchiile grafului
ordonate sunt:
12
23