Question

Am nevoie de putin ajutor,va rog!


Se consideră un graf neorientat complet cu 10 vârfuri. Câte lanţuri elementare distincte de lungime 3 există între vârful 2 şi vârful 4? Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie.

a.90

b.28

c.45

d.56

Varianta corecta este d.56, dar nu inteleg modul de gandire. Imi poate explica cineva?

Answer 1

Pai tu o sa ai un lanț de genul 2-x-y-4. X și y pot lua valori din mulțimea {1, 3, 5, 6, 7, 8, 9, 10}, de unde rezulta ca x poate lua 8 valori, iar y poate lua 7 valori întrucât e lanț elementar și poate trece printr-un nod o singura data. Deci răspunsul e 7*8=56.