Arbori Partiali De Cost Minim

Extras din referat Cum descarc?

Fie G =  un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.
Un arbore este un asemenea graf ce nu are cicluri. Fiecare muchie are un cost pozitiv (sau o lungime pozitiva). Pentru a gasi un arbore se pune problema sa gasim o submultime A inclusa in U, astfel incat toate varfurile din X sa ramina conectate atunci cand sunt folosite doar muchii din A.
Numim arbore partial de cost minim acel arbore ce are multimea varfurilor X si a muchiilor A iar suma lungimilor muchiilor din A este minima. Cautam deci o submultime A de cost total minim care sa lege printr-un drum oricare doua noduri din X. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.
Problema conectarii oraselor de cost minim: Se dau n orase precum si costul conectarii anumitor perechi de orase.
Se cere sa se eleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim.
Graful partial  este un arbore si este numit arborele partial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai multi arbori partiali de cost minim si acest lucru se poate verifica pe un exemplu. Vom prezenta doi algoritmi greedy care determina arborele partial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o multime de muchii este o solutie, daca constituie un arbore partial al grafului G, si este fezabila, daca nu contine cicluri. O multime fezabila de muchii este promitatoare, daca poate fi completata pentru a forma solutia optima. O muchie atinge o multime data de varfuri, daca exact un capat al muchiei este in multime. Urmatoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.
Multimea initiala a candidatilor este V. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica fiecarui algoritm.
Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu.
Alegem astfel X 1 muchii.
Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat? Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6. 1. a.
Ordonam crescator (in functie de cost) muchiile grafului: {1,  2}, {2,  3}, {4,  5}, {6,  7}, {1,  4}, {2,  5}, {4,  7}, {3,  5}, {2,  4}, {3,  6}, {5,  7}, {5,  6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1. Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1,  2}, {2,  3}, {4,  5}, {6,  7}, {1,  4}, {4,  7}. La fiecare pas, graful partial  formeaza o padure de componente ...


Fisiere in arhiva (1):

  • Arbori Partiali De Cost Minim
    • Referat.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!