Grafuri neorientate la Bac informatică

28 de exerciții date la Bac, 2020–2026, toate rezolvate.

2026

Varianta 1 · Subiectul al II-lea, exercițiul 2
Un graf neorientat are 8 noduri și 10 muchii. Scrieți numărul de valori nenule și numărul de valori nule din matricea de adiacență corespunzătoare grafului.
Varianta 3 · Subiectul I, exercițiul 5
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat alăturat. Indicați numărul maxim de muchii care pot fi adăugate, astfel încât graful obținut să fie eulerian.
Varianta 4 · Subiectul I, exercițiul 5
O companie de logistică are o rețea formată din 12 centre, numerotate de la 1 la 12, între care există comunicații bidirecționale, astfel: între 1 și 2, între 1 și 3, între 2 și 3, între 2 și 4, între 3 și 5, între 4 și…
Simulare · Subiectul al II-lea, exercițiul 2
Un graf neorientat, fără cicluri, are 26 de muchii și două componente conexe. Pentru fiecare dintre cele două componente, scrieți un exemplu de număr de noduri, respectiv de număr de muchii.
Model · Subiectul I, exercițiul 5
Un graf neorientat are 7 noduri, numerotate de la 1 la 7, și 8 muchii, dintre care șase sunt: [1,2], [2,5], [2,6], [2,7], [3,7], [4,7]. Știind că unul dintre lanțurile elementare care au lungimea maximă este 3, 7, 4, 5,…

Varianta 1 · Subiectul al II-lea, exercițiul 2
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin listele de adiacență alăturate. Scrieți mulțimea nodurilor și mulțimea muchiilor unui subgraf al acestuia, fără noduri izolate, care să fie…
Varianta 6 · Subiectul I, exercițiul 5
Un graf neorientat are 7 noduri și 21 de muchii. Indicați numărul minim de muchii care pot fi eliminate din acest graf, astfel încât graful parțial obținut să aibă două componente conexe, cu cel puțin două noduri…
Simulare · Subiectul I, exercițiul 5
Un graf neorientat are 25 de noduri și 5 componente conexe, fiecare dintre acestea fiind fără cicluri. Indicați numărul de muchii ale grafului.
Model · Subiectul I, exercițiul 5
Indicați numărul de noduri ale unui graf neorientat, complet, cu 300 de muchii.

Varianta 3 · Subiectul I, exercițiul 5
Într-un graf neorientat, cu 10 muchii, două noduri au gradul 0, șase noduri au grade impare, iar celelalte noduri au grade pare, nenule. Indicați numărul maxim de noduri ale grafului.
Varianta 4 · Subiectul al II-lea, exercițiul 2
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [2,3], [2,4], [2,5], [4,5], [4,6], [5,6]. Scrieți listele de adiacență ale unui graf parțial al său care să fie conex și fără cicluri.
Model · Subiectul I, exercițiul 5
Într-un oraș sunt 5 piețe, iar una dintre acestea este conectată direct cu fiecare dintre celelalte patru prin câte o bandă de transport bidirecțională. Indicați numărul minim de benzi de transport bidirecționale care…

Varianta 7 · Subiectul I, exercițiul 5
Un graf neorientat are 5 noduri, numerotate de la 1 la 5, cu gradele figurate în tabelul alăturat. Indicați o pereche de valori posibile pentru x și y.
Simulare · Subiectul al II-lea, exercițiul 2
Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (4,1,1,0,7,4,4). Scrieți trei muchii care i se pot adăuga, astfel încât graful obținut să fie eulerian.
Model · Subiectul I, exercițiul 5
Un graf neorientat admite un ciclu eulerian, de lungime 11, precum și un ciclu hamiltonian, de lungime 7. Indicați numărul de muchii care pot fi eliminate din graf, astfel încât graful parțial obținut să fie arbore.

Varianta 1 · Subiectul I, exercițiul 4
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [2,3], [4,6]. Indicați numărul de componente conexe ale acestuia.
Varianta 4 · Subiectul al II-lea, exercițiul 2
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,5], [4,6], [5,6]. Scrieți mulțimea muchiilor unui subgraf al acestui graf, care să fie complet și…
Varianta 5 · Subiectul I, exercițiul 5
Un graf neorientat are 7 noduri, numerotate de la 1 la 7, și 8 muchii, dintre care șase sunt: [1,2], [2,4], [2,7], [3,4], [4,5], [4,6]. Știind că unul dintre lanțurile elementare care au lungimea maximă este 1, 2, 7, 5,…
Simulare · Subiectul I, exercițiul 5
Un graf neorientat complet are 4 noduri. Indicați o valoare care NU poate fi numărul de muchii ale unui subgraf al acestui graf.
Model · Subiectul I, exercițiul 4
Indicați numărul de noduri ale unui graf neorientat fără cicluri, cu 22 de muchii și două componente conexe.

Varianta 1 · Subiectul I, exercițiul 4
Un graf neorientat are 6 noduri, numerotate de la 1 la 6, și muchiile [1,2], [1,3], [2,3], [3,4], [3,5], [4,5], [5,6]. Indicați un ciclu elementar al acestui graf.
Varianta 4 · Subiectul I, exercițiul 5
Un graf neorientat are 21 de noduri, numerotate de la 1 la 21; pentru oricare două noduri distincte ale sale, numerotate cu i, respectiv cu j, există muchia [i,j] dacă și numai dacă ultima cifră a lui i este egală cu…
Varianta 7 · Subiectul I, exercițiul 5
Indicați numărul de noduri ale unui graf neorientat, complet, cu 210 muchii.
Simulare · Subiectul I, exercițiul 5
Un graf neorientat are 40 de noduri și 5 componente conexe, fiecare dintre acestea fiind arbore. Indicați numărul de muchii ale grafului.
Simulare · Subiectul al II-lea, exercițiul 2
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin listele de adiacență alăturate. Pentru acest graf scrieți un lanț care să nu fie elementar, precum și un ciclu elementar.
Model · Subiectul I, exercițiul 5
Un graf neorientat complet are 21 de noduri. Indicați numărul de muchii ce pot fi eliminate, astfel încât graful parțial obținut să fie conex și fără cicluri.

Varianta 5 · Subiectul I, exercițiul 5
Un graf neorientat eulerian cu 5 noduri are un nod cu gradul 4. Indicați numărul minim de muchii ale grafului.
Varianta 6 · Subiectul I, exercițiul 5
Un graf neorientat cu 5 noduri este reprezentat prin matricea de adiacență alăturată. Indicați numărul grafurilor parțiale conexe ale acestuia care sunt diferite de graful dat.