Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
laboratoare:laborator-06 [2017/03/23 13:28] florina_elena.barbu [5. Exerciții de laborator] |
laboratoare:laborator-06 [2018/02/25 22:43] 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 |
- | * Î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 |
- | * rețele de calculatoare: | + | |
- | * 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, | + | |
- | {{ : | ||
- | ===== 2. Introducere ===== | ||
- | ==== 2.1 Conexitate în grafuri | + | =====2 Grafuri neorientate===== |
+ | ====2.1 | ||
+ | Un **graf neorientat** este o pereche ordonată de multimi(X, | ||
+ | *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> | + | 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-o 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 | + | <note important> |
- | Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**. | + | <note important> |
+ | \\ | ||
+ | \\ | ||
- | <note tip> | + | ====2.3 Reprezentare ==== |
+ | * **Matricea de adiacență** | ||
+ | | ||
+ | *a[i,j] = 0 ,în caz contrar | ||
+ | * **Lista de adiacență** - este un tablou de liste egal cu numarul de varfuri; | ||
+ | * **Vectorul de muchii** - mulțime ce conține toate muchiile | ||
- | ===Graf orientat slab 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. | + | |
- | ===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. | + | |
+ | * **B**: | ||
+ | * **C**: | ||
+ | * **D**: | ||
+ | * **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 | ||
+ | </ | ||
- | ==== 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 | + | <note importante> |
+ | Un **subgraf** este un graf obținut din graful inițial prin eliminarea unui număr | ||
+ | </ | ||
- | ==== 2.4 Arbore de cost minim ==== | + | <note importante> |
- | Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele. | + | Se numește |
- | 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 | + | Se numeşte **lanţ elementar** |
- | Cu alte cuvinte, găsește submulțimea muchiilor | + | 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. |
- | < | + | 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> |
- | | + | =====3 Grafuri orientate===== |
- | * | + | ====3.1 Definiție==== |
- | * atât timp cât S este nevidă | + | Un **graf orientat** este o pereche ordonată de mulțimi G={X,U},unde: |
- | * 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 | + | |
- | | + | |
- | </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/ | ||
- | {{ : | + | <note important> |
- | ===== 4. Algoritmul lui Prim ===== | + | |
- | Algoritmul lui Prim este un algoritm din teoria grafurilor | + | ====3.3 Reprezentare==== |
+ | **Matricea de adiacență** - este o matrice **a** cu **n** linii și **n** coloane, | ||
+ | | ||
+ | *a[i,j] = 0 ,în caz contrar | ||
- | <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: | + | |
- | * 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 | + | |
- | </ | + | Matricea **vârfuri-arce** este o matrice **B** cu n = |X| linii și m = |U| coloane,în care fiecare element **b[i,j]** este: |
+ | * **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 | ||
- | {{ : | + | {{ : |
- | ===== 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 | + | =====4 Parcurgerea grafurilor===== |
+ | ====4.1 Parcurgerea în lățime==== | ||
+ | |||
+ | Parcurgerea în lățime **(Breadth-First-Search -BFS)** este o metodă ce presupune vizitarea nodurilor în următoarea ordine: | ||
+ | * nodul sursă (considerat | ||
+ | * 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=== | ||
+ | |||
+ | Pe masură ce algoritmul avansează,se colorează nodurile în felul următor: | ||
+ | * **alb** - nodul este nedescoperit încă | ||
+ | * **gri** - nodul a fost descoperit și este în curs de procesare | ||
+ | * **negru** - procesarea nodului | ||
+ | Se păstrează informațiile | ||
+ | Se obține arborele BFS | ||
+ | |||
+ | \\ | ||
+ | Pentru implementarea BFS se utilizează | ||
<file cpp> | <file cpp> | ||
- | # explicatii format | + | Pentru fiecare nod u din graf |
- | # n=numar varfuri m=numar muchii | + | { |
- | # m randuri, cate unul pentru fiecare muchie: start end cost | + | |
- | 8 13 | + | |
- | 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ă) |
- | 3 8 13 | + | |
- | 4 5 7 | + | Cât timp coada Q nu este vidă |
- | 4 6 8 | + | { |
- | 5 6 3 | + | v=dequeue(Q) |
- | 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, | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | |||
</ | </ | ||
- | ===== 6. Referințe ===== | + | \\ |
- | - [[https://en.wikipedia.org/wiki/Minimum_spanning_tree|Minimum spanning tree]] | + | **Exemplu** |
- | | + | {{ : |
- | | + | |
- | - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]] | + | ====4.2 Parcurgerea în adâncime==== |
- | | + | Parcurgea în adâncime **(Depth-First-Search -DFS)** presupune explorarea nodurilor în următoarea ordine: |
+ | | ||
+ | | ||
+ | | ||
+ | *ș.a.m.d | ||
+ | *În momentul în care am epuizat vecinii unui nod //Vn//, continuăm cu următorul vecin nevizitat al nodului anterior,// | ||
+ | |||
+ | 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**, | ||
+ | |||
+ | <file cpp> | ||
+ | funcţie pasDFS(curent) | ||
+ | { | ||
+ | pentru fiecare u dintre vecinii nodului curent | ||
+ | dacă culoare[u] == alb | ||
+ | { | ||
+ | | ||
+ | p[u] = curent | ||
+ | d[u] = d[curent] + 1 | ||
+ | | ||
+ | } | ||
+ | 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 | ||
+ | { | ||
+ | | ||
+ | d[u] = infinit | ||
+ | p[u] = null | ||
+ | } | ||
+ | culoare[sursă] = gri; | ||
+ | d[sursă] = 0; | ||
+ | |||
+ | //se apelează iniţial pasDFS(sursă) | ||
+ | |||
+ | </file> | ||
+ | {{ : | ||
+ | |||
+ | ===== 5. Exerciţii ===== | ||
+ | Implementaţi, | ||
+ | - 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==== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/ | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | ====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. | ||
+ | |||
+ | Un lanţ hamiltonian este un lanţ elementar(nu se repetă nodurile) care trece prin fiecare nod. | ||
+ | |||
+ | Un lanţ eulerian este un lanţ simplu(nu se repetă muchiile) care trece prin fiecare muchie. | ||
+ | |||
+ | 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). |