Question

De ce este 29? Nu inteleg

Answer 1

Ok deci nu stiu cat de bine o sa reusesc sa explic, dar incearca sa urmaresti. La final spune "indiferent de modul in care acestea sunt dispuse", deci asta ar insemna ca daca avem deja o componenta conexa cu 8 noduri, trebuie sa mai ramana fix o muchie (pe care nu o mai putem baga in componenta conexa cu 8 noduri) cu are sa unim acea componenta cu ultimul nod. Cu alte cuvinte, privim graful ca fiind format din 2 parti, un subgraf complet (caci daca nu ar fi complet, am putea sa mai bagam muchii in el) cu 8 noduri + un ultim nod pe care l legam cu o muchie. Cate muchii sunt intr-un subgraf complet cu n noduri? n(n-1)/2, deci daca avem 8 noduri, ne trebuie 7*8/2, adica 28 de muchii + 1 cu care legam ultimul nod, deci raspunsul e 29.