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
- Când sensul contează
- Matricea de adiacență: nu mai e simetrică
- Drumuri și circuite
- Conexitate tare
- Grafuri speciale orientate
- Greșeli frecvente
- La BAC
- Exersează pe hârtie
- Mai departe (pentru cine vrea mai mult)
- Rezumat
- Fișa de lucru
- Probleme de lucru
- Temă
- Pentru cei care vor mai mult
- Grile din subiectele de BAC
- Citește și exersează în plus
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Parcurgeri BFS/DFS și grafuri orientate
6 pagini · 100 min
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).
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 |
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).
- 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.
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.
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 |
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.
- ușoară
grade2#573
https://www.pbinfo.ro/probleme/573/grade2
- ușoară
gradintnul#586
https://www.pbinfo.ro/probleme/586/gradintnul
- ușoară
roy-warshall#580
https://www.pbinfo.ro/probleme/580/roy-warshall
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
cunoscuti#575
https://www.pbinfo.ro/probleme/575/cunoscuti
- ușoară
grade3#4153
https://www.pbinfo.ro/probleme/4153/grade3
- ușoară
ctcmax#3423
https://www.pbinfo.ro/probleme/3423/ctcmax
- ușoară
afiscicluri#576
https://www.pbinfo.ro/probleme/576/afiscicluri
- medie
tare-conexitate#583
https://www.pbinfo.ro/probleme/583/tare-conexitate
- medie
drumuri#581
https://www.pbinfo.ro/probleme/581/drumuri
Pentru cei care vor mai mult
- medie
anunt#584
https://www.pbinfo.ro/probleme/584/anunt
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.
- #133proprietăți ale unui graf orientat cu n vârfuri
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=133
- #142arce de adăugat pentru a obține o proprietate
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=142
- #213numărul de circuite pentru un graf dat prin matrice
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=213
- #515graf fără circuite: număr maxim de arce
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=515
- #644graf fără circuite cu 8 vârfuri: arce maxime
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=644
- #656componente tare conexe și arce
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=656
- #1066graf orientat cu 5 vârfuri dat prin desen: grade, drumuri
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1066
- #1122arce minime pentru un graf tare conex
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1122
- #1152graf cu 10 vârfuri și 12 arce: valoarea maximă a unui grad
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1152
- #1795graf cu 4 vârfuri dat prin matrice de adiacență
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1795
Citește și exersează în plus
- Teorie grafuri orientate · pbinfo.ro
https://www.pbinfo.ro/articole/509/grafuri-orientate
- Graf tare conex. Componente tare conexe · pbinfo.ro
https://www.pbinfo.ro/articole/6036/tare-conexitate
- Matricea drumurilor. Algoritmul Roy-Warshall · pbinfo.ro
https://www.pbinfo.ro/articole/5888/matricea-drumurilor
- Graf orientat — definiții · ro.wikipedia.org
terminologia completă, cu exemple (arc, drum, circuit, conexitate tare)
https://ro.wikipedia.org/wiki/Graf_orientat
- VisuAlgo — Topological Sort · visualgo.net
DFS/BFS pe grafuri orientate și ordinea topologică (engleză)
https://visualgo.net/en/dfsbfs
- CSES — Course Schedule · cses.fi
sortare topologică: ordinea în care parcurgi cursurile (engleză)
https://cses.fi/problemset/task/1679
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 04. 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).