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

Question

У меня есть друг, которому нужно вычислить следующее:

В полном графе Kn (k <= 13) имеется k * (k-1) / 2 ребер. Каждое ребро может быть направлено двумя способами, следовательно, 2 ^ [(k ​​* (k-1)) / 2] разных случаев. </p>

Ей нужно вычислить P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X! -> Y означает "нет пути от X к Y", а P [] - вероятность.

Таким образом, алгоритм грубой силы состоит в том, чтобы исследовать каждый из 2 ^ [(k ​​* (k-1)) / 2] различных графов, и, поскольку они завершены, в каждом графе нужно рассмотреть только один набор A , B, C, D из-за симметрии.

P [A! -> B] затем вычисляется как «количество графов без пути между узлами 1 и 2», деленное на общее количество графов, т.е. 2 ^ [(k ​​* (k-1)) / 2 ].

Метод грубой силы работает в математике до K8, но ей нужны K9, K10 ... до K13.

Нам, очевидно, не нужно искать кратчайший путь в случаях, мы просто хотим найти, если он есть.

У кого-нибудь есть предложения по оптимизации? (Это звучит как типичная проблема Project Euler).

Пример: * ** 1022 тысячу двадцать одна * Минимальный граф K4 имеет 4 вершины, дающие 6 ребер. Следовательно, существует 2 ^ 6 = 64 возможных способов назначения направлений для ребер, если мы пометим 4 вершины A, B, C и D.

В некоторых графах НЕ существует пути от А до В (скажем, из них X), а в некоторых других нет пути от С до D (допустим, Y). Но на некоторых графиках нет пути от A к B, и в то же время нет пути от C к D. Это W.

То есть P[A !-> B]=X/64, P[C !-> D]=Y/64 и P[A !-> B && C !-> D] = W/64.

Обновление:

• A, B, C и D - это 4 разные версии, поэтому нам нужно как минимум K4.
• Заметьте, что мы имеем дело с НАПРАВЛЕННЫМИ графами, поэтому нормального представления с UT-матрицами будет недостаточно.
• В mathematica есть функция, которая находит расстояние между узлами в ориентированном графе (если он возвращает бесконечность, пути нет), но это немного излишне, поскольку нам не нужно расстояние, просто если есть путь или нет.

Answer 1

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

Я согласен, что существует 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 (и существует 2 ^ (n-2) таких способов связать X), то некоторые графы 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)?

EDIT:
Теперь я вижу, что самая сложная часть - это P [A! -> B && C! -> D]. Но я думаю, что рекурсивный подход все еще будет работать: начните с {A, B, C, D}, затем продолжайте добавлять точки, отслеживая количество графиков, в которых A -> (точки), (точки b) -> B, C -> (точки c) и (точки d) -> D, сохраняя желаемое ограничение. Уродливый, но послушный.

Answer 2

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

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

9: 2 ^ 36 ~ 64 млрд.

10: 2 ^ 45 ~ 32 трлн

11: 2 ^ 55> 10 ¹⁶

12: 2 ^ 66> 10 ¹⁹

13: 2 ^ 78> 10 ²³

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

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

Answer 3

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

Если A!->B, укажите 0 в строке A и столбце B *. 1008 *

Положите 1 везде.

Количество отсчетов 0s = 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 . . . .

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