4

以下を計算する必要がある友人がいます。

完全なグラフ 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 の 1 つのセットを考慮するだけで済みます。 C、D は対称性によるものです。

次に、P[A !-> B] は、「ノード 1 と 2 の間にパスがないグラフの数」をグラフの総数で割った値、つまり 2^[(k*(k-1))/2] として計算されます。

ブルートフォース法は K8 までの Mathematica で機能しますが、彼女には 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 が必要です。
  • DIRECTED グラフを扱っていることに注意してください。したがって、UT 行列を使用した通常の表現では十分ではありません。
  • Mathematica には、有向グラフのノード間の距離を求める関数があります (無限大を返す場合、パスはありません)。ただし、パスまたはいいえ。
4

3 に答える 3

4

私には理論がありますが、それをテストするための Mathematica がありません。(そして、用語の間違いを許してください。私はグラフ理論にあまり詳しくありません。)

2^(n*(n-1)/2) の異なる有向 Kn グラフがあることに同意します。問題は、パス A->B を含むものがいくつあるかです。その番号を S(n) と呼びます。

いくつかの n について S(n) がわかっていると仮定し、別のノード X を追加して S(n+1) を計算したいとします。パス X->A を探します。

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

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

XA が X を指している場合、エッジ XB を試します。XB が B を指している場合 (そして、X を接続する方法が 2^(n-2) 個ある場合)、いくつかの 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(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、目的の制約を維持します。醜いが扱いやすい。

于 2009-08-24T18:05:24.317 に答える
2

すべてのグラフを考慮する強引なアプローチでは、それ以上のことはできません。一度に複数のグラフを考慮する必要があります。

8 の場合、2^28 ～ 2 億 5,600 万のグラフがあります。

9: 2^36～640億

10: 2^45 ~ 32 兆

11: 2^55 > 10 16

12: 2^66 > 10 19

13: 2^78 > 10 23

パスを見つける目的で興味深い部分は、グラフの強連結コンポーネントの半順序付けです。実際には、任意の 2 つのノード間にエッジがあるため、順序付けは合計でなければなりません。

したがって、合計順序を検討してみてください。確かに、グラフよりもはるかに少ないです。

于 2009-08-24T19:47:46.420 に答える
0

行列を使ってグラフを表現することはとても役立つと思います。

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)//ここで何かがおかしい私はそれを修正しています where X = k(k-1)/2

  あいうえお
A。0 1 1
B。。1 1
C。。。1
D。。。。

注：一般性を失うことなく、上の三角形を使用できます。

于 2009-08-24T18:32:42.173 に答える