Prof. Stroe Mariana

Fi de lucru grafuri neorientate

1. Fie un graf neorientat cu 50 noduri i 32 muchii. Care este numrul maxim de vrfuri de grad 0 pe care le poate avea graful ? 2. Se consider un graf neorientat cu 5 noduri, etichetate cu literele a, b, c, d, e, n care orice nod etichetat cu o vocal este adiacent cu toate nodurile etichetate cu consoane, iar orice nod etichetat cu o consoan este adiacent cu toate nodurile etichetate cu vocale. Cte muchii are acest graf? 3. Se consider graful neorientat cu 8 noduri, numerotate de la 1 la 8, i muchiile [1,2], [1,6], [1,7], [2,3], [2,6], [3,6], [3,4], [4,5], [4,8], [5,6], [7,8]. Care este gradul minim al unui nod din acest graf? Care sunt nodurile care au acest grad minim? 4. Se sider un graf neorientat5noduri i3muchii. Care este numrul maxim de noduri cu grad1care pot exista n graf? 5. Cte grafuri neorientate, distincte, cu 4 vrfuri se pot construi? Dou grafuri se considerdistincte dac matricele lor de adiacen sunt diferite. a. 46

b. 26

c. 64

d. 46. ntr-un graf neorientat cu 10 muchii, fiecare nod are gradul un numr nenul. Doar trei dintrenoduri au gradul un numr par, restul nodurilor avnd gradele numere impare. Care estenumrul maxim de noduri pe care poate s le aib graful? a. 14

b. 17c. 10

d. 16

7. Care dintre urmtoarele valori pot reprezenta gradele nodurilor unui graf neorientat cu 6noduri? a. 3 2 2 2 3 3

b. 4 2 2 2 3 2

c. 5 2 2 2 0 3

d. 5 2 2 2 1 28. Care este numrul maxim de vrfuri de grad 0 pe care le poate avea un graf neorientat cu10 noduri i 7 muchii? a. 5

b. 6

c. 4

d. 79. Se consider graful neorientat G cu 8 noduri, care are urmtoarele proprieti:

- suma gradelor tuturor nodurilor este 12

- graful are exact 3 noduri cu gradul 1

Care este numrul maxim de noduri de grad 0 ale grafului G? a. 1b. 4 c. 2d. 010.Care este gradul maxim pe care l poate avea un nod al unui graf neorientat cu 6 muchii i6 noduri dintre care exact dou au gradul 0? Care este reprezentarea prin liste deadiacen pentru un astfel de graf?11. Cte grafuri neorientate distincte, cu 5 noduri, numerotate de la 1 la 5, se pot construi,astfel nct nodul 1 s aib gradul 1? Dou grafuri sunt distincte dac matricele lor deadiacen sunt diferite. a. 32

b. 256

c. 15

d. 2412. Se consider graful neorientat cu 8 noduri, numerotate de la 1 la 8, i muchiile [1,2],[1,6], [1,7], [2,3], [2,6], [3,6], [3,4], [4,5], [4,8], [5,6], [7,8]. Care estegradul minim al unui nod din acest graf? Care sunt nodurile care au acest grad minim? 13. Numrul de muchii ale unui graf neorientat cu 12 noduri, n care fiecare nod este adiacentcu exact 11 noduri, este : a. 144

b. 66

c. 78

d. 1114. ntr-un graf neorientat cu 6 noduri, numerotate de la 1 la 6, exist cte o muchie ntreoricare dou noduri numerotate cu numere consecutive i cte o muchie ntre nodulnumerotat cu 6 i fiecare dintre celelalte noduri. Cte subgrafuri cu exact 3 noduri, toateadiacente dou cte dou, are graful dat? Scriei pentru fiecare dintre aceste subgrafurinodurile din care este format.15. Care este numrul minim de muchii ce pot fi eliminate din grafulalturat astfel nct n graful parial rezultat s existe exact un vrf degrad 0? a. 1b. 3 c. 2

