Teoria Grafurilor: Adiacență, Incidență, Grad, Drum și Circuit 23

---

1. Adiacență

1. Definiție:
   Două noduri sunt adiacente dacă există o muchie (în grafuri neorientate) sau un arc (în grafuri orientate) între ele.
2. Exemple:
   • Într-un graf neorientat, uuu și vvv sunt adiacente dacă {u,v}∈E\{u, v\} \in E{u,v}∈E.
   • Într-un graf orientat, uuu este adiacent cu vvv dacă există un arc (u,v)∈E(u, v) \in E(u,v)∈E.
3. Reprezentări:
   • Matricea de adiacență: A[i][j]=1A[i][j] = 1A[i][j]=1 dacă iii și jjj sunt adiacente, altfel 000.
   • Lista de adiacență: Fiecare nod are o listă de noduri adiacente.
4. Exemplu grafic:

1–2

|   |

4–3

4. Nodul 1 este adiacent cu nodurile 2, 3, 4.
5. Nodul 2 este adiacent cu nodurile 1, 3.

---

2. Incidență

1. Definiție:
   • O muchie (în grafuri neorientate) sau un arc (în grafuri orientate) este incidentă la un nod dacă acel nod este unul dintre extremitățile muchiei sau arcului.
2. Exemplu:
   • Pentru muchia {1,2}\{1, 2\}{1,2}, nodurile 1 și 2 sunt incidente.
   • Într-un graf orientat, pentru arcul (1,2)(1, 2)(1,2), nodul 1 este incident la origine, iar nodul 2 este incident la destinație.
3. Reprezentare prin matricea de incidență:
   • O matrice I[i][j]I[i][j]I[i][j], unde:
     • I[i][j]=1I[i][j] = 1I[i][j]=1, dacă nodul iii este incident la muchia jjj.
     • I[i][j]=−1I[i][j] = -1I[i][j]=−1, dacă iii este nodul de origine (în grafuri orientate).
4. Exemplu grafic:

1–2

|   |

4–3

4. Muchia {1,2}\{1, 2\}{1,2} este incidentă la nodurile 1 și 2.

---

3. Grad

1. Definiție:
   Gradul unui nod reprezintă numărul de muchii incidente la acel nod.
2. Tipuri de grad:
   • Graf neorientat: Gradul unui nod este numărul de muchii incidente.
   • Graf orientat:
     • Grad intrare (degindeg_{in}degin​): Numărul de arce care intră în nod.
     • Grad ieșire (degoutdeg_{out}degout​): Numărul de arce care ies din nod.
3. Proprietăți:
   • Într-un graf neorientat, suma gradelor tuturor nodurilor este de două ori numărul muchiilor: ∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} deg(v) = 2|E|v∈V∑​deg(v)=2∣E∣
4. Exemplu grafic:

1–2

|   |

4–3

4. Gradul nodului 1: deg(1)=3deg(1) = 3deg(1)=3.
5. Gradul nodului 2: deg(2)=2deg(2) = 2deg(2)=2.

---

4. Drum

1. Definiție:
   Un drum este o secvență de noduri conectate prin muchii sau arce, unde fiecare muchie/arce este parcursă o singură dată.
2. Tipuri de drumuri:
   • Drum simplu: Toate nodurile sunt distincte.
   • Drum elementar: Toate muchiile sunt distincte.
   • Drum circuit: Pornim și revenim la același nod, dar nodurile intermediare sunt distincte.
3. Exemplu grafic:

1–2

|   |

4–3

3. Drum simplu: 1→2→31 \to 2 \to 31→2→3.
4. Drum circuit: 1→2→3→4→11 \to 2 \to 3 \to 4 \to 11→2→3→4→1.

---

5. Circuit

1. Definiție:
   Un circuit este un drum care începe și se termină în același nod, iar toate nodurile intermediare sunt distincte.
2. Proprietăți:
   • Circuitul conține cel puțin trei noduri.
   • În grafuri orientate, sensul fiecărui arc trebuie respectat.
3. Exemplu grafic:

1–2

|   |

4–3

3. Circuit: 1→2→3→4→11 \to 2 \to 3 \to 4 \to 11→2→3→4→1.

---

6. Implementări în C++

---

1. Matricea de adiacență și gradul fiecărui nod

#include <iostream>

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 calculeazaGrad(int n, int matrice[100][100]) {

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

        int grad = 0;

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

            if (matrice[i][j] == 1) grad++;

        }

        cout << „Gradul nodului ” << i + 1 << „: ” << grad << endl;

    }

}

int main() {

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

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

    // Adăugare muchii

    matrice[0][1] = matrice[1][0] = 1; // Muchie 1-2

    matrice[0][3] = matrice[3][0] = 1; // Muchie 1-4

    matrice[1][2] = matrice[2][1] = 1; // Muchie 2-3

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

    cout << „Matricea de adiacență:\n”;

    afisareMatrice(n, matrice);

    cout << „\nGradurile nodurilor:\n”;

    calculeazaGrad(n, matrice);

    return 0;

}

---

2. Detectarea unui drum simplu folosind DFS

#include <iostream>

#include <vector>

using namespace std;

void dfs(int nod, vector<int> lista[], vector<bool>& vizitat) {

    cout << nod + 1 << ” „;

    vizitat[nod] = true;

    for (int vecin : lista[nod]) {

        if (!vizitat[vecin]) {

            dfs(vecin, lista, vizitat);

        }

    }

}

int main() {

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

    vector<int> lista[4]; // Lista de adiacență

    // Adăugare muchii

    lista[0].push_back(1); lista[1].push_back(0); // Muchie 1-2

    lista[0].push_back(3); lista[3].push_back(0); // Muchie 1-4

    lista[1].push_back(2); lista[2].push_back(1); // Muchie 2-3

    lista[3].push_back(2); lista[2].push_back(3); // Muchie 4-3

    vector<bool> vizitat(n, false);

    cout << „Drum simplu pornind de la nodul 1: „;

    dfs(0, lista, vizitat);

    cout << endl;

    return 0;

}

---

7. Concluzie

• Adiacența și incidența sunt relațiile fundamentale dintre noduri și muchii.
• Gradul unui nod indică numărul de conexiuni directe ale acestuia.
• Drumurile și circuitele sunt concepte cheie pentru analiza conectivității în grafuri.
• Înțelegerea acestor noțiuni este esențială pentru aplicațiile mai avansate ale teoriei grafurilor.