O componentă conexă a unui graf neorientat este un subgraf cu următoarele proprietăţi:
Un graf neorientat este numit conex dacă are o singură componentă conexă.
Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor arcelor cu muchii. Atunci un graf orientat este slab conex dacă graful neorientat asociat acestuia este conex.
Un graf orientat este tare conex dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
Se pot defini similar componentele slab conexă şi tare conexă.
Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru simplitate, fie neorientat) conex şi cu număr minim de muchii, prin urmare, aciclic.
Pentru un graf neorientat, construirea unui arbore de acoperire(nu neapărat de cost minim) presupune construirea unui arbore care să fie graf parţial(să acopere toate nodurile).
Acest lucru este posibil numai dacă graful este conex. În caz contrar, se poate construi câte un arbore de acoperire pentru fiecare componentă conexă a grafului, spunând că se construieşte o pădure de acoperire pentru graf.
Dacă fiecare muchie dintr-un arbore are un cost(o pondere), atunci costul arborelui este dat de suma costurilor muchiilor ce formează arborele.
Dacă, pe acelaşi principiu, fiecare muchie dintr-un graf are un cost, atunci alegerea unui arbore minim de acoperire presupune alegerea unui arbore care să acopere toate nodurile şi care să folosească muchiile ce dau suma costurilor minimă.
Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat.
Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului.
Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de algoritm greedy.
Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat.
1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale.
# explicatii format # n=numar varfuri m=numar muchii # m randuri, cate unul pentru fiecare muchie: start end cost 8 13 1 2 4 1 3 9 1 4 1 1 6 7 2 3 12 2 4 4 3 8 13 4 5 7 4 6 8 5 6 3 5 7 6 5 8 5 7 8 2
Pentru acest laborator puteți descărca scheletul de cod de aici. Descărcați arhiva și dezarhivați-o.
Puteti folosi utilitarul wget
pentru descarcare si utilitarul unzip
pentru dezarhivare.
wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip
unzip lab6_arbori_min-skel.zip
Pentru compilare folositi comanda make
. Pentru rulare puteti folosi comanda make run
sau ./graph
.