Grafuri orientate

Graful folosit în exemple

Noțiuni fundamentale

Drum — o succesiune de vârfuri D = (x₁, x₂, …, x_k) cu proprietatea că oricare două vârfuri consecutive sunt extremitățile unui arc, adică (x_i, x_{i+1}) ∈ U pentru orice i de la 1 la k−1. Vârful x₁ este extremitatea inițială, iar x_k extremitatea finală. Lungimea drumului este numărul de arce care îl compun.

Exemplu: D = (1, 2, 3, 4, 5) este drum în G, de lungime 4, pentru că (1,2), (2,3), (3,4) și (4,5) sunt arce.

Drum elementar — un drum în care toate vârfurile sunt distincte, adică niciun vârf nu se repetă.

Exemplu: D = (1, 2, 4, 5) este drum elementar: vârfurile 1, 2, 4 și 5 apar o singură dată. În schimb, D = (1, 2, 3, 1, 2) nu este elementar, pentru că vârfurile 1 și 2 se repetă.

Drum simplu — un drum în care toate arcele sunt distincte, adică niciun arc nu este parcurs de două ori. Un drum elementar este întotdeauna și simplu, dar un drum simplu nu este neapărat elementar.

Exemplu: D = (3, 1, 2, 3, 4) este drum simplu, pentru că arcele (3,1), (1,2), (2,3) și (3,4) sunt distincte două câte două. El nu este drum elementar, pentru că vârful 3 apare de două ori.

Circuit — un drum simplu în care extremitatea inițială coincide cu extremitatea finală (x₁ = x_k), iar lungimea drumului este cel puțin 1.

Exemplu: C = (1, 2, 3, 1) este circuit: pornește și se încheie în vârful 1, iar arcele (1,2), (2,3) și (3,1) sunt distincte.

Circuit elementar — un circuit în care toate vârfurile sunt distincte, cu excepția primului și a ultimului, care coincid. Altfel spus, pentru circuitul C = (x₁, x₂, …, x_k), vârfurile x₁, x₂, …, x_{k−1} sunt distincte două câte două, iar x₁ = x_k.

Exemplu: C = (4, 5, 4) este circuit elementar, de lungime 2. La fel și C = (1, 2, 3, 1), de lungime 3.

Problema propusă

Enunț. Într-o rețea de transport public, stațiile sunt numerotate de la 1 la n, iar legăturile directe dintre ele sunt cu sens unic: de la stația a se poate ajunge direct la stația b, dar nu neapărat și invers. Se cere să se verifice dacă un vehicul care pleacă dintr-o stație dată p se poate întoarce în aceeași stație fără să circule în gol, adică dacă în graful orientat asociat rețelei există un circuit care trece prin vârful p.

Descrierea soluției în limbaj natural. Rețeaua se modelează printr-un graf orientat cu n vârfuri, în care fiecare legătură directă este un arc. Graful se reține prin matricea de adiacență a, în care a[i][j] = 1 dacă există legătură directă de la stația i la stația j și a[i][j] = 0 în caz contrar.

Un circuit care trece prin vârful p există dacă și numai dacă din p se poate ajunge, pe un drum de lungime cel puțin 1, înapoi în p. Se determină, prin parcurgere în adâncime pornind din p, toate vârfurile la care se poate ajunge din p. Dacă printre succesorii direcți ai vreunui vârf atins se află chiar p, atunci drumul parcurs până acolo, completat cu arcul către p, formează circuitul căutat.

Parcurgerea folosește un vector vizitat, în care se marchează vârfurile deja atinse, ca fiecare vârf să fie prelucrat o singură dată. Vârful de plecare p se marchează ca vizitat de la început. În timpul parcurgerii, dacă se întâlnește un arc (x, p), unde x este un vârf accesibil din p, atunci drumul de la p la x, completat cu arcul (x, p), determină existența unui circuit care trece prin p.

Implementarea soluției.

#include <iostream>
using namespace std;

int n, a[101][101], vizitat[101], plecare;

/* Parcurge in adancime graful pornind din varful x si intoarce 1 daca
   se gaseste un arc catre varful de plecare, 0 altfel.

   Testul y == plecare se face inaintea celui de vizitare: altfel, varful
   de plecare fiind deja marcat, arcul care inchide circuitul ar fi sarit. */
int seIntoarce(int x) {
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1) {
            if (y == plecare) return 1;
            if (!vizitat[y]) {
                vizitat[y] = 1;
                if (seIntoarce(y)) return 1;
            }
        }
    return 0;
}

int main() {
    int m, i, j;
    cin >> n >> m >> plecare;
    for (int k = 1; k <= m; k++) {
        cin >> i >> j;
        a[i][j] = 1;
    }

    vizitat[plecare] = 1;

    if (seIntoarce(plecare))
        cout << "DA";
    else
        cout << "NU";

    return 0;
}

Pentru graful G din exemplu și p = 1, programul afișează DA, pentru că există circuitul (1, 2, 3, 1). Pentru p = 5 afișează tot DA, prin circuitul (5, 4, 5). Dacă din rețea se elimină arcul (3,1), pentru p = 1 programul afișează NU.