Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-05 [2017/03/18 13:00]
florina_elena.barbu [Laborator 06: Introducere în teoria grafurilor]
+++ laboratoare:laborator-05 [2017/03/23 23:03]
iulian.matesica
@@ Linia 15: / Linia 15: @@
 ====2.2 Structură====
-#poate o poza si continuare cu exemplu rezolvat#
 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** - Suma muchiilor formate cu ajutorul nodului respectiv
+* **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
+<note important>Ce relaţie există între suma gradelor tuturor vârfurilor dintr-un graf neorientat şi numărul de muchii?</note>
+<note important>Într-un graf **complet**, oricare două noduri sunt adiacente. Câte muchii are un astfel de graf?</note>
 \\
 \\
@@ Linia 55: / Linia 56: @@
 <note importante>
-Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea
+Se numește **lanț** într-un graf,o succesiune de vârfuri L={v1,v2,...,vk},cu proprietatea că oricare două vârfuri consecutive sunt adiacente,adică există o muchie între acestea.
+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).
 </note>
@@ Linia 65: / Linia 75: @@
 ====3.2 Structură====
-poza
+Î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
+<note important>Ce relaţie există între suma gradelor exterioare, suma gradelor interioare şi numărul de arce?</note>
 ====3.3 Reprezentare====
@@ Linia 90: / Linia 103: @@
    * nodul sursă (considerat a fi pe nivelul 0)
    * vecinii nodului sursă (reprezentând nivelul 1)
-   * vecinii încă nevizitați ai nodurilot de pe nivelul 1 (reprezentând nivelul 2)
+   * vecinii încă nevizitați ai nodurilor de pe nivelul 1 (reprezentând nivelul 2)
    * ș.a.m.d
@@ Linia 150: / Linia 163: @@
 ====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**, prin apeluri **recursive**.
-Cod
-</code>
+<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====
+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===
+Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.
+  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab5_grafuri-skel.zip%%''
+  * ''%%unzip lab5_grafuri-skel.zip%%''
+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.
+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).

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină