1. ホーム
  2. 質問と答え
  3. N個のノードを持つグラフの長さ2の最大パス数

N個のノードを持つグラフの長さ2の最大パス数

2011-07-01 14 views

答えて

2

uからvまでの長さ2のパスはu-> u0-> v（u0はグラフの異なる頂点です）です。 cliqueでは、n-2（u、vを除くすべて）をu0とすることができます。 -
ので、各2つのノード間のN-2パス有する長さ2
のように全体的には、uとvとを選択でき：choose(2,n) = n!/((n-2)!)及びそれらのそれぞれのためにそう全N-2の可能性を有する：n!*(n-2)/((n-2)!)= n!/((n-3)!)=n*(n-1)*(n-2)

を

出典

2011-07-01 13:07:58 amit

2

私はこれはちょうど度の合計が1よりも大きい程度で、すべてのノード上の2つを選択していると思う：2つの特定のノード間の

formula

出典

2011-07-01 15:40:41 job

+0

これは正しいと思います。 a - > b - > cのように、与えられた頂点bに焦点を合わせます。今、a-> b-> cとc-> b-> aは一度だけカウントされます（これらは同じパスです）。 bに隣接する頂点の数はd（b）（bの次数）です。次に、長さ2のパスを作成するには、bに隣接するすべての頂点のセットから2つの頂点を選択します。これにより、上記の式が得られます。 – ady

関連する問題

 関連する問題