圖論中的定義

• 設G=<V,E>為任意無向圖，頂點總和為|V|，邊數總和為|E| ，若|E|=m，則所有頂點的度數和=2m

圖論-->現實的理解

• 頂點-->人
• 邊-->人與人握手
• 度-->一個人與其他人握手的次數
• |E|=m-->共m次握手
• 總定理-->n個人參與握手，若發(fā)生握手的總次數為m,則每個人的握手次數之和為2m
• 理解：
  • 假設只有兩個人，求總握手次數
  • 一次握手 == 兩個人的握手次數分別加一 == 2個握手次數 ==總握手次數
  • so:總握手次數==2m
  • ps:不一定每個人都要與其他人握手，總度數只與總邊數有關

握手定理引理

• 一定有偶數個奇數度，或者沒有奇數度：

  • 因為總度數==2m 偶數

• 度數和<=n(n-1) :

  • 假設每個頂點都和其他頂點相連，則總度數=n*(n-1) (ps:頂點數*每個頂點的度數)

• 一定兩個度數相同的節(jié)點

  證明：

  • 設G是具有n個結點的簡單圖(n≥2) ，所以節(jié)點度有 0，1，2。。。(n-1)共n中可能
  • 但節(jié)點0或(n-1)不能同時于一張圖(0代表沒有節(jié)點相連，(n-1)代表跟剩下的節(jié)點都相連)
  • 所以n個節(jié)點只有(n-1)種度可能，必定有兩個度數相同的節(jié)點