Grafuri-Fisa de lucru 1
Fisa de lucru 1
1. Într-un graf neorientat cu 20 de muchii, fiecare nod al grafului are gradul un număr natural, nenul. Doar patru dintre noduri au gradul au gradul un număr par, restul nodurilor având grade impare. Care este numărul maxim de noduri pe care poate să le aibă graful?
2. Câte noduri de grad par conține un graf neorientat cu cinci noduri, care are următoarele muchii: (1,4), (2,3), (3,5), (2,5), (1,5), (2,4).
3. În orice graf neorientat cu n noduri si m muchii are loc relația:
a. grad(1)+grad(2)+...grad(n)=m
c. grad(1)+grad(2)+...grad(n)=m+m
b. grad(1)+grad(2)+...grad(n)=m+n
d. grad(1)=grad(2)=...=grad(n)
4. Se consideră un graf cu cinci noduri numerotate a, b, c, d, e în care orice nod etichetat cu o vocală este adiacent cu toate nodurile etichetate cu consoane, și numai cu acestea, iar orice nod etichetat cu o consoană este adiacent numai cu nodurile etichetate cu vocale. Câte muchii are acest graf?
5. Se consideră un graf neorientat cu opt 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), (6,8). care este gradul minim al unui nod din acest graf? Câte noduri de grad minim sunt?
6. Într-un graf neorientat cu zece noduri, există câte o muchie între oricare două noduri numerotate cu numere consecutive, și câte o muchie între nodul 10 și celelalte noduri. Care este gradul maxim? Câte noduri de grad minim sunt? Câte grafuri parţiale cu exact trei noduri, toate adiacente doua câte două, are graful dat?
7. Un graf neorientat cu n noduri este graf complet dacă şi numai dacă:
a. toate nodurile au gradele pare;
b. nu conţine noduri izolate şi noduri terminale;
c. există câte o muchie între oricare două noduri din graf;
d. numarul de muchii este egal cu n-1.
8. Fie următorul graf neorientat:
a. Câte noduri terminale conţine graful?
b. Care este gradul nodului 5?
c. Câte noduri de grad 3 conţine graful?
d. Care sunt nodurile izolate?
e. Care este numărul minim de muchii care trebuie adăugate astfel încât graful să devină regulat?
f. Câte noduri sunt adiacente cu nodul 1? Care sunt acele noduri?
9. Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de numere pot fi gradele nodurilor unui graf?
10.Care este numărul minim de muchii care trebuie adăugate la graf astfel încât să devină graf complet?
11. Câte grafuri distincte cu n=10 noduri de pot construi?
12. Fie G un graf complet cu n noduri şi m muchii. Care dintre următoarele relaţii este adevărată?
a. grad(1)=grad(2)=...=grad(n)=2*n
c. grad(1)+grad(2)+...+grad(n)=2*n
b. grad(1)+grad(2)+...+grad(n)=n+m
d. grad(1)+grad(2)+...+grad(n)=n*(n-1)
13. Câte muchii conţine un graf regulat cu 10 noduri, în care fiecare nod are gradul egal cu 4?
14. Desenaţi un graf bipartit cu 5 noduri, care sa aibă 3 noduri de grad 2 si doua noduri terminale.
15. Desenati un graf bipartit, regulat cu 6 noduri, în care gradele tuturor nodurilor să fie egal cu 3.
16. Se consideră un graf neorientat G cu 101 noduri şi 101 muchii. Numărul maxim de vârfuri izolate ale grafului poate fi:
17. 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?