Задача на графы

[Iliya]

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

[Cave]

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

[Circiter]

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

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

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

[Iliya]

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

[Circiter]

Ой, потерял в предыдущем сообщении основание степени, надо читать не $n^2-n$, а $2^{n^2-n}$.

2Iliya

Цитата:

я таки нашел эту формулу

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

Цитата:

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

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

[Iliya]

Circiter
А по-моему их всего $3^{\frac{n(n-1)}{2}}$. Не?

[ИСН]

Это смотря допускаем ли мы двойные рёбра "туда-сюда".

[Iliya]

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

[ИСН]

Либо иметь два ребра: туда и сюда. Очевидно, Circiter допускает и такое.