SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Grafuri · lecția 12

Grafuri orientate: arce, grade, drumuri, circuite, tare conexitate

60 minmate-info

Înainte de lecția asta: XI.11 Parcurgerea grafurilor: în lățime (BFS) și în adâncime (DFS)

Ce vei ști după lecție

  • Cunoști terminologia: arc, extremitate inițială/finală, grad interior și exterior, drum, circuit.
  • Reprezinți un graf orientat prin matrice de adiacență (nesimetrică) și liste de succesori.
  • Aplici formulele pentru numărul de arce și suma gradelor.
  • Recunoști componentele tare conexe și construiești matricea drumurilor (Roy-Warshall).

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 12 din 21 · mai sunt 9Urmează: XI.13 · Arbori: definiție, arbori cu rădăcină, vectorul de tațiVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Când sensul contează

Un drum cu sens unic, o prietenie care nu e reciprocă (te urmăresc, dar nu-i urmărești), un curs care trebuie făcut înaintea altuia: legăturile au direcție. Le modelăm cu un graf orientat: G = (V, E) cu arce (x, y) care merg doar de la x la y. Arcul (x, y) este diferit de (y, x).

Graf orientat

Exemplu: n = 5, arcele (1,2), (2,3), (3,1), (3,4), (5,4).

Termen Definiție În exemplu
grad exterior d⁺(x) câte arce ies din x d⁺(3) = 2
grad interior d⁻(x) câte arce intră în x d⁻(4) = 2
vârf sursă d⁻ = 0 (nimic nu intră) 5
vârf destinație (sink) d⁺ = 0 (nimic nu iese) 4

Grade

La BAC

  • Σ d⁺(x) = Σ d⁻(x) = m: fiecare arc iese dintr-un vârf și intră în altul.
  • Numărul maxim de arce (fără bucle, cel mult un arc în fiecare sens între două vârfuri): n(n − 1), dublul celui de la grafuri neorientate.
  • Numărul de grafuri orientate distincte cu n vârfuri etichetate (fără bucle): 2^(n(n−1)).

2. Matricea de adiacență: nu mai e simetrică

a[i][j] = 1 dacă există arcul (i, j). Citim arcele cu a[x][y] = 1; (o singură atribuire).

Matricea

  • linia i: arcele care ies din i, deci d⁺(i) = suma liniei i;
  • coloana j: arcele care intră în j, deci d⁻(j) = suma coloanei j;
  • numărul de arce = numărul de 1 din matrice (nu se mai împarte la 2).

Listele de adiacență: L[x].push_back(y); o singură dată (doar vecinii în care se poate ajunge direct).

#include <iostream>
using namespace std;

int a[101][101], n, m;

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;                       // doar un sens!
    }
    for (int i = 1; i <= n; i++)           // gradele exterioare: sume pe linii
    {
        int s = 0;
        for (int j = 1; j <= n; j++) s += a[i][j];
        cout << s << ' ';
    }
    cout << '\n';
    for (int j = 1; j <= n; j++)           // gradele interioare: sume pe coloane
    {
        int s = 0;
        for (int i = 1; i <= n; i++) s += a[i][j];
        cout << s << ' ';
    }
    return 0;
}

De ce așa?

De ce linie pentru d⁺ și coloană pentru d⁻? a[i][j] descrie arcul de la i la j. Toate arcele care pleacă din i sunt pe linia i; toate cele care ajung în j sunt pe coloana j. Dacă încurci cele două, răspunsul la „sursă” și „destinație” se inversează.

Trace pentru gradele vârfului 3 (arcele (3,1) și (3,4) ies, (2,3) intră):

i linia i d⁺(i) coloana i d⁻(i)
1 0 1 0 0 0 1 0 0 1 0 0 1
2 0 0 1 0 0 1 1 0 0 0 0 1
3 1 0 0 1 0 2 0 1 0 0 0 1
4 0 0 0 0 0 0 0 0 1 0 1 2
5 0 0 0 1 0 1 0 0 0 0 0 0

3. Drumuri și circuite

  • drum: șir de vârfuri x₁, x₂, …, xₖ cu arcele (x₁,x₂), (x₂,x₃), … toate existente; lungimea = numărul de arce;
  • circuit: drum care se întoarce unde a plecat (x₁ = xₖ), fără să repete arce; circuit elementar = vârfuri distincte, în afară de primul = ultimul.

Drum și circuit

Atenție — greșeli frecvente

Spre deosebire de lanț (neorientat), la drum nu poți merge pe un arc „înapoi”: din 4 nu se poate ajunge la 3, deși se poate de la 3 la 4.

Ce vârfuri pot fi atinse dintr-un vârf?

Același DFS ca la grafuri neorientate, dar cu o singură atribuire la citire (și deci urmăm arcele doar în sensul lor):

#include <iostream>
using namespace std;

