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/23 13:20]
florina_elena.barbu [4. Algoritmul lui Prim] 		laboratoare:laborator-06 [2017/03/30 22:27]
iulian.matesica
Linia 67: Linia 67:
  
 {{ :laboratoare:kruskal.gif?900 |}} {{ :laboratoare:kruskal.gif?900 |}}
 +
 +
 +{{ :laboratoare:kruskal2.gif?900 |}}
 ===== 4. Algoritmul lui Prim ===== ===== 4. Algoritmul lui Prim =====
  
Linia 83: Linia 86:
  
 {{ :laboratoare:prim.gif?900 |}} {{ :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