Grafuri neorientate (doar matematică-informatică)

Pe scurt

2 minesențialul, de recitit oricând

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

• Doar la matematică-informatică. Capitolul 11 din programă nu apare la științele naturii.
• Graful e un desen cu puncte și legături, iar la examen îl folosești ca atare: cu desen pe ciornă și câteva formule.
• În toate cele 23 de lucrări MI din 2023-2027 din platformă sunt exact 2 itemi de grafuri sau arbori. Din cei 46, 14 sunt pe grafuri neorientate, 15 pe grafuri orientate, 17 pe arbori.
• Nu am găsit în aceste lucrări niciun item care să ceară un program pe graf. Se cere să raționezi și să scrii un răspuns scurt.

Urmează · 2 min

Ideea, apoi numele oficial

5 min

Desenează cinci orașe și câteva drumuri între ele. Pe un drum poți merge în ambele sensuri. Atât e un graf neorientat.

Antetul lucrărilor recente precizează că în grafuri orice muchie are extremități distincte și că două muchii diferă prin cel puțin o extremitate. Deci nu există bucle și nici muchii duble.

Urmează · 5 min

Reprezentarea

2 min

Matricea de adiacență are a[i][j]=1 dacă există muchia [i,j], altfel 0. La graful neorientat e simetrică și are zero pe diagonala principală.

Listele de adiacență dau, pentru fiecare nod, vecinii lui:

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

Citirea muchiilor, gradele și listele, în C++:

int a[101][101],gr[101],n,m,x,y,i,j;
cin>>n>>m;
for(i=1;i<=m;i++)
{ cin>>x>>y;
  a[x][y]=1;
  a[y][x]=1;
  gr[x]++;
  gr[y]++;
}

int L[101][101],nr[101];
for(i=1;i<=m;i++)
{ cin>>x>>y;
  nr[x]++;
  L[x][nr[x]]=y;
  nr[y]++;
  L[y][nr[y]]=x;
}

Numerotăm de la 1, pentru că și enunțurile numerotează nodurile de la 1. În Pascal: a:array[1..100,1..100] of integer, cu a[x,y]:=1.

Urmează · 2 min

Proprietățile care rezolvă grilele

2 min

Suma gradelor fiind pară, numărul nodurilor cu grad impar este și el par.

Urmează · 2 min

Oficial: II.2, cu 6 puncte

6 min o întrebare la final

August 2026, varianta 1. Un graf neorientat are 8 noduri și 10 muchii. Se cere numărul de valori nenule și de valori nule din matricea de adiacență.

Matricea are 8·8 = 64 de valori. Fiecare muchie dă doi de 1. Deci 20 de valori nenule și 44 de valori nule. Barem: câte 3 p.

Iunie 2025, varianta 1. Graful are listele:

1: 2, 3, 4, 6
2: 1, 3, 5
3: 1, 2, 5
4: 1, 5, 6
5: 2, 3, 4, 6
6: 1, 4, 5

Se cere mulțimea nodurilor și a muchiilor unui subgraf fără noduri izolate, care să fie eulerian. Cel mai simplu e un triunghi: nodurile 1, 2, 3 și muchiile [1,2], [2,3], [1,3]. Toate gradele sunt 2, iar graful e conex.

Sesiunea specială 2024, varianta 4. Muchiile sunt [1,2], [2,3], [2,4], [2,5], [4,5], [4,6], [5,6]. Se cer listele de adiacență ale unui graf parțial conex și fără cicluri.

Graf parțial: aceleași 6 noduri, mai puține muchii. Conex fără cicluri: 5 muchii. Păstrez [1,2], [2,3], [2,4], [2,5], [4,6].

1: 2
2: 1, 3, 4, 5
3: 2
4: 2, 6
5: 2
6: 4

Barem: câte 2 p pentru liste de adiacență ale unui graf parțial, graf conex, graf fără cicluri.

Simulare 2026. Un graf fără cicluri are 26 de muchii și două componente conexe. Se cere, pentru fiecare componentă, un exemplu de număr de noduri și de muchii.

Fiecare componentă are m=n-1. Deci totalul de noduri este 26+2 = 28. De exemplu: prima componentă cu 10 noduri și 9 muchii, a doua cu 18 noduri și 17 muchii.

Barem: câte 2 p pentru numărul de noduri al primei componente, numărul de muchii al ei, datele celei de-a doua. Se punctează orice soluție cu n1 din [1,27], m1=n1-1, n2=28-n1, m2=n2-1.

Urmează · 6 min

Oficial: grile de 4 puncte

10 min 2 întrebări la final

August 2023, varianta 7, I.5. Gradele sunt 2, x, 3, 3, y, pentru 5 noduri. Se cer valori posibile pentru x și y.

• Gradul maxim este n-1 = 4, deci 5 nu se poate (varianta b).
• Dacă un nod are grad 0 și altul grad 4, cel cu grad 4 ar trebui să fie vecin cu toate, deci și cu cel izolat: imposibil (varianta a).
• La 2 și 3, suma este 13, impară: imposibil (varianta c).
• Rămâne 3 și 3, cu suma 14, varianta d.

Sesiunea specială 2026, varianta 4, I.5. Rețea cu 12 centre și 16 muchii, din care se elimină minimum de muchii ca să rămână trei componente conexe cu câte 4 noduri. Împărțirea cu cele mai puține muchii tăiate este 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Muchiile dintre grupe sunt [3,5], [4,5], [4,6], [7,9], [8,9], deci 5, varianta c.

Model 2026, I.5. Graf cu 7 noduri și 8 muchii, din care se dau șase. Lanțul elementar de lungime maximă este 3, 7, 4, 5, 2, 1, de lungime 5. Se cer celelalte două muchii. Lanțul are nevoie de [4,5], deci rămân a și c. Dacă adaugi și [1,6] (a), apare un lanț mai lung, care trece și prin 6: nu mai e maxim. Deci [2,3] și [4,5], varianta c.

Urmează · 10 min

Ce se cere la BAC

2 mincum apare la examen

Urmează · 2 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Scrii muchiile o singură dată în liste: fiecare apare la ambele capete.
• Confunzi subgraful cu graful parțial.
• Numeri lungimea în noduri, nu în muchii.
• Pui 1 pe diagonală sau uiți că matricea e simetrică.
• Spui eulerian doar din grade, fără să verifici că e conex.
• Uiți nodurile izolate când numeri componentele: un nod singur este o componentă conexă.
• Dai un exemplu fără să verifici că muchiile există în graful din enunț, când ți se cere un subgraf sau un graf parțial.

Urmează · 1 min