[canonical]: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-052

> Pagina completă: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-052
> 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 Preadmitere Politehnica București · Informatică #052

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 Preadmitere Politehnica București

## Teaser gratuit, fără cont

1. Pentru un graf orientat cu $4$ noduri, `L[i]` memorează lista succesorilor nodului `i`, iar `nr[i]` numărul lor. Ce se afișează?

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

Răspuns corect: e) `6 2`

Numărul de arce este suma lungimilor listelor: $2+1+2+1=6$; nodul $3$ apare în listele nodurilor $1$ și $2$, deci are gradul intern $2$.

2. Ce afișează programul de mai jos și ce reprezintă valoarea afișată?

a) `120` — numărul grafurilor neorientate cu $5$ noduri și cel mult $3$ muchii
b) `120` — numărul grafurilor neorientate cu $5$ noduri și exact $3$ muchii
c) `1024` — numărul grafurilor neorientate cu $5$ noduri
d) `10` — numărul de muchii ale grafului complet cu $5$ noduri
e) `60` — numărul ciclurilor hamiltoniene din graful complet cu $5$ noduri

Răspuns corect: b) `120` — numărul grafurilor neorientate cu $5$ noduri și exact $3$ muchii

`comb` calculează recursiv combinări (relația lui Pascal); apelul este $\binom{10}{3}=120$, adică numărul de moduri de a alege $3$ muchii dintre cele $10$ posibile între $5$ noduri.

3. Programul de mai jos afișează numărul de noduri în care se poate ajunge din nodul $1$ printr-un drum (nodul $1$ inclusiv), într-un graf orientat memorat în matricea de adiacență `a`. Cu ce trebuie înlocuite punctele de suspensie?

a) `a[y][x]`
b) `!viz[y]`
c) `y != x`
d) `!viz[x]`
e) `viz[y]`

Răspuns corect: b) `!viz[y]`

Se continuă parcurgerea doar spre succesorii încă nevizitați; altfel apelurile s-ar repeta la nesfârșit pe un circuit sau ar număra nodurile de mai multe ori.

4. Câte grafuri neorientate cu $6$ noduri, numerotate de la $1$ la $6$, au nodurile $1$ și $2$ izolate?

a) $32768$
b) $16$
c) $4096$
d) $15$
e) $64$

Răspuns corect: e) $64$

Nodurile $1$ și $2$ nu au muchii, deci muchiile se aleg doar dintre cele $\binom{4}{2}=6$ posibile între nodurile $3,4,5,6$: $2^6=64$.

5. Vectorii `x` și `y` memorează arcele $(x_i,y_i)$ ale unui graf orientat cu $4$ noduri, iar `a` și `b` sunt matrice inițial nule. Ce se afișează?

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

Răspuns corect: b) `2 1 1 3`

`b` este transpusa lui `a`, adică matricea grafului cu toate arcele inversate; suma liniei `i` din `b` este gradul intern al nodului `i` în graful inițial: $2,1,1,3$.