Arbori parțiali de cost minim

Lucrarea de faţă prezintă o aplicaţie practică în domeniul construcţiei arborilor parţiali de cost minim. În practică ne întâlnim deseori cu probleme în care dându-se nişte puncte legate între ele trebuie să ajungem dintr-o parte în alta cu un cost minim.

Programele de simulare permit experimentarea unor situaţii, care ar fi dificil sau imposibil de realizat în practică.

Simulările pot fi mai instructive atunci când sunt utilizate pentru a ilustra idei şi experimente explorate în prealabil prin alte mijloace - idei, teste, discuţii, chestionare, etc.

Aceste programe pot fi de asemenea utilizate în economie, în simularea experimentelor care sunt prea costisitoare, complicate sau mari consumatoare de timp.

Simulatoarele asigură simularea unor situaţii, modele, în care rezultatele finale să fie obţinute din deciziile proprii ale utilizatorului.

Ghidaţi după datele furnizate de simulator, se pot selecta anumite opţiuni sau alege anumite situaţii şi apoi se obţin rezultatele deciziilor.

O utilizare în creştere o au simulatoarele grafice prin care se simulează grafic diferite procese şi fenomene, păstrându-se totuşi, interacţiunea dintre utilizator şi calculator.

Programul va rezolva configurarea unei reţele telefonice între toate oraşele unei ţări astfel încât toate oraşele să fie conectate şi costul reţelei să fie minim.

2. Arbori

2.1. Noţiuni introductive

Există mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex şi fără cicluri. Dacă graful este aciclic, dar nu este conex îl vom numi pădure.

De exemplu,

Fig. 1.

a. este arbore, b. este pădure, nefiind conex, iar c. nu este nici arbore, nici pădure, deoarece conţine cicluri.

2.1.1. Proprietăţi ale arborilor

Teorema 1

Fie G  (V, U) un graf neorientat. Următoarele afirmaţii sunt echivalente:

1) G este arbore.

2) Oricare două vârfuri din G sunt unite printr-un lanţ simplu unic.

3) G este conex minimal (dacă suprimăm o muchie, graful obţinut este neconex).

4) G este conex şi are - V- -1 muchii.

5) G este aciclic şi are - V- -1 muchii.

6) G este aciclic maximal (dacă adăugăm o muchie, graful obţinut conţine cicluri).

Teorema 2

Numerele întregi 0 < d1  d2   dn (n  2) sunt gradele vârfurilor unui arbore dacă şi numai dacă d1d2 dn  2.n-2.

Demonstraţia acestei teoreme oferă şi o soluţie constructivă pentru obţinerea unui arbore cu secvenţa gradelor dată.

Vom reţine gradele vârfurilor într-un vector d de dimensiune n, ordonat crescător, cu suma componentelor egală cu 2.n-2.

Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu două linii şi n-1 coloane, în care pentru fiecare muchie din arbore vom reţine extremităţile.

Spre deosebire de ideea din demonstraţie, pentru a conserva ordinea în vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 şi nu ultimul.

De exemplu, pentru n 11 şi şirul gradelor:

1 2 3 4 5 6 7 8 9 10 11

1 1 1 1 1 1 1 2 3 4 4

obţinem arborele din figura 4.

Fig. 4

Acest procedeu sugerează o metodă foarte eficientă de reprezentare a arborilor. Dacă An este un arbore cu vârfurile x1, x2, , xn, suprimăm vârful terminal cu cel mai mic indice şi muchia incidentă cu acesta şi reţinem a1, vârful adiacent cu vârful terminal suprimat. Am obţinut astfel un subgraf cu n-2 muchii conex şi aciclic, deci un arbore An-1. Repetăm procedeul pentru arborele An-1, determinând un al doilea vârf, a2, adiacent cu vârful terminal de indice minim ce va fi eliminat din An-1 împreună cu muchia incidentă cu el ş.a.m.d., până când se obţine un arbore A2 cu două vârfuri adiacente.

2.1.2. Reprezentarea arborilor

Reprezentarea cu referinţe descendente

Informaţie Fiu1 Fiu2 Fiun

Pentru fiecare nod din arbore vom reţine informaţia asociată nodului şi referinţe către fiii săi. Dacă presupunem că gradul oricărui nod este cel mult egal cu n, putem reprezenta referinţele spre fii printr-un vector cu n componente.

Structura unui nod va fi :

B. Pătruţ, M. Miloşescu, Informatică (cls a IX-a), ed. Teora, 1999

Tudor Sorin, Turbo Pascal (cls a IX-a), ed. L&S Infomat

Internet

Turbo Pascal 6.0, Ghid de utilizare, ed.Microinformatica

Cornelia Ivaşc, Mona Prună, Bazele informaticii (cls a X-a) ed. Petrion, Bucureşti, 1995

Tudor Sorin, Informatică (cls a XI-a), ed. L&S Infomat