完整图中的路径
我有一个朋友需要计算以下内容：
在完整的图Kn (k<=13)中，有k*(k-1)/2条边。 每条边可以通过两种方式定向，因此有 2^[(k*(k-1))/2] 种不同的情况。
她需要计算 P[A !->住宿加早餐旅馆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。
显然，我们不需要找到案例中的最短路径，只是想找到是否存在。
有人有优化建议吗？ （这听起来像是一个典型的欧拉计划问题）。
示例：
最小图 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 !->住宿加早餐旅馆C！-> D] = W/64。
更新：
- A、B、C 和 D 是 4 个不同的顶点，因此我们至少需要 K4。
- 请注意，我们正在处理有向图，因此 UT 矩阵的正常表示是不够的。
- mathematica 中有一个函数可以找到有向图中节点之间的距离（如果它返回无穷大，则没有路径），但这有点矫枉过正，因为我们不需要距离，只要有路径或不是。
I have a friend that needs to compute the following:
In the complete graph Kn (k<=13), there are k*(k-1)/2 edges.
Each edge can be directed in 2 ways, hence 2^[(k*(k-1))/2] different cases.
She needs to compute P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]
X !-> Y means "there is no path from X to Y", and P[ ] is the probability.
So the bruteforce algorithm is to examine every one of the 2^[(k*(k-1))/2] different graphes, and since they are complete, in each graph one only needs to consider one set of A,B,C,D because of symmetry.
P[A !-> B] is then computed as "number of graphs with no path between node 1 and 2" divided by total number of graphs, i.e 2^[(k*(k-1))/2].
The bruteforce method works in mathematica up to K8, but she needs K9,K10... up to K13.
We obviously don't need to find the shortest path in the cases, just want to find if there is one.
Anyone have optimization suggestions? (This sound like a typical Project Euler problem).
Example:
The minimal graph K4 have 4 vertices, giving 6 edges. Hence there are 2^6 = 64 possible ways to assign directions to the edges, if we label the 4 vertices A,B,C and D.
In some graphs, there is NOT a path from A to B, (lets say X of them) and in some others, there are no path from C to D (lets say Y). But in some graphs, there is no path from A to B, and at the same time no path from C to D. These are W.
So P[A !-> B]=X/64, P[C !-> D]=Y/64 and P[A !-> B && C !-> D] = W/64.
Update:
- A, B,C and D are 4 different vertives, hence we need at least K4.
- Observe that we are dealing with DIRECTED graphs, so normal representation with UT-matrices won't suffice.
- There is a function in mathematica that finds the distance between nodes in a directed graph, (if it returns infinity, there is no path), but this is a little bit overkill since we dont need the distance, just if there is a path or not.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我有一个理论，但我没有数学来测试它，所以就这样吧。 （请原谅我在术语上的错误，我不太熟悉图论。）
我同意有 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)；有 2^(n-1) 种方式以这种方式连接 X，并且它将通向 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(n) 的封闭形式？
编辑：
我现在发现最难的部分是这个 P[A !->住宿加早餐旅馆C！-> D]。但我认为递归方法仍然有效：从 {A,B,C,D} 开始，然后不断添加点，跟踪其中 A->(a 点), (b 点)- 的图的数量>B，C->(c点)和(d点)->D，保持所需的约束。丑陋，但很容易驯服。
I have a theory, but I don't have mathematica to test it with, so here goes. (And please excuse my mistakes in terminology, I'm not really familiar with graph theory.)
I agree that there are 2^(n*(n-1)/2) different directed Kn graphs. The question is how many of those contain a path A->B. Call that number S(n).
Suppose we know S(n) for some n, and we want to add another node, X, and calculate S(n+1). We will look for paths X->A.
There are 2^n ways to connect X to the preexisting graph.
The edge X-A might point in the "right" direction (X->A); there are 2^(n-1) ways to connect X this way, and it will lead to a path for any of the 2^(n*(n-1)/2) different Kn graphs.
If X-A points to X, try the edge X-B. If X-B points to B (and there are 2^(n-2) such ways to connect X) then some Kn graphs will give a path B->A, S(n) of them in fact.
If X-B points to X, try X-C; there are 2^(n-3)S(n) successful graphs there.
If my math is correct, S(n+1) = 2^((n+2)(n-1)/2) + (2^(n-1)-1)S(n)
So this gives the following:
Can someone check this? Or give a closed form for S(n)?
EDIT:
I see now that the hard part is this P[A !-> B && C !-> D]. But I think the recursion approach will still work: start with {A,B,C,D}, then keep adding points, keeping track of the number of graphs in which A->(a points), (b points)->B, C->(c points) and (d points)->D, keeping the desired constraint. Ugly, but tractable.
考虑所有图表的强力方法不会让您走得更远，您必须一次考虑多个图表。
对于 8，你有 2^28 ~ 2.56 亿张图。
9: 2^36 ~ 640 亿
10: 2^45 ~ 32 万亿
11: 2^55 > 1016
12：2^66> 1019
13：2^78> 1023
为了查找路径，有趣的部分是图的强连接组件的偏序。实际上，排序必须是全序的，因为任意两个节点之间都存在边。
所以你可以尝试考虑总排序，肯定比图表少很多。
The brute force approach of considering all graphs will not get you much further, you'll have to consider more than one graph at a time.
For 8 you have 2^28 ~ 256 million graphs.
9: 2^36 ~ 64 billion
10: 2^45 ~ 32 trillion
11: 2^55 > 1016
12: 2^66 > 1019
13: 2^78 > 1023
For the purpose of finding paths the interesting part is the partial ordering on the strongly connected components of the graph. Actually the ordering must be total, because there is an edge between any two nodes.
So you could try to consider total orderings, there are certainly a lot fewer than graphs.
我认为使用矩阵表示图将会非常有帮助。
如果
A!->B将 0 放在 A 行 B 列中。将 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)// 这里出了点问题，我'我修复它whereX = k(k-1)/2注意：我们可以使用上三角形而不失一般性。
I think that representing graph using matrix will be very helpful.
If
A!->Bput 0 in A th row and B th column.Put 1 everywhere else.
Count no of 0s = Z.
then
P[A!->B] = 1 / 2^Z=>
P[A!->B && C!->B] - P[A!-B].P[C!-D] = 1/2^2 - 1/ 2^(X-2)// Somthing wrong here I'm fixin itwhereX = k(k-1)/2NOTE:We can use upper triangle without loss of generality.