Unelte utilizator

Unelte site


laboratoare:laborator-06

Diferențe

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

Link către această vizualizare comparativă

Both sides previous revision Versiuni anterioare
laboratoare:laborator-06 [2017/03/30 19:27]
iulian.matesica
laboratoare:laborator-06 [2018/02/25 20:43] (curent)
mihai.iacov
Linia 1: Linia 1:
-====== Laborator 06: Arbori minimi de acoperire ​======+====== Laborator 06: Introducere în teoria grafurilor ​======
  
-===== 1. Obiective laborator===== +\\ 
-  Înțelegerea conceptului de arbore minim de acoperire ​ +=====1 ​Obiectivele laboratorului===== 
-  Înțelegerea implementării algoritmilor care determină acest arbore +*Definirea structurii și elementelor unui graf neorientat 
-  * Înțelegere aplicațiilor practice în: +*Definirea structurii și elementelor ​unui graf orientat
-    * rețele de calculatoare:​ obținerea ​unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri) +
-    * prelucrarea de imagine: segmentarea cadrelor (ex: folosită în analiza medicală) +
-    * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore,​ inel)+
  
-{{ :​laboratoare:​segmentation.jpg?​600 | Segmentarea de imagini}} 
  
-===== 2. Introducere ===== 
  
-==== 2.1 Conexitate în grafuri ​====+=====2 Grafuri neorientate===== 
 +====2.1 ​Definiție==== 
 +Un **graf neorientat** este o pereche ordonată de multimi(X,​U),​unde:​ 
 +*X este o mulțime finită și nevidă de elemente numite **noduri** sau **vârfuri** 
 +*U este o mulțime de perechi neordonate din X,numite **muchii**
  
-===Componentă conexă=== +====2.2 Structură====
-O componentă conexă a unui graf **neorientat** este un subgraf cu următoarele proprietăţi:​ +
-  - oricare două noduri din acest subgraf sunt **conectate**(există un lanţ între ele) +
-  - orice nod din acest subgraf **NU este conectat** cu niciun nod din afara subgrafului(nodurile din componentă fac muchii numai cu alte noduri din componentă)+
  
-<note important>​Orice ​graf neorientat ​are cel puţin ​componentă conexă.</​note>​+Un graf are următoarele elemente: 
 +* **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului 
 +* **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului 
 +* **Gradul nodului** - numărul de muchii formate cu ajutorul nodului respectiv 
 +* **Nod izolat** - Un nod ce nu formează nici-muchie 
 +* **Noduri terminale** - Un nod ce formează o singură muchie 
 +* **Noduri adiacente** - Noduri intre care există o muchie 
 +* **Nod si muchie incidente** - Nodul face parte dintr-o muchie
  
-===Graf ​neorientat ​conex=== +<note important>​Ce relaţie există între suma gradelor tuturor vârfurilor dintr-un graf neorientat ​şi numărul de muchii?</​note>​ 
-Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**.+<note important>​Într-un ​graf **complet**, oricare două noduri sunt adiacente. Câte muchii ​are un astfel de graf?</​note>​ 
 +\\  
 +\\ 
  
-<note tip>​Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere ​a grafului(DFS sau BFS).</​note>​+====2.3 Reprezentare ==== 
 +* **Matricea de adiacență** ​este matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel: 
 +   ​*a[i,​j] = 1 ,dacă ∃ muchia [i,j] cu i≠j 
 +   *a[i,j] = 0 ,în caz contrar 
 +* **Lista de adiacență** - este un tablou de liste egal cu numarul de varfuri;​dacă există o muchie intre nodul curent si un alt nod,atunci acesta se trece în listă 
 +* **Vectorul de muchii** - mulțime ce conține toate muchiile ​grafului
  
-===Graf orientat slab conex=== +{{ :​laboratoare:​graf1.jpg?500 |}}
-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.+
  
-===Graf orientat tare conex=== +Având lista de adiacentă: 
-Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.+   ​* **A**:​B→C→D 
 +   * **B**:​A→D→E 
 +   * **C**:​A→D 
 +   * **D**:​A→B→C→D→E 
 +   * **E**:B→D
  
