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 =…
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…