Grafuri orientate (doar matematică-informatică)

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:cifră, datăidee-cheie

• Doar la matematică-informatică.
• Diferența față de grafurile neorientate: legătura are sens. Se numește arc și se scrie cu paranteze rotunde.
• Din 46 de itemi de grafuri și arbori din 2023-2027, 15 sunt pe grafuri orientate, de obicei grile de 4 p; la modelul 2027 apare și la II.2.

Urmează · 1 min

Ideea, apoi numele oficial

4 min

Gândește-te la un oraș cu străzi cu sens unic. Intersecțiile sunt vârfuri, străzile sunt arce. Dintr-o intersecție pleacă niște străzi și în ea intră altele.

Urmează · 4 min

Reprezentarea

1 min

Matricea de adiacență are a[i][j]=1 dacă există arcul (i,j). Nu mai e neapărat simetrică.

Listele de adiacență dau, pentru fiecare vârf, vârfurile spre care pleacă arce:

1: 2
2: 3
3: 1, 4
4: (lista vidă)

Gradele, în C++, când ai matricea:

for(i=1;i<=n;i++)
{ ge[i]=0;
  gi[i]=0;
  for(j=1;j<=n;j++)
  { ge[i]=ge[i]+a[i][j];
    gi[i]=gi[i]+a[j][i];
  }
}

La citire, un arc se memorează într-un singur sens: a[x][y]=1;, fără a[y][x]. Cu liste, adaugi y doar în lista lui x.

Urmează · 1 min

Oficial: model 2027, II.2 (6 p)

2 min

Graf cu 5 vârfuri și arcele (4,5), (2,1), (3,1), (1,4), (1,2), (5,3). Se cere un drum cu lungimea minimum 3 și un circuit care nu este elementar.

Scrie arcele ca vecini: din 1 spre 2 și 4; din 2 spre 1; din 3 spre 1; din 4 spre 5; din 5 spre 3.

• Drum: 2, 1, 4, 5 are 3 arce.
• Circuit neelementar: trebuie să treacă de două ori printr-un vârf. Există două circuite elementare care se ating în 1: 1, 2, 1 și 1, 4, 5, 3, 1. Le pui cap la cap: 1, 2, 1, 4, 5, 3, 1.

Urmează · 2 min

Oficial: grade

3 min o întrebare la final

Iunie 2026, varianta 3, I.4. Se dă matricea cu liniile 0 1 0 0 1, 1 0 0 0 0, 1 1 0 1 0, 0 0 1 0 1, 0 0 1 1 0. Se cere numărul de vârfuri la care diferența absolută dintre gradul intern și cel extern este 1.

Răspuns: 2, varianta a.

August 2025, varianta 4, I.4. Arcele sunt (3,1), (4,1), (4,2), (4,3), (5,6), (6,4). Se cere numărul de vârfuri cu gradul extern egal cu cel intern.

Vârfurile 3 și 6, deci 2, varianta b.

Urmează · 3 min

Oficial: circuite

3 min o întrebare la final

Sesiunea specială 2026, varianta 4, I.4. Matricea are liniile 0 1 1 0, 1 0 1 0, 0 0 0 1, 1 1 0 0. Se cere un circuit elementar. Verifică fiecare variantă, arc cu arc:

• 1, 2, 1, 3, 4, 1 trece de două ori prin 1, deci nu e elementar.
• 1, 2, 3, 4 nu revine în 1.
• 1, 3, 4, 2, 1 are arcele (1,3), (3,4), (4,2), (2,1), toate în matrice. Varianta c.
• 1, 4, 3, 2, 1 folosește (1,4), care nu există.

Model 2025, I.4. Arcele sunt (1,2), (1,6), (2,3), (3,1), (3,4), (4,5), (5,3), (5,6). Varianta corectă e 1, 2, 3, 1 (b). 1, 2, 3 nu se închide, 1, 2, 3, 4, 5, 3, 1 repetă 3, iar 1, 2, 3, 4, 5, 6, 1 folosește arcul (6,1), care nu există.

Iunie 2025, varianta 1, I.5. Graf fără circuite, cu 10 vârfuri, număr maxim de arce. Așază vârfurile în linie și trage arce doar spre dreapta. Fiecare pereche are un arc: 10·9/2 = 45, varianta b. Două arce pe aceeași pereche, câte unul în fiecare sens, ar forma un circuit.

Urmează · 3 min

Oficial: componente tare conexe

8 min o întrebare la final

Model 2023, I.4. Arcele sunt (1,2), (1,3), (2,3), (2,6), (3,2), (3,4), (3,6), (4,5), (4,7), (6,1), (7,4). Se cere numărul de vârfuri al componentei tare conexe a lui 3.

Din 3 ajungi la 2, 4, 5, 6, 7, 1. Ca să se întoarcă la 3, un vârf trebuie să aibă și drum înapoi: 1, 2, 6 da; 4, 5, 7 nu, pentru că din 4 și 7 nu se revine. Componenta este 1, 2, 3, 6, deci 4, varianta c.

La rezervă 2025, o verificare rapidă: după (3,2), din vârful 5 nu pleacă niciun arc, deci nu poate intra în componentă.

La specială 2023, drumul este 1, 2, 4, 8, 16, 15, 14, 13, 12, 11, 22, 21, 20, 19, 18, 17, adică 16 vârfuri. De la 17 s-ar ajunge la 16, deja folosit, deci drumul elementar se oprește.

Urmează · 8 min

Ce se cere la BAC

3 mincum apare la examen

Urmează · 3 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Citești linia ca grad intern: linia pleacă, coloana intră.
• Scrii arcul în sensul invers.
• Uiți să închizi circuitul, scriind și primul vârf la final.
• Confunzi tare conex cu conex: trebuie drum în ambele sensuri.
• Numeri arcele ca la muchii: în graful orientat, două vârfuri pot avea două arce, câte unul pe sens.
• Scrii [1,2] în loc de (1,2): parantezele drepte sunt pentru muchii.

Urmează · 1 min