Question

Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte, ce uneşte nodul 6 cu nodul 1?

Am atașat graful pe care l-am desenat pentru cerință. Răspunsul meu la întrebare a fost 5, dar aparent e greșit (nici măcar nu e o opțiune) și nu înțeleg de ce. Dacă am avea drumul 5 - 4 - 2 - 1 - 6 - 3 nu am avea doar noduri distincte și nu ar fi unite nodurile 6 și 1? Atunci de ce nu e corect răspunsul meu? M-ar interesa să-mi ziceți nu doar răspunsul corect, ci și DE CE răspunsul acela e corect.

Answer 1

Graful si solutia ta par corecte. Nu sunt sigur ce e un "drum", pentru ca toata teoria grafurilor cata o stiu este in engleza, dar daca se refera la "path" atunci e ok.

Posibil ca ei sa fi pus drumul 5 - 4 - 2 - 1 - 6 - 3 ca avand lungime 6? Sau sa fi vrut sa te opresti cand ai unit 1 cu 6?