Question

vaaa rogfff problema 1 am tezaaaaaa

Answer 1

1) X este multimea nodurilor din graf, U este multimea muchiilor din graf
X={1,2,3,4,5,6,7}
U={(1,6),(1,2),(2,5),(2,7),(1,7),(2,3),(3,7),(5,7)}
2) Gradul unui varf(sau unui nod) este numarul de muchii incidente acelui nod(care contin acel nod). se noteaza cu d. Avem atunci
d(1)=3
d(2)=4
d(3)=2
d(4)=0
d(5)=2
d(6)=1
d(7)=4
c) Matricea adiacenta Aij este o matrice care are valoarea 1 daca intre linia i si coloana j(adica nodurile i si j) exista o muchie, si 0 daca nu exista
Diagonala principala a matricii, unde i=j, adica nodul este egal cu el insusi va fi intotdeauna 0, pentru ca nu poti trage o muchie cu tine insuti.

0 1 0 0 0 1 0
1 0 1 0 1 0 1
0 1 0 0 0 0 1
0 0 0 0 0 0 0 
0 1 0 0 0 0 1
1 0 0 0 0 0 0
1 1 1 0 1 0 0 

d) Copiezi graful si elimini muchiile care trec prin 2 si 6, sau te folosesti de matricea de adiacenta si elimini toate valorile de 1  de pe randurile respectiv coloanele 2 si 6

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0 
0 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 1 0 1 0 0 

e) daca sunt eliminate varfurile 4,5,6, atunci aceste linii si coloane dispar complet din matricea adiacenta

0 1 0 0
1 0 1 1
0 1 0 1
1 1 1 0 

f) Lant elementar: succesiune de varfuri cu muchii intre ele care apar o singura data
Neelementar daca un varf apare de mai multe ori
Elementar: (6,1,2)
Neelementar: (2,7,3,2,1)
g) Ciclu elementar: lant in care primul varf este egal cu ultimul celelalte distince 2 cate 2, altfel este neelementar
Elementar: (2,7,5,2)
Neelementar: (2,3,7,2,3,7,5,2)