有向非巡回グラフ (DAG) には E=V-1 の辺があることはわかっています。E = エッジの数。V = 頂点の数。
問題は、「有向グラフ G では、辺の数は常に頂点の数よりも少ない」ということです。正しいか間違っているか？
助けてくれてありがとう。
1 に答える
1
N 個の頂点/ノードを想定して、エッジが最大の DAG を作成する方法を調べてみましょう。任意のノード、たとえば N1 を考えてみましょう。この初期段階でポイントできるノードまたはエッジの最大数は N-1 です。2 番目のノード N2 を選択してみましょう。ノード自体と N1 を除くすべてのノードを指すことができます。これは、N-2 個の追加エッジです。残りのノードについて続行します。各ノードは、前のノードよりも 1 つ少ないエッジを指すことができます。最後のノードは、0 個の他のノードを指すことができます。
すべてのエッジの合計:(N-1) + (N-2) + .. + 1 + 0 == (N-1)(N)/2
于 2013-09-25T04:06:56.383 に答える