Lucrarea de fata prezinta o aplicatie practica in domeniul constructiei arborilor partiali de cost minim. In practica ne intalnim deseori cu probleme in care dandu-se niste puncte legate intre ele trebuie sa ajungem dintr-o parte in alta cu un cost minim.
Programele de simulare permit experimentarea unor situatii, care ar fi dificil sau imposibil de realizat in practica.
Simularile pot fi mai instructive atunci cand sunt utilizate pentru a ilustra idei si experimente explorate in prealabil prin alte mijloace - idei, teste, discutii, chestionare, etc.
Aceste programe pot fi de asemenea utilizate in economie, in simularea experimentelor care sunt prea costisitoare, complicate sau mari consumatoare de timp.
Simulatoarele asigura simularea unor situatii, modele, in care rezultatele finale sa fie obtinute din deciziile proprii ale utilizatorului.
Ghidati dupa datele furnizate de simulator, se pot selecta anumite optiuni sau alege anumite situatii si apoi se obtin rezultatele deciziilor.
O utilizare in crestere o au simulatoarele grafice prin care se simuleaza grafic diferite procese si fenomene, pastrandu-se totusi, interactiunea dintre utilizator si calculator.
Programul va rezolva configurarea unei retele telefonice intre toate orasele unei tari astfel incat toate orasele sa fie conectate si costul retelei sa fie minim.
2. Arbori
2.1. Notiuni introductive
Exista mai multe moduri echivalente de definire a arborilor. Din punctul de vedere al teoriei grafurilor numim arbore un graf neorientat conex si fara cicluri. Daca graful este aciclic, dar nu este conex il vom numi padure.
De exemplu,
Fig. 1.
a. este arbore, b. este padure, nefiind conex, iar c. nu este nici arbore, nici padure, deoarece contine cicluri.
2.1.1. Proprietati ale arborilor
Teorema 1
Fie G ? (V, U) un graf neorientat. Urmatoarele afirmatii sunt echivalente:
1) G este arbore.
2) Oricare doua varfuri din G sunt unite printr-un lant simplu unic.
3) G este conex minimal (daca suprimam o muchie, graful obtinut este neconex).
4) G este conex si are - V- -1 muchii.
5) G este aciclic si are - V- -1 muchii.
6) G este aciclic maximal (daca adaugam o muchie, graful obtinut contine cicluri).
Teorema 2
Numerele intregi 0 < d1 ? d2 ? ? dn (n ? 2) sunt gradele varfurilor unui arbore daca si numai daca d1?d2? ?dn ? 2.n-2.
Demonstratia acestei teoreme ofera si o solutie constructiva pentru obtinerea unui arbore cu secventa gradelor data.
Vom retine gradele varfurilor intr-un vector d de dimensiune n, ordonat crescator, cu suma componentelor egala cu 2.n-2.
Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu doua linii si n-1 coloane, in care pentru fiecare muchie din arbore vom retine extremitatile.
Spre deosebire de ideea din demonstratie, pentru a conserva ordinea in vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 si nu ultimul.
De exemplu, pentru n ?11 si sirul gradelor:
1 2 3 4 5 6 7 8 9 10 11
1 1 1 1 1 1 1 2 3 4 4
obtinem arborele din figura 4.
Fig. 4
Acest procedeu sugereaza o metoda foarte eficienta de reprezentare a arborilor. Daca An este un arbore cu varfurile x1, x2, , xn, suprimam varful terminal cu cel mai mic indice si muchia incidenta cu acesta si retinem a1, varful adiacent cu varful terminal suprimat. Am obtinut astfel un subgraf cu n-2 muchii conex si aciclic, deci un arbore An-1. Repetam procedeul pentru arborele An-1, determinand un al doilea varf, a2, adiacent cu varful terminal de indice minim ce va fi eliminat din An-1 impreuna cu muchia incidenta cu el s.a.m.d., pana cand se obtine un arbore A2 cu doua varfuri adiacente.
2.1.2. Reprezentarea arborilor
Reprezentarea cu referinte descendente
Informatie Fiu1 Fiu2 Fiun
Pentru fiecare nod din arbore vom retine informatia asociata nodului si referinte catre fiii sai. Daca presupunem ca gradul oricarui nod este cel mult egal cu n, putem reprezenta referintele spre fii printr-un vector cu n componente.
Structura unui nod va fi :
B. Patrut, M. Milosescu, Informatica (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 Ivasc, Mona Pruna, Bazele informaticii (cls a X-a) ed. Petrion, Bucuresti, 1995
Tudor Sorin, Informatica (cls a XI-a), ed. L&S Infomat
Primești atestatul în câteva minute,
cu sau fără cont
Ai gasit ceva în neregulă cu acest document?
