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

> Pagina completă: https://grile.online/informatica/subiecte/model-bac-informatica-050
> 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ă #050

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. Câte grafuri neorientate cu $5$ noduri, numerotate de la $1$ la $5$, au cel mult o muchie?

a) $2$
b) $1024$
c) $10$
d) $11$

Răspuns corect: d) $11$

Un singur graf fără muchii, plus câte un graf pentru fiecare dintre cele $\binom{5}{2}=10$ muchii posibile: $1+10=11$.

2. Vectorii `x` și `y` memorează arcele $(x_i,y_i)$ ale unui graf orientat fără circuite, cu $7$ noduri. Ce se afișează?

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

Răspuns corect: d) `3 1`

Nodurile fără arce care intră (grad intern $0$) sunt $1$, $2$ și $7$; singurul nod din care nu pleacă niciun arc (grad extern $0$) este $6$.

3. Vectorii `x` și `y` memorează arcele $(x_i,y_i)$ ale unui graf orientat cu $6$ noduri. Ce se afișează?

a) `2`
b) `1`
c) `3`
d) `0`

Răspuns corect: a) `2`

`gi` numără arcele care intră în fiecare nod. Gradele interne sunt $0,2,2,2,2,0$: nodurile $1$ și $6$ nu sunt extremitate finală a niciunui arc.

4. Într-un graf orientat cu $6$ noduri, din fiecare nod pleacă exact un arc, iar `urm[i]` este extremitatea finală a arcului care pleacă din nodul `i`. Ce se afișează?

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

Răspuns corect: b) `3`

Se numără arcele parcurse până la revenirea în $1$: $1\to3\to5\to1$, deci circuitul care conține nodul $1$ are lungimea $3$.

5. Un subgraf al unui graf neorientat se obține eliminând unele noduri (eventual niciunul, dar nu pe toate), împreună cu muchiile incidente lor; toate muchiile dintre nodurile rămase se păstrează. Câte subgrafuri are un graf neorientat complet cu $6$ noduri?

a) $63$
b) $64$
c) $32768$
d) $15$

Răspuns corect: a) $63$

Un subgraf se obține eliminând noduri (împreună cu muchiile lor) și păstrând toate muchiile dintre nodurile rămase, deci este determinat de mulțimea nevidă de noduri păstrate: $2^6-1=63$.