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

还有一个解决方案,组合:这个问题相当于图中可能的节点对的数量,即:

在此处输入图像描述

于 2012-12-05T19:48:27.523 回答
10

对不起,命名不好,我是物理学家,而不是 CS/Math 人。

每个单个节点(其中有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

归纳证明。基本情况 - 对于 2 个节点,有 1 个连接和2 * 1 / 2 == 1. 现在假设对于N节点我们有N * (N-1) / 2连接。添加一个节点必须建立N额外的连接,并且:

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

最后一行正好被N * (N - 1) / 2替换NN+1,所以证明很好。

于 2012-12-05T19:11:33.890 回答
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 

量子点

于 2012-12-05T19:06:56.957 回答
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) - 0.5) * n

于 2020-01-22T02:00:15.603 回答
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

迟到而不是证明,但是您可以将节点“可视化”为坐标,将关系“可视化”为矩阵中的单元格,我不知道如何在这里绘制一些东西。

每个节点一列,每个节点一行,交叉处的单元格是关系。

您有 x x 个可能的单元格。但是您需要删除左上-右下对角单元格(节点可以链接到自身)。因此,您删除了 x 个单元格,并且只有 (x x-x) = x*(x-1) 个剩余单元格。然后,单元格 (x,y) 与单元格 (y,x) 的链接相同,因此您可以删除剩余的一半单元格:x*(x-1)/2

于 2019-03-13T15:06:02.397 回答