握手定理,这是离散数据里面的概念。
特别是在计算机当中,甚至管理当中,都会用到这一个原理。
里面最关键的地方就是点与边的关系。
比如说:
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
证明成功,我们终于,得到了这一个握手定理的公式。