Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Digrafuri

 Notă: Se acordă 2 puncte din oficiu. Se acordă nota 10 oricărui punctaj mai mare sau egal cu 10. Problema 6 necesită scrierea unui program, iar problema 7 necesită scrierea unui algoritm.

1. (1 punct) Desenaţi un digraf cu 6 noduri şi în care toate vârfurile au gradul exterior 4. Este posibil?

2. (2 puncte) Se dau n persoane numerotate de la 1 la n. Fiecare ştie câte o informaţie pe care nu o mai ştie nimeni. Se defineşte relaţia i > j (persoana i spune informaţia pe care o ştie persoanei j). Se cere să se determine numărul minim de relaţii (în funcţie de n) astfel încât orice persoană din cele n să ştie toate informaţiile. Modelaţi problema cu digrafuri şi desenaţi soluţia problemei pentru n=6.

3. (3 puncte) Se dau n oraşe conectate prin şosele unidirecţionale. Se ştie că pentru orice două oraşe X şi Y există cel puţin un drum de la X la Y (care poate trece şi prin alte oraşe intermediare) sau de la Y la X, dar nu neapărat trebuie să existe drumuri în ambele sensuri. Arătaţi că există un oraş în care se poate ajunge plecând din toate celelalte oraşe şi că există un oraş din care se poate ajunge în toate celelalte oraşe. Digraful asociat problemei este tare conex?

4. (3 puncte) Trei cupluri stabilesc o petrecere. Persoanele ajung la acea petrecere pe rând, cuplurile neajungând neapărat în acelaşi timp. Fiecare când ajunge strânge mâna tuturor celor ajunşi deja, cu excepţia propriei perechi. Când au ajuns toţi, persoana X întreabă pe ceilalţi câte mâini a strâns fiecare şi primeşte ca răspuns cinci valori diferite. Determinaţi câte mâini a strâns persoana X. Justificaţi răspunsul.

5. (3 puncte) Într-o clasă cu n elevi fiecare are exact 3 prieteni, oricare doi prieteni nu au prieteni comuni şi oricare doi elevi care nu sunt prieteni au exact un prieten comun. Câţi elevi sunt în clasă?
a) 6      b) 9      c) 10     d) 12     e) 17
Justificaţi răspunsul.

6. (4 puncte) Se consideră un digraf pentru care se ştie că din vîrful 1 sunt accesibile toate celelalte vârfuri (parcurgerea BFS(1) vizitează toate vârfurile digrafului). Scrieţi un program care citeşte digraful şi două vârfuri u, v şi verifică dacă u este descendent (nu neapărat fiu) al lui v.

7. (3 puncte) N şahişti numerotaţi de la 1 la N participă la un turneu. Se cunosc mai multe relaţii de forma (i, j) cu semnificaţia şahistul i l-a învins pe j. Explicaţi în ce constă algoritmul care verifică dacă se poate stabili un clasament unic al turneului şi în caz afirmativ să afişeze clasementul. Determinaţi complexitatea algoritmului prezentat.

8.  (4 puncte) Se dă digraful cu 45 de vârfuri şi matricea de adiacenţă asociată construită astfel:

for (i=1 ; i<=45 ; i++)
   for (j=1 ; j<=45 ; j++) a[i][j] = 0 ;
for (i=1 ; i<=41 ; i+=4)
  a[i][i+1] = a[i][i+2] = a[i][i+3] = 1 ;
for (i=5 ; i<=45 ; i+=4)
    a[i-3][i] = a[i-2][i] = a[i-1][i] = 1 ;

a) Este digraful aciclic? Justificaţi.
b) Câte componente tare conexe are digraful? Justificaţi.
c) Câte drumuri de lungime minimă există de la vârful 1 la vârful 45? Justificaţi matematic.

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =