単純経路の平均長さを計算するためのアルゴリズム

Question

接続されたグラフと2つのノードとtとtを与えられると、sからtへのシンプルなパス（サイクルなし）が多数あります。これらの経路の平均長さを見つけるための効率的なアルゴリズムはありますか？

Answer 1

私は2つのノード間の単純経路の数を数える多項式アルゴリズムがP= NPであることを知っていることを推測していると思いますが、この結果は勇敢によるものです（列挙と信頼性の問題の複雑さ、1979）。

今すぐ想像して、 $ \ text {avg}（g、u、v）$ をpolynomial timeに計算することができます。

$ g + l $ $ l $ $ u $ と $ v $ $ g $ 。この新しいパスは $ L-1 $ 新しいノードでできていて、 $ udからの以前のパスを妨害しません。 $ v $ への $ l \ geq 2 $ 。

その後、 $ \ text {avg}（g + 3、u、v） - \ text {avg}（g + 2、u、v）$ = $ 1 /（\＃\ text {paths}（g、u、v）+1）$ 、 $ \＃\ text {paths}（g、u、v）$ 多項式時間。しかし、私たちはこれが多項式の時間、矛盾で行われることが期待できないことを知っています。