d. 516. Care este numrul maxim de noduri de grad 3 ntr-un graf neorientat cu 5 noduri? a. 4

b. 5

c. 3

d. 217. Se consider un graf neorientat cu 5 noduri i 9 muchii. Care dintre urmtoarele iruri denumere pot fi gradele nodurilor grafului? a. 4, 2, 6, 4, 2

b. 2, 2, 1, 2, 2

c. 1, 1, 1, 1, 1

d. 4, 3, 3, 4, 4

18. Dac G este un graf neorientat cu 4 noduri, atunci numrul maxim de muchii pe care lepoate avea graful este: a. 5

b. 4 c. 3

d. 619. se consider graful neorientat cu 6 noduri, numerotat de la 1 la 6 definitprin listele de adiacen alturate. Cte muchii trebuie adugate astfel nct s devin graf complet ?20. Se consider graful neorienat cu 6 noduri , definit cu ajutorul listelor de adiacen alturate.

n acest graf suma gradelor tuturor nodurilor este ........21. 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 deaceeai paritate sau dac i este divizor al lui j. Gradul minim al unui nod din acest grafeste: a. 1

b. 2

c. 4

d. 322. Se consider graful neorientat: cu 60 de noduri i 40 de muchii. Suma gradelor tuturornodurilor este egal cu : a. 120

b. 80

c. 100

d. 2023. Se consider un graf neorientat 5 noduri i 3 muchii. Care este numrul maxim de noduricu grad 1 care pot exista n graf? a. 2

b. 3

c. 4

d. 5

Lan. Ciclu

1. Pentru graful neorientat din figura alturat , care este numrul de muchii ale celui mai lung lan elementar, ce are ca extremiti nodurile 1 i 3 ?

2. Se consider un graf neorientat complet cu 10 vrfuri. Cte lanuri elementare distincte de lungime 3 exist ntre vrful 2 i vrful 4? Dou lanuri sunt distincte dac difer prin cel puin o muchie. a. 90

b. 28

c. 45

d. 563. 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 elementare distincte exist de la nodul 1 la nodul 6 n graful dat? 4. Fie graful neorientat de mai jos:a) Sa se scrie matricea de adicenta.

b) Sa se determine nodul de grad maxim.

c) Reprezentati grafic 1 subgraf al grafului.

d) Reprezentati grafic 1 graf partial.

e) Sa se determine numarul de muchii necesare

ce trebuiesc adaugate pentru a obtine un graf complet.

f) Sa se determine un lant elementar de lungime maxima.

g) Contine graful un ciclu? Daca raspunsul este da, dati un exemplu de ciclu.5. Se consider graful neorientat cu 6 noduri, numerotate cu 1, 2, 3, 4, 5, 6, i 9 muchii dat prin listele de adiacen alturate.Care este cel mai scurt lan cu o extremitate n nodul 1 i cealalt extremitate n nodul 3?6. Se consider graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacen alturate. Care dintre mulimile urmtoare de noduri are toate elementele extremiti ale unor lanuri elementare de lungime 2 cu cealalt extremitate n nodul 5?1: 4,5,62: 53: 44: 1,35: 1,2,66: 1,5

7.Fie un graf neorientat cu6noduri memorat prin urmtoarealist de adiacen. Reprezentai grafic graful neorientat. Afiati toate lanturile elementare de lungime 4 care pleac din nodul 2.1: 2 5 62:1 3 43:2 4 64:2 3 5 5:1 4 66: 1 3 5

1 : 3 5

2: 3 4 6

3: 1 2 5

4: 2 6

5: 1 3

6: 2 4

1: 4 , 5 , 6

2: 3 , 4

3: 2 , 4

4: 1 , 2 , 3

5: 1 , 6

6: 1 , 5

1

2

3

4

5

6

7

1: 2, 5, 62: 1, 3, 43: 2, 4, 64: 2, 3, 55: 1, 4, 66: 1, 3, 5