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 Ultima versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-05 [2017/03/19 02:12] mihai.iacov [5. Exerciţii] |
laboratoare:laborator-05 [2017/03/23 23:03] iulian.matesica |
||
---|---|---|---|
Linia 15: | Linia 15: | ||
====2.2 Structură==== | ====2.2 Structură==== | ||
- | |||
- | #poate o poza si continuare cu exemplu rezolvat# | ||
Un graf are următoarele elemente: | Un graf are următoarele elemente: | ||
Linia 58: | Linia 56: | ||
<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ţ elementar** un lanţ în care nu se repetă vârfuri. | ||
Linia 201: | Linia 200: | ||
- primeşte un şir de noduri şi afişează matricea de adiacenţă a subgrafului format cu nodurile respective | - 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: | - afişează matricea de adiacenţă a unui graf orientat construit astfel: | ||
- | * graful orientat are atâtea arce câte muchii are graful | + | * graful orientat are atâtea arce câte muchii are graful |
* există arc în graful orientat între două noduri daca şi numai dacă există muchie între aceleaşi noduri în 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? | * 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. | 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:// | ||
+ | |||
+ | === 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). |