Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Ești aici: Structuri de date și algoritmi » Laboratoare » Laborator 06: Introducere în teoria grafurilor
Traseu:
laboratoare:laborator-06

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune 		Versiuni anterioare
Ultima versiune Ambele părți următoarea reviziune
laboratoare:laborator-06 [2017/03/21 02:09]
mihai.iacov [2.3 Arbore vs. pădure de acoperire de cost minim] 		laboratoare:laborator-06 [2017/03/30 22:27]
iulian.matesica
Linia 37: Linia 37:
 ==== 2.2 Arborele văzut ca graf ==== ==== 2.2 Arborele văzut ca graf ====
 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**. 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**.
-==== 2.3 Arbore vs. pădure de acoperire de cost minim ====+==== 2.3 Arbore vs. pădure de acoperire ====
 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). 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. 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.
 +
 +==== 2.4 Arbore de cost minim ====
 +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ă.
 ===== 3. Algoritmul lui Kruskal ===== ===== 3. Algoritmul lui Kruskal =====
  
 +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**.
 +
 +<note tip>
 +Algoritmul funcționează în felul următor:
 +
 +  *  creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat
 +  *  creează o mulțime S care conține toate muchiile din graf
 +  *  atât timp cât S este nevidă
 +      * elimină o muchie de cost minim din S
 +      * dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur
 +      * altfel, ignoră muchia
 +
 +</note>
 +
 +{{ :laboratoare:kruskal.gif?900 |}}
 +
 +
 +{{ :laboratoare:kruskal2.gif?900 |}}
 ===== 4. Algoritmul lui Prim ===== ===== 4. Algoritmul lui Prim =====
  
 +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. 
 +
 +<note tip>
 +Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile.
 +
 +    * Intrare: Un graf conex ponderat cu nodurile V și muchiile E.
 +    * Initializare: Vnou = {x}, unde x este un nod arbitrar (punct de plecare) din V, Enou= {} repetă până când Vnou=V:
 +        * Alege muchia (u,v) din E de cost minim astfel încât u este în Vnou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
 +        * Se adaugă v la Vnou, (u,v) la Enou
 +    * Ieșire: Vnou și Enou descriu arborele parțial de cost minim
 +
 +</note>
 +
 +{{ :laboratoare:prim.gif?900 |}}
 +
 +
 +
 +{{ :laboratoare:prim2.gif?900 |}}
 ===== 5. Exerciții de laborator ===== ===== 5. Exerciții de laborator =====
 +
 +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. 
 +
 +<file cpp>
 +# 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
 +</file>
 +
 +====5.1. Exerciții - schelet de laborator====
 +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 
 +
 +=== Linux===
 +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%%''.
 +
 +
 +==== Extra ====
 +  - Se dă un graf care coincide cu un arbore minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ce va fi scoasă.
 +  - Se dă un graf care coincide cu un arbore minim de acoperire şi un vector(V) cu K noduri din graf. Care este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V).
 +  - Se dă un graf care coincide cu un arbore minim de acoperire şi un nod auxiliar care formează doar două muchii. Verificaţi dacă folosirea nodului auxiliar pentru a conecta nodurile duce la un arbore de acoperire cu un cost mai mic.
  
  
laboratoare/laborator-06.txt · Ultima modificare: 2018/02/25 22:43 de către mihai.iacov

Unelte pagină

Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki