路径在完全图

我有需要计算下面的朋友：路径在完全图

在完全图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 []的概率。

所以bruteforce算法是检查2^[（k *（k-1））/ 2]中的每一个不同的图形，并且由于它们是完整的，每个图中只需要考虑一组A，B，C，D由于对称性。然后计算P [A！→B]作为“在节点1和2之间没有路径的图的数量”除以图的总数，即2^[（k *（k-1））/ 2]。

bruteforce方法可以在K8以下的mathematica中使用，但是她需要K9，K10 ...高达K13。

我们显然不需要在案例中找到最短路径，只需要查找是否存在最短路径。

任何人都有优化建议？（这听起来像一个典型的项目欧拉问题）。

实施例：

最小图形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个不同的vertives，因此，我们需要至少K4。
观察到我们正在处理DIRECTED图，所以UT矩阵的正常表示是不够的。
在mathematica中有一个函数可以找到有向图中节点之间的距离（如果它返回无穷大，没有路径），但这有点矫枉过正，因为我们不需要距离，只要有是否有路径。

来源

2009-08-24 Per Alexandersson

请您增加一个小例子来使问题更清楚吗？ – 2009-08-24 18:21:17

A，B，C，D允许相等吗？ – 2009-08-24 18:51:42

我有一个理论，但我没有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）;边缘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）个成功图。（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 - >乙& &Ç - > d！]。但我认为递归方法仍然有效：以{A，B，C，D}开始，然后继续添加点，跟踪A - >（a点），（b点） - > B，C - >（c点）和（d点） - > D，保持所需的约束。丑，但易于处理。

来源

2009-08-24 18:05:24 Beta

是的，递归看起来真的很难看，但K14和更多的证明不是我相信的最漂亮的。 2 ^（n^2）复杂度是PITA ... – 2009-08-25 07:21:01

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

如果A!->B放第a行和B列英寸

把其他地方。

0的计数no = 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) //财产以后错在这里我fixin它 whereX = k(k-1)/2

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

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

来源

2009-08-24 18:32:42

因此，对于k = 4，P = 15/64？我不认为这是正确的。以我的纸和铅笔计算，P = 95/4096。 – Beta 2009-08-24 19:22:27

@Beta：对于k = 4，有6个边，2 ** 6 = 64个边的不同方向。 – tonfa 2009-08-24 19:55:43

@tonfa，是的，什么是P [A！ - > B]？什么是P [A！ - > B && C！ - > D]？ – Beta 2009-08-24 20:56:36

考虑所有图形的蛮力方法不会让你更进一步，你必须一次考虑多个图形。

对于8你有2^28〜256万图。

9：2^36〜64十亿

10：2^45〜320000亿

11：2^55> 10

12：2^66> 10

13：2^78> 10 23

佛寻找路径的目的有趣的部分是图的强连通分量的偏序。实际上，排序必须是全部的，因为在任何两个节点之间存在边缘。

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

来源

2009-08-24 19:47:46 starblue

路径在完全图

回答

相关问题