clasa a XI-a · Grafuri · lecția 9
Grafuri neorientate (1): noțiuni de bază, grad, reprezentări
60 minmate-info
Înainte de lecția asta: X.8 Tablouri bidimensionale (matrice): declarare, parcurgere pe linii și coloane
Ce vei ști după lecție
- Cunoști terminologia: vârf (nod), muchie, adiacență, incidență, grad, vârf izolat, vârf terminal.
- Aplici formula sumei gradelor și numărul maxim de muchii.
- Reprezinți un graf prin matrice de adiacență, liste de adiacență și lista muchiilor.
- Recunoști lanțuri, cicluri, subgrafuri și grafuri parțiale.
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a XI-aLecția 9 din 21 · mai sunt 12Urmează: XI.10 · Grafuri neorientate (2): conexitate, graf complet, bipartit, hamiltonian, eulerianVezi toate lecțiile
Cuprins
- Ce este un graf
- Suma gradelor: formula care apare la fiecare Bac
- Trei moduri de a păstra un graf în memorie
- Lanțuri și cicluri
- Subgraf și graf parțial
- 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: Grafuri neorientate
6 pagini · 100 min
1. Ce este un graf
Un graf modelează lucruri legate între ele: orașe unite prin drumuri, elevi care sunt prieteni, calculatoare dintr-o rețea, pagini web cu legături. Nu contează cum arată desenul, ci cine cu cine este legat.
Un graf neorientat G = (V, E) are:
- vârfuri (noduri) V = {1, 2, …, n};
- muchii E: fiecare muchie leagă două vârfuri, [x, y]. Muchia [x, y] este aceeași cu [y, x] (drumul merge în ambele sensuri).
Exemplu: n = 5, muchiile [1,2], [1,3], [2,3], [3,4]. Vârful 5 nu e legat de nimeni.
| Termen | Definiție | În exemplu |
|---|---|---|
| vârfuri adiacente | legate printr-o muchie | 1 și 2 |
| muchie incidentă cu x | muchie care îl conține pe x | [3,4] e incidentă cu 3 și cu 4 |
| gradul lui x, d(x) | numărul de muchii incidente cu x | d(3) = 3 |
| vârf izolat | grad 0 | 5 |
| vârf terminal | grad 1 | 4 |
Sfat
Gradul = „câți vecini are”. Pe desen: numeri liniile care pleacă din vârf.
2. Suma gradelor: formula care apare la fiecare Bac
Suma gradelor = 2 · m. De ce: fiecare muchie are două capete, deci contribuie cu 1 la gradul fiecăruia dintre cele două vârfuri, adică 2 în total.
La BAC
- Σ d(x) = 2m; de aici, numărul de vârfuri cu grad impar este întotdeauna par.
- Numărul maxim de muchii: n(n − 1)/2 (fiecare pereche de vârfuri este legată: graf complet).
- Numărul de grafuri distincte cu n vârfuri etichetate: 2^(n(n−1)/2) (fiecare pereche are muchie sau nu).
Cum se folosesc:
| Întrebare | Raționament | Răspuns |
|---|---|---|
| Graf cu 7 vârfuri, gradele 1, 2, 2, 3, 3, 4, x. Ce poate fi x? | 15 + x trebuie să fie par, deci x impar; x ≤ 6 | 1, 3 sau 5 |
| Graf complet cu 20 de muchii? | n(n−1)/2 = 20 nu are soluție întreagă (n = 6 dă 15, n = 7 dă 21) | nu există |
| Un graf are 10 vârfuri și toate au gradul 3. Câte muchii? | 10 · 3 / 2 | 15 |
| Câte grafuri cu 4 vârfuri (etichetate)? | 2^(4·3/2) = 2⁶ | 64 |
3. Trei moduri de a păstra un graf în memorie
3.1 Matricea de adiacență
a[i][j] = 1 dacă [i, j] este muchie, altfel 0.
- este simetrică față de diagonala principală (muchia e în ambele sensuri);
- diagonala conține doar 0 (nu există muchii de la un vârf la el însuși);
- gradul lui i = suma liniei i; numărul de muchii = (numărul de 1) / 2.
3.2 Listele de adiacență
Pentru fiecare vârf, lista vecinilor lui.
3.3 Lista muchiilor
Un șir de perechi (x, y), exact forma în care se citesc datele: [1,2] [1,3] [2,3] [3,4].
De știut
Care alegi? Matricea: simplă, răspunde în O(1) la „există muchia [i, j]?”, dar ocupă n² (bună pentru n ≤ 1000). Listele: ocupă doar 2m, parcurgerea vecinilor unui vârf e rapidă (bune pentru grafuri mari cu puține muchii). La Bac cele mai frecvente sunt matricea și listele.
Citirea grafului: din muchii în matrice
Intrarea: n m, apoi m perechi x y. Programul de mai jos construiește matricea și afișează gradele.
#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] = a[y][x] = 1; // muchia merge în ambele sensuri
}
for (int i = 1; i <= n; i++)
{
int grad = 0;
for (int j = 1; j <= n; j++) grad += a[i][j];
cout << grad << ' ';
}
return 0;
}De ce așa?
De ce a[x][y] = a[y][x] = 1? Muchia [x, y] este aceeași cu [y, x]. Dacă am nota doar a[x][y], matricea nu ar mai fi simetrică și gradul lui y ar ieși greșit. De ce suma pe linie? a[i][j] = 1 exact pentru vecinii j ai lui i; numărând 1-urile de pe linia i numărăm vecinii.
Trace pentru primele două muchii (1 2 și 1 3) și gradul vârfului 3:
| Pas | citit | a[x][y] | a[y][x] | grad(3) după parcurgerea liniei 3 |
|---|---|---|---|---|
| 1 | 1 2 | a[1][2] = 1 | a[2][1] = 1 | |
| 2 | 1 3 | a[1][3] = 1 | a[3][1] = 1 | |
| 3 | 2 3 | a[2][3] = 1 | a[3][2] = 1 | |
| 4 | 3 4 | a[3][4] = 1 | a[4][3] = 1 | linia 3 = 1 + 1 + 0 + 1 + 0 = 3 |
Aceleași date, cu liste de adiacență
#include <iostream>
#include <vector>
using namespace std;
vector<int> L[101];
int n, m;
int main()
{
cin >> n >> m;
for (int k = 1; k <= m; k++)
{
int x, y;
cin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
cout << i << ":";
for (int j = 0; j < (int)L[i].size(); j++) cout << ' ' << L[i][j];
cout << '\n';
}
return 0;
}De ce așa?
De ce L[i].size() este gradul? Lista lui i conține exact vecinii lui i. De ce push_back de două ori? Tot pentru că muchia merge în ambele sensuri: y e vecin al lui x și x e vecin al lui y.
Din matrice: câte muchii, care vârfuri sunt izolate
#include <iostream>
using namespace std;
int a[101][101], n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cin >> a[i][j];
int suma = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) suma += a[i][j];
cout << suma / 2 << '\n'; // m = (suma gradelor) / 2
for (int i = 1; i <= n; i++)
{
int grad = 0;
for (int j = 1; j <= n; j++) grad += a[i][j];
if (grad == 0) cout << i << ' '; // vârf izolat
}
return 0;
}De ce așa?
De ce împărțim la 2? Fiecare muchie apare de două ori în matrice (în a[i][j] și în a[j][i]). Suma tuturor valorilor este suma gradelor, deci 2m.
Intrare / ieșire
| Intrare | Ieșire |
|---|---|
5 41 21 32 33 4 |
2 2 3 1 0 (gradele) |
| aceeași intrare, listele de adiacență | 1: 2 32: 1 33: 1 2 44: 35: |
4. Lanțuri și cicluri
- lanț: șir de vârfuri x₁, x₂, …, xₖ în care oricare două consecutive sunt adiacente; lungimea = numărul de muchii (k − 1);
- lanț elementar: vârfurile sunt distincte;
- ciclu: lanț cu primul vârf = ultimul și muchii distincte; ciclu elementar: vârfurile distincte (în afară de primul = ultimul).
Atenție — greșeli frecvente
Un ciclu are cel puțin 3 vârfuri distincte: 1, 2, 1 nu e ciclu (folosește aceeași muchie de două ori).
5. Subgraf și graf parțial
- graf parțial: aceleași vârfuri, se elimină unele muchii;
- subgraf: se elimină unele vârfuri, iar odată cu ele dispar toate muchiile incidente.
Sfat
Reține: „parțial” = păstrez toate nodurile (scot doar muchii). „subgraf” = scot noduri. Un graf cu m muchii are 2ᵐ grafuri parțiale (fiecare muchie rămâne sau nu), inclusiv el însuși și graful fără muchii.
6. Greșeli frecvente
| Greșeala | Efect | Corect |
|---|---|---|
a[x][y] = 1; fără a[y][x] = 1; |
matrice nesimetrică, grade greșite | ambele |
int a[100][100] cu n = 100 |
indici 1..100, depășire | a[101][101] |
| gradul = numărul de 1 din toată matricea | număr de 2m, nu d(i) | suma liniei i |
| m = suma gradelor | de două ori prea mult | m = suma / 2 |
| confuzia parțial / subgraf | răspuns greșit la grilă | parțial = scot muchii |
ciclu 1, 2, 1 |
nu e ciclu | cel puțin 3 vârfuri |
7. La BAC
La BAC
La Subiectul I apar mai ales: „care este gradul maxim / minim”, „câte muchii are graful dat prin matrice/liste”, „care vârfuri sunt izolate / terminale”, „care dintre șirurile următoare poate fi șirul gradelor” (suma pară, fiecare grad ≤ n − 1), „câte grafuri parțiale / distincte există”. Se rezolvă cu formulele din secțiunea 2: scrii gradele, aplici suma = 2m, verifici.
8. Exersează pe hârtie
Răspunsurile sunt la finalul paginii: încearcă întâi singur.
1. Un graf are 6 vârfuri cu gradele 3, 3, 2, 2, 1, x. Câte valori poate lua x (0 ≤ x ≤ 5)? Care?
2. Care este numărul maxim de muchii ale unui graf cu 9 vârfuri? Dar dacă vârful 1 este izolat?
3. Un graf cu 8 vârfuri este regulat de grad 3. Câte muchii are?
4. Câte grafuri parțiale are un graf cu 5 muchii?
5. Desenează graful dat prin matricea de adiacență:
0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0Câte muchii are? Care sunt vârfurile terminale?
6. Scrie listele de adiacență pentru graful cu n = 4 și muchiile [1,2], [1,3], [1,4], [3,4].
7. (BAC) Poate fi șirul 4, 3, 3, 2, 2 secvența gradelor unui graf cu 5 vârfuri? Dar 4, 4, 4, 1, 1?
8. Câte grafuri neorientate distincte (cu vârfurile etichetate 1..n) există pentru n = 5?
9. Un graf are 8 vârfuri și 14 muchii, iar fiecare vârf are gradul 3 sau 4. Câte vârfuri au gradul 4?
10. Scrie un program care citește n, m și muchiile și afișează vârfurile de grad maxim.
9. Mai departe (pentru cine vrea mai mult)
Teorema „strângerilor de mână”. Numărul de persoane care au dat mâna cu un număr impar de persoane este par: este exact faptul că numărul de vârfuri de grad impar este par.
Secvența gradelor: testul lui Havel-Hakimi. Un șir de grade (sortat descrescător) d₁ ≥ d₂ ≥ … este valid dacă, scăzând 1 din următoarele d₁ valori și eliminând d₁, șirul rămas este valid. Exemplu: 3, 3, 2, 2, 2 → scoți 3, scazi 1 din următoarele 3: 2, 1, 1, 2 → sortezi 2, 2, 1, 1 → scoți 2: 1, 0, 1 → sortezi 1, 1, 0 → scoți 1: 0, 0 → valid.
Grafuri mari. Pentru n = 100 000 matricea nu încape în memorie (10¹⁰ elemente); se folosesc doar listele de adiacență.
Multigrafuri și bucle. Dacă două vârfuri au mai multe muchii sau o muchie se întoarce în același vârf, nu mai avem graf „simplu”; matricea ar conține numere > 1 sau valori pe diagonală.
Rezumat
- Graf = vârfuri + muchii; gradul = numărul de vecini; izolat = grad 0; terminal = grad 1.
- Σ grade = 2m; m maxim = n(n−1)/2; grafuri distincte cu n vârfuri: 2^(n(n−1)/2).
- Matricea: simetrică, diagonala 0, gradul = suma liniei. Listele:
L[x].push_back(y)șiL[y].push_back(x). - Graf parțial = scot muchii; subgraf = scot vârfuri.
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
Grafuri neorientate
- Citești un graf din matrice sau din lista de muchii și afli rapid grade, muchii, componente.
- Rezolvi itemii de BAC cu formule: muchii de adăugat/eliminat, grafuri parțiale, subgrafuri, șiruri de grade.
- Recunoști și testezi în cod grafurile conexe, bipartite, euleriene și hamiltoniene.
Fișa acoperă și: XI.10
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ă
adiacenta#412
https://www.pbinfo.ro/probleme/412/adiacenta
- ușoară
listavecini#414
https://www.pbinfo.ro/probleme/414/listavecini
- ușoară
grade#416
https://www.pbinfo.ro/probleme/416/grade
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
adiacenta1#413
https://www.pbinfo.ro/probleme/413/adiacenta1
- ușoară
gradmax#417
https://www.pbinfo.ro/probleme/417/gradmax
- ușoară
izolate#430
https://www.pbinfo.ro/probleme/430/izolate
- ușoară
subgraf#418
https://www.pbinfo.ro/probleme/418/subgraf
- ușoară
graf-partial#420
https://www.pbinfo.ro/probleme/420/graf-partial
- ușoară
veriflant#474
https://www.pbinfo.ro/probleme/474/veriflant
- ușoară
matad#2707
https://www.pbinfo.ro/probleme/2707/matad
Pentru cei care vor mai mult
- ușoară
gradek#4068
https://www.pbinfo.ro/probleme/4068/gradek
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.
- #3câte grafuri neorientate distincte există cu n vârfuri (2^(n(n-1)/2))
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=3
- #67suma gradelor și numărul de muchii
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=67
- #86graf complet: câte muchii lipsesc / câte are
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=86
- #116graf complet: calcul cu n(n-1)/2
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=116
- #119matricea de adiacență: numărul de valori 1 și numărul de muchii
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=119
- #136valoarea unui grad necunoscut din suma gradelor
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=136
- #148numărul maxim de noduri cu un grad dat
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=148
- #159citirea gradelor dintr-o matrice de adiacență
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=159
- #162liste de adiacență: gradul unui nod
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=162
- #1041poate fi acest șir secvența gradelor unui graf?
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1041
Citește și exersează în plus
- Teorie grafuri neorientate · pbinfo.ro
https://www.pbinfo.ro/articole/810/grafuri-neorientate
- Teoria grafurilor — introducere · ro.wikipedia.org
definiții și istorie (Euler, podurile din Königsberg)
https://ro.wikipedia.org/wiki/Teoria_grafurilor
- VisuAlgo — Graph Data Structures · visualgo.net
desenezi un graf și vezi matricea, listele și lista de muchii (engleză)
https://visualgo.net/en/graphds
- USACO Guide — Introduction to Graphs · usaco.guide
aceleași noțiuni, cu probleme de concurs (engleză)
https://usaco.guide/silver/intro-graphs
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. Suma 3+3+2+2+1+x = 11 + x trebuie să fie pară, deci x impar: x ∈ {1, 3, 5} (3 valori).
2. Maxim 9·8/2 = 36. Cu vârful 1 izolat: 8·7/2 = 28.
3. Suma gradelor 8·3 = 24, deci m = 24/2 = 12.
4. 2⁵ = 32 grafuri parțiale.
5. Muchii: [1,2], [1,4], [2,3] → 3 muchii (numărul de 1 este 6). Gradele: 2, 2, 1, 1. Vârfuri terminale: 3 și 4.
6. L[1]: 2 3 4, L[2]: 1, L[3]: 1 4, L[4]: 1 3.
7. 4, 3, 3, 2, 2: suma 14 (pară), ținând cont că vârful de grad 4 e legat de toate celelalte, restul rămâne 2, 2, 1, 1 → valid, deci da. 4, 4, 4, 1, 1: trei vârfuri de grad 4 sunt legate de toate, deci fiecare din celelalte două are gradul cel puțin 3: nu.
8. 2^(5·4/2) = 2¹⁰ = 1024.
9. Suma gradelor = 2 · 14 = 28. Dacă toate cele 8 vârfuri ar avea gradul 3, suma ar fi 24; fiecare vârf de grad 4 adaugă 1, deci sunt 28 − 24 = 4 vârfuri de grad 4 (și 4 de grad 3).
10. Calculezi gradele, găsești maximul, apoi afișezi toate vârfurile cu acel grad:
int gr[101], mx = 0;
// calculează gr[i] ca suma liniei i (sau L[i].size())
for (int i = 1; i <= n; i++) if (gr[i] > mx) mx = gr[i];
for (int i = 1; i <= n; i++) if (gr[i] == mx) cout << i << ' ';