2014 dxdy logo

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

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




 
 Задача на графы
Сообщение06.12.2009, 20:01 
Вот уже неделю не могу придумать решения для казалось бы простой задачи: нужно найти количество ациклических орграфов с количеством вершин N. Буду рад любой подсказки.

 
 
 
 Re: Задача на графы
Сообщение07.12.2009, 00:55 
В каком виде ответ хочется? Явная формула тут вряд ли есть. Ещё вопрос в том, считаем ли графы с точностью до изоморфизма или вершины считаем пронумерованными.
В любом случае, обе последовательности есть на OEIS: http://www.research.att.com/~njas/sequences/A003087 и http://www.research.att.com/~njas/sequences/A003024

 
 
 
 Re: Задача на графы
Сообщение07.12.2009, 01:13 
2Iliya
Первое, что приходит на ум. Можно перечислить все $n^2-n$ орграфов (или сколько их там всего?) и проверить каждый на ацикличность. :)

-- Пн дек 07, 2009 04:18:45 --

А вообще, копайте в сторону теоремы Пойа и общих методов неконструктивного перечисления графов.

 
 
 
 Re: Задача на графы
Сообщение07.12.2009, 08:54 
Всем спасибо. Благодаря Вам я таки нашел эту формулу: http://en.wikipedia.org/wiki/Directed_a ... numeration Теперь осталось понять как ее получили и еще одним пробелом в образовании станет меньше :wink:

 
 
 
 Re: Задача на графы
Сообщение09.12.2009, 01:14 
Ой, потерял в предыдущем сообщении основание степени, надо читать не $n^2-n$, а $2^{n^2-n}$. :)

2Iliya
Цитата:
я таки нашел эту формулу

Хм, в приведенной вами ссылке, вроде бы говорится, что проверить орграф на ацикличность можно проверкой положительности собственных значений $(0,1)$-матрицы смежности (детали здесь: Acyclic digraphs and eigenvalues of (0,1)-matrices). Это получается, что можно не только количество узнать, но и сгенерировать искомые объекты? Но все равно, вариантов слишком много и готовая формула лучше. :)

Цитата:
Теперь осталось понять как ее получили

Попробуйте глянуть Харари Ф., Палмер Э. Перечисление графов.

 
 
 
 Re: Задача на графы
Сообщение09.12.2009, 08:20 
Circiter
А по-моему их всего $3^{\frac{n(n-1)}{2}}$. Не?

 
 
 
 Re: Задача на графы
Сообщение09.12.2009, 10:09 
Аватара пользователя
Это смотря допускаем ли мы двойные рёбра "туда-сюда".

 
 
 
 Re: Задача на графы
Сообщение09.12.2009, 16:12 
ИСН
Не совсем хорошо понял про двойные ребра. Я считаю количество орграфов так: всего ребер в графе $\frac{n^2-n}{2}$, каждая пара точек может либо содержать ребро туда, либо обратно, либо не иметь ребра вообще. Следовательно, получаем $3^\frac{n^2-n}{2}$ Где я не прав?

 
 
 
 Re: Задача на графы
Сообщение09.12.2009, 17:21 
Аватара пользователя
Либо иметь два ребра: туда и сюда. Очевидно, Circiter допускает и такое.

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


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