Matricea drumurilor. Conexitate

Un graf neorientat este conex dacă din orice nod se poate ajunge în oricare altul pe un lanț. La graful orientat se cere mai mult: graful este tare conex dacă între oricare două noduri există drum în ambele sensuri. Când graful nu are aceste proprietăți, nodurile lui se împart în componente conexe, respectiv în componente tare conexe.

Existența unui lanț sau a unui drum între toate perechile de noduri se reține într-o singură matrice: matricea lanțurilor la graful neorientat și matricea drumurilor la graful orientat.

Noțiuni preliminare

Conexitatea se definește cu ajutorul următoarelor noțiuni:

• graful neorientat este o pereche G = (X, U), în care X este o mulțime finită și nevidă de noduri, iar U o mulțime de perechi neordonate de noduri distincte, numite muchii;
• două noduri x și y sunt adiacente dacă [x, y] este muchie a grafului;
• lanțul este o succesiune de noduri (x1, x2, …, xk) în care oricare două noduri consecutive sunt adiacente; nodurile x1 și xk sunt extremitățile lanțului;
• drumul este, într-un graf orientat, o succesiune de noduri în care oricare două noduri consecutive xi, xi+1 sunt legate prin arcul (xi, xi+1).

Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie.

Graful conex

Definiție

Un graf neorientat G = (X, U) este conex dacă pentru oricare două noduri distincte x și y există un lanț de la x la y. Graful cu un singur nod este conex, fiindcă nu are două noduri distincte.

Contraexemplu. Graful G5 are nodurile X5 = {1, 2, 3, 4, 5, 6, 7} și muchiile U5 = {[1,2], [1,4], [2,4], [3,5], [5,6]}. El nu este conex: nu există niciun lanț de la nodul 1 la nodul 3, iar nodul 7 este izolat.

Exemplu. Graful G6 are aceleași noduri, iar la muchiile lui G5 se adaugă [4,5] și [6,7]. Graful G6 este conex. De exemplu, nodurile 1 și 7 sunt legate prin lanțul (1, 4, 5, 6, 7), iar nodurile 2 și 3 prin lanțul (2, 4, 5, 3).

Verificarea conexității

O parcurgere pornită dintr-un nod x vizitează exact nodurile la care se ajunge din x pe lanțuri. Graful este conex dacă o singură parcurgere, în lățime sau în adâncime, pornită din nodul 1, vizitează toate cele n noduri. În G5, parcurgerea din nodul 1 vizitează numai nodurile 1, 2 și 4.

Parcurgerile sunt descrise în subcapitolul Parcurgerea grafurilor.

Enunț. Se citește un graf neorientat cu n noduri și m muchii. Să se afișeze dacă graful este conex. Dacă nu este, să se afișeze un nod la care nu se ajunge din nodul 1.

Date de intrare. Pe prima linie n și m, pe fiecare dintre următoarele m linii extremitățile unei muchii (datele grafului G5 sunt mai jos, la determinarea componentelor conexe).

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in adancime din nodul x marcheaza in viz
   toate nodurile la care se ajunge din x pe lanturi. */
void dfs(int x) {
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && viz[j] == 0)
            dfs(j);
}

/* Intoarce primul nod nevizitat sau 0, daca toate nodurile
   au fost vizitate. */
int primulNevizitat() {
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            return i;
    return 0;
}

int main() {
    citire();
    dfs(1);
    int x = primulNevizitat();
    if (x == 0)
        cout << "Graful este conex\n";
    else
        cout << "Graful nu este conex: nu exista lant de la 1 la " << x << "\n";
    return 0;
}

Pentru graful G5 programul afișează:

Graful nu este conex: nu exista lant de la 1 la 3

Pentru graful G6 afișează Graful este conex.

Descrierea soluției. Subprogramul dfs pornește din nodul 1 și marchează în vectorul viz fiecare nod atins. Subprogramul primulNevizitat caută un nod cu viz[i] = 0: dacă nu există, toate nodurile sunt legate de nodul 1 prin lanțuri, deci, trecând prin nodul 1, oricare două noduri sunt legate între ele, iar graful este conex. Timpul este de ordinul O(n²), cât o parcurgere cu matricea de adiacență.

