2014 dxdy logo

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

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




 
 количество графов с n вершинами и m компонентами связности
Сообщение14.11.2011, 15:11 
Нужна формула для количества возможных графов имеющих n вершин и m компонент связности. Для общего случая.
Графы попарно неизоморфные, неориентированные, без петель и кратных ребер.

Предполагаю, что для этого существует доказанная теорема и не надо изобретать велосипед, но никак не могу эту теорему найти.
Буду благодарен, если порекомендуете книгу, в которой это есть/может быть или сошлетесь на конкретную теорему.

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение15.11.2011, 19:24 
Аватара пользователя
То, что этой формулы нет даже для банально связных графов, Вас не смущает?

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение06.12.2011, 10:36 
Аватара пользователя
См. A201922 и рядом. Там есть формула.

-- Tue Dec 06, 2011 02:58:33 --

ИСН в сообщении #504204 писал(а):
То, что этой формулы нет даже для банально связных графов, Вас не смущает?

Как это нет?! A001349 легко выражается в терминах A000088, а для последней есть формула.

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение06.12.2011, 14:10 
Аватара пользователя
Ну, если это считать формулой, тогда конечно.
(Наверное, в строгом смысле это так и есть, но у меня как-то язык не поворачивается называть формулой такой алгоритм, который начинается со слов "сумма по таким-то специальным разбиениям...")

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение06.12.2011, 22:47 
Аватара пользователя
ИСН в сообщении #511994 писал(а):
Ну, если это считать формулой, тогда конечно.
(Наверное, в строгом смысле это так и есть, но у меня как-то язык не поворачивается называть формулой такой алгоритм, который начинается со слов "сумма по таким-то специальным разбиениям...")

Вполне себе стандартная вещь в комбинаторике. Например, полиномы Белла определяются через аналогичные суммы.

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение27.11.2012, 19:12 
А формулу для количества перенумерованных связных графов с n вершинами и l ребрами не подскажете?

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение27.11.2012, 19:29 
Аватара пользователя
melancholic в сообщении #650540 писал(а):
А формулу для количества перенумерованных связных графов с n вершинами и l ребрами не подскажете?


В A057500 приводится такая формула:

$$\sum_{k=1}^n \frac{(-1)^{k+1}}{k} \sum_{n_1+\dots+n_k=n,\ n_i>0} \binom{n}{n_1, \dots, n_k} \binom{\binom{n_1}{2}+\dots+\binom{n_k}{2}}{\ell}$$

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение28.11.2012, 16:33 
Ого, вот это формула! Спасибо большое. Только непонятно, что это за разбиение n1 + ... + nk = n?

Ага, посмотрел в оригинале - это, вроде, по каждому дереву длиной k проходим.

 
 
 
 Re: количество графов с n вершинами и m компонентами связности
Сообщение28.11.2012, 16:36 
Аватара пользователя
 i  melancholic, для набора формул используйте ТеХ

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


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