4

我有一个朋友需要计算以下内容：

在完整的图 Kn (k<=13) 中，有 k*(k-1)/2 条边。每条边可以以​​ 2 种方式定向，因此有 2^[(k*(k-1))/2] 种不同的情况。

她需要计算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 问题）。

例子：

最小图 K4 有 4 个顶点，给出 6 条边。因此，如果我们标记 4 个顶点 A、B、C 和 D，则有 2^6 = 64 种可能的方式来为边分配方向。

在某些图表中，没有从 A 到 B 的路径（比如说其中的 X），而在其他一些图中，没有从 C 到 D 的路径（假设是 Y）。但是在某些图中，没有从 A 到 B 的路径，同时也没有从 C 到 D 的路径。这些是 W。

所以和。P[A !-> B]=X/64_P[C !-> D]=Y/64P[A !-> B && C !-> D] = W/64

更新：

  • A、B、C 和 D 是 4 个不同的谓词，因此我们至少需要 K4。
  • 请注意，我们正在处理有向图，因此使用 UT 矩阵的正常表示是不够的。
  • 在mathematica中有一个函数可以找到有向图中节点之间的距离，（如果它返回无穷大，则没有路径），但这有点矫枉过正，因为我们不需要距离，只要有路径或不是。
4

3 回答 3

4

我有一个理论，但我没有数学来测试它，所以就这样吧。（请原谅我在术语上的错误，我对图论并不熟悉。）

我同意有 2^(n*(n-1)/2) 个不同的有向 Kn 图。问题是其中有多少包含路径 A->B。调用那个数字 S(n)。

假设我们知道某个 n 的 S(n)，并且我们想要添加另一个节点 X，并计算 S(n+1)。我们将寻找路径 X->A。

有 2^n 种方法可以将 X 连接到预先存在的图。

边缘 XA 可能指向“右”方向（X->A）；以这种方式连接 X 有 2^(n-1) 种方法，它将导致任何 2^(n*(n-1)/2) 个不同 Kn 图的路径。

如果 XA 指向 X，则尝试边 XB。如果 XB 指向 B（并且有 2^(n-2) 种这样的方式连接 X），那么一些 Kn 图将给出一条路径 B->A，实际上它们的 S(n)。

如果 XB 指向 X，则尝试 XC；那里有 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 points) and (d points)->D, 保持期望的约束。丑陋，但易于处理。

于 2009-08-24T18:05:24.317 回答
2

考虑所有图表的蛮力方法不会让您走得更远，您一次必须考虑多个图表。

对于 8，您有 2^28 ~ 2.56 亿张图。

9：2^36~640亿

10：2^45~32万亿

11: 2^55 > 10 16

12：2^66 > 10 19

13: 2^78 > 10 23

为了找到路径，有趣的部分是图的强连通分量的部分排序。实际上排序必须是总的，因为任何两个节点之间都有一条边。

所以你可以尝试考虑总排序，肯定比图表少很多。

于 2009-08-24T19:47:46.420 回答
0

我认为使用矩阵表示图形将非常有帮助。

如果A!->B将0放在第 A 行和第 B 列中。

将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
一个 。0 1 1
乙。. 1 1
C 。. . 1
D. . . .

注意：我们可以使用上三角形而不失一般性。

于 2009-08-24T18:32:42.173 回答