Lanț

Ce este

Într-un graf neorientat, un lanț este o succesiune de noduri

$v_0, v_1, v_2, \ldots, v_k$

în care oricare două noduri consecutive sunt unite printr-o muchie: există muchia dintre v0 și v1, dintre v1 și v2, și așa mai departe. Imaginea mentală: pornești dintr-un nod și, la fiecare pas, treci la un vecin pe o legătură care chiar există în graf — nu ai voie să „sari" între noduri neunite.

De aici pornesc trei precizări care apar mereu la grile și la olimpiadă:

• Lungimea lanțului = numărul de muchii parcurse, nu de noduri. Un lanț cu k + 1 noduri are lungimea k. Un singur nod, fără nicio muchie, este un lanț de lungime 0.
• Lanț simplu = un lanț în care nicio muchie nu se repetă. Ai voie să revii într-un nod deja vizitat, dar nu pe aceeași legătură.
• Lanț elementar = un lanț în care niciun nod nu se repetă. E cea mai strictă variantă: fiecare nod apare o singură dată.

Încă o chestiune de vocabular: „lanț" este termenul pentru grafuri neorientate, unde muchiile nu au sens. Noțiunea corespunzătoare pe grafuri orientate, unde parcurgi arcele doar în sensul lor, se numește drum. Dacă enunțul spune „lanț", gândește graf neorientat.

Cum arată

Pornește animația de mai jos. Se construiește pas cu pas lanțul 0 — 1 — 4 — 5 — 2: urmărește cum, la fiecare pas, muchia folosită se aprinde înainte ca nodul următor să intre în traseu — saltul e legal doar pentru că legătura există în graf. Nodurile deja parcurse rămân colorate, ca să vezi lanțul crescând.

Iată același lanț scris liniar, în ordinea parcurgerii:

Verifică pe rând că fiecare pas este legal: muchiile 0—1, 1—4, 4—5 și 5—2 există toate în graf, deci succesiunea chiar este un lanț. Niciun nod nu apare de două ori, deci este un lanț elementar (și, automat, simplu).

În schimb, succesiunea 0 — 1 — 3 NU este un lanț pe acest graf: între 1 și 3 nu există muchie, deci pasul al doilea e ilegal — ca și cum ai încerca să dai mâna cu cineva care nu e lângă tine.

Acum exemplul-cheie pentru grile — un lanț simplu, dar NU elementar, pe același graf:

Cele cinci muchii folosite — 3—4, 4—5, 5—0, 0—1, 1—4 — sunt toate diferite, deci lanțul e simplu. Dar traseul trece de două ori prin nodul 4, deci nu e elementar. Exact acest tip de exemplu decide răspunsul la grilele cu „care dintre următoarele lanțuri este elementar?".

Implementare C++

Reținem graful ca matrice de adiacență adj[u][v] = 1 dacă există muchia u—v. Pentru a verifica dacă o succesiune de noduri este lanț, controlăm fiecare pereche consecutivă; pentru elementar, numărăm aparițiile fiecărui nod.

#include <iostream>
using namespace std;

int adj[105][105];    // matrice de adiacenta: adj[u][v] = 1 daca exista muchia u-v
int aparitii[105];    // de cate ori apare fiecare nod in succesiune

int main() {
    int n, m;
    cin >> n >> m;    // n noduri, m muchii
    for (int e = 0; e < m; e++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1;    // graf neorientat: muchia exista in ambele sensuri
        adj[v][u] = 1;
    }

    int k;
    cin >> k;    // cate noduri are succesiunea de verificat
    int sir[105];
    for (int i = 0; i < k; i++) cin >> sir[i];

    bool esteLant = true;
    for (int i = 0; i + 1 < k; i++) {
        // fiecare pereche consecutiva trebuie unita printr-o muchie
        if (adj[sir[i]][sir[i + 1]] == 0) {
            esteLant = false;
            break;
        }
    }

    if (!esteLant) {
        cout << "NU este lant\n";
        return 0;
    }

    bool elementar = true;
    for (int i = 0; i < k; i++) {
        aparitii[sir[i]]++;
        if (aparitii[sir[i]] > 1) elementar = false;    // nod repetat
    }

    cout << "lant de lungime " << k - 1 << "\n";    // lungimea = nr de muchii
    if (elementar)
        cout << "elementar\n";
    else
        cout << "NU este elementar\n";

    // exemplu: sirul 0 1 4 5 2 pe graful din lectie -> lant de lungime 4, elementar
    return 0;
}

Observă două detalii. Pentru graf neorientat marcăm ambele sensuri (adj[u][v] și adj[v][u]), fiindcă muchia nu are direcție. Iar lungimea afișată este k - 1: succesiunea are k noduri, deci între ele sunt k - 1 muchii.