無向グラフには 'n' 個の頂点と 0 個のエッジがあります。グラフが切断されたままになるように描画できるエッジの最大数はいくつですか。
1 つの頂点を除外し、無向グラフの n-1 頂点間のエッジの最大数を見つけて、グラフがまだ切断されたままになるようにするソリューションを作成しました。
これは、n 頂点の場合は n(n-1)/2 であり、n-1 頂点の場合は (n-1)(n-2)/2 になります。より良い解決策はありますか？
質問する
5786 次
3 に答える
7
これは、分析を使用して解決できます。あなたのアイデアを一般化してください。xn 個の頂点をとのサイズの 2 つのグループに分けますn-x。ここで、エッジの数は の関数であり、次のxように表されます。
f(x)= x(x-1)/2 + (n-x)(n-x-1)/2
f(x) = 1/2(2x^2 - 2nx +n^2 - n)
この関数を最大化する値が、必要なパーティション サイズです。x=0計算すると、 から に減少しx=n/2、 に増加することがわかりますx=n。x = 0 または x = n はグラフが収集されることを意味するため、次の最大値を取りますx=1。したがって、あなたの直感は最適です。
于 2012-04-08T11:18:11.873 に答える
3
あなたの解決策は最善の解決策でなければなりません。
追加された新しいエッジには、一方の端に n 番目の頂点がなければならないためです。
于 2012-04-08T10:35:58.387 に答える
0
グラフが多重辺を持つことができる場合、答えはn>=3の場合は無限大です。
自己ループも含めることができる場合、答えはn>=2の場合は無限大です。
それらのどれも当てはまらない場合、あなたの解決策は正しいです。
于 2012-04-08T10:56:32.030 に答える