[canonical]: https://grile.online/informatica/subiecte/model-bac-informatica-047

> Pagina completă: https://grile.online/informatica/subiecte/model-bac-informatica-047
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model BAC Informatică · Informatică #047

10 grile din Grafuri, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul BAC Informatică

## Teaser gratuit, fără cont

1. Un graf orientat are $7$ noduri. Care este numărul maxim de arce pe care le poate avea un circuit elementar al grafului?

a) $21$
b) $7$
c) $8$
d) $6$

Răspuns corect: b) $7$

Un circuit elementar nu repetă niciun nod (în afara celui de plecare), deci trece prin cel mult $7$ noduri și are cel mult $7$ arce.

2. Vectorii `x` și `y` memorează extremitățile celor $9$ muchii ale unui graf neorientat cu $6$ noduri. Ce se afișează?

a) `2 3`
b) `6 2`
c) `4 4`
d) `4 3`

Răspuns corect: c) `4 4`

Gradele sunt $3,3,3,4,3,2$; primul nod cu grad maxim este $4$, cu gradul $4$ (este adiacent cu $1,2,5,6$).

3. Programul de mai jos prelucrează un graf neorientat cu $8$ noduri, ale cărui muchii sunt memorate în vectorii `x` și `y`. Ce se afișează?

a) `3`
b) `2`
c) `4`
d) `5`

Răspuns corect: a) `3`

Programul numără componentele conexe: $\{1,2,3\}$, $\{4,5\}$ și $\{6,7,8\}$ — fiecare apel `dfs` din `main` marchează o componentă întreagă.

4. Un graf orientat cu $n=6$ noduri are arcele $(1,2)$, $(2,3)$, $(1,6)$, $(6,5)$, $(5,4)$ și este memorat în matricea de adiacență `a`. Ce se afișează în urma executării algoritmului de mai jos?

a) `1`
b) `3 4`
c) `1 3 4`
d) `2 6`

Răspuns corect: b) `3 4`

Suma liniei `i` este gradul extern al nodului `i`; se afișează nodurile din care nu pleacă niciun arc: $3$ și $4$.

5. Care dintre următoarele afirmații este adevărată pentru orice graf orientat fără circuite, cu cel puțin un nod?

a) Toate nodurile au gradul intern cel puțin $1$.
b) Fiecare nod are gradul extern cel puțin $1$.
c) Numărul de arce este egal cu numărul de noduri.
d) Există cel puțin un nod cu gradul intern $0$.

Răspuns corect: d) Există cel puțin un nod cu gradul intern $0$.

Dacă toate nodurile ar avea un predecesor, mergând mereu înapoi pe un arc am repeta la un moment dat un nod și am obține un circuit. Celelalte afirmații sunt false chiar pentru graful cu un singur nod.