ARBORI PARTIALI DE COST MINIM REFERAT SCOALA

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.