int a[101][101], viz[101], n, m;

void dfs(int x)
{
    viz[x] = 1;
    cout << x << ' ';
    for (int y = 1; y <= n; y++)
        if (a[x][y] && !viz[y]) dfs(y);
}

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    int start;
    cin >> start;
    dfs(start);
    return 0;
}

De ce așa?

Singura diferență față de graful neorientat este a[x][y] = 1 fără a[y][x]. Din 1 putem ajunge la 2, 3 și 4; din 5 doar la 4 (iar 4 nu mai are arce care ies).

4. Conexitate tare

Un graf orientat este tare conex dacă pentru orice două vârfuri x, y există drum de la x la y și de la y la x. O componentă tare conexă este o mulțime maximală de vârfuri cu această proprietate.

Tare conex

La BAC

  • Un graf tare conex cu n vârfuri are cel puțin n arce (un circuit care trece prin toate vârfurile este varianta minimă).
  • Un circuit este întotdeauna în interiorul unei componente tare conexe.
  • Graful condensat (fiecare componentă tare conexă devine un singur vârf) nu are circuite.

Test practic: graful este tare conex ⇔ din vârful 1 se poate ajunge la toate (în G) și din toate se poate ajunge la 1, adică din 1 se atinge tot în graful cu arcele inversate (matricea transpusă).

#include <iostream>
using namespace std;

int a[101][101], t[101][101], v1[101], v2[101], n, m;

void dfs(int x, int g[][101], int viz[])
{
    viz[x] = 1;
    for (int y = 1; y <= n; y++)
        if (g[x][y] && !viz[y]) dfs(y, g, viz);
}

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        t[y][x] = 1;                        // arcul inversat
    }
    dfs(1, a, v1);                          // ce atinge 1
    dfs(1, t, v2);                          // cine ajunge în 1
    bool tare = true;
    for (int i = 1; i <= n; i++)
        if (!v1[i] || !v2[i]) tare = false;
    cout << (tare ? "DA" : "NU");
    return 0;
}

De ce așa?

De ce e suficient să verificăm doar vârful 1? Dacă din 1 ajungem la oricine și oricine ajunge la 1, atunci pentru orice x, y: x → 1 → y este un drum de la x la y. De ce transpusa? Un drum de la i la 1 în G este un drum de la 1 la i în graful cu arcele inversate.

5. Grafuri speciale orientate

Graf Definiție Număr de arce
complet pentru orice x ≠ y ambele arce (x,y) și (y,x) n(n − 1)
turneu pentru orice x ≠ y exact unul dintre (x,y) și (y,x) n(n − 1)/2
fără circuite (DAG) nu există circuite cel mult n(n − 1)/2

DAG

Un graf fără circuite are o ordine topologică: vârfurile pot fi scrise în șir astfel încât toate arcele merg spre dreapta. Exemplu: sarcini cu dependențe (să te îmbraci înainte de a ieși).

6. Greșeli frecvente

Greșeala Efect Corect
a[x][y] = a[y][x] = 1 la graf orientat transformi arcele în muchii doar a[x][y] = 1
m = suma matricei / 2 jumătate din arce m = suma matricei
d⁺ pe coloană, d⁻ pe linie surse și destinații inversate linie = ies, coloană = intră
„lanț” pentru drum ignori sensul arcelor drum = respecți sensul
tare conex = „conex dacă ignor sensul” graful (1→2) are legătură, dar nu e tare conex drumuri în ambele sensuri

7. La BAC

La BAC

Întrebări tipice: „câte arce are graful dat prin matrice” (numeri 1-urile), „care vârf are gradul exterior / interior maxim”, „câte circuite elementare”, „câte componente tare conexe”, „număr minim de arce de adăugat pentru a deveni tare conex”, „număr maxim de arce într-un graf fără circuite” (n(n−1)/2: arcele merg doar „înainte” într-o ordine topologică). Începe prin a nota d⁺ și d⁻ pentru fiecare vârf.

8. Exersează pe hârtie

1. Graful orientat cu n = 4 și arcele (1,2), (1,3), (2,3), (3,4), (4,2). Scrie d⁺ și d⁻ pentru fiecare vârf.

2. Câte arce poate avea cel mult un graf orientat cu 8 vârfuri? Dar un graf orientat fără circuite?

3. Scrie matricea de adiacență a grafului de la exercițiul 1.

4. Are graful de la exercițiul 1 circuite? Care? Este tare conex?

5. Un graf orientat cu 6 vârfuri are 3 componente tare conexe, fiecare cu 2 vârfuri. Care este numărul minim de arce?

6. (BAC) Câte grafuri turneu (fără circuite) cu n = 4 vârfuri etichetate 1..4 există, dacă se cere ca vârful 1 să aibă gradul exterior 3?

7. Un graf orientat are 7 vârfuri și toate au gradul interior 2. Câte arce are?

