[理工] 離散 圖論

看板Grad-ProbAsk作者 (還很新)時間9年前 (2016/12/28 14:56), 9年前編輯推噓7(7推 0噓 12→)
留言19則, 2人參與, 最新討論串8/16 (看更多)
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
推
12/28 15:37, , 1F
因為Ham-cycle會經過n個邊（就會經過每一點洽一次）
12/28 15:37, 1F
推
12/28 15:37, , 2F
n是奇數 就把1放在中心點 偶數的話 中心就不用有點
12/28 15:37, 2F
意思是這個定理如果n不為奇數的話就……不符合了？
→
12/28 15:37, , 3F
所以總共有n取2個邊，最多會有n取2再除n個不具共同邊
12/28 15:37, 3F
n個不取共同邊的(n-1)/2路徑 ->總共n取2個ham-cycle嗎
→
12/28 15:38, , 4F
的Ham-cycle
12/28 15:38, 4F
那如果n是奇數的話？ ※ 編輯: newpuma (1.160.244.226), 12/28/2016 17:23:25
推
12/28 17:42, , 5F
總共有(n-1)/2個Ham-cycle, 每個長度是n
12/28 17:42, 5F
推
12/28 17:43, , 6F
抱歉忽略我的話我發現要有中心那點才會每轉個角度邊才
12/28 17:43, 6F
→
12/28 17:43, , 7F
會都不同
12/28 17:43, 7F
推
12/28 17:45, , 8F
n是奇數偶數都符合,你會舉例怎麼畫出(n-1)/2個Ham-cycle
12/28 17:45, 8F
推
12/28 17:46, , 9F
等等我想一下
12/28 17:46, 9F
推
12/28 17:57, , 10F
我發現，因為如果n是奇數的畫，我們可以把一個點放在圓
12/28 17:57, 10F
→
12/28 17:58, , 11F
中心，剩下n-1個點把圓2π分成2π/(n-1)等分, 因為n-1
12/28 17:58, 11F
→
12/28 17:59, , 12F
是偶數，所以在走Ham-cycle的時候每一條Ham-cycle會剛好
12/28 17:59, 12F
→
12/28 18:00, , 13F
經過圓心，所以我們從圓心出發，最後一個點還可以回到圓
12/28 18:00, 13F
→
12/28 18:00, , 14F
心，不過如果n是偶數的話，我們把圓分成2π/n等分，也是
12/28 18:00, 14F
→
12/28 18:00, , 15F
每條Ham-cycle會經過圓心，不過這時候就會”重疊“了
12/28 18:00, 15F
→
12/28 18:01, , 16F
因為我們之前有一個點在圓心，回到圓心等於回到原點,可
12/28 18:01, 16F
→
12/28 18:01, , 17F
是n為偶數的時候圓心沒有點等於是直接穿過去到對面的點
12/28 18:01, 17F
→
12/28 18:01, , 18F
這樣會打到重複的點，所以n為偶數應該不行
12/28 18:01, 18F
→
12/28 18:02, , 19F
我是畫n=8的一個圖出來再畫Ham-cycle試試，你也可以試試
12/28 18:02, 19F
‣ 更多 newpuma 的文章
文章代碼(AID): #1OOs8lgr (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 8 之 16 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共16篇)
‣ 更多 newpuma 的文章
文章代碼(AID): #1OOs8lgr (Grad-ProbAsk)