1. Noțiuni introductive Ce este un graf? Un graf este o structură matematică care constă din: Grafuri neorientate Un graf neorientat este un graf în care muchiile nu au direcție, adică {u,v}={v,u}\{u, v\} = \{v, u\}{u,v}={v,u}. Elemente fundamentale: Reprezentarea grafurilor 2. Parcurgerea în adâncime (DFS) Definiție: DFS (Depth-First Search) explorează un graf mergând cât mai…
1. Obiectivele lecției: 2. Ce este un graf orientat? Un graf orientat (sau digraf) este o structură matematică formată din: Proprietăți: 3. Exemple de grafuri orientate (1) → (2) ↑ ↓ (4) ← (3) 4. Reprezentări ale grafurilor orientate 1. Matricea de adiacență (1) → (2) ↑ ↓ (4) ← (3) Matricea de adiacență: 0…
1. Adiacență 1–2 | | 4–3 2. Incidență 1–2 | | 4–3 3. Grad 1–2 | | 4–3 4. Drum 1–2 | | 4–3 5. Circuit 1–2 | | 4–3 6. Implementări în C++ 1. Matricea de adiacență și gradul fiecărui nod #include <iostream> using namespace std; void afisareMatrice(int n, int matrice[100][100]) { for…
1. Graf Parțial 1–2–3 | | 4–5 1–2 3 | 4 2. Subgraf 1–2–3 | | 4–5 1–2 | 5 3. Graf Plin (Graf Dens) 4. Graf Complet 1–2 |\ /| | X | |/ \| 3–4 5. Graf Turneu (1) → (2) ↑ ↘ ↓ (3) ← (4) 6. Graf Bipartit 1–3…
1. Ce este Matricea de Adiacență? Matricea de adiacență este o metodă de reprezentare a unui graf (neorientat sau orientat) folosind o matrice binară AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de noduri din graf. 2. Definiție Pentru un graf G=(V,E)G = (V, E)G=(V,E): 3. Caracteristici 4. Avantaje și Dezavantaje Avantaje Dezavantaje…
1. Ce este Matricea de Incidență? Matricea de incidență este o metodă de reprezentare a unui graf (neorientat sau orientat) utilizând o matrice III de dimensiune ∣V∣×∣E∣|V| \times |E|∣V∣×∣E∣, unde: 2. Definiție Pentru un graf G=(V,E)G = (V, E)G=(V,E): 3. Caracteristici 4. Exemplu pentru Grafuri Neorientate Graf: 1–2 | | 4–3 Reprezentare: Matricea de incidență:…
1. Ce este Lista Nodurilor? Lista nodurilor este o metodă de reprezentare a grafurilor în care se specifică explicit nodurile grafului, iar conexiunile dintre noduri (muchiile sau arcele) sunt tratate separat. Aceasta este o metodă simplă și fundamentală, utilizată adesea ca bază pentru alte tipuri de reprezentări, cum ar fi lista de adiacență sau lista…
1. Ce este Lista Arcelor? Lista arcelor este o metodă de reprezentare a unui graf (neorientat sau orientat) printr-o listă de perechi care descriu conexiunile dintre noduri. Această metodă este utilă pentru a stoca și prelucra graful într-un mod eficient, mai ales atunci când graful este sparse (cu puține conexiuni comparativ cu numărul de noduri)….
1. Ce este Matricea Costurilor? Matricea costurilor este o metodă de reprezentare a unui graf ponderat (orientat sau neorientat) în care fiecare element din matrice reprezintă costul asociat unei muchii sau unui arc dintre două noduri. Dacă nu există o muchie/arc între două noduri, se utilizează o valoare convențională (de obicei infinit ∞\infty∞). 2. Structura…
1. Ce este Matricea Drumurilor? Matricea drumurilor este o metodă de reprezentare a unui graf care indică existenta unui drum între două noduri. Aceasta este o matrice binară PPP de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde: 2. Caracteristici 3. Exemple de Grafuri și Matricea Drumurilor Graf Neorientat Graful: 1–2 | | 4–3 Lista muchiilor: E =…