Arbori partiali de cost minim

Previzualizare atestat:

Cuprins atestat:

1. Introducere 3
2. Arbori 4
2.1. Notiuni introductive 4
2.1.1. Proprietati ale arborilor 4
2.1.2. Reprezentarea arborilor 6
2.2. Arbori partiali 8
2.2.1. Arbori partiali de cost minim 9
2.2.2. Algoritmul lui Kruskal 10
2.2.3. Algoritmul lui Prim 13
3. Aplicarea temei in informatica 16
3.1. Generalitati 16
3.2. Notiuni despre program 17
3.3. Resurse utilizate 1?
4. Concluzii finale 18
5. Programul sursa 19
6. Bibliografie 23
7. Cuprins 24

Extras din atestat:

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 :

Bibliografie:

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

Download atestat

Primești atestatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc, pas
Diacritice:
Da
Nota:
10/10 (1 voturi)
Anul redactarii:
2003
Nr fișiere:
3 fisiere
Pagini (total):
25 pagini
Imagini extrase:
25 imagini
Nr cuvinte:
3 816 cuvinte
Nr caractere:
19 850 caractere
Marime:
55.69 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatica
Data publicare:
18.09.2017
Structură de fișiere:
  • RETEA.PAS
  • DATE.PAS
  • Arbori partiali de cost minim.doc
Predat:
Grup Şcolar Bicaz
Profil:
Real
Profesorului:
Prof. Vancea Ioan

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Arbori partiali de cost minim Fie G = <X, V> un graf neorientat conex, unde X este...
Fie G = un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor....
INTRODUCERE 1. Definitii Se numeste arbore orice graf conex si fara cicluri. Arborele partial...
O categorie importanta de grafuri esteaceea in care muchiile sun niste legaturi de tip...
1. Teoria grafurilor 1.1. Notiuni generale de teoria grafurilor Graful = o pereche ordonata de...
Sus!