Varianta cu parcurgerea în lățime. Nodurile vizitate sunt exact nodurile puse în coadă, deci graful este conex dacă, la sfârșitul parcurgerii, în coadă au intrat n noduri:

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], coada[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in latime din nodul pl; intoarce numarul
   nodurilor vizitate, adica numarul nodurilor puse in coada. */
int BF(int pl) {
    int p = 1, u = 1;
    coada[1] = pl;
    viz[pl] = 1;
    while (p <= u) {
        for (int j = 1; j <= n; j++)
            if (a[coada[p]][j] == 1 && viz[j] == 0) {
                u++;
                coada[u] = j;
                viz[j] = 1;
            }
        p++;
    }
    return u;
}

int main() {
    citire();
    if (BF(1) == n)
        cout << "Graful este conex\n";
    else
        cout << "Graful nu este conex\n";
    return 0;
}

Componentele conexe

Definiție

O componentă conexă a grafului neorientat G este un subgraf conex al lui G care este maximal cu această proprietate: dacă i se adaugă orice alt nod al grafului, subgraful generat nu mai este conex. Altfel spus, între un nod al componentei și un nod din afara ei nu există niciun lanț.

Graful G5 are trei componente conexe, desenate cu culori diferite:

• subgraful generat de nodurile {1, 2, 4}, cu muchiile [1,2], [1,4], [2,4];
• subgraful generat de nodurile {3, 5, 6}, cu muchiile [3,5], [5,6];
• subgraful format numai din nodul 7.

Subgraful generat de nodurile {1, 2} este conex, dar nu este componentă conexă: i se mai poate adăuga nodul 4, iar subgraful rămâne conex.

Proprietăți

• fiecare nod aparține unei singure componente conexe; un nod izolat formează singur o componentă;
• un graf este conex dacă și numai dacă are o singură componentă conexă;
• numărul componentelor conexe ale unui graf cu n noduri este cuprins între 1, pentru graful conex, și n, pentru graful fără muchii;
• o muchie nouă micșorează numărul componentelor conexe cu cel mult 1, fiindcă unește cel mult două componente;
• dacă graful are p componente conexe, pentru a deveni conex trebuie adăugate cel puțin p − 1 muchii, iar p − 1 muchii sunt suficiente: câte o muchie între o componentă și următoarea. Graful G5 are 3 componente, iar muchiile [4,5] și [6,7] îl transformă în graful conex G6;
• un graf conex cu n noduri are cel puțin n − 1 muchii: graful fără muchii are n componente, iar fiecare muchie scade numărul lor cu cel mult 1;
• un graf cu n noduri și p componente conexe are cel mult (n − p)(n − p + 1)/2 muchii. Valoarea se atinge când p − 1 componente sunt noduri izolate, iar ultima componentă este graful complet cu n − p + 1 noduri.

Din ultima proprietate, pentru p = 2, un graf neconex cu n noduri are cel mult (n − 2)(n − 1)/2 muchii. Prin urmare, un graf cu cel puțin (n − 1)(n − 2)/2 + 1 muchii este conex, oricum ar fi așezate muchiile. Pentru n = 21, numărul acesta este 190 + 1 = 191.

Determinarea componentelor conexe

Parcurgerea în adâncime pornită dintr-un nod vizitează toate nodurile componentei lui și numai pe acestea. Algoritmul reia parcurgerea din fiecare nod care nu aparține încă unei componente:

1. Vectorul comp are inițial toate elementele 0.
2. Se parcurg nodurile de la 1 la n. Când se găsește un nod x cu comp[x] = 0, se mărește numărul nr al componentelor.
3. Parcurgerea în adâncime din x pune comp[i] = nr pentru fiecare nod i vizitat.
4. La sfârșit, nr este numărul componentelor conexe, iar nodurile componentei c sunt nodurile i cu comp[i] = c.

Enunț. Se citește un graf neorientat. Să se afișeze dacă graful este conex. În caz contrar, să se afișeze nodurile fiecărei componente conexe și numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex.

Date de intrare. Pe prima linie n și m, pe fiecare dintre următoarele m linii extremitățile unei muchii. Pentru graful G5:

7 5
1 2
1 4
2 4
3 5
5 6

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], comp[MAX], n, m, nr;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in adancime din nodul x: toate nodurile atinse
   primesc numarul nr al componentei conexe. */
void dfs(int x) {
    comp[x] = nr;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && comp[j] == 0)
            dfs(j);
}

/* Afiseaza nodurile componentei cu numarul k. */
void afiseazaComponenta(int k) {
    cout << "Componenta " << k << ":";
    for (int i = 1; i <= n; i++)
        if (comp[i] == k)
            cout << " " << i;
    cout << "\n";
}

