Question

Dându-se un număr natural N, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu N noduri.

Answer 1

Graful este complet deci orice nod p are o muchie catre orice nod q

Pornim de la primul nod. El se poate conecta la n-1 noduri. Urmatorul nod, nu se va mai putea conecta la primul, pentru ca deja am numarat acea conexiune, deci se poate conecta la n-2 noduri. Al treilea nod la n-3 noduri, si asa mai departe pana cand penultimul nod se mai poate conecta doar la un nod, ultimul
avem atunci numarul de cicluri hamiltoniene

$N_{ham}=(n-1)*(n-2)*(n-2)*..*2*1=(n-1)!$
Dar daca ne cere sa vedem cate cicluri hamiltonene distincte exista, remarca ca noi am citit multe cicluri din ambele sensuri: De exemplu daca am avea 3 noduri 1,2,3 am citit atat 1->2->3->1 cat si 1->3->2->1 adica acelasi ciclu citit din sens invers. Astfel, toate ciclurile sunt numarate de 2 ori, deci numarul de cicluri citite este de fapt
$N_{ham>distincte}=\frac{(n-1)!}{2}$