Algoritmul lui Kruskal Optimizare combinatorie

Previzualizare referat:

Extras din referat:

Joseph Kruskal s-a nascut la New York in 29 ianuarie 1928 si a decedat in 19 septembrie 2010. A fost un american matematician, statiscian, om de stiinta in domeniul calculatoarelor. El a trait 82 de ani si a scris algoritmul in 1956.

Este un algoritm in teoria grafurilor care gaseste arborele partial de cost minim pentru un graf conex ponderat (graf in care fiecare muchie are asociat un cost). Cu alte cuvinte, gaseste submultimea muchiilor care formeaza un arbore care include toate varfurile si care este minimizat din punct de vedere al costului. Daca graful nu este conex, atunci algoritmul gaseste un arbore partial de cost minim pentru fiecare componenta conexa. Algoritmul lui Kruskal este un exemplu de algoritm greedy.

Descrierea algoritmului:

- se ordoneaza muchiile grafului dupa cost

- se porneste in construire de la graful partial care contine toate nodurile izolate

- se adauga pe rand n-1 muchii in graf (in ordinea crescatoare a costurilor) urmarind ca fiecare muchie adaugata sa nu formeze un ciclu

Consideram un graf neorientat ponderat (cu costuri) conex G. Se numeste arbore partial un graf partial al lui G care este arbore. Se numeste arbore partial de cost minim un arbore partial pentru care suma costurilor muchiilor este minima.

Daca graful nu este conex, vorbim despre o padure partiala de cost minim.

Algoritmul lui Kruskal permite determinarea unui arbore partial de cost minim (APM) intr-un graf ponderat cu N noduri.

Acesta este graful original. Numerele de pe muchii reprezinta costul acestora. Nici o muchie nu este evidentiata.

Intrare: Un graf conex neorientat G cu ponderile c: E(G) - R.

Iesire: Un arbore indus T cu pondere minima.

(1) Sortati muchiile astfel incat c(e1) <= c(e2) <= ... <= c(em).

(2) Setati T: = (V (G), ?).

(3) Pentru i: = 1 pana la m faceti:

Daca T + ei nu contine niciun circuit, atunci setati T: = T + ei.

Teorema 3. Algoritmul lui Kruskal functioneaza corect.

Este clar ca algoritmul construieste un arbore T indus. De asemenea, garanteaza conditia (b) a teoremei 2, deci T este optima.

Durata de functionare a algoritmului lui Kruskal este O (mn): muchiile pot fi sortate in timp O (m log m) (teorema 1.5) si testarea unui circuit intr-un graf cu cel mult n muchii poate fi implementat in O(n) timp (aplicati doar DFS (sau BFS) si verificati daca exista vreo muchie care nu apartine arborelui DFS). Deoarece acest lucru se repeat m ori, obtinem un timp total de functionare de O (m log m + mn) = O (mn). Cu toate acestea, este posibila o implementare mai eficienta:

Download referat

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

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Da
Nota:
7/10 (1 voturi)
Anul redactarii:
2020
Nr fișiere:
1 fisier
Pagini (total):
7 pagini
Imagini extrase:
7 imagini
Nr cuvinte:
1 663 cuvinte
Nr caractere:
7 354 caractere
Marime:
76.64 KB (arhivat)
Nivel studiu:
Facultate
Tip document:
Referat
Domeniu:
Statistica
Data publicare:
31.03.2021
Structură de fișiere:
  • Algoritmul lui Kruskal Optimizare combinatorie.doc
Predat:
la facultate
Specializare:
Informatică aplicată în tehnologie și științe
Materie:
Dezvoltare web
An de studiu:
I

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Capitolul 1 INTRODUCERE Pentru notiunile din acest paragraf am consultat Behzad, Chartrand,...
ste inutil sa mai spunem ca traim astazi intr-o era a informaticii si a calculatoarelor. Ceea ce...
Acest manual este dedicat in special studentilor de la formele de invatamant ID (invatamant la...
Avand in vedere ca, in abordarea procedurala a programarii, este valabila relatia Program =...
Sus!