Conexitate

Un graf neorientat este conex dacă între orice două vârfuri există un lanț. În graful 1–2–3, nu există muchie directă între 1 și 3, dar lanțul 1–2–3 le unește, deci graful este conex. Dacă adăugăm un vârf 4 izolat, graful nu mai este conex.

Un graf neorientat este conex dacă între oricare două vârfuri există un lanț. O componentă conexă este un subgraf conex maximal, adică nu mai poate fi extins cu alte vârfuri fără să-și piardă conexitatea. Testul de conexitate pornește dintr-un vârf și marchează toate vârfurile la care ajunge printr-o parcurgere. Pentru un graf cu $n\ge 1$ vârfuri, dacă după parcurgere toate cele $n$ poziții sunt marcate, graful este conex.

Exemplul 1 — testul de conexitate. Graful are 4 vârfuri și muchiile $[1,2]$, $[2,3]$:

#include <iostream>
using namespace std;
int a[5][5] = {}, viz[5] = {}, n = 4;
void df(int u) {
    viz[u] = 1;
    for (int v = 1; v <= n; ++v)
        if (a[u][v] && !viz[v]) df(v);
}
int main() {
    a[1][2] = a[2][1] = a[2][3] = a[3][2] = 1;
    df(1);
    bool conex = true;
    for (int i = 1; i <= n; ++i)
        if (!viz[i]) conex = false;
    cout << conex;
}

Se afișează 0, deoarece vârful 4 este izolat și nu este marcat de parcurgerea pornită din 1. Fără vârful 4, graful 1–2–3 ar fi conex, pentru că 1 și 3 sunt unite prin lanțul 1–2–3, chiar dacă nu există muchia $[1,3]$.

Exemplul 2 — numărul componentelor conexe. Se parcurg indicii de la 1 la $n$ și se pornește o nouă parcurgere la fiecare vârf încă nemarcat; numărul pornirilor este numărul componentelor:

#include <iostream>
using namespace std;
int a[11][11], viz[11], n, m;
void df(int u) {
    viz[u] = 1;
    for (int v = 1; v <= n; ++v)
        if (a[u][v] && !viz[v]) df(v);
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int comp = 0;
    for (int i = 1; i <= n; ++i)
        if (!viz[i]) { ++comp; df(i); }
    cout << comp;
}

Pentru intrarea 6 3, 1 2, 2 3, 4 5 se afișează 3: componentele sunt $\{1,2,3\}$, $\{4,5\}$ și $\{6\}$. Pentru graful din primul exemplu, parcurgerea din 1 acoperă $\{1,2,3\}$, iar vârful 4 pornește a doua parcurgere, deci sunt două componente. Parcurgerea cu matrice cere $O(n^2)$ operații, iar cu liste de adiacență $O(n+m)$.

Dacă la fiecare pornire memorezi în comp[i] numărul parcurgerii care a marcat vârful $i$, două vârfuri sunt unite printr-un lanț dacă și numai dacă au aceeași valoare în comp. Adăugarea unei muchii între două vârfuri din componente diferite reunește componentele, deci numărul lor scade cu 1; adăugarea unei muchii în interiorul unei componente nu îl schimbă. Eliminarea unei muchii fie lasă numărul componentelor neschimbat, fie îl mărește cu 1; o astfel de muchie se numește punte. În lanțul 1–2–3 fiecare muchie este punte, iar în triunghi nicio muchie nu este: după eliminarea oricăreia, graful rămâne conex.

Exemplul 3 — urmărirea parcurgerii. Pentru graful cu $n=6$ și muchiile $[1,2]$, $[2,3]$, $[4,5]$, apelul df(1) marchează vârful 1, apoi găsește vecinul 2 și apelează df(2). Din 2, vecinul 1 este deja marcat, iar vecinul 3 duce la df(3), care nu mai găsește vecini nemarcați. Parcurgerea din 1 se încheie cu viz egal cu 1, 1, 1, 0, 0, 0. Ciclul din main ajunge la $i=4$, pornește df(4) și marchează vârfurile 4 și 5; la $i=6$ pornește df(6), care marchează doar vârful 6. Contorul comp crește de trei ori, deci graful are 3 componente. Dacă se adaugă muchia $[3,4]$, parcurgerea din 1 ajunge și la 4 și 5, iar rămân două componente: $\{1,2,3,4,5\}$ și $\{6\}$. Pentru graful inițial, vectorul comp este 1, 1, 1, 2, 2, 3 și arată direct că vârfurile 1 și 3 sunt unite printr-un lanț, iar vârfurile 3 și 4 nu sunt.

Un graf simplu conex cu $n$ vârfuri are cel puțin $n-1$ muchii; un arbore atinge această limită. Condiția $m\ge n-1$ este necesară, dar nu suficientă pentru conexitate: pot exista multe muchii într-o componentă și un vârf izolat. Mai general, un graf cu $n$ vârfuri și $k$ componente conexe are cel puțin $n-k$ muchii, deoarece fiecare componentă cu $n_i$ vârfuri are cel puțin $n_i-1$ muchii, iar suma este $n-k$. Pentru a uni $k$ componente într-un graf conex sunt suficiente $k-1$ muchii noi, câte una între componente diferite. Un graf cu $n$ vârfuri și mai mult de $(n-1)(n-2)/2$ muchii este sigur conex; limita se atinge când $K_{n-1}$ are un vârf izolat alături.

Exemplu în formatul examenului. Un graf neorientat are 7 vârfuri și 3 componente conexe, cu 3, 2 și 2 vârfuri. Care este numărul minim de muchii pe care le poate avea?

• a) 3
• b) 4
• c) 6
• d) 7

Răspunsul corect este b). Componenta cu 3 vârfuri are cel puțin 2 muchii, iar fiecare componentă cu 2 vârfuri are cel puțin 1, deci minimul este $2+1+1=4=n-k=7-3$. Varianta a) este numărul componentelor. Varianta c) este $n-1$, limita pentru un graf conex cu 7 vârfuri, iar graful dat nu este conex. Varianta d) este numărul vârfurilor.

Greșeli frecvente

• Greșit: conex înseamnă că orice pereche are muchie directă.
  Corect: este suficient un lanț.
• Greșit: un vârf izolat poate aparține unui graf conex cu mai multe vârfuri.
  Corect: un vârf izolat face graful neconex.
• Greșit: $m\ge n-1$ garantează conexitatea.
  Corect: este doar o condiție necesară.

Înainte și după