Lanțuri și cicluri

Un lanț dintr-un graf neorientat este o succesiune de vârfuri în care fiecare pereche consecutivă este legată printr-o muchie. Pentru muchiile [1,2] și [2,3], 1–2–3 este lanț de lungime 2. Dacă vârfurile nu se repetă, lanțul este elementar. Dacă muchiile nu se repetă, este simplu. Un ciclu este un lanț cu muchii distincte care se întoarce la vârful de plecare; dacă, în afară de acesta, vârfurile sunt distincte, ciclul este elementar. Într-un graf orientat, folosim termenul „drum” și urmăm sensul arcelor.

În graful neorientat, un lanț este o succesiune de vârfuri $[x_1,x_2,\dots ,x_k]$ în care oricare două consecutive sunt adiacente. Lungimea este numărul muchiilor parcurse, adică $k-1$, nu numărul vârfurilor scrise. Lanțul este elementar dacă vârfurile sunt distincte și simplu dacă muchiile sunt distincte; orice lanț elementar este și simplu. Un ciclu este un lanț simplu cu primul și ultimul vârf identice; este elementar dacă celelalte vârfuri sunt distincte. În graful orientat, succesiunea de arce care respectă sensul formează un drum, iar drumul închis este circuit.

Pentru muchiile $[1,2]$, $[2,3]$, $[3,1]$, succesiunea 1–2–3–1 este ciclu elementar de lungime 3. Succesiunea 1–2–1 este lanț de lungime 2, dar nici elementar, nici simplu: repetă muchia $[1,2]$.

Exemplul 1 — clasificarea unei succesiuni. Graful are muchiile $[1,2]$, $[2,3]$, $[3,1]$, $[3,4]$. Programul citește o succesiune și verifică dacă este lanț, apoi calculează lungimea și dacă este elementar sau simplu:

#include <iostream>
using namespace std;
int main() {
    int a[5][5] = {}, x[21], k;
    a[1][2] = a[2][1] = a[2][3] = a[3][2] = a[3][1] = a[1][3] = a[3][4] = a[4][3] = 1;
    cin >> k;
    for (int i = 0; i < k; ++i) cin >> x[i];
    bool lant = true, elementar = true, simplu = true;
    for (int i = 0; i + 1 < k; ++i)
        if (!a[x[i]][x[i + 1]]) lant = false;
    for (int i = 0; i < k; ++i)
        for (int j = i + 1; j < k; ++j)
            if (x[i] == x[j]) elementar = false;
    for (int i = 0; i + 1 < k; ++i)
        for (int j = i + 1; j + 1 < k; ++j)
            if ((x[i] == x[j] && x[i + 1] == x[j + 1]) || (x[i] == x[j + 1] && x[i + 1] == x[j]))
                simplu = false;
    cout << lant << " " << k - 1 << " " << elementar << " " << simplu;
}

Pentru 4 și 1 2 3 4 se afișează 1 3 1 1: lanț elementar de lungime 3. Pentru 4 și 1 2 3 1 se afișează 1 3 0 1: vârful 1 se repetă, deci lanțul nu este elementar, dar muchiile sunt distincte, deci este simplu (este chiar un ciclu). Pentru 3 și 1 2 1 se afișează 1 2 0 0: muchia $[1,2]$ este parcursă de două ori. Pentru 3 și 1 2 4 se afișează 0 2 1 1: nu există muchia $[2,4]$, deci succesiunea nu este lanț și celelalte două valori nu au sens.

Exemplul 2 — cel mai scurt lanț. Pe graful cu muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,2]$, între vârfurile 1 și 4 există lanțul 1–2–3–4 de lungime 3 și lanțul 1–2–4 de lungime 2. Un lanț elementar nu este neapărat cel mai scurt: parcurgerea în lățime pornită din 1 găsește vârful 2 la distanța 1, iar vârfurile 3 și 4 la distanța 2, deci cel mai scurt lanț dintre 1 și 4 are lungimea 2. În același graf, 2–3–4–2 este un ciclu elementar de lungime 3. Un ciclu poate fi parcurs începând din oricare dintre vârfurile lui, deci 3–4–2–3 este același ciclu.

Exemplul 3 — ciclurile de lungime 3. Un ciclu elementar de lungime 3 este format din trei vârfuri $i<j<k$ legate două câte două. Cu matricea de adiacență a, fiecare triplet se testează printr-o singură condiție:

int nr = 0;
for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
        for (int k = j + 1; k <= n; ++k)
            if (a[i][j] && a[j][k] && a[i][k])
                ++nr;

Pe graful cu muchiile $[1,2]$, $[2,3]$, $[3,1]$, $[3,4]$ se examinează patru triplete: $(1,2,3)$ are toate cele trei muchii, deci se numără; $(1,2,4)$, $(1,3,4)$ și $(2,3,4)$ nu se numără, pentru că lipsesc muchiile $[1,4]$ și $[2,4]$. Rezultatul este nr = 1. Cerința $i<j<k$ face ca același ciclu, scris 1–2–3–1 sau 2–3–1–2, să fie numărat o singură dată. O succesiune de forma 1–2–1 nu este ciclu, deoarece folosește aceeași muchie de două ori.

La un ciclu elementar în graf simplu, sunt necesare cel puțin trei vârfuri distincte înaintea revenirii la start. În triunghi, 1–2–3–1 are lungimea 3, nu 4: vârful de început repetat la final nu adaugă o muchie suplimentară. Existența unui lanț între oricare două vârfuri caracterizează conexitatea. Un graf conex cu $n$ vârfuri și $n-1$ muchii nu are niciun ciclu, iar un graf simplu cu $n$ vârfuri și cel puțin $n$ muchii are cel puțin un ciclu. Când ți se cere „lungimea” unui lanț sau ciclu, numără muchiile din desen sau din lista dată, nu vârfurile din succesiune. Dacă un ciclu elementar are lungimea $k$, el trece prin exact $k$ vârfuri distincte, deoarece vârful de start apare de două ori în scriere, dar este numărat o singură dată.

Exemplu în formatul examenului. Un graf neorientat are vârfurile 1, 2, 3, 4 și muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,2]$. Care este lungimea celui mai scurt lanț între vârfurile 1 și 4?

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

Răspunsul corect este b). Muchia $[1,4]$ nu există, deci lungimea 1 este exclusă. Din 1 se poate merge numai la 2, iar din 2 se ajunge direct la 4 prin muchia $[4,2]$. Lanțul 1–2–4 are două muchii. Varianta c) este lungimea lanțului 1–2–3–4, care este elementar, dar mai lung. Varianta d) numără vârfurile lanțului 1–2–3–4 în loc de muchii.

Greșeli frecvente

• Greșit: lungimea lanțului este numărul vârfurilor scrise.
  Corect: este numărul muchiilor parcurse.
• Greșit: 1–2–3–1 este ciclu chiar dacă lipsește muchia $\{3,1\}$.
  Corect: fiecare trecere trebuie să fie o muchie.
• Greșit: vârful de start scris din nou la final mărește lungimea ciclului cu încă o muchie.
  Corect: lungimea triunghiului este 3.

Înainte și după