[理工] 離散 圖論

[newpuma (還很新)]

Kn具有多少個不具共同邊的Hamilton cycle之證明

Kn邊數為n取2個，且每個邊數為n

為什麼不具共同邊的環路是n取2/n？(n(n-1)/2)除以n= (n-1)/2

這個問題課本上有特別說n為奇數，但是n為奇數不是應該是Euler cycle的定義嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.172.102
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482908207.A.AB5.html
推 Transfat: 因為Ham-cycle會經過n個邊（就會經過每一點洽一次）
推 PTTleader: n是奇數 就把1放在中心點 偶數的話 中心就不用有點
意思是這個定理如果n不為奇數的話就……不符合了？
→ Transfat: 所以總共有n取2個邊，最多會有n取2再除n個不具共同邊
n個不取共同邊的(n-1)/2路徑
->總共n取2個ham-cycle嗎
→ Transfat: 的Ham-cycle
那如果n是奇數的話？
※ 編輯: newpuma (1.160.244.226), 12/28/2016 17:23:25
推 Transfat: 總共有(n-1)/2個Ham-cycle, 每個長度是n
推 PTTleader: 抱歉忽略我的話我發現要有中心那點才會每轉個角度邊才
→ PTTleader: 會都不同
推 Transfat: n是奇數偶數都符合,你會舉例怎麼畫出(n-1)/2個Ham-cycle
推 Transfat: 等等我想一下
推 Transfat: 我發現，因為如果n是奇數的畫，我們可以把一個點放在圓
→ Transfat: 中心，剩下n-1個點把圓2π分成2π/(n-1)等分, 因為n-1
→ Transfat: 是偶數，所以在走Ham-cycle的時候每一條Ham-cycle會剛好
→ Transfat: 經過圓心，所以我們從圓心出發，最後一個點還可以回到圓
→ Transfat: 心，不過如果n是偶數的話，我們把圓分成2π/n等分，也是
→ Transfat: 每條Ham-cycle會經過圓心，不過這時候就會”重疊“了
→ Transfat: 因為我們之前有一個點在圓心，回到圓心等於回到原點,可
→ Transfat: 是n為偶數的時候圓心沒有點等於是直接穿過去到對面的點
→ Transfat: 這樣會打到重複的點，所以n為偶數應該不行
→ Transfat: 我是畫n=8的一個圖出來再畫Ham-cycle試試，你也可以試試