теория графов, помогите разобраться

[defolt87]

интересует следующий вопрос - есть ли алгоритм подсчета связных подграфов (определенного порядка) полного графа. За ранее спасибо.

[Null]

Для полного пронумерованного графа $K_n$количество связных подграфов (порядка $n$)равно

$$\sum\limits_{n-1=s_1+s_2+\dots +s_k}2^{\frac{s_1(s_1-1)}{2}}\cdot (2^{s_1}-1)^{s_2} \cdot 2^{\frac{s_2(s_2-1)}{2}}\cdot (2^{s_2}-1)^{s_3}\cdot \dots \cdot (2^{s_{k-1}}-1)^{s_k}\cdot 2^{\frac{s_k(s_k-1)}{2}}\cdot\frac{(n-1)!}{s_1!s_2!\dots s_k!}$$

Где сумма берется по всем разбиениям(их будет $2^{n-1}$) числа $n-1$ на упорядоченные натуральные слагаемые.

Это мое решение.

Более простая формула здесь.
Результаты здесь.

Если вам нужно количество связных подграфов размера $n$ в $K_m$ то надо результат умножить на $C_m^n$.

[defolt87]

спасибо за помощь)