Care este numarul de cicluri elementare de lungime impara dintr-un graf complet cu n noduri? Sau chiar de orice lungime as vrea sa aflu.
Răspunsuri la întrebare
◘ Raspuns :
◘ 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 , unde . 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 cicluri elementare, deci cicluri elementare.
Dar nu toate aceste cicluri sunt distincte.
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 , 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 , trebuie acum sa adunam toate numerele de forma , 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
Combinari de 17 cate 5 +
Combinari de 17 cate 7 +
Combinari de 17 cate 9 +
Combinari de 17 cate 11 +
Combinari de 17 cate 13 +
Combinari de 17 cate 15 +
Combinari de 17 cate 17 +