Metode de Reprezentare a Grafurilor: Matricea Drumurilor 30

---

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:

• ∣V∣|V|∣V∣ reprezintă numărul de noduri.
• P[i][j]=1P[i][j] = 1P[i][j]=1 dacă există un drum (oricât de lung) între nodurile iii și jjj.
• P[i][j]=0P[i][j] = 0P[i][j]=0 dacă nu există niciun drum între nodurile iii și jjj.

---

2. Caracteristici

1. Grafuri neorientate:
   • Matricea este simetrică (P[i][j]=P[j][i]P[i][j] = P[j][i]P[i][j]=P[j][i]).
2. Grafuri orientate:
   • Matricea nu este neapărat simetrică (P[i][j]≠P[j][i]P[i][j] \neq P[j][i]P[i][j]=P[j][i]).
3. Drumuri reflexive:
   • Diagonala principală conține P[i][i]=1P[i][i] = 1P[i][i]=1, deoarece orice nod are un drum către el însuși (inclusiv drumuri de lungime zero).
4. Calculul matricei drumurilor:
   • Matricea drumurilor se poate calcula folosind puterea matricei de adiacență sau algoritmi precum Floyd-Warshall.

---

3. Exemple de Grafuri și Matricea Drumurilor

---

Graf Neorientat

Graful:

1–2

|   |

4–3

Lista muchiilor:

E = {(1, 2), (1, 4), (2, 3), (3, 4)}

Matricea drumurilor:

    1   2   3   4

1   1   1   1   1

2   1   1   1   1

3   1   1   1   1

4   1   1   1   1

---

Graf Orientat

Graful:

(1) → (2)

 ↑      ↓

(4) ← (3)

Lista arcelor:

E = {(1, 2), (2, 3), (3, 4), (4, 1)}

Matricea drumurilor:

    1   2   3   4

1   1   1   1   1

2   1   1   1   1

3   1   1   1   1

4   1   1   1   1

---

4. Calculul Matricei Drumurilor

1. Folosind matricea de adiacență:
   • Dacă AAA este matricea de adiacență, matricea drumurilor PPP se calculează ca: P=A+A2+A3+⋯+A∣V∣P = A + A^2 + A^3 + \dots + A^{|V|}P=A+A2+A3+⋯+A∣V∣
   • P[i][j]=1P[i][j] = 1P[i][j]=1 dacă există un drum de orice lungime de la iii la jjj.
2. Algoritmul Floyd-Warshall:
   • Este un algoritm eficient pentru calcularea matricei drumurilor într-un graf.

---

5. Implementare în C++

---

1. Calculul Matricei Drumurilor folosind Matricea de Adiacență

#include <iostream>

#include <vector>

#define INF 100000

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++) {

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

        }

        cout << endl;

    }

}

void calculeazaDrumuri(int n, int adiacenta[100][100], int drumuri[100][100]) {

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

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

            drumuri[i][j] = adiacenta[i][j];

        }

    }

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

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

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

                drumuri[i][j] = drumuri[i][j] || (drumuri[i][k] && drumuri[k][j]);

            }

        }

    }

}

int main() {

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

    int adiacenta[100][100] = {

        {0, 1, 0, 1},

        {1, 0, 1, 0},

        {0, 1, 0, 1},

        {1, 0, 1, 0}

    };

    int drumuri[100][100] = {0};

    calculeazaDrumuri(n, adiacenta, drumuri);

    cout << „Matricea drumurilor:\n”;

    afisareMatrice(n, drumuri);

    return 0;

}

---

2. Calculul Matricei Drumurilor folosind Floyd-Warshall

#include <iostream>

using namespace std;

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

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

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

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

                matrice[i][j] = matrice[i][j] || (matrice[i][k] && matrice[k][j]);

            }

        }

    }

}

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

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

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

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

        }

        cout << endl;

    }

}

int main() {

    int n = 4;

    int matrice[100][100] = {

        {0, 1, 0, 1},

        {0, 0, 1, 0},

        {0, 0, 0, 1},

        {1, 0, 0, 0}

    };

    floydWarshall(n, matrice);

    cout << „Matricea drumurilor este:\n”;

    afisareMatrice(n, matrice);

    return 0;

}

---

6. Aplicații ale Matricei Drumurilor

1. Analiza conectivității:
   Determinarea dacă un graf este conex sau tare conex (în cazul grafurilor orientate).
2. Găsirea componentelor conexe:
   Matricea drumurilor poate identifica subgrafuri conexe.
3. Detectarea ciclurilor:
   Dacă P[i][i]=1P[i][i] = 1P[i][i]=1 pentru un nod iii, graful conține cicluri.
4. Probleme de accesibilitate:
   Verificarea dacă există un drum între două noduri.

---

7. Concluzie

• Matricea drumurilor este o metodă fundamentală de reprezentare a grafurilor pentru analiza conectivității.
• Se calculează eficient utilizând algoritmi precum Floyd-Warshall.
• Este utilă în probleme de accesibilitate, drumuri minime și analiza structurii grafului.