0

頂点とエッジGを持つ完全に接続された有向グラフがあるとしましょう。NM

グラフにはいくつのエッジがありますか？それM = N^2ですか？

1つの頂点を取得し、「深さ優先探索」方式でその隣接頂点を訪問し、ループを回避すると、非循環的な単純なパスがいくつ取得されますか？

たとえば、4つの頂点のグラフの頂点1から開始する場合、パスは次のようになります。

- 1
- 1,2
- 1,3
- 1,4
- 1,2,3
- 1,2,4
- 1,3,2
- 1,3,4
- 1,4,2
- 1,4,3

頂点のあるグラフの場合はそれN!以上ですか？Nこれを一般化し、使用可能な式を導き出す方法を見つけることができませんでした。

4

1 に答える 1

1

グラフがいっぱいの場合、n!頂点ごとに単純なパスがあるためn*n!、グラフ内の単純なパスの合計。

開始頂点をv_1。 次に何をすべきかという可能性
があります：それぞれの1つに移動するか、停止します。 次に、可能性があります。それぞれの1つに移動するか、[v_2は2番目に選択されたノードです]停止します。 ... [ここで正式に証明するために誘導を行う] ノードのパスを取得した後、唯一の可能性は停止です。 各頂点の可能な単純なパスの合計と、グラフ内の可能な単純なパスの合計を示します|V|V\{v_1}
|V|-1V\{v_1,v_2}

n
n*(n-1)*...*1 = n!n*n!

于 2011-12-10T16:11:16.533 に答える