给定 n 个节点,如果每个节点都连接到每个其他节点(除了它自己),则连接数将为 n*(n-1)/2
如何证明这一点?
这不是一个家庭作业问题。我已经远离 CS 教科书很久了,忘记了如何证明这一点的理论。
给定 n 个节点,如果每个节点都连接到每个其他节点(除了它自己),则连接数将为 n*(n-1)/2
如何证明这一点?
这不是一个家庭作业问题。我已经远离 CS 教科书很久了,忘记了如何证明这一点的理论。
你有 n 个节点,每个节点都有 n -1 个连接(每个节点都连接到除自身之外的每个节点),所以我们得到n*(n-1)
. 然而,因为连接 (x,y) 和 (y,x) 是相同的(对于所有连接),我们最终得到n*(n-1)/2
.
还有一个解决方案,组合:这个问题相当于图中可能的节点对的数量,即:
对不起,命名不好,我是物理学家,而不是 CS/Math 人。
每个单个节点(其中有n
)都必须连接到其他每个节点。还有(n-1)
“其他所有人”。
所以每个 n 节点都有n-1
来自它们的连接。n(n-1)
但由于每个连接都是“双向的” (a to b = b to a)
,你最终会得到一个因素1/2
所以n*(n-1)/2
归纳证明。基本情况 - 对于 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
替换N
为N+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)
另一个可能的等式,但不如上面的建议那么干净 ((n/2) - 0.5) * n
确定来自 N 个网络节点的最大链接数的最合适的答案是......
一个链接需要 2 个节点的可能组合/连接的总数;所以:
(N!) / [(N-2)!)(2!)] = N(N-1)(N-2)! / (N-2)!(2!);
所以N(N-1) / 2
因为N>1
需要 2 个节点才能拥有一个链接。
迟到而不是证明,但是您可以将节点“可视化”为坐标,将关系“可视化”为矩阵中的单元格,我不知道如何在这里绘制一些东西。
每个节点一列,每个节点一行,交叉处的单元格是关系。
您有 x x 个可能的单元格。但是您需要删除左上-右下对角单元格(节点可以链接到自身)。因此,您删除了 x 个单元格,并且只有 (x x-x) = x*(x-1) 个剩余单元格。然后,单元格 (x,y) 与单元格 (y,x) 的链接相同,因此您可以删除剩余的一半单元格:x*(x-1)/2