Informatică, întrebare adresată de iVictory, 8 ani în urmă

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

Răspuns de andrei750238
3

◘ Raspuns :

\sum_{k=3}^n{C_n^k*\frac{1-(-1)^k}{2} }

◘ 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 A_1A_2A_3...A_k, unde i\neq j, \forall i,j \in \overline{1,n}, i\neq j, k\leq n. 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 n*(n-1)*(n-2)*...*(n-k+1) cicluri elementare, deci \frac{n!}{(n-k)!} cicluri elementare.

Dar nu toate aceste cicluri sunt distincte. A_1A_2A_3...A_k = A_2A_3...A_kA_1 = A_3...A_kA_1A_2=...

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 \frac{n!}{(n-k)!*k!}, 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 C_n^k, trebuie acum sa adunam toate numerele de forma C_n^k, 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 \sum_{k=3}^n{C_n^k*\frac{1-(-1)^k}{2} }


iVictory: Ești un adevărat zeu
iVictory: Inca o intrebare, cum ar trebui sa calculez asta pe foaie pentru n = 17 sa zicem spre exemplu pentru un subiect de admitere? =))
andrei750238: Combinari de 17 cate 3 +
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 +
andrei750238: https://brainly.ro/tema/9794377
iVictory: mersi, asa facusem dar am zis ca poate o fi fost un shortcut sau ceva, multuemsc mult de tot
Alte întrebări interesante