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. 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 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 Algoritmul Roy-Warshall? Algoritmul Roy-Warshall este un algoritm utilizat pentru a determina matricea drumurilor într-un graf. Mai exact, acest algoritm determină dacă există un drum între două noduri iii și jjj într-un graf (orientat sau neorientat). 2. Obiectiv 3. Ideea Algoritmului Algoritmul Roy-Warshall se bazează pe conceptul de nod intermediar: 4. Pas cu…
1. Ce este Algoritmul Roy-Floyd? Algoritmul Roy-Floyd (cunoscut și ca Floyd-Warshall) este un algoritm utilizat pentru a determina drumurile minime între toate perechile de noduri dintr-un graf ponderat. Acesta este aplicabil atât pentru grafuri orientate, cât și pentru grafuri neorientate. 2. Obiectiv 3. Ideea Algoritmului Algoritmul Roy-Floyd se bazează pe conceptul de nod intermediar: 4….
1. Ce este Algoritmul lui Dijkstra? Algoritmul Dijkstra este un algoritm de găsire a drumului minim între un nod sursă și toate celelalte noduri dintr-un graf ponderat, orientat sau neorientat. Este eficient pentru grafuri fără greutăți negative. 2. Obiectiv 3. Ideea Algoritmului Algoritmul funcționează pe baza unui proces iterativ: 4. Complexitate 5. Exemplu Graf Ponderat…
1. Ce este Algoritmul lui Prim? Algoritmul Prim este un algoritm utilizat pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat neorientat conectat. Un arbore de acoperire minim este un subgraf care conectează toate nodurile cu costul total minim al muchiilor. 2. Obiectiv 3. Ideea Algoritmului Algoritmul funcționează pe…
1. Ce este Algoritmul lui Kruskal? Algoritmul Kruskal este o metodă pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat, neorientat. Se bazează pe alegerea iterativă a muchiilor cu cea mai mică greutate, asigurându-se că nu se formează cicluri. 2. Obiectiv 3. Ideea Algoritmului Pentru a detecta ciclurile eficient,…