-Se pot defini similar componentele slab conexă şi tare conexă.+<note importante>​ 
 +Un **graf parțial** este un graf obținut din graful inițial prin eliminarea uneia sau mai multor muchii 
 +</​note>​
  
-==== 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**. 
-==== 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). 
  
-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.+<note importante>​ 
 +Un **subgraf** este un graf obținut din graful inițial prin eliminarea unui număr ​de noduri impreună cu muchiile formate cu acele noduri 
 +</​note>​
  
-==== 2.4 Arbore de cost minim ==== +<note importante>​ 
-Dacă fiecare muchie dintr-un arbore are un **cost**(pondere)atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele.+Se numește ​**lanț** într-un graf,succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,​adică există o muchie între acestea.
  
-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 ===== 
  
-Algoritmul lui Kruskal este un algoritm ​în teoria grafurilor ​care găsește arborele parțial de cost minim pentru un graf conex ponderat+Se numeşte **lanţ elementar** ​un lanţ în care nu se repetă vârfuri.
  
-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+Se numeşte **lanţ simplu** un lanţ în care nu se repetă muchii.
  
-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**.+Se numeşte **ciclu** un lanţ simplu pentru care primul şi ultimul vârf coincid.
  
-<​note ​tip> +Se numeşte **ciclu elementar** un ciclu în care nu se repetă vârfuri(excepţie primul şi ultimul). 
-Algoritmul funcționează în felul următor:+</note>
  
-  ​ ​creează ​pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat +=====3 Grafuri orientate===== 
-   ​creează ​o mulțime ​S care conține toate muchiile din graf +====3.1 Definiție==== 
-  *  atât timp cât S este nevidă +Un **graf orientat** este pereche ordonată de mulțimi G={X,U},unde: 
-      * elimină o muchie de cost minim din S +   ​*X este o mulțime ​finită și nevidă ​numită mulțimea nodurilor(vârfurilor) 
-      dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur +   ​*U este o mulțime formată din **perechi ordonate** de elemente ale lui X,numită mulțimea arcelor
-      ​altfelignoră muchia+
  
-</note>+====3.2 Structură==== 
 +Într-un graf orientat, distingem:​ 
 +  * **gradul interior/intern** al unui nod: numărul de arce care intră în nod 
 +  * **gradul exterior/​extern** al unui nod: numărul de arce care ies din nod
  
-{{ :​laboratoare:​kruskal.gif?900 |}}+<note important>​Ce relaţie există între suma gradelor exterioare, suma gradelor interioare şi numărul de arce?</​note>​
  
 +====3.3 Reprezentare====
 +**Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane,în care elementele **a[i,j]** se definesc astfel:
 +   ​*a[i,​j] = 1 ,dacă ∃ arcul (i,j) în mulțimea U
 +   ​*a[i,​j] = 0 ,în caz contrar
  
-{{ :​laboratoare:​kruskal2.gif?900 |}} +{{ :​laboratoare:​graf2.png?400 |}}
-===== 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> +Matricea **vârfuri-arce** este o matrice **B** cu n = |X| linii și m = |U| coloane,în care fiecare element **b[i,j]** este: 
-Algoritmul incrementează mărimea unui arborepornind de la un nodpână când sunt incluse toate nodurile.+   * **1** ,dacă nodul i este o extremitate inițială a arcului  
 +   * **-1** ​,dacă nodul i este o extremitate finală a arcului  
 +   * **0** ,dacă nodul i nu este o extremitate a arcului
  
-    * IntrareUn graf conex ponderat cu nodurile V și muchiile E. +{{ :laboratoare:​graf3.png?300 |}}
-    * 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>​+=====4 Parcurgerea grafurilor===== 
 +====4.1 Parcurgerea în lățime====
  
