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

> Pagina completă: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-051
> 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ă #051

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. Câte grafuri neorientate cu $6$ noduri, numerotate de la $1$ la $6$, au exact $2$ muchii?

a) $32768$
b) $15$
c) $30$
d) $210$
e) $105$

Răspuns corect: e) $105$

Între $6$ noduri există $\binom{6}{2}=15$ muchii posibile, iar graful se obține alegând $2$ dintre ele: $\binom{15}{2}=105$.

2. Vectorii `x` și `y` memorează muchiile unui graf neorientat `G` cu $5$ noduri. Programul afișează gradele nodurilor grafului complementar al lui `G` (graful cu aceleași noduri, în care două noduri sunt adiacente exact când nu sunt adiacente în `G`).

Ce se afișează?

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

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

În `G` (un lanț $1\text{-}2\text{-}3\text{-}4\text{-}5$) gradele sunt $1,2,2,2,1$; în complementar fiecare nod are gradul $4-g[i]$.

3. Câte grafuri orientate (fără bucle) cu $3$ noduri, numerotate de la $1$ la $3$, există?

a) $6$
b) $64$
c) $27$
d) $512$
e) $8$

Răspuns corect: b) $64$

Între $3$ noduri există $3\cdot2=6$ arce posibile (perechi ordonate distincte), iar fiecare poate lipsi sau exista: $2^6=64$.

4. Vectorii `x` și `y` memorează muchiile unui graf neorientat cu $5$ noduri. Ce se afișează?

a) `36`
b) `12`
c) `26`
d) `24`
e) `30`

Răspuns corect: e) `30`

Gradele sunt $3,2,3,2,2$, iar programul afișează suma pătratelor lor: $9+4+9+4+4=30$.

5. Vectorii `ex` și `ey` memorează toate cele $6$ muchii posibile între $4$ noduri; fiecare valoare `s` codifică un graf neorientat cu $4$ noduri (bitul `i` indică prezența muchiei `i`). Ce se afișează?

a) `4`
b) `16`
c) `64`
d) `8`
e) `3`

Răspuns corect: d) `8`

Programul numără grafurile în care nodul $1$ are gradul $3$: cele $3$ muchii din $1$ sunt obligatorii, iar celelalte $3$ muchii pot fi alese oricum: $2^3=8$.