Cea mai simpla solutie consta in generarea tuturor submultimilor de muchii pe care le eliminam. Ce ramane este o reuniune de componente conexe, care defineste fiecare cate o partitie. Dintre toate cele $2^N-1^$ partitii generate, le pastram pe cele unice si impartim acest numar la numarul total de partitii (care poate fi generat si el prin backtracking sau folosind programare dinamica).

O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste $100$, pt $N=13$) si, pentru fiecare astfel de partitie (care are, sa presupunem $K$ elemente), calcularea urmatoarelor valori: $ok[i][j][S] = 1$ sau $0$ , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii $S$ ( $S$ e un numar pe $K$ biti), folosind nodurile din subarborele lui $i$ si ramanand $j$ noduri, inclusiv nodul $i$, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui $i$); o valoare $j=0$ indica ca au fost folosite toate nodurile din subarborele lui $i$, inclusiv $i$, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul $ok[fiu][j'][S']$, cu $j' < j$ si $S'$ inclus in $S$). Daca $ok[ 1 ][ 0 ][2^K^-1]$ are valoarea $1$, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste $100$, pt $N=13$) si, pentru fiecare astfel de partitie (care are, sa presupunem $K$ elemente), calcularea urmatoarelor valori: $ok[i][j][S] = 1$ sau $0$ , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii $S$ ($S$ e un numar pe $K$ biti), folosind nodurile din subarborele lui $i$ si ramanand $j$ noduri, inclusiv nodul $i$, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui $i$); o valoare $j=0$ indica ca au fost folosite toate nodurile din subarborele lui $i$, inclusiv $i$, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul $ok[fiu][j'][S']$, cu $j' < j$ si $S'$ inclus in $S$). Daca $ok[ 1 ][ 0 ][2^K^-1]$ are valoarea $1$, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

h2. 'CT':problema/ct