8. Pentru DAG-ul din figura secțiunii 5 (arcele 1→2, 1→3, 2→4, 3→4), scrie toate ordinile topologice posibile.

9. Care este numărul minim de arce într-un graf orientat tare conex cu 100 de vârfuri?

10. Scrie un program care afișează sursele (d⁻ = 0) și destinațiile (d⁺ = 0) ale unui graf citit prin arce.

9. Mai departe (pentru cine vrea mai mult)

Sortare topologică (algoritmul lui Kahn). Cât timp există un vârf cu gradul interior 0: îl scoți, îl adaugi în rezultat și scazi gradul interior al vecinilor lui. Dacă toate vârfurile au fost scoase, graful nu avea circuite.

#include <iostream>
using namespace std;

int a[101][101], gint[101], coada[101], n, m;

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        gint[y]++;                              // gradul interior
    }
    int prim = 0, ultim = 0;
    for (int i = 1; i <= n; i++)
        if (gint[i] == 0) coada[ultim++] = i;
    while (prim < ultim)
    {
        int x = coada[prim++];
        cout << x << ' ';
        for (int y = 1; y <= n; y++)
            if (a[x][y] && --gint[y] == 0)      // y nu mai așteaptă pe nimeni
                coada[ultim++] = y;
    }
    return 0;
}

Dacă ultim < n la final, graful are circuit (vârfurile din circuit nu ajung niciodată cu gradul interior 0).

Matricea drumurilor (Roy-Warshall). d[i][j] = 1 dacă există drum de la i la j; se calculează cu trei for-uri, ca la Floyd (lecția XI.19).

Rețele sociale. „Cine urmărește pe cine” este un graf orientat; „prieteni” (reciproc) înseamnă că ambele arce există. PageRank, algoritmul de la început al Google, lucrează pe un astfel de graf cu miliarde de vârfuri.

Rezumat

  • Arc (x, y): doar de la x la y. d⁺ = ies (suma liniei), d⁻ = intră (suma coloanei); Σ d⁺ = Σ d⁻ = m.
  • Matrice nesimetrică, citire cu a[x][y] = 1; arce = numărul de 1; maxim n(n − 1) arce.
  • Drum / circuit respectă sensul; tare conex = drum în ambele sensuri între oricare două vârfuri (≥ n arce).
  • Fără circuite ⇒ ordine topologică, cel mult n(n − 1)/2 arce.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Parcurgeri BFS/DFS și grafuri orientate

  • Scrii de mână ordinea DFS și BFS, vectorul distanțelor `d` și vectorul de tați.
  • Citești un graf orientat din matrice: grade, drumuri, circuite, componente tare conexe.
  • Folosești BFS/DFS ca unealtă: lanț minim, vârfuri la distanța k, tare conexitate, ordine topologică.

Fișa acoperă și: XI.11

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • grade2#573

    ușoară
  • gradintnul#586

    ușoară
  • roy-warshall#580

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • cunoscuti#575

    ușoară
  • grade3#4153

    ușoară
  • ctcmax#3423

    ușoară
  • afiscicluri#576

    ușoară
  • tare-conexitate#583

    medie
  • drumuri#581

    medie

Pentru cei care vor mai mult

  • anunt#584

    medie

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. d⁺: 1 → 2, 2 → 1, 3 → 1, 4 → 1. d⁻: 1 → 0, 2 → 2 (de la 1 și 4), 3 → 2 (de la 1 și 2), 4 → 1. Suma d⁺ = 5 = suma d⁻ = m.

2. Maxim 8 · 7 = 56 arce. Fără circuite: cel mult 8 · 7 / 2 = 28.

3.

0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 0

4. Da: 2 → 3 → 4 → 2 (circuit de lungime 3). Nu este tare conex: din 2 nu se poate ajunge la 1 (niciun arc nu intră în 1).

5. Fiecare componentă tare conexă cu 2 vârfuri are nevoie de cel puțin 2 arce (x → y și y → x): 3 · 2 = 6 arce. (Între componente nu se cere nimic.)

6. Turneu fără circuite = ordinea topologică totală (o permutare a vârfurilor); vârful 1 cu d⁺ = 3 înseamnă că 1 este primul, iar restul pot fi ordonate în 3! = 6 moduri.

7. Suma gradelor interioare = 7 · 2 = 14 arce.

8. 1 este mereu primul și 4 mereu ultimul; 2 și 3 se pot alege în orice ordine: 1 2 3 4 și 1 3 2 4.

9. 100 arce (un circuit care trece prin toate vârfurile: 1 → 2 → … → 100 → 1).

10. Calculezi gint[] și gext[] la citire (la x y: gext[x]++, gint[y]++), apoi afișezi vârfurile cu gint[i] == 0 (surse) și cele cu gext[i] == 0 (destinații).