Metode de Reprezentare a Grafurilor: Matricea de Incidență 26
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:
- ∣V∣|V|∣V∣ este numărul de noduri ale grafului.
- ∣E∣|E|∣E∣ este numărul de muchii (sau arce) ale grafului.
2. Definiție
Pentru un graf G=(V,E)G = (V, E)G=(V,E):
- În cazul unui graf neorientat, I[i][j]=1I[i][j] = 1I[i][j]=1 dacă nodul viv_ivi este incident la muchia eje_jej.
- În cazul unui graf orientat:
- I[i][j]=−1I[i][j] = -1I[i][j]=−1 dacă nodul viv_ivi este nodul de origine al arcului eje_jej.
- I[i][j]=1I[i][j] = 1I[i][j]=1 dacă nodul viv_ivi este nodul de destinație al arcului eje_jej.
- I[i][j]=0I[i][j] = 0I[i][j]=0 altfel.
3. Caracteristici
- Grafuri neorientate:
- Matricea conține doar valori binare (0 și 1).
- O muchie este reprezentată de două elemente de valoare 1.
- Grafuri orientate:
- Matricea poate conține valori −1,0-1, 0−1,0 și 111.
- Arcele au direcții bine definite, iar matricea reflectă această orientare.
- Grafuri ponderate:
- Valorile din matrice pot reprezenta greutățile muchiilor în loc de valori binare.
4. Exemplu pentru Grafuri Neorientate
Graf:
1–2
| |
4–3
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Muchii: E={e1={1,2},e2={1,4},e3={2,3},e4={3,4}}E = \{e_1 = \{1, 2\}, e_2 = \{1, 4\}, e_3 = \{2, 3\}, e_4 = \{3, 4\}\}E={e1={1,2},e2={1,4},e3={2,3},e4={3,4}}
Matricea de incidență:
e1 e2 e3 e4
1: 1 1 0 0
2: 1 0 1 0
3: 0 0 1 1
4: 0 1 0 1
5. Exemplu pentru Grafuri Orientate
Graf:
(1) → (2)
↑ ↓
(4) ← (3)
Reprezentare:
- Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
- Arce: E={e1=(1,2),e2=(3,4),e3=(4,1),e4=(2,3)}E = \{e_1 = (1, 2), e_2 = (3, 4), e_3 = (4, 1), e_4 = (2, 3)\}E={e1=(1,2),e2=(3,4),e3=(4,1),e4=(2,3)}
Matricea de incidență:
e1 e2 e3 e4
1: -1 0 1 0
2: 1 0 0 -1
3: 0 -1 0 1
4: 0 1 -1 0
6. Avantaje și Dezavantaje
| Avantaje | Dezavantaje |
| Reprezentare simplă a conexiunilor dintre noduri și muchii. | Necesită spațiu mai mare (( O( |
| Ușor de utilizat pentru calcule matematice și algoritmi. | Ineficient pentru grafuri sparse sau foarte mari. |
| Compatibilitate cu grafuri orientate și ponderate. | Traversarea vecinilor unui nod necesită timp ( O( |
7. Implementare în C++
1. Matricea de incidență pentru graf neorientat
#include <iostream>
using namespace std;
void afisareMatrice(int n, int m, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int m = 4; // Numărul de muchii
int matrice[100][100] = {0};
// Adăugare muchii
matrice[0][0] = 1; matrice[1][0] = 1; // Muchie e1 = {1, 2}
matrice[0][1] = 1; matrice[3][1] = 1; // Muchie e2 = {1, 4}
matrice[1][2] = 1; matrice[2][2] = 1; // Muchie e3 = {2, 3}
matrice[2][3] = 1; matrice[3][3] = 1; // Muchie e4 = {3, 4}
cout << „Matricea de incidență pentru graful neorientat:\n”;
afisareMatrice(n, m, matrice);
return 0;
}
2. Matricea de incidență pentru graf orientat
#include <iostream>
using namespace std;
void afisareMatrice(int n, int m, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int m = 4; // Numărul de arce
int matrice[100][100] = {0};
// Adăugare arce
matrice[0][0] = -1; matrice[1][0] = 1; // Arc e1 = (1, 2)
matrice[2][1] = -1; matrice[3][1] = 1; // Arc e2 = (3, 4)
matrice[3][2] = -1; matrice[0][2] = 1; // Arc e3 = (4, 1)
matrice[1][3] = -1; matrice[2][3] = 1; // Arc e4 = (2, 3)
cout << „Matricea de incidență pentru graful orientat:\n”;
afisareMatrice(n, m, matrice);
return 0;
}
8. Aplicații ale Matricei de Incidență
- Analiza conexiunilor nodurilor:
Matricea de incidență facilitează analiza conexiunilor dintre noduri și muchii. - Probleme de flux:
Este utilizată pentru calcularea fluxului maxim în rețele orientate. - Reprezentarea ponderată:
Matricea poate fi extinsă pentru a include greutăți asociate muchiilor/arcelor.
9. Concluzie
- Matricea de incidență este o metodă eficientă de reprezentare pentru grafuri dense sau pentru probleme care implică analiza muchiilor/arcelor.
- Este mai puțin eficientă pentru grafuri sparse sau foarte mari, comparativ cu alte metode (ex.: lista de adiacență).
- Alegerea metodei de reprezentare depinde de tipul de problemă și de proprietățile grafului.