Tare conexitate

Un graf orientat este tare conex dacă pentru orice pereche de vârfuri există drum orientat în ambele sensuri. Arcele 1→2, 2→3, 3→1 formează un ciclu orientat și dau un graf tare conex. Dacă eliminăm 3→1, putem merge de la 1 la 3, dar nu înapoi, deci proprietatea dispare.

Un graf orientat este tare conex dacă pentru orice pereche de vârfuri $x$ și $y$ există drum orientat de la $x$ la $y$ și drum orientat de la $y$ la $x$. O componentă tare conexă este o mulțime maximală de vârfuri care se pot atinge reciproc prin drumuri orientate. Componenta tare conexă a unui vârf $x$ este intersecția dintre mulțimea vârfurilor la care se poate ajunge din $x$ (succesorii) și mulțimea vârfurilor din care se poate ajunge la $x$ (predecesorii). Prima mulțime se obține prin parcurgerea grafului, a doua prin parcurgerea grafului cu toate arcele inversate, adică folosind transpusa matricei de adiacență.

Exemplul 1 — testul de tare conexitate. Un graf este tare conex dacă, pornind din vârful 1, parcurgerea în graful dat și parcurgerea în graful cu arcele inversate ating toate vârfurile. Este suficient un singur vârf de start, fiindcă, dacă toate vârfurile sunt atinse din 1 și 1 este atins din toate, orice pereche se unește printr-un drum care trece prin 1.

#include <iostream>
using namespace std;
int a[11][11], n, m;
int v1[11], v2[11];
void df(int u, int viz[], bool inv) {
    viz[u] = 1;
    for (int v = 1; v <= n; ++v)
        if ((inv ? a[v][u] : a[u][v]) && !viz[v]) df(v, viz, inv);
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    df(1, v1, false);
    df(1, v2, true);
    bool tare = true;
    for (int i = 1; i <= n; ++i)
        if (!v1[i] || !v2[i]) tare = false;
    cout << (tare ? "tare conex" : "nu");
}

Pentru 3 3 cu arcele $(1,2)$, $(2,3)$, $(3,1)$ se afișează tare conex: din 1 se ajunge la 2 și 3, iar în graful inversat se ajunge la 3 și 2. Pentru 3 2 cu arcele $(1,2)$, $(2,3)$ se afișează nu: din 1 se ajunge la toate vârfurile, dar în graful cu arcele inversate nu se ajunge la 2 și 3, deci nu există drum înapoi la 1.

Exemplul 2 — componentele tare conexe. Se repetă calculul intersecției pentru fiecare vârf încă neatribuit unei componente:

#include <iostream>
using namespace std;
int a[11][11], n, m, comp[11];
void df(int u, int viz[], bool inv) {
    viz[u] = 1;
    for (int v = 1; v <= n; ++v)
        if ((inv ? a[v][u] : a[u][v]) && !viz[v]) df(v, viz, inv);
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int x = 1; x <= n; ++x) {
        if (comp[x]) continue;
        int s[11] = {}, p[11] = {};
        df(x, s, false);
        df(x, p, true);
        for (int i = 1; i <= n; ++i)
            if (s[i] && p[i]) { comp[i] = x; cout << i << " "; }
        cout << "| ";
    }
}

Pentru 5 6 cu arcele $(1,2)$, $(2,3)$, $(3,1)$, $(3,4)$, $(4,5)$, $(5,4)$ se afișează 1 2 3 | 4 5 |. Din 1 se ajunge la toate vârfurile, dar la 1 se ajunge numai din $\{1,2,3\}$; intersecția este $\{1,2,3\}$. Vârful 4 formează cu 5 a doua componentă, pentru că $4\to 5$ și $5\to 4$. Arcul $3\to 4$ merge dintr-o componentă în alta, dar nu există drum înapoi. Pentru arcele $(1,2)$, $(2,1)$, $(2,3)$, vârfurile 1 și 2 formează o componentă, iar 3 una separată. Fiecare vârf aparține exact unei componente.

Exemplul 3 — urmărirea calculului pe șase vârfuri. Graful are arcele $(1,2)$, $(2,1)$, $(2,3)$, $(3,4)$, $(4,5)$, $(5,3)$ și $(5,6)$. Pentru $x=1$, succesorii sunt $\{1,2,3,4,5,6\}$, iar predecesorii sunt $\{1,2\}$, deoarece la 1 se ajunge numai din 2 și din el însuși; intersecția este $\{1,2\}$. Primul vârf neatribuit este 3: succesorii lui sunt $\{3,4,5,6\}$, predecesorii $\{1,2,3,4,5\}$, deci componenta este $\{3,4,5\}$, circuitul $3\to 4\to 5\to 3$. Rămâne vârful 6, care are succesorii $\{6\}$ și toți ceilalți ca predecesori; componenta lui este $\{6\}$. Graful are trei componente. Arcele dintre ele, $(2,3)$ și $(5,6)$, merg numai de la $\{1,2\}$ spre $\{3,4,5\}$ și de la $\{3,4,5\}$ spre $\{6\}$, deci componentele nu formează niciun circuit. Cu matrice de adiacență, fiecare parcurgere cere $O(n^2)$ operații.

Nu confunda tare conexitatea cu proprietatea că graful neorientat obținut prin ignorarea sensurilor este conex. Ultima este mai slabă: arcele $(1,2)$ și $(2,3)$ dau un graf conex dacă ignori sensurile, dar nu un graf tare conex. Pentru un graf tare conex cu cel puțin două vârfuri, fiecare vârf trebuie să aibă grad intern și extern pozitiv; condiția este necesară, dar nu suficientă, fiindcă în graful cu arcele $(1,2)$, $(2,1)$, $(3,4)$, $(4,3)$ toate gradele sunt pozitive, dar nu există drum de la 1 la 3. Un graf cu $n\ge 2$ vârfuri care este tare conex are cel puțin $n$ arce, iar cele $n$ arce ale unui circuit care trece prin toate vârfurile sunt suficiente. Între componentele tare conexe, drumurile merg într-un singur sens: dacă se poate trece din componenta A în B, nu se poate trece și din B în A.

Exemplu în formatul examenului. Un graf orientat are vârfurile 1, 2, 3, 4, 5 și arcele $(1,2)$, $(2,3)$, $(3,1)$, $(3,4)$, $(4,5)$, $(5,4)$. Câte componente tare conexe are?

• a) 1
• b) 2
• c) 3
• d) 5

Răspunsul corect este b). Vârfurile 1, 2, 3 formează circuitul $1\to 2\to 3\to 1$, deci se ating reciproc. Vârfurile 4 și 5 se ating reciproc prin arcele $(4,5)$ și $(5,4)$. Arcul $(3,4)$ duce dintr-o componentă în cealaltă, dar nu există drum de la 4 sau 5 înapoi la 1, 2 sau 3. Varianta a) ar corespunde unui graf tare conex, iar aici graful este doar conex dacă ignori sensurile. Varianta c) ar presupune că vârfurile 4 și 5 nu se ating reciproc, iar d) ar presupune că fiecare vârf este singur în componenta lui.

Greșeli frecvente

• Greșit: un drum de la 1 la 3 garantează și drum de la 3 la 1.
  Corect: sensul arcelor poate împiedica întoarcerea.
• Greșit: ignorarea sensurilor păstrează testul de tare conexitate.
  Corect: verifică drumuri orientate în ambele sensuri.
• Greșit: un singur vârf accesibil din toate celelalte face graful tare conex.
  Corect: fiecare pereche trebuie conectată reciproc.

Înainte și după