WorksheetsGrafuri neorientate
Total questions: 10
Worksheet time: 6mins
Name
Class
Date
1.
Matricea de adiacență asociată unui graf neorientat cu n noduri, în care pentru orice pereche de noduri distincte i și j există o muchie, are în total
(a)
2.
Se consideră graful neorientat cu 6 noduri și muchiile [1,2], [1,3],[1,5], [3,4], [4,6]. Numărul minim de muchii ce trebuie adăugate astfel încât în graful obținut fiecare nod să aparțină unui ciclul este:
a)
1
b)
2
c)
4
d)
5
3.
Graful neorientat G cu 8 noduri şi mulţimea de muchii [1,2], [1,3], [2,4] ,[3,4] ,[4,5], [5,7], [5,8], [6,7],[6,8] are:
a)
două noduri de grad maxim
b)
patru noduri de grad minim
c)
noduri izolate
d)
toate nodurile de același grad
4.
Se consideră un graf neorientat conex cu 50 de noduri şi 52 de muchii. Numărul minim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să nu aibă niciun ciclu este:
a)
1
b)
2
c)
3
d)
4
5.
Se consideră graful neorientat cu 8 noduri, numerotate de la 1 la 8, definit cu ajutorul listelor de adiacenţă următoare. Scrieți care este numărul maxim de muchii ce pot fi eliminate astfel încât graful să păstreze proprietatea de graf eulerian. Listele de adiacență sunt: 1:2, 3, 4, 6, 7, 8; 2:1, 8; 3:1, 4, 5, 7; 4:1, 3, 5, 6; 5:3, 4, 6, 7; 6:1, 4, 5, 7; 7:1, 3, 5, 6; 8:1, 2
a)
3
b)
4
c)
5
d)
6
6.
Care este numărul maxim de muchii pe care le poate avea un graf neorientat eulerian cu 10 noduri?
a)
10
b)
40
c)
45
d)
50
7.
Se consideră un graf neorientat complet cu 10 noduri . Câte lanţuri elementare de lungime 4 există între nodul 1 şi nodul 4? Lungimea unui lanţ este egală cu numărul de muchii din care este compus lanţul. Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie. Dacă vârfurile unui lanţ sunt distincte două câte două, atunci lanţul se numeşte elementar.
a)
50
b)
72
c)
336
d)
1000
8.
Se consideră un graf neorientat complet, cu 9 noduri. Pentru a obține un graf parțial al său cu două componente conexe, fiecare dintre acestea fiind grafuri complete, numărul maxim de muchii care pot fi eliminate este:
a)
14
b)
18
c)
20
d)
24
9.
Se consideră un graf neorientat cu 7 noduri şi două componente conexe. Numărul de muchii ale grafului NU poate fi:
a)
5
b)
11
c)
15
d)
21
10.
Numărul maxim de muchii ale unui graf neorientat, cu 100 de noduri, care nu conţine niciun ciclu, este:
(a)
100 %