int main() {
    citire();
    for (int i = 1; i <= n; i++)
        if (comp[i] == 0) {             // i incepe o componenta noua
            nr++;
            dfs(i);
        }
    if (nr == 1)
        cout << "Graful este conex\n";
    else {
        cout << "Graful nu este conex\n";
        for (int k = 1; k <= nr; k++)
            afiseazaComponenta(k);
        cout << "Muchii de adaugat: " << nr - 1 << "\n";
    }
    return 0;
}

Pentru graful G5 programul afișează:

Graful nu este conex
Componenta 1: 1 2 4
Componenta 2: 3 5 6
Componenta 3: 7
Muchii de adaugat: 2

Pentru graful G6 afișează Graful este conex.

Colorarea componentelor prin parcurgeri în adâncime repetate se poate urmări pas cu pas în simulatorul componentelor conexe, care arată vectorul comp, ordinea vizitării și matricea de adiacență.

Descrierea soluției. Graful se reține în matricea de adiacență. Structura repetitivă din main caută nodurile care nu au primit încă un număr de componentă; pentru fiecare dintre ele mărește nr și apelează dfs, care atribuie numărul nr tuturor nodurilor accesibile. Fiecare nod este vizitat o singură dată, iar vizitarea examinează o linie a matricei, deci timpul este de ordinul O(n²). Numărul minim de muchii de adăugat este p − 1, după proprietatea de mai sus.

Probleme practice în care se folosește conexitatea

În fiecare dintre problemele următoare, datele se reprezintă printr-un graf neorientat, iar cerința se reduce la conexitate:

Matricea lanțurilor

Pentru un graf neorientat cu n noduri, matricea lanțurilor este matricea pătratică L, cu n linii și n coloane, în care:

L[i][j] = 1, dacă există un lanț de la nodul i la nodul j
L[i][j] = 0, în caz contrar

Matricea lanțurilor are următoarele proprietăți:

• este simetrică: un lanț de la i la j, parcurs în ordine inversă, este un lanț de la j la i;
• pentru i ≠ j, L[i][j] = 1 dacă și numai dacă nodurile i și j aparțin aceleiași componente conexe;
• graful este conex dacă și numai dacă toate elementele din afara diagonalei principale au valoarea 1;
• pe diagonala principală, L[i][i] = 1 pentru orice nod i care nu este izolat, fiindcă (i, k, i) este un lanț pentru orice vecin k; informația despre legăturile dintre noduri este în elementele din afara diagonalei.

Matricea lanțurilor pentru graful G5:

Linia i se completează printr-o parcurgere din nodul i: L[i][j] = 1 pentru fiecare nod j vizitat. Matricea se obține și cu algoritmul Roy-Warshall, descris la matricea drumurilor, aplicat matricei de adiacență a grafului neorientat.

Verificarea conexității cu matricea lanțurilor

Enunț. Se citește un graf neorientat. Să se afișeze matricea lanțurilor și dacă graful este conex.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Aplicat matricei de adiacenta a unui graf neorientat,
   algoritmul Roy-Warshall construieste matricea lanturilor. */
void royWarshall() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][k] == 1 && a[k][j] == 1)
                    a[i][j] = 1;
}

void afiseazaMatricea() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
}

/* Graful este conex daca toate elementele din afara diagonalei
   principale a matricei lanturilor sunt 1. */
int esteConex() {
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i][j] == 0)
                return 0;
    return 1;
}

int main() {
    citire();
    royWarshall();
    afiseazaMatricea();
    if (esteConex())
        cout << "Graful este conex\n";
    else
        cout << "Graful nu este conex\n";
    return 0;
}

Pentru graful G5 programul afișează matricea lanțurilor din tabelul de mai sus și mesajul Graful nu este conex; pentru graful G6 afișează o matrice cu toate elementele 1 și mesajul Graful este conex.

Descrierea soluției. Matricea lanțurilor este simetrică, deci subprogramul esteConex verifică numai elementele de deasupra diagonalei principale (j > i). Construirea matricei cere O(n³), mai mult decât o singură parcurgere; metoda se folosește atunci când matricea lanțurilor este cerută oricum.

Graful tare conex

Definiție

Un graf orientat G = (X, U) este tare conex dacă pentru oricare două noduri distincte x și y există un drum de la x la y și un drum de la y la x.

Pentru graful orientat se definește și conexitatea obișnuită: graful orientat este conex dacă între oricare două noduri distincte există un lanț, adică o succesiune de noduri legate prin arce, fără să se țină seama de sensul lor.

Orice graf tare conex este conex, fiindcă orice drum este și lanț. Reciproca nu este adevărată.

