Drum

Ce este

Într-un graf orientat, un drum este o succesiune de noduri $v_0, v_1, v_2, \ldots, v_k$ în care fiecare pereche de noduri consecutive este legată printr-un arc parcurs în sensul săgeții: există arcul $v_i \to v_{i+1}$ pentru fiecare $i$. Este exact aceeași idee de „înlănțuire de noduri” ca la lanț, cu o singură deosebire — dar una esențială: legăturile sunt arce, iar un arc se poate parcurge doar în sensul lui. Arcul 1→2 te lasă să treci de la 1 la 2, nu și invers.

• Lungimea drumului = numărul de arce parcurse ($k$, dacă drumul are $k+1$ noduri).
• Drumul este simplu dacă niciun arc nu se repetă.
• Drumul este elementar dacă niciun nod nu se repetă (implicit, e și simplu).
• Capetele drumului: nodul de start $v_0$ și nodul de final $v_k$.

Fiecare noțiune de pe grafuri neorientate are o „pereche” pe grafuri orientate. Ține corespondența la îndemână — la teste se pierd puncte exact pe ea:

Cum arată

Urmărește mai întâi mecanismul de construire a unui traseu: pornești dintr-un nod și avansezi pas cu pas, aprinzând de fiecare dată legătura folosită. Fii atent la două lucruri: fiecare salt se face doar pe o legătură existentă și niciun nod nu se repetă — proprietatea de drum elementar.

O notă de vocabular: în unele manuale și culegeri, termenul „drum” apare și pe grafuri neorientate, cu sensul de „lanț cu noduri distincte” — accepțiunea din animația de mai sus. În programa de bacalaureat și în această lecție folosim convenția standard: drum ↔ graf orientat, lanț ↔ graf neorientat. Când citești un enunț, verifică întâi dacă graful e orientat sau nu.

Acum pe un graf orientat concret. Fie arcele 1→2, 2→4, 4→3, 3→1 și 2→3. Verificăm dacă secvența 1, 2, 4 este un drum:

Fiecare pereche consecutivă respectă sensul: de la 1 la 2 ai arcul 1→2, de la 2 la 4 ai arcul 2→4. Drumul e valid.

Atenție acum la sens. Citim aceeași secvență invers:

Pe un graf neorientat, secvența citită invers ar fi fost automat un lanț valid. Pe graf orientat, inversarea nu e niciodată garantată — fiecare arc trebuie verificat în sensul lui.

Înseamnă asta că din 4 nu poți ajunge deloc înapoi la 1? Nu neapărat — doar că nu pe traseul inversat:

Exact ca în orașul cu sensuri unice: întoarcerea, dacă există, poate arăta complet diferit de dus. Iar dacă graful ar fi avut doar arcele 1→2 și 2→4, din 4 n-ai fi putut pleca nicăieri — drumul de întoarcere pur și simplu nu ar fi existat.

Implementare C++

Reprezentăm graful orientat cu o matrice de adiacență: adiacent[a][b] = 1 înseamnă că există arcul a → b — și nu spune nimic despre b → a. Apoi verificăm dacă o secvență dată de noduri formează un drum valid: fiecare pereche consecutivă trebuie să aibă arc în sensul parcurgerii.

#include <iostream>
using namespace std;

int adiacent[105][105];    // adiacent[a][b] = 1 daca exista arcul a -> b

// verifica daca secventa v[0], v[1], ..., v[k-1] e drum valid
bool esteDrum(int v[], int k) {
    for (int i = 0; i < k - 1; i++) {
        // pereche consecutiva: trebuie arc in sensul v[i] -> v[i+1]
        if (adiacent[v[i]][v[i + 1]] == 0) {
            return false;          // lipseste arcul in sensul corect
        }
    }
    return true;
}

int main() {
    // arce orientate: 1->2, 2->4, 4->3, 3->1, 2->3
    adiacent[1][2] = 1;
    adiacent[2][4] = 1;
    adiacent[4][3] = 1;
    adiacent[3][1] = 1;
    adiacent[2][3] = 1;

    int drum1[] = {1, 2, 4};       // 1->2->4, in sensul arcelor
    cout << esteDrum(drum1, 3) << "\n";    // 1 (este drum)

    int drum2[] = {4, 2, 1};       // secventa inversata
    cout << esteDrum(drum2, 3) << "\n";    // 0 (merge contra sensului)

    int drum3[] = {4, 3, 1};       // intoarcere pe alt traseu
    cout << esteDrum(drum3, 3) << "\n";    // 1 (ocolirea e drum valid)

    return 0;
}

Cheia e că testăm adiacent[v[i]][v[i+1]], în ordinea exactă a parcurgerii. Pe graf orientat această ordine contează: adiacent[1][2] poate fi 1, în timp ce adiacent[2][1] rămâne 0. Verificarea rulează în timp proporțional cu lungimea secvenței — un test pe fiecare pereche consecutivă.