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

Question

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

如何证明这一点？

这不是一个家庭作业问题.我已经远离CS教科书,并且忘记了如何证明这一点的理论.

Answer 1

你有n个节点,每个节点都有n -1个连接(每个连接都连接到除了它自己以外的每个节点),所以我们得到了n*(n-1).但是,因为连接(x,y)和(y,x)是相同的(对于所有连接),我们最终会得到n*(n-1)/2.

Answer 2

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

Answer 3

对不好的命名法,我是物理学家,而不是CS /数学家.

每个节点(其中都有n)必须连接到其他每个节点.有(n-1)"每个人".

因此每个n个节点都有n-1来自它们的连接.n(n-1)

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

所以 n*(n-1)/2