◘ Raspuns :
[tex]\sum_{k=3}^n{C_n^k*\frac{1-(-1)^k}{2} }[/tex]
◘ Demonstratie & explicatie :
Intr-un graf complet toate nodurile sunt adiacente, exista muchie intre fiecare doua noduri.
Un ciclu elementar de lungime k este de forma [tex]A_1A_2A_3...A_k[/tex], unde [tex]i\neq j, \forall i,j \in \overline{1,n}, i\neq j, k\leq n[/tex]. Nu punem primul nod si la final, desi aceasta e notatia consacrata pentru a usura demonstratia,
Vom determina numarul de cicluri elementare de lungime k folosind regula produsului :
► Cate moduri avem pentru a alege A1 ?
Putem alege A1 in n moduri, primul nod poate fi oricare nod al grafului.
► Cate moduri avem pentru a alege A2 ?
Putem alege A2 in n-1 moduri, primul nod poate fi oricare nod al grafului inafara de nodul ales pentru A1.
► Cate moduri avem pentru a alege A3 ?
Putem alege A3 in n-2 moduri, primul nod poate fi oricare nod al grafului inafara de nodul ales pentru A1 si cel ales pentru A2.
..............
► Cate moduri avem pentru a alege Ak ?
Putem alege Ak in n+1-k moduri, primul nod poate fi oricare nod al grafului inafara de nodurile alese pentru A1, A2, .... Ak-1
Rezulta din regula produsului ca avem [tex]n*(n-1)*(n-2)*...*(n-k+1)[/tex] cicluri elementare, deci [tex]\frac{n!}{(n-k)!}[/tex] cicluri elementare.
Dar nu toate aceste cicluri sunt distincte. [tex]A_1A_2A_3...A_k = A_2A_3...A_kA_1 = A_3...A_kA_1A_2=...[/tex]
Altfel spus, toate permutarile circulare ale ciclului se regasesc in multimea de mai sus, stiind ca un set cu k elemente are k permutari circulare, rezulta ca impartind numarul determinat mai sus la k obtinem numarul de cicluri elementare distincte.
Deci numarul de cicluri elementare distincte de lungime k al unui graf complet cu n noduri este egal cu [tex]\frac{n!}{(n-k)!*k!}[/tex], egal altfel spus cu numarul de combinari de n elemente luate cate k.
Daca numarul de cicluri elementare distincte de lungime k al unui graf complet cu n noduri este [tex]C_n^k[/tex], trebuie acum sa adunam toate numerele de forma [tex]C_n^k[/tex], pentru fiecare k impar. Consider ca un ciclu are cel putin noduri distince, formula pentru numarul de cicluri impare de lungime k al unui graf complet devine [tex]\sum_{k=3}^n{C_n^k*\frac{1-(-1)^k}{2} }[/tex]
