完全图中的路径

Question

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

在完全图Kn(k<=13)中，有k*(k-1)/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]。

暴力方法在Mathematica中适用于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/64，P[A !-> B && C !-> D] = W/64。

更新：

A、B、C和D是4个不同的顶点，因此我们至少需要K4。

请注意，我们正在处理定向图，因此UT矩阵的正常表示不足以说明问题。

Mathematica中有一个函数可以找到定向图中节点之间的距离（如果返回无穷大，则表示没有路径），但这有点过度，因为我们只需要知道是否存在路径即可。

- Per Alexandersson

---

请添加一个小例子以使问题更清晰明了？ - Pratik Deoghare

A、B、C、D是否允许相等？ - Craig Gidney

Answer 1

我有一个理论，但我没有Mathematica来测试它，所以请看以下内容。（请原谅我术语上的错误，我不太熟悉图论。）

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

假设我们知道某个n的S(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)的闭合形式？

编辑： 我现在看到困难部分是P[A !-> B && C !-> D]。但我认为递归方法仍然有效：从{A，B，C，D}开始，然后继续添加点，跟踪A->（a点），（b点）->B，C->（c点）和（d点）->D的图形数量，保持所需的约束条件。丑陋，但可处理。

- Beta

---

是的，递归看起来确实很丑陋，但我相信K14和更多的证明并不是最漂亮的。2^(n^2)的复杂度真是让人头疼... - Per Alexandersson

Answer 2

粗暴的全图考虑方法并不能让你更进一步，你需要同时考虑多个图。

对于8，你有2^28 ~ 256百万个图。

9: 2^36 ~ 640亿

10: 2^45 ~ 32万亿

11: 2^55 > 10的16次方

12: 2^66 > 10的19次方

13: 2^78 > 10的23次方

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

因此，您可以尝试考虑总排序，这样的总排序肯定比图少得多。

- starblue

Answer 3

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

如果 A!->B，则在 A 行和 B 列中放置0。

其他地方都放置1。

计算 0 的个数 = 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) // 这里有些问题，我正在修复它 其中 X = k(k-1)/2

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

注意：我们可以无损失地使用上三角形。

- Pratik Deoghare

---

那么对于k=4，P=15/64吗？我认为不是这样的。根据我的手算，P=95/4096。 - Beta

@Beta: 当k=4时，有6个边，而边的不同方向有2 ** 6 = 64种。 - tonfa

@tonfa，是的，P[A!->B]是什么？P[A!->B && C!->D]又是什么？ - Beta