離散數學握手定理推論的應用

握手定理，這是離散數據裏面的概念。

特別是在計算機當中，甚至管理當中，都會用到這一個原理。

裏面最關鍵的地方就是點與邊的關係。

比如説:

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

證明成功，我們終於，得到了這一個握手定理的公式。