[理工] [離散] Hamiltonian cycle條件

[goldflower (金色小黃花)]

各位高手好

想請問一下關於Hamiltonian cycle的判斷上

是不是只要degree為2的點畫完形成cycle

但此不為HC的話即無HC呢？

感覺好像很直觀 但是不知道有沒有錯XD

--
Sent from my Android

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.13.33.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1445233790.A.009.html
※ 編輯: goldflower (101.13.33.151), 10/19/2015 18:00:45
推 odanaga: degree都是2形成cycle 不就一個圈圈嗎
推 SpaceMine: degree>=2的點也有可能在HC上不是嗎？
推 amge1524: 必要的edge有形成小Cycle就不是HC了
→ amge1524:  http://i.imgur.com/dxQ7duV.jpg
→ amge1524: 寫的不是很嚴謹，但我想大概是這原因吧？！
→ goldflower: 感謝樓上~!  其實我覺得夠嚴謹了...吧?
推 irenelove: 你是對的
推 odanaga: 我懂惹 QQ 看不懂題目
推 iwtes: 如果degree為二的點形成小cycle 那就已經不是連通圖了吧?
→ iwtes: 不是連通圖 應該就不用討論HC了吧!?