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
Urmatoarea versiune Ambele părți următoarea reviziune
laboratoare:laborator-06 [2017/03/23 21:28]
mihai.iacov [3. Algoritmul lui Kruskal] 		laboratoare:laborator-06 [2017/03/26 23:54]
mihai.iacov [5. Exerciții de laborator]
Linia 92: Linia 92:
 ===== 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 carora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigure conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale. +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> <file cpp>
Linia 113: Linia 113:
 7 8 2 7 8 2
 </file> </file>
 +
 +==== 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.
 +
 +
 ===== 6. Referințe ===== ===== 6. Referințe =====
   - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]]   - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]]
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