Determinarea Arborelui Parțial de Cost Minim

1. Teoria grafurilor

1.1. Noţiuni generale de teoria grafurilor

Graful = o pereche ordonată de mulţimi, notată G=(X,U);

Unde: X - este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri;

U - este o mulţime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate).

Obs:

• graful orientat are noduri şi arce;

• graful neorientat are vârfuri şi muchii;

• un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor sau nodurilor) şi din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor);

• drum într-un graf = o succesiune de muchii adiacente şi distincte care conectează două vârfuri din graf (numite capetele drumului);

• drum simplu = un drum în care muchiile care îl compun sunt distincte

• ciclu = un drum care are drept capete un acelaşi vârf;

• ciclu hamiltonian = un ciclu simplu ce trece prin toate vârfurile sau nodurile grafului G, exact o dată;

• ciclu eulerian = un ciclu simplu ce trece prin toate muchiile grafului G, exact o dată;

• spunem că S este un subgraf al lui G, dacă acesta conţine o parte din vârfurile lui G şi numai acele muchii care le conectează;

• graf conex = dacă între oricare două vârfuri ale acestuia există cel puţin un drum;

• arbore = un graf conex şi fără cicluri.

2. Metode de determinare a arborelui partial de cost minim

Aplicatie:

Se consideră un post de transformare 1 care trebuie sa alimenteze cu energie electrică 7 consumatori. Legăturile posibile între sursă şi consumatori , respectiv între consumatori şi consumatori sunt prezentate în fig. 1.a. . pe fiecare muchie s-a marcat costul liniei electrice în unitţi relative, u.r..

Se cere să se determine configuraţia optimă a reţelei electrice astfel încât costul liniilor electrice să fie minim.

1.a 1.b

2.1. Algoritmul Prim

Rezolvare:

1. – matricea costurilor a[i, j]=

0 50 25 140 70 45 95 170

0 40 125 105 0 0 0

0 65 0 30 0 70

0 0 35 0 75

0 0 95 0

0 80 15

0 65

0

2. – construcţia arborelui de cost minim prin algoritmul lui Prim

- Se consideră 3 vectorii:

• s[i]= vector caracteristic, are val. 1 dacă vf. i a fost inclus în arbore şi 0 altfel;

• t[i]= vectorul părintelui, conţine vf. părinte a lui i în arbore;

• c[i]= vectorul costurilor, conţine valoarea costului muchiei ce îl leagă pe i de părintele său .