n個の頂点を持つ有向非巡回グラフでは、その中の有向エッジの可能な最大数はいくつですか？
18490 次
1 に答える
27
N個の頂点/ノードを想定し、最大のエッジを持つDAGを構築する方法を見てみましょう。任意のノード、たとえばN1について考えてみます。この初期段階でポイントできるノードまたはエッジの最大数はN-1です。2番目のノードN2を選択しましょう。それはそれ自体とN1を除くすべてのノードを指すことができます-それはN-2の追加のエッジです。残りのノードについて続行します。各ノードは、前のノードより1つ少ないエッジを指すことができます。最後のノードは他の0ノードを指すことができます。
すべてのエッジの合計：（N-1）+（N-2）+ .. + 1 + 0 ==（N-1）（N）/ 2
于 2012-07-28T07:19:51.110 に答える