1: 4,5,6
2: 5
3: 4
4: 1,3
5: 1,2,6
6: 1,5
a. {1,4,6} b. {2} c. {3} d. {2,6}
Raspuns : d ,sunt singurele care lanturi de lungime 2 cu cealalta extremitate in nodul 5.
Varianta 35 . Se considera graful neorientat cu multimea nodurilor {1,2,3,4,5,6,7,8} si multimea muchiilor {[1,2], [2,3], [2,4], [4,7], [2,6], [1,5], [5,6], [6,8], [7,8]}. Pentru a trasforma graful într-un arbore, putem elimina: (4p.)
a. muchiile [1,5] si [1,2]
b. muchia [5,6]
c. nodul 3
d. muchiile [2,6] si [4,7]
Raspuns:d.deoarece daca eliminam muchiile [1,5] si [1,2] sau nodul 3 graful nu este conex,iar daca eliminam muchia [5,6] graful nu este aciclic .
Varianta 36 . Câte muchii trebuie eliminate dintr-un graf neorientat complet cu 20 de noduri, pentru ca acesta sa devina arbore? Un graf este complet daca oricare doua noduri distincte sunt adiacente.
Rezolvare (2 la puterea 190 ) - 19
Varianta 38 . Urmatorul doi itemi se refera la un graf neorientat cu 7 noduri, numerotate de la 1 la 7 si muchiile
[1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].
1. Care este numarul minim de muchii care trebuie eliminate astfel încât graful sa aiba 3 componente conexe? (6p.)Eliminam [1,5] [5,6] (2 muchii ) si avem 1 componenta conexa 6 componenta conexa iar {2,3,4,5,7} formeaza a treia componenata conexa .
2. Câte cicluri elementare distincte exista în graf? Doua cicluri sunt distincte daca difera prin cel putin o muchie.
Raspuns: 7 cicluri elementare
Varianta 41. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de adiacenta alaturata, au gradul un numar par? (4p.)
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
a. 1 b. 3 c. 2 d. 5
Rezolvare :suma de pe prima coloana este nr par rezulta ca nodul 1 are grad par.
Varianta 42. Câte dintre vârfurile grafului neorientat G, reprezentat prin matricea de
adiacenta alaturata, au gradul 0? (4p.)
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
1 0 0 0 0
a. 2 b. 1 c. 3 d. 0
REZ:coloanele 2 si 3 au doar zero(acestea nu sunt incidente cu nici un nod) deci au gradul zero.
Varianta 43. Un graf neorientat este reprezentat prin matricea de adiacenta alaturata. Câte grafuri partiale distincte, formate doar din noduri cu gradul egal cu 2, se pot obtine din graful dat? Doua grafuri sunt distincte daca matricele lor de adiacenta difera. (4p.)
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
a. 2 b. 1 c. 3 d. 0
Raspuns :b
Rezolvare
0 1 0 0 1
1 0 0 1 0
0 0 0 1 1
0 1 1 0 0
1 0 1 0 0
0 0 0 0 1
0 0 1 1 0
0 1 0 1 1
0 1 1 0 1
1 0 1 1 0
a. 1 b. 2 c. 3 d. 0
R:a ,fiindca doar prima coloana are suma egala cu 1
Niciun comentariu:
Trimiteți un comentariu