Aplicatii

Problema 1:

Determinati vecinii unui varf al unui graf orientat.

Exemplu:

Pentru varful 1, vecinii sunt: 2,3, si 4

Problema 2:

Determinati gradele exterioare si interioare ale varfurilor unui graf, gradul exterior minim, gradul

exterior maxim, gradul interior minim si gradul interior maxim.

Exemplu:

Pentru varful 1:

d+(1)= 2, d-(1)= 2

min d+(3,5)= 0, max d+(1,2)= 2

min d-(4)= 0, max d-(1)= 2

  Subiecte tip grila

1. Graful neorientat cu 60 de noduri, numerotate de la 1 la

60, are numai muchiile [1,60], [60,20], [20,30] si [4,3].

Numarul componentelor conexe ale grafului este egal

cu:

a) 3 b) 56 c) 54 d) 0

Raspuns: b) 56

Avem 4 muchii intre 6 noduri formand 2 componente

conexe.

Din 60 scadem cele 6 noduri si raman 54 de noduri izolate

à adica 54 de componente conexe

Deci sunt 54 + 2 = 56 componente conexe

 

2. Se considera graful neorientat cu 7 noduri

numerotate de la 1 la 7 si muchiile [1,2], [1,3],

[2,3], [2,4], [2,5], [2,6], [4,6], [5,7], [6,7].

Care este numarul minim de muchii care trebuie

eliminate pentru ca acest graf sa contina 3

componente conexe?

Raspuns: 3

Raman 2 noduri izolate(1,3) si o componenta conexa (2,4,5,6,7)

 3 componente conexe

3. Se considera graful neorientat din figura alaturata. Care este

numarul minim de muchii ce se pot elimina astfel incat graful

partial obtinut sa aiba exact 3 componente conexe?

a) 2 b) 4 c) 1 d) 3

Raspuns: b) 4                         

4 - raman 2 noduri

izolate + 1 componenta conexa

 3 componente conexe

 4. Care este numarul maxim de componente

conexe pe care le poate avea un graf neorientat

cu 20 de noduri si 12 muchii?

a) 6 b) 12 c) 10 d) 15

Raspuns: d) 15

Trebuie sa adaugam 12 muchii intre cat mai putine noduri.

Folosim formula: n(n-1)/2, n-numarul de noduri (formula ne ajuta sa aflam

numarul muchiilor dintr-un graf neorientat complet)

6(6-1)/2=15- intre 6 noduri putem adauga 15 muchii - avem 6 noduri care

formeaza o componenta conexa si 14 noduri izolate

 1+14 = 15 componente conexe

5. Se considera graful orientat reprezentat prin

listele de adiacenta alaturate. Cate noduri au

gradul extern mai mare decat gradul intern?

 6. Se considera un graf orientat cu 6 noduri care

are urmatoarele proprietati:

- Suma gradelor externe ale tuturor varfurilor

grafului este egala cu 6.

- Sunt numai 3 varfuri care au gradul intern egal

cu 1

Care este valoarea maxima pe care o poate avea

gradul extern al unui varf din graful dat?