２点同士の距離の平均が最小となる木

質問

グラフ理論に関してです。
ネットや手持ちのグラフ理論入門書で探しても見つけられなかったので質問させて下さい。

重みつき連結グラフにおいて, 入力が「グラフ上の複数(>=2)の節点」であり、出力が「節点同士の距離平均が最小であるような木」となるようなアルゴリズムはあるでしょうか。
もしくはそれに対する近似的なアルゴリズムでもかまいません。

言い直すと、入力された節点集合を U として
(　　Σ<iとjの距離> ) / |U|
　i,j∈U, i≠j
が最小となるような木です。

回答No.1

bender · ベストアンサー

与えられた式　(Σ<iとjの距離> )/|U|　について考えると、入力されたグラフに対して|U|は定数なので、問題としては、分子の (Σ<iとjの距離>)　が最小になる木を求める、ということと同じかと思うのですが、これは「最小全域木問題」ではないでしょうか。

最小全域木（Minimum Spanning Tree）を求めるアルゴリズムについては、インターネットや、アルゴリズムの本で詳しく紹介されていると思います。

ところで、「頂点同士の距離の平均」を求める式は、(Σ<iとjの距離>)/|U|　ではなく、おそらく、(Σ<iとjの距離>)/(|U|-1)　であるような気がします。