Пути в полном графе

У меня есть теория, но нет математики, чтобы проверить ее, так что поехали. (И, пожалуйста, извините за мои ошибки в терминологии, я не совсем знаком с теорией графов.)

Я согласен, что существует 2^(n*(n-1)/2) различных ориентированных графов Kn. Вопрос в том, сколько из них содержат путь A->B. Назовите этот номер S(n).

Предположим, мы знаем S(n) для некоторого n и хотим добавить еще один узел X и вычислить S(n+1). Будем искать пути X->A.

Есть 2 ^ n способов соединить X с ранее существовавшим графом.

Ребро X-A может указывать в «правильном» направлении (X->A); существует 2 ^ (n-1) способов соединить X таким образом, и это приведет к пути для любого из 2 ^ (n * (n-1)/2) различных графов Kn.

Если X-A указывает на X, попробуйте ребро X-B. Если X-B указывает на B (а таких способов соединить X 2^(n-2)), то некоторые графы Kn дадут путь B->A, их фактически S(n).

Если X-B указывает на X, попробуйте X-C; там 2^(n-3)S(n) успешных графов.

Если моя математика верна, S(n+1) = 2^((n+2)(n-1)/2) + (2^(n-1)-1)S(n)

Итак, это дает следующее:

S(2) = 1
S(3) = 5
S(4) = 47
S(5) = 841
S(6) = 28999

Кто-нибудь может это проверить? Или дать закрытую форму для S(n)?

РЕДАКТИРОВАНИЕ:
Теперь я вижу, что сложная часть — это P[A !-> B && C !-> D]. Но я думаю, что рекурсивный подход все равно будет работать: начните с {A,B,C,D}, затем продолжайте добавлять точки, отслеживая количество графиков, в которых A->(a точки), (b точки)-> B, C->(c точек) и (d точек)->D, сохраняя желаемое ограничение. Некрасиво, но сговорчиво.

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

Для 8 у вас есть 2 ^ 28 ~ 256 миллионов графиков.

9: 2^36 ~ 64 миллиарда

10: 2^45 ~ 32 триллиона

11: 2^55 > 10¹⁶

12: 2^66 > 10¹⁹

13: 2^78 > 10²³

С целью поиска путей интересной частью является частичное упорядочение сильно связанных компонентов графа. На самом деле порядок должен быть тотальным, потому что между любыми двумя узлами есть ребро.

Таким образом, вы можете попытаться рассмотреть общие заказы, их, безусловно, намного меньше, чем графиков.

Я думаю, что представление графика с использованием матрицы будет очень полезным.

Если A!->B, поместите 0 в строку A и столбец B.

Ставьте 1 везде.

Количество нулей = Z.

затем P[A!->B] = 1 / 2^Z

=> P[A!->B && C!->B] - P[A!-B].P[C!-D] = 1/2^2 - 1/ 2^(X-2) // Что-то тут не так, исправлю where X = k(k-1)/2

  A B C D
A . 0 1 1
B . . 1 1
C . . . 1
D . . . .

ПРИМЕЧАНИЕ. Мы можем использовать верхний треугольник без потери общности.