パス

Question

Iは、以下を計算する必要がある友人があります完全グラフ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の対称性があるためです。 【数1】P [A！→B]は、「ノード1と2との間の経路を持たないグラフの数」をグラフの総数で割ったもの、すなわち2^[（k *（k-1））/ 2]。

bruteforceメソッドはK8までmathematicaで動作しますが、K9、K10 ... K13までが必要です。

明らかに、最短パスを見つける必要はありませんが、ケースがある場合は見つけたいだけです。

誰にでも最適化の提案がありますか？ （これは典型的なProject Euler問題のようなものです）。

例：

最小グラフK4 6つのエッジを与え、4つの頂点を有しています。したがって、4つの頂点A、B、CおよびDにラベルを付けると、エッジに方向を割り当てる2^6 = 64の可能な方法があります。

一部のグラフでは、AからBへのパスはありません彼らのXと言うことができます）、他のものでは、CからDへのパスがありません（Yと言うことができます）。しかし、いくつかのグラフでは、AからBへのパスはなく、同時にCからDへのパスもありません。これらはWです。

更新：

• A、B、C及びDは、4つの異なるvertivesあり、それゆえ我々は、少なくともK4を必要とします。
• DIRECTEDグラフを扱っていることに注意してください。そうすれば、UT-行列による正規表現では十分ではありません。
• 有向グラフのノード間の距離を求める関数があります（無限大を返す場合はパスがありません）が、これはちょっと距離が必要ないのでちょっと残念ですパスかどうか。

Answer 1

私は理論を持っていますが、私はそれをテストするための数学を持っていないので、ここに行きます。

私は、2 ^（n *（n-1）/ 2）の異なる有向グラフがあることに同意します。問題はどれくらいのものがパスA→Bを含んでいるかです。その番号S（n）を呼ぶ。

いくつかのnについてS（n）を知り、別のノードXを追加してS（n + 1）を計算したいとします。パスX-> Aを探す。

Xを既存のグラフに接続する方法は2^n通りあります。

エッジX-Aが「右」方向を指している可能性があります（X-> A）。このようにXを接続する2 ^（n-1）通りの方法があり、2 ^（n *（n-1）/ 2）の異なるKnグラフのいずれかのパスにつながります。

X-AがXを指している場合は、エッジX-Bを試してください。 X-BがBを指していれば（Xを接続する2 ^（n-2）通りの方法がある）、いくつかの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）の閉じた形式を与えますか？

EDIT：
私は、ハードの部分は、このPであることを今見る[ - > B & & C - > D！！]。 A点、B点、C点、D点から始まり、A点、A点、B点、B点のグラフの数を記録して、 B、C→（c点）と（d点）→Dとなり、所望の制約が維持される。醜い、しかし扱いやすい。

Answer 2

行列を使ってグラフを表現すると非常に便利だと思います。

A!->B場合は行とB列目にを置きます。

他のすべての場所。

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

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

NOTEそれをfixinよ：私たちは、一般性を失うことなく上部の三角形を使用することができます。

Answer 3

すべてのグラフを考慮すると、それほど威力を発揮しません。一度に複数のグラフを検討する必要があります。

8の場合、2〜28〜256万のグラフがあります。

9：2^36〜640億

10：2^45〜32000000000000

11：2^55> 10

12：2^66> 10

13：2^78> 10

Foを興味深い部分を見つける経路の目的は、グラフの強連結成分の部分的な順序付けである。実際には、2つのノードの間にエッジがあるため、順序は合計でなければなりません。

したがって、全体の順序を検討することができますが、確かにグラフよりもはるかに少ないです。