[canonical]: https://grile.online/informatica/grafuri

> Pagina completă: https://grile.online/informatica/grafuri
> 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 Grafuri · Informatică

7 grile, în 3 seturi, cu explicații.

## Teaser gratuit, fără cont

1. Un graf orientat are $6$ vârfuri, numerotate de la $1$ la $6$.

Arcele grafului sunt: $$\begin{gathered} (1,2),\quad (1,6),\quad (2,3) \\ (3,1),\quad (3,4),\quad (4,5) \\ (5,3),\quad (5,6) \end{gathered}$$

Indicați un circuit elementar al acestui graf.

a) $1,2,3$
b) $1,2,3,1$
c) $1,2,3,4,5,3,1$
d) $1,2,3,4,5,6,1$

Răspuns corect: b) $1,2,3,1$

Succesiunea de arce $(1,2)$, $(2,3)$, $(3,1)$ formează un ciclu ce revine la nodul de plecare cu toate nodurile intermediare distincte, deci $1,2,3,1$ este un circuit elementar.

2. Indicați numărul de noduri ale unui graf neorientat, complet, cu $300$ de muchii.

a) $25$
b) $30$
c) $299$
d) $301$

Răspuns corect: a) $25$

Într-un graf complet cu $n$ noduri există $n(n-1)/2$ muchii; din $n(n-1)/2=300$ rezultă $n(n-1)=600$, deci $n=25$.

3. Un graf orientat fără circuite are $10$ vârfuri. Indicați numărul maxim de arce ale grafului.

a) $10$
b) $45$
c) $50$
d) $90$

Răspuns corect: b) $45$

Un graf orientat fără circuite are cel mult o muchie între oricare pereche ordonată compatibilă cu o ordine topologică, deci maximum $n(n-1)/2 = 10 \cdot 9 / 2 = 45$ de arce.

4. Î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.

a) $17$
b) $15$
c) $12$
d) $10$

Răspuns corect: b) $15$

Suma gradelor este $2 \cdot 10 = 20$; cele $6$ noduri de grad impar consumă minimum $6$, iar nodurile rămase, de grad par nenul, minimum câte $2$ fiecare, permit cel mult $7$ noduri suplimentare — în total $2+6+7=15$ noduri.

5. Oricare dintre cele $5$ vârfuri ale unui graf orientat are proprietatea că suma dintre gradul său extern și gradul său intern este $4$. Indicați lungimea maximă a unui drum elementar în acest graf.

a) $10$
b) $8$
c) $4$
d) $3$

Răspuns corect: c) $4$

Un drum elementar într-un graf cu $5$ noduri nu poate vizita mai mult de $5$ noduri distincte, deci nu poate avea mai mult de $4$ arce, indiferent de gradele individuale.

## Seturi care conțin acest capitol

- [Informatică #001](https://grile.online/informatica/rezolva?set=informatica-bac-1)
- [Informatică #002](https://grile.online/informatica/rezolva?set=informatica-bac-2)
- [Informatică #003](https://grile.online/informatica/rezolva?set=informatica-poli-2025)