18

n個のノードがある場合、すべてのノードが他のすべてのノード（それ自体を除く）に接続されている場合、接続数はn *（n-1）/2になります。

これをどのように証明しますか？

これは宿題の問題ではありません。私は長い間CSの教科書から離れていて、これを証明する方法についての理論を忘れていました。

4

9 に答える 9

44

n個のノードがあり、それぞれにn -1個の接続があります（それぞれがそれ自体を除くすべてのノードに接続されています）。したがって、が得られn*(n-1)ます。ただし、接続（x、y）と（y、x）は（すべての接続で）同じであるため、最終的にはになりn*(n-1)/2ます。

于 2012-12-05T19:05:54.973 に答える
26

そしてもう1つの解決策、組み合わせ論：問題は、グラフ内のノードの可能なペアの数に相当します。

ここに画像の説明を入力してください

于 2012-12-05T19:48:27.523 に答える
10

悪い命名法で申し訳ありませんが、私は物理学者であり、CS/数学の人ではありません。

すべての単一ノード（そこにありますn）は、他のすべてのノードに接続する必要があります。(n-1)「他のすべて」があります。

したがって、各nノードにn-1はそれらからの接続があります。n(n-1)

ただし、各接続は「双方向」(a to b = b to a)であるため、最終的には次の係数になります。1/2

それでn*(n-1)/2

于 2012-12-05T19:09:00.030 に答える
1

各頂点の次数は（隣接する 頂点がn-1あるため）です。握手補題は、次のように述べています。したがって：n-1
Sigma(deg(v)) (for each node) = 2|E|

Sigma(deg(v)) (for each node) = 2|E|
Sigma(n-1) (for each node) = 2|E|
(n-1)*n = 2|E|
|E| = (n-1)*n /2

QED

于 2012-12-05T19:06:56.957 に答える
1

帰納法による証明。基本ケース-2ノードの場合、1つの接続と2 * 1 / 2 == 1。Nここで、ノードに接続があると仮定しN * (N-1) / 2ます。ノードをもう1つ追加するには、N追加の接続を確立する必要があります。

N * (N-1) / 2 + N =
(N^2 - N + 2N) / 2 =
(N^2 + N) / 2 =
(N + 1) * N / 2

この最後の行は正確N * (N - 1) / 2ににN置き換えられてN+1いるので、証明は良好です。

于 2012-12-05T19:11:33.890 に答える
1

1ノードの場合：n接続

2ノードの場合：n-1接続（すでに最初のノードが接続されています）

3ノードの場合：n-2接続.. nノードの場合：n-（n-1）接続

したがって、合計接続数= n + n-1 + n-2 + ........ 1

                        = n(n-1)/2 (sum of first n-1 natural numbers)
于 2016-03-24T03:37:41.037 に答える
0

N個のネットワークノードから可能なリンクの最大数を決定するための最も適切な答えは...

リンクに2つのノードが必要な場合の可能な組み合わせ/接続の総数。それで：

(N!) / [(N-2)!)(2!)] = N(N-1)(N-2)! / (N-2)!(2!);

それでN(N-1) / 2

N>1リンクを作成するには2つのノードが必要です。

于 2017-08-01T13:15:21.943 に答える
0

遅く、証明ではありませんが、ノードを座標として「視覚化」し、マトリックス内のセルとして関係を「視覚化」することができます。ここで何かを描画する方法がわかりません。

ノードごとに1列、ノードごとに1行、クロスのセルがリレーションです。

xx個の可能なセルがあります。ただし、左上から右下の対角セルを削除する必要があります（ノードはそれ自体にノードをリンクできます）。したがって、x個のセルを削除し、残りのセルは（x x-x）= x *（x-1）のみになります。次に、セル（x、y）はセル（y、x）と同じリンクであるため、残りのセルの半分を削除できます：x *（x-1）/ 2

于 2019-03-13T15:06:02.397 に答える
0

別の可能な方程式ですが、上記の提案ほどきれいではありません（（n / 2）-0.5）* n

于 2020-01-22T02:00:15.603 に答える