|

Metode de Reprezentare a Grafurilor: Matricea Costurilor 29


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 Matricei Costurilor

  1. Dimensiune:
    Matricea este de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de noduri.
  2. Elementele matricei:
    • C[i][j]=wC[i][j] = wC[i][j]=w, unde www este costul (greutatea) muchiei/arcului (i,j)(i, j)(i,j).
    • C[i][j]=∞C[i][j] = \inftyC[i][j]=∞ dacă nu există muchie/arc între iii și jjj.
  3. Proprietăți:
    • Pentru grafuri neorientate: Matricea este simetrică (C[i][j]=C[j][i]C[i][j] = C[j][i]C[i][j]=C[j][i]).
    • Pentru grafuri orientate: Matricea poate fi asimetrică (C[i][j]≠C[j][i]C[i][j] \neq C[j][i]C[i][j]=C[j][i]).
    • Pentru muchiile/arcele fără cost, se poate utiliza C[i][j]=1C[i][j] = 1C[i][j]=1.

3. Exemple de Grafuri și Matricea Costurilor


Graf Neorientat

Graful:

1–2 (5)

|   |

(3) (2)

|   |

3–4 (4)

Matricea costurilor:

    1   2   3   4

1   0   5   3   ∞

2   5   0   ∞   2

3   3   ∞   0   4

4   ∞   2   4   0


Graf Orientat

Graful:

(1) → (2, 5)

 ↑         ↓

(4, 7) ← (3, 2)

Matricea costurilor:

    1   2   3   4

1   0   5   ∞   ∞

2   ∞   0   2   ∞

3   ∞   ∞   0   7

4   7   ∞   ∞   0


Graf Complet

Un graf complet cu 3 noduri, unde costurile sunt definite:

    1–2 (4)

     \ /

     (3)

Matricea costurilor:

    1   2   3

1   0   4   3

2   4   0   3

3   3   3   0


4. Avantaje și Dezavantaje

AvantajeDezavantaje
Simplu de utilizat pentru calcularea drumurilor minime.Ineficient pentru grafuri sparse (( O(
Acces direct la costul unei muchii (O(1)O(1)O(1)).Necesită o convenție pentru muchiile inexistente (∞\infty∞).
Reprezentare compactă pentru grafuri dense.Crește consumul de memorie pentru grafuri mari.

5. Implementare în C++


1. Matricea costurilor pentru graf neorientat

#include <iostream>

#include <vector>

#define INF 100000 // Valoare convențională pentru infinit

using namespace std;

void afisareMatrice(int n, int matrice[100][100]) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            if (matrice[i][j] == INF)

                cout << „INF „;

            else

                cout << matrice[i][j] << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4; // Numărul de noduri

    int matrice[100][100];

    // Inițializare matrice cu INF

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            matrice[i][j] = (i == j) ? 0 : INF; // Cost 0 pe diagonală

        }

    }

    // Adăugare muchii cu costuri

    matrice[0][1] = matrice[1][0] = 5; // Muchie 1-2, cost 5

    matrice[0][2] = matrice[2][0] = 3; // Muchie 1-3, cost 3

    matrice[1][3] = matrice[3][1] = 2; // Muchie 2-4, cost 2

    matrice[2][3] = matrice[3][2] = 4; // Muchie 3-4, cost 4

    cout << „Matricea costurilor pentru graful neorientat:\n”;

    afisareMatrice(n, matrice);

    return 0;

}


2. Matricea costurilor pentru graf orientat

#include <iostream>

#include <vector>

#define INF 100000 // Valoare convențională pentru infinit

using namespace std;

void afisareMatrice(int n, int matrice[100][100]) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            if (matrice[i][j] == INF)

                cout << „INF „;

            else

                cout << matrice[i][j] << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4; // Numărul de noduri

    int matrice[100][100];

    // Inițializare matrice cu INF

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            matrice[i][j] = (i == j) ? 0 : INF; // Cost 0 pe diagonală

        }

    }

    // Adăugare arce cu costuri

    matrice[0][1] = 5; // Arc 1 → 2, cost 5

    matrice[1][2] = 2; // Arc 2 → 3, cost 2

    matrice[3][0] = 7; // Arc 4 → 1, cost 7

    matrice[2][3] = 7; // Arc 3 → 4, cost 7

    cout << „Matricea costurilor pentru graful orientat:\n”;

    afisareMatrice(n, matrice);

    return 0;

}


6. Aplicații ale Matricei Costurilor

  1. Algoritmul Dijkstra:
    Utilizat pentru determinarea drumurilor minime într-un graf ponderat.
  2. Algoritmul Floyd-Warshall:
    Folosit pentru a calcula toate drumurile minime între perechi de noduri.
  3. Probleme de optimizare:
    Matricea costurilor este utilizată pentru problemele de comis-voiajor (TSP) sau alte probleme similare.

7. Concluzie

  • Matricea costurilor este o metodă ideală pentru grafuri dense și pentru rezolvarea problemelor de drumuri minime.
  • Este mai puțin eficientă pentru grafuri sparse, unde lista de adiacență este mai potrivită.
  • Alegerea metodei depinde de aplicație, dimensiunea grafului și densitatea acestuia.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *