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 Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-05 [2017/03/18 13:00] florina_elena.barbu [Laborator 06: Introducere în teoria grafurilor] |
laboratoare:laborator-05 [2017/03/19 02:34] mihai.iacov [5. Exerciţii] |
||
---|---|---|---|
Linia 21: | Linia 21: | ||
* **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului | * **Mulțimea nodurilor X** - Mulțimea tuturor nodurilor grafului | ||
* **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului | * **Multimea muchiilor U** - Mulțimea tuturor muchiilor grafului | ||
- | * **Gradul nodului** - Suma muchiilor | + | * **Gradul nodului** - numărul de muchii |
* **Nod izolat** - Un nod ce nu formează nici-o muchie | * **Nod izolat** - Un nod ce nu formează nici-o muchie | ||
* **Noduri terminale** - Un nod ce formează o singură muchie | * **Noduri terminale** - Un nod ce formează o singură muchie | ||
* **Noduri adiacente** - Noduri intre care există o muchie | * **Noduri adiacente** - Noduri intre care există o muchie | ||
* **Nod si muchie incidente** - Nodul face parte dintr-o muchie | * **Nod si muchie incidente** - Nodul face parte dintr-o muchie | ||
+ | |||
+ | <note important> | ||
+ | <note important> | ||
\\ | \\ | ||
\\ | \\ | ||
Linia 56: | Linia 59: | ||
<note importante> | <note importante> | ||
Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1, | Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1, | ||
+ | |||
+ | Se numeşte **lanţ elementar** un lanţ în care nu se repetă vârfuri. | ||
+ | |||
+ | Se numeşte **lanţ simplu** un lanţ în care nu se repetă muchii. | ||
+ | |||
+ | 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). | ||
</ | </ | ||
Linia 65: | Linia 76: | ||
====3.2 Structură==== | ====3.2 Structură==== | ||
- | poza | + | Într-un graf orientat, distingem: |
- | \\ | + | * **gradul interior/ |
+ | * **gradul exterior/ | ||
+ | |||
+ | <note important> | ||
====3.3 Reprezentare==== | ====3.3 Reprezentare==== | ||
Linia 90: | Linia 104: | ||
* nodul sursă (considerat a fi pe nivelul 0) | * nodul sursă (considerat a fi pe nivelul 0) | ||
* vecinii nodului sursă (reprezentând nivelul 1) | * vecinii nodului sursă (reprezentând nivelul 1) | ||
- | * vecinii încă nevizitați ai nodurilot | + | * vecinii încă nevizitați ai nodurilor |
* ș.a.m.d | * ș.a.m.d | ||
Linia 150: | Linia 164: | ||
====4.2.1 Implementare==== | ====4.2.1 Implementare==== | ||
- | <code> | + | Spre deosebire de BFS, DFS utilizează o **stivă** în loc de o coadă. Putem defini o stivă sau ne putem folosi de **stiva compilatorului**, |
- | Cod | + | |
- | </code> | + | <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 orientat | ||
+ | * 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. | ||
+ | |||
+ | ====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). |