Se consideră graful neorientat G=(X,U) unde X={1,2,3,4,5,6} şi U={[1,2], [1,3], [5,1], [3,4], [4,5], [3,2], [3,5]}. Precizați câte cicluri elementare distincte există în graful G. (Două cicluri elementare sunt distincte dacă diferă prin cel puţin o muchie).
Se consideră graful orientat G=(V, E) unde V={1,2,3,4,5,6,7} şi E={(1,2), (6,1), (2,5), (2,3), (4,5), (3,4), (3,6)}. Precizați numărul componente tare conexe din graful dat.
Un arbore cu nodurile numerotate de la 1
la 12
, este memorat cu ajutorul vectorului de taţi tata= (2,5,5,3,0,2,3,7,6,6,7,4)
.
Numărul de lanțuri elementare de lungime maximă care leagă două noduri ale arborelui este:
Se consideră un arbore în care fiecare nod intern (nod care nu este pe ultimul nivel) are doi descendenți direcți. Dacă arborele are 38
niveluri (rădăcina se află pe nivelul 0
) câte noduri are arborele?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Se consideră un arbore în care fiecare nod intern (nod care nu este pe ultimul nivel) are doi descendenți direcți. Dacă arborele are 38 niveluri (rădăcina se află pe nivelul 0) câte noduri are arborele?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Se consideră un arbore cu rădăcină în care fiecare nod intern (nod care nu este pe ultimul nivel) are doi descendenți direcți. Dacă arborele are k niveluri (rădăcina se află pe nivelul 0) câte noduri sunt pe nivelul k ?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Se consideră graful neorientat G
reprezentat prin următoarea matrice de adiacență:
0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Precizați numărul componentelor conexe ale grafului G
.
Într-un plan cartezian se găsesc 8 roboți dați prin coordonatele lor. Coordonatele celor 8 roboți sunt: (2,2),(2,4),(2,6),(2,8),(4,2),(6,2),(6,-2), (-2,-2)
.
Doi roboți A și B se numesc vecini dacă se găsesc pe o paralelă la axele de coordonate și nu există un robot C situat între A și B pe aceeași paralelă. Ținând cont de regulile de mai sus, construiți un graf neorientat cu 8 noduri. Nodurile grafului sunt numerotate în ordinea coordonatelor (nodul 1 are coordonatele (2,2)
, nodul 2 coordonatele (2,4)
ș.a.m.d.). Dacă robotul 1 este vecin cu robotul 2 atunci va exista muchie de la 1 la 2 în graf.
Precizați care dintre următoarele afirmații despre graful astfel obținut este adevărată?
Varianta 1 |
Graful este eulerian |
Varianta 2 |
Graful este hamiltonian |
Varianta 3 |
Graful conține două componente conexe |
Varianta 4 |
Graful este aciclic. |
Precizați care dintre următoarele șiruri de numere poate reprezenta șirul gradelor nodurilor unui graf neorientat cu 7
noduri.
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Numărul de grafuri neorientate cu șase noduri, în care nodul 1 are gradul 1 și nodul 2 are gradul 2 este:
Varianta 1 |
1536 |
Varianta 2 |
1792 |
Varianta 3 |
1920 |
Varianta 4 |
2560 |