Contraexemplu. Graful orientat G7 are nodurile {1, 2, 3, 4, 5, 6} și arcele (1,2), (2,1), (2,3), (3,4), (4,5), (5,3), (6,5). Graful este conex, dar nu este tare conex:

• din nodurile 3, 4 și 5 nu pleacă niciun arc spre nodurile 1, 2 sau 6, deci de la nodul 3 nu există drum la nodul 1;
• în nodul 6 nu intră niciun arc, deci niciun drum nu ajunge în nodul 6.

Exemplu. Graful G8 se obține din G7 prin adăugarea arcelor (4,1) și (4,6). Graful G8 este tare conex: el conține circuitele (1, 2, 3, 4, 1) și (3, 4, 6, 5, 3), care au în comun nodurile 3 și 4, deci din orice nod se ajunge în oricare altul.

Verificarea conexității unui graf orientat

Conexitatea unui graf orientat nu ține seama de sensul arcelor. Parcurgerea din nodul 1 trece de la nodul k la nodul i dacă există arcul (k, i) sau arcul (i, k); graful este conex dacă parcurgerea vizitează toate nodurile.

Date de intrare. Pentru graful G7:

6 7
1 2
2 1
2 3
3 4
4 5
5 3
6 5

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = 1;
    }
}

/* Parcurgere in adancime in care sensul arcelor nu conteaza:
   din x se trece in j daca exista arcul (x,j) sau arcul (j,x). */
void dfsFaraSens(int x) {
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if ((a[x][j] == 1 || a[j][x] == 1) && viz[j] == 0)
            dfsFaraSens(j);
}

/* Intoarce 1 daca toate nodurile au fost vizitate. */
int totiVizitati() {
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            return 0;
    return 1;
}

int main() {
    citire();
    dfsFaraSens(1);
    if (totiVizitati())
        cout << "Graful orientat este conex\n";
    else
        cout << "Graful orientat nu este conex\n";
    return 0;
}

Pentru graful G7 programul afișează Graful orientat este conex, deși din nodul 1 nu există drum la nodul 6: nodul 6 este atins prin arcul (6,5), parcurs în sens invers. Dacă din G7 se elimină arcul (6,5), nodul 6 rămâne izolat, iar programul afișează Graful orientat nu este conex.

Verificarea tare conexității

Nu este nevoie să se verifice drumurile dintre toate perechile de noduri. Graful orientat este tare conex dacă și numai dacă:

• din nodul 1 există drum la fiecare nod;
• în nodul 1 există drum din fiecare nod.

Condiția este suficientă: pentru două noduri oarecare x și y, drumul de la x la 1 continuat cu drumul de la 1 la y duce de la x la y. Prima condiție se verifică printr-o parcurgere în sensul arcelor, iar a doua printr-o parcurgere în sens invers arcelor, adică în graful transpus.

Enunț. Se citește un graf orientat. Să se afișeze dacă graful este tare conex. Dacă nu este, să se afișeze o pereche de noduri între care lipsește drumul.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], fwd[MAX], bwd[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = 1;
    }
}

/* Marcheaza in fwd nodurile la care se ajunge din x pe drumuri
   (parcurgere pe arcele x -> j). */
void dfsInainte(int x, int fwd[]) {
    fwd[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && fwd[j] == 0)
            dfsInainte(j, fwd);
}

/* Marcheaza in bwd nodurile din care se ajunge in x pe drumuri
   (parcurgere pe arcele inversate j -> x, adica in graful transpus). */
void dfsInapoi(int x, int bwd[]) {
    bwd[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[j][x] == 1 && bwd[j] == 0)
            dfsInapoi(j, bwd);
}

/* Intoarce primul nod nemarcat in vectorul v sau 0. */
int primulNemarcat(int v[]) {
    for (int i = 1; i <= n; i++)
        if (v[i] == 0)
            return i;
    return 0;
}

int main() {
    citire();
    dfsInainte(1, fwd);
    dfsInapoi(1, bwd);
    int x = primulNemarcat(fwd), y = primulNemarcat(bwd);
    if (x == 0 && y == 0)
        cout << "Graful este tare conex\n";
    else if (x != 0)
        cout << "Graful nu este tare conex: nu exista drum de la 1 la " << x << "\n";
    else
        cout << "Graful nu este tare conex: nu exista drum de la " << y << " la 1\n";
    return 0;
}

Pentru graful G7 programul afișează:

Graful nu este tare conex: nu exista drum de la 1 la 6