路徑在完全圖

我有需要計算下面的朋友：路徑在完全圖

在完全圖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

路徑在完全圖

回答

相關問題