Algoritmi de Determinare a Arborilor Partiali de Cost Minim

Extras din referat Cum descarc?

INTRODUCERE
1. Definitii
Se numeste arbore orice graf conex si fara cicluri. Arborele partial al unui graf conex G este un graf partial al lui G, care este arbore.
Un graf (neorientat) si fara cicluri se numeste padure.
Componentele conexe ale unei paduri vor fi arbori. Un arbore cu n varfuri are n-1 muchii.
2. Problema arborelui partial de cost minim
Fie G = (V, E) un graf neorientat conex, unde V este multimea nodurilor si E este multimea muchiilor. Fiecarei muchii u din E ii asociem un cost c(u) > 0.
Problema consta in a determina un graf partial conex A = ( V, E' ) astfel incat suma costurilor muchiilor din E' sa fie minima. Se observa ca graful partial de cost minim este chiar un arbore. Intr-adevar A este conex. Daca A ar contine un ciclu, se obtine tot un graf partial conex, avand insa un cost mai mic. Deci, A este un arbore.
O problema economica ce conduce la problema arborelui partial de cost minim este cea a conectarii oraselor cu cost minim:
Se dau n orase precum si costul conectarii anumitor perechi de orase. Se cere sa se aleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total al cuplarii sa fie minim.
Dupa modelarea matematica necesara, o astfel de problema se reduce la o problema clasica de teoria grafurilor, deoarece costul unei muchii (i, j) reprezinta costul conectarii directe a oraselor i si j, iar arborele partial de cost minim reprezinta modalitatea optima de a lega direct perechi de orase astfel incat in final orice oras sa fie conectat direct sau indirect cu toate celelalte.
Construirea arborelui partial de cost minim este permisa de catre metoda 
Greedy. El poate fi obtinut fie prin algoritmul lui Kruskal, fie prin algoritmul lui Prim.
ALGORITMUL LUI KRUSKAL
Algoritmul lui Kruskal este una dintre metodele cunoscute de rezolvare a problemei determinarii arborelui partial de cost minim. Pasii acestui algoritm sunt urmatorii:
-se alege intai muchia de cost minim,
-se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu,
-se vor alege n-1 muchii. 
(a) (b)
(c) (d)
(e)
Figura 1- Arborele partial de cost minim obtinut prin algoritmul lui Kruskal


Fisiere in arhiva (1):

  • Algoritmi de Determinare a Arborilor Partiali de Cost Minim.doc

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!