2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: теория графов, помогите разобраться
Сообщение23.12.2013, 12:05 
Для полного пронумерованного графа $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$.

 
 
 
 Re: теория графов, помогите разобраться
Сообщение23.12.2013, 15:41 
спасибо за помощь)

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group