algorithm - 如何证明 n 个节点之间的最大连接数是 n*(n-1)/2

Question

给定 n 个节点，如果每个节点都连接到每个其他节点（除了它自己），则连接数将为 n*(n-1)/2

如何证明这一点？

这不是一个家庭作业问题。我已经远离 CS 教科书很久了，忘记了如何证明这一点的理论。

score 44 · Accepted Answer

你有 n 个节点，每个节点都有 n -1 个连接（每个节点都连接到除自身之外的每个节点），所以我们得到n*(n-1). 然而，因为连接 (x,y) 和 (y,x) 是相同的（对于所有连接），我们最终得到n*(n-1)/2.

score 26 · Accepted Answer

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

在此处输入图像描述

score 10 · Accepted Answer

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

每个单个节点（其中有n）都必须连接到其他每个节点。还有(n-1)“其他所有人”。

所以每个 n 节点都有n-1来自它们的连接。n(n-1)

但由于每个连接都是“双向的” (a to b = b to a)，你最终会得到一个因素1/2

所以n*(n-1)/2

score 1 · Accepted Answer

归纳证明。基本情况 - 对于 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，所以证明很好。

score 1 · Accepted Answer

每个顶点的度数是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

量子点

score 1 · Accepted Answer

对于 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)

score 0 · Accepted Answer

0

另一个可能的等式，但不如上面的建议那么干净 ((n/2) - 0.5) * n

于 2020-01-22T02:00:15.603 回答

score 0 · Accepted Answer

确定来自 N 个网络节点的最大链接数的最合适的答案是......

一个链接需要 2 个节点的可能组合/连接的总数；所以：

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

所以N(N-1) / 2

因为N>1需要 2 个节点才能拥有一个链接。

score 0 · Accepted Answer

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

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

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

9 回答 9