离散数学握手定理推论的应用

握手定理，这是离散数据里面的概念。

特别是在计算机当中，甚至管理当中，都会用到这一个原理。

里面最关键的地方就是点与边的关系。

比如说:

1个点对应0个边

2个点对应1个边

3个点对应3个边

4个点对应6个边。

那么，点与边的关系，是怎么样的

从这些数字当中，真不好理出其中的关系，但是分解到一个点问题就比较好办了。

假设，一共n个点，那么一个点对应着，n-1个边，那么，所有的点加起来，就成了：n(n-1)，但是只有两个点才能构成一个边，所以一个点的边数肯定是另一个边的点数，也就是存在重合2次的问题，所以：n(n-1)/2.

这样就得到了这一个公式：边数 = 点数*（点数-1）/2

我们可以，用数据归纳方，对上面的分析进行证明：

数学归纳法：

1个顶点为0 2个顶点为1 满足1=2*1/2

3个顶点以上时 假如n=k-1 k>=3时结论成立

也就是k-1个顶点有 (k-1)*(k-2)/2=k^2/2-3k/2+1个边

加入第k个顶点时 与前k-1个顶点产生k-1条边

则边数一共为k^2/2-3k/2+1+k-1=k^2/2-k/2=k*(k-1)/2

即当n=k时也满足条件

因此一个具有N个顶点的无向完全图的边数为n*(n-1)/2

证明成功，我们终于，得到了这一个握手定理的公式。