-{{ :laboratoare:​prim.gif?900 |}}+Parcurgerea în lățime **(Breadth-First-Search -BFS)** este o metodă ce presupune vizitarea nodurilor în următoarea ordine: 
 +   * nodul sursă (considerat a fi pe nivelul 0) 
 +   * vecinii nodului sursă (reprezentând nivelul 1) 
 +   * vecinii încă nevizitați ai nodurilor de pe nivelul 1 (reprezentând nivelul 2) 
 +   * ș.a.m.d
  
  
 +===4.1.1 Implementare===
  
-{{ :laboratoare:​prim2.gif?​900 |}} +Pe masură ce algoritmul avansează,​se colorează nodurile în felul următor
-===== 5Exerciții de laborator =====+   * **alb** - nodul este nedescoperit încă 
 +   * **gri** - nodul a fost descoperit și este în curs de procesare 
 +   * **negru** - procesarea nodului s-a încheiat 
 +Se păstrează informațiile despre distanța până la nodul sursă. 
 +Se obține arborele BFS 
  
-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+\\ 
 +Pentru implementarea BFS se utilizează o coadă (Qîn care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați,​nodul sursă este scos din coadă.
  
 <file cpp> <file cpp>
-# explicatii format ​ +Pentru fiecare nod u din graf 
-# n=numar varfuri m=numar muchii +
-# m randuricate unul pentru fiecare muchie: start end cost +     ​culoare[u]=alb 
-8 13  ​ +     ​d[u] ​infinit ​   //in d se retine distanta pana la nodul sursa 
-1 2 4  +     p[u] = null       // 
-1 3 9 +
-1 4 1 + 
-1 6 7 +culoare[sursă]=gri 
-2 3 12 +d[sursă]=0 
-2 4 4 +enqueue(Q,sursă) ​    //​punem nodul sursă în coada Q 
-3 8 13 + 
-4 5 7 +Cât timp coada Q nu este vidă 
-4 6 8 +{ 
-5 6 3 +     v=dequeue(Q) ​  //​extragem nodul v din coadă 
-5 7 6 +     pentru fiecare u dintre vecinii lui v 
-5 8 5 +          dacă culoare[u] == alb 
-7 8 2+          { 
 +               culoare[u] = gri 
 +               p[u] = v 
 +               d[u] = d[v] + 1 
 +               enqueue(Q,​u) ​  //​adăugăm nodul u în coadă 
 +          } 
 +     ​culoare[v] = negru   //am terminat explorarea vecinilor lui v 
 +} 
 + 
 </​file>​ </​file>​
 +\\
 +**Exemplu**
 +{{ :​laboratoare:​bfs.jpg |}}
 +
 +====4.2 Parcurgerea în adâncime====
 +Parcurgea în adâncime **(Depth-First-Search -DFS)** presupune explorarea nodurilor în următoarea ordine:
 +   ​*Nodul sursă
 +   ​*Primul vecin nevizitat al nodului sursă (îl numim //V1//)
 +   ​*Primul vecin nevizitat al lui //V1// (îl numim //V2//)
 +   ​*ș.a.m.d
 +   *În momentul în care am epuizat vecinii unui nod //Vn//, continuăm cu următorul vecin nevizitat al nodului anterior,//​Vn-1//​
 +
 +Această metoda de parcurgere pune prioritate pe explorarea **în adâncime** (pe distanțe tot mai mari față de nodul sursă).
 +
 +====4.2.1 Implementare====
 +
 +Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**,​ prin apeluri **recursive**.
 +
 +<file cpp>
 +funcţie pasDFS(curent)
 +{
 + pentru fiecare u dintre vecinii nodului curent
 +          dacă culoare[u] == alb
 +          {
 +               ​culoare[u] = gri
 +               p[u] = curent
 +               d[u] = d[curent] + 1
 +               ​pasDFS(u); ​  //​adăugăm nodul u în "​stivă"​ şi începem explorarea
 +          }
 + culoare[curent] = negru   //am terminat explorarea vecinilor nodului curent
 + //ieşirea din funcţie este echivalentă cu eliminarea unui element din stivă
 +}
 +Pentru fiecare nod u din graf
 +{
 +     ​culoare[u]=alb
 +     d[u] = infinit ​   //in d se retine distanta pana la nodul sursa
 +     p[u] = null
 +}
 +culoare[sursă] = gri;
 +d[sursă] = 0;
 +
 +//se apelează iniţial pasDFS(sursă)
 +
 +</​file>​
 +{{ :​laboratoare:​df1.jpg |}}
 +
 +===== 5. Exerciţii =====
 +Implementaţi,​ pentru fiecare cerinţă, câte o funcţie care:
 +  - creează matricea de adiacenţă pentru un graf neorientat cu N noduri, folosindu-se de o listă(sau o matrice cu 2 coloane) de muchii(la alegere - muchiile citite în funcţie sau primite printr-un parametru).
 +  - calculează gradul fiecărui nod. Afişaţi numărul de noduri izolate şi numărul de noduri terminale.
 +  - primeşte un şir de noduri şi verifică dacă acesta poate reprezenta un lanţ.
 +  - primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective
 +  - afişează matricea de adiacenţă a unui graf orientat construit astfel:
 +    * graful orientat are atâtea arce câte muchii are graful neorientat
 +    * există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în graful neorientat.
 +    * Extra - câte astfel de grafuri orientate pot fi formate?
 +
 +Cerinţele 2, 3, 4 şi 5 se vor folosi de matricea de adiacenţă a grafului de la cerinţa 1.
  
 ====5.1. Exerciții - schelet de laborator==== ====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. ​+Pentru acest laborator puteți descărca scheletul de cod de [[http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab5_grafuri-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. ​
  
 === Linux=== === Linux===
 Puteti folosi utilitarul ''​%%wget%%''​ pentru descarcare si utilitarul ''​%%unzip%%''​ pentru dezarhivare. 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%%''​ +  * ''​%%wget http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab5_grafuri-skel.zip%%''​ 
-  * ''​%%unzip ​lab6_arbori_min-skel.zip%%''​+  * ''​%%unzip ​lab5_grafuri-skel.zip%%''​
  
 Pentru compilare folositi comanda ''​%%make%%''​. Pentru rulare puteti folosi comanda ''​%%make run%%''​ sau ''​%%./​graph%%''​. Pentru compilare folositi comanda ''​%%make%%''​. Pentru rulare puteti folosi comanda ''​%%make run%%''​ sau ''​%%./​graph%%''​.
  
 +====De interviu====
 +  * Plecând dintr-un nod K, verificaţi dacă puteţi găsi un ciclu în graf.
 +  * Verificaţi dacă există un lanţ care uneşte nodurile sursă(S) şi destinaţie(D). Dacă există, cum puteţi găsi lanţul cu număr minim de muchii?
 +  * Verificaţi dacă există un lanţ **hamiltonian** în graf.
 +  * Verificaţi dacă există un lanţ **eulerian** în graf.
 +  * Verificaţi dacă o muchie dată (A, B) este un **pod** pentru drumul de la S la D.
  
-==== Extra ==== +Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare ​nod.
-  - 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.+
  
 +Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie.
  
-===== 6Referințe ===== +Spunem că muchia (A, B) este pod pentru drumul de la S la D dacă orice lanţ care duce de la S la D trece prin muchia (A, B).
-  - [[https://​en.wikipedia.org/​wiki/​Minimum_spanning_tree|Minimum spanning tree]] +
-  - [[https://​en.wikipedia.org/​wiki/​Kruskal%27s_algorithm|Algoritmul lui Kruskal]] +
-  - [[https://​en.wikipedia.org/​wiki/​Prim%27s_algorithm|Algoritmul lui Prim]] +
-  - [[http://​www.bogdanturcanu.ro/​spanning-tree-protocol-stp/​|Protocolul STP]] +
-  - [[https://​en.wikipedia.org/​wiki/​Image_segmentation|Segmentarea de imagini]]+
laboratoare/laborator-06.txt · Ultima modificare: 2018/02/25 20:43 de către mihai.iacov