グラフ理論最大エッジ？

単純なグラフに3つのコンポーネントがあり、これらのコンポーネントの頂点が4,5,6の場合、グラフのエッジの最大数が表示されます。グラフ理論最大エッジ？

（a）は26

（b）は76

（c）は30

（D）42

I場合、私は間違った答えを得るのはなぜ「頂点がn個、連結成分がk個のグラフに最大辺がある」という式を適用します。(n-k)(n-k+1)/2？

nを4 + 5 + 6 = 15、コンポーネント数= 3とすることはできませんか？私の理解に

2017-03-13 Bongbirdie

私はプログラミングに関するものではないので、この質問をトピックとしてクローズすることにしました。 –

頂点の最大数は、頂点を 'k '成分にどのように分配するかを選択するときに' m≤（n-k）（n-k + 1）/ 2'です。 http://math.stackexchange.com/questions/1075692/number-of-edges-in-a-graph-with-n-vertices-and-k-connected-componentsを参照してください。コンポーネントの頂点の数を指定すると、[Codor's answer]（http://stackoverflow.com/a/42758345/1377097）のように、そのコンポーネントが完全なグラフであるときの最大エッジ数があります。 – beaker

、連結成分の各々は、それぞれの連結成分の頂点の数であるnせいぜい

n*(n-1)/2

縁を有することができます。数式は、n個の頂点を持つ完全なグラフの辺の数です。合計で、一つ

4*3 5*4 6*5 
--- + --- + --- = 6 + 10 + 15 = 31 
    2  2  2

縁（一方、驚くべきことに、この番号が有効な回答のリストでは生じない）の最大数を取得します。

出典

2017-03-13 07:26:43 Codor

グラフ理論最大エッジ？

答えて

関連する問題