Varianta 080 S.II2. Se consider un graf neorientat cu 7 noduri, numerotate de la 1 la 7, cu proprietatea c exist muchie cu extremitile n nodurile i i respectiv j dac numerele i i j sunt de aceeai paritate sau dac i este divizor al lui j. Gradul maxim al unui nod din acest graf este: (4p.)a. 1 b. 7 c. 4 d. 63. Fie graful orientat cu 9 vrfuri numerotate de la 1 la 9 i arcele (1,2) (2,3) (3,1)(4,5) (5,6) (5,7) (6,7) (7,4) (8,7) (8,9) (9,8). Care este numrul de vrfuri cu proprietatea c gradul interior este egal cu gradul exterior ? (6p.)

Varianta 081 S.II2. Graful neorientat cu 5 noduri numerotate de la 1 la 5, este reprezentat cu ajutorul matricei de adiacen alturate. Numrul maxim de muchii ce pot fi eliminate astfel nct graful parial rezultat s aib 2 componente conexe este: (4p.)0 1 1 1 11 0 1 1 01 1 0 1 01 1 1 0 11 0 0 1 0a. 5 b. 4 c. 6 d. 3Varianta 082 S.II1. Se consider graful orientat cu nodurile numerotate de la 1 la 5 i arcele (1,2), (1,5),(2,1), (2,3), (2,5), (3,4), (5,2),(5,4). Care este lungimea maxim a unui drum format din noduri distincte, de la nodul 1 la nodul 4? (4p.)a. 5 b. 6 c. 4 d. 74. Un graf neorientat cu nodurile numerotate de la 1 la 4 este reprezentat prin matricea de adiacen alturat. Scriei numrul de noduri care au grad par i numrul de noduri care au grad impar. (6p.)0 1 1 01 0 0 01 0 0 10 0 1 0Varianta 083 S.II1. Se consider graful orientat cu nodurile numerotate de la 1 la 5 i arcele (1,2), (1,4),(2,1), (2,5), (3,2), (4,3), (5,1), (5,4). Care este numrul minim de arce care poate fi adugat pentru ca toate nodurile s aib i gradul extern i gradul intern numere par? (4p.)a. 2 b. 1 c. 0 d. 33. Se consider un graf neorientat cu 5 noduri, n care nodurile au urmtoarele grade: 2,2,2,1,1. tiind c graful are dou componente conexe, scriei matricea de adiacen a acestuia. (6p.)

Varianta 084 S.II1. Se consider graful neorientat cu nodurile numerotate de la 1 la 6 i avnd muchiile [1,2], [1,4], [2,3], [3,5], [3,6], [4,5], [5,6]. Cte lanuri, distincte, formate doar din noduri distincte, exist de la nodul 1 la nodul 6 n graful dat? Dou lanuri sunt distincte dac difer prin cel puin o muchie. (4p.)a. 4 b. 2 c. 6 d. 02. Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tai t=(9,3,4,7,3,9,0,7,2). Numrul tuturor descendenilor nodului 2 este: (4p.)a. 3 b. 1 c. 0 d. 2

Varianta 085 S.II1. Se consider graful orientat cu vrfurile numerotate de la 1 la 7 i arcele (1,2),(1,7), (2,3), (3,2), (3,4), (4,3), (5,4), (5,6), (6,4), (7,6). Cte noduri cu gradul extern par exist n graful dat? (4p.)a. 3 b. 2 c. 4 d. 02. Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tait=(9,3,4,7,3,9,0,7,2). Lungimea celui mai lung lan format din noduri distincte, care pornete din rdcin este: (4p.)a. 1 b. 5 c. 3 d. 4

Varianta 086 S.II1. Care este suma gradelor grafului neorientat cu 4 noduri numerotate de la 1 la 4, reprezentat prin matricea de adiacen alturat? (4p.)0 1 1 11 0 1 01 1 0 01 0 0 0a. 4 b. 10 c. 6 d. 83. Scriei matricea de adiacen a arborelui cu 6 noduri, numerotate de la 1 la 6, definit prin urmtorul vector "de tai": (0, 1, 1, 1, 3, 3). (6p.)

Varianta 087 S.II1. Cte muchii are graful neorientat cu 6 noduri numerotate de la1 la 6, reprezentat prin lista de adiacene alturat?(4p.)1: 2 62: 1 3 4 53: 24: 25: 2 66: 1 5a. 5 b. 4 c. 12 d. 63. Se consider un arbore cu 6 noduri, numerotate de la 1 la 6, reprezentat prin matricea de adiacen dat alturat. Scriei toate nodurile care pot fi alese ca rdcin a arborelui astfel nct acesta s aib un numr maxim de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

Varianta 088 S.II1. Care este numrul de noduri de grad 1 ale grafului neorientat cu 8 noduri numerotate de la 1 la 8, reprezentat prin listele de adiacen alturate? (4p.)1: 2 6 82: 1 33: 2 4 74: 3 55: 46: 17: 38: 1a. 4 b. 8 c. 3 d. 63. Se consider un arbore cu 6 noduri, numerotate de la 1 la 6, reprezentat prin matricea de adiacen dat alturat. Scriei toate nodurile care pot fi alese ca rdcin a arborelui astfel nct acesta s aib un numr minim de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

Varianta 089 S.II1. Enumerai nodurile de grad 1 din graful neorientat cu 8 noduri numerotate de la 1 la 8, reprezentat prin listele de adiacen alturate.(4p.)1: 3 4 5 62: 33: 1 2 74: 15: 1 86: 17: 38: 5a. 2 3 4 5 6 b. 2 4 7 8 c. 2 4 6 d. 2 4 6 7 8

3. Determinai ultima valoare (notat cu ?) din vectorului de tai (0, 1, 1, 2, 3, 3, ?) astfelnct arborele cu 7 noduri, numerotate de la 1 la 7, descris de acest vector, s aib pefiecare nivel n exact 2n noduri, nodul rdcin fiind pe nivelul n=0, i fiecare nod s aib celmult doi descendeni. Scriei matricea de adiacen a unui arbore astfel definit. (6p.)

Varianta 090 S.II

1. Enumerai nodurile cu grad impar ale grafului neorientat cu 6 noduri numerotate de la 1 la6 i muchiile [1,6], [2,1], [2,6], [3,2], [3,4], [3,6], [4,5], [4,6], [6,5]. (4p.)a. 2 3 4 6 b. 1 3 5 c. 2 4 6 d. 1 3 5 63. Se consider un arbore cu 6 noduri, numerotate de la 1 la 6,reprezentat prin matricea de adiacen dat alturat. Scriei toate nodurile care pot fi alese ca rdcin a arborelui astfel nct acesta s aib un numr par de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0