TEST DE EVALUARE CLASA a XI-a INFORMATICA - GRAFURI NEORIENTATE-NOTIUNI INTRODUCTIVE

TEST DE EVALUARE CLASA a XI-a

Subiect: GRAFURI NEORIENTATE-NOTIUNI INTRODUCTIVE

-VARIANTA 1-

1. Se da urmatorul graf :

Completati:

a)      Multimea nodurilor X= ...................

b)      Multimea muchiilor U= ....................

c)      Un varf x_i pentru care d(x_i) = 0 se numeste............

d)      Un varf x_i pentru care d(x_i) = 1 se numeste............

e)      Varfurile adiacente cu varful 5 in graf sunt............

f)       Muchiile incidente varfului 6 in graf sunt..............

g)      Gradul varfului 3 in graf este ..................

Care dintre urmatoarele succesiuni de varfuri reprezinta lanturi in graful dat?

Precizati tipul fiecarui lant gasit.

a)      L = (1 , 2 , 3 , 6 , 8)

b)      L = (1 , 3 , 6 , 9 , 10)

c)      L = (4 , 5 , 3, 6 , 7)

d)      L = (1, 3 , 5, 4 , 2 , 3 , 6)

Care dintre urmatoarele succesiuni de varfuri este un ciclu? Precizati tipul fiecarui ciclu gasit.

a)      C = (1 , 2 , 3 , 5 , 2 , 6)

b)      C = (1 , 3 , 5 , 2 , 1)

c)      C = (3 , 1 , 2 , 3 , 4 , 5 , 3)

d)      C = (1, 2 , 5, 3 , 1)

Construiti un subgraf obtinut prin eliminarea varfurilor 1, 6 , 7 , 8 , 9 , 10 .

a)      ce proprietate are subgraful construit?

b)      determinati numarul total de muchii ale subgrafului construit si generalizati pentru cazul unui graf cu n varfuri .

Construiti graful partial obtinut prin eliminarea muchiilor care trec prin varfu-

rile 2 si 6.

2. Se citesc de la tastatura doua numere intregi m si n , apoi m perechi de numere intregi reprezentand extremitatile muchiilor unui graf neorientat cu m muchii si n varfuri . Sa se construiasca matricea de adiacenta si sa se scrie gradele varfurilor in fisierul "grad.txt"(pe fiecare rand se vor scrie un varf si gradul sau, separate prin spatii).Sa se determine si sa se afiseze varfurile izolate ale grafului.

BAREM DE NOTARE: 1 ..5 p 1.1...... 1,75 p

2.. 4p 1.2...... 0,75 p

+1 p din oficiu 1.3...... 0,75 p

1.4...... 1,25 p

1.5...... 0,50 p

TEST DE EVALUARE CLASA a XI-a

Subiect: GRAFURI NEORIENTATE-NOTIUNI INTRODUCTIVE

-VARIANTA 2-

1. Se da urmatorul graf :

Completati:

a)      Multimea nodurilor X= ...................

b)      Multimea muchiilor U= ....................

c)      Un varf x_i pentru care d(x_i) = 1 se numeste............

d)      Un varf x_i pentru care d(x_i) = 0 se numeste............

e)      Varfurile adiacente cu varful 2 in graf sunt............

f)       Muchiile incidente varfului 1 in graf sunt..............

g)      Gradul varfului 6 in graf este ..................

Care dintre urmatoarele succesiuni de varfuri reprezinta lanturi in graful dat?

Precizati tipul fiecarui lant gasit.

a)      L = (2 , 1 , 3 , 5, 4)

b)      L = (1 , 3 , 6 , 9 , 10)

c)      L = (4 , 5 , 3, 6 , 8)

d)      L = (1, 2 , 4, 3 , 2 , 5)

Care dintre urmatoarele succesiuni de varfuri este un ciclu? Precizati tipul fiecarui ciclu gasit.

a)      C = (1 , 3 , 5 , 2 , 1)

b)      C = (1 , 3 , 5 , 2 , 1)

c)      C = (3 , 1 , 2 , 3 , 4 , 5 , 3)

d)      C = (1, 2 , 5, 3 , 2)

Construiti un subgraf obtinut prin eliminarea varfurilor 1, 6 , 7 , 8 , 9 , 10 .

a)      ce proprietate are subgraful construit?

b)      determinati numarul total de muchii ale subgrafului construit si generalizati pentru cazul unui graf cu n varfuri .

Construiti graful partial obtinut prin eliminarea muchiilor care trec prin varfu-

rile 3 si 6.

2. Se citeste de la tastatura matricea de adiacenta a unui graf neorientat cu n varfuri .Sa se scrie gradele varfurilor in fisierul "grad.txt"(pe fiecare rand se vor scrie un varf si gradul sau, separate prin spatii).Sa se determine si sa se afiseze varfurile terminale ale grafului.

BAREM DE NOTARE: 1 ..5 p 1.1...... 1,75 p

2.. 4p 1.2...... 0,75 p

+1 p din oficiu 1.3...... 0,75 p

1.4...... 1,25 p

1.5...... 0,50 p