[理工] Hamilton cycle的判斷問題 ok8752665 PTT批踢踢實業坊

[理工] Hamilton cycle的判斷問題

作者: ok8752665 (dd8752665) 2019-06-21 21:21:44

http://i.imgur.com/dTItiFa.jpg
老師上課的時候說
如果裡面有小cycle就不會有大cycle
所以不會有hamilton cycle
不過如果圖長這樣
http://i.imgur.com/sTLrlT3.jpg
裡面的456型成一個小cycle
不過依然可以走1234561為一個hamilton cycle不是嗎？
是我哪裡理解錯了？

作者: mistel (Mistel) 2019-06-23 17:55:00

從deg=2的點推應該會是比較穩妥的辦法，或者你把你的圖畫成跟他同構的另一個圖很明顯他就有HC 好像沒有回答到你的問題哈哈哈

作者: ok8752665 (dd8752665) 2019-06-23 19:44:00

好吧看來這個找小cycle的方法不能用

作者: DLHZ ( ) 2019-06-24 01:22:00

要的話我認為要加上連接另一個cycle的點不得為adjacent

作者: ok8752665 (dd8752665) 2019-06-24 09:04:00

什麼意思?

繼續閱讀

[理工] 離散_關於排列fmtshk 離散 3-2 排列 3-17houallan5478 [理工] 線代筆記例題疑問（么正對角化）mistel Re: [理工] 資料結構_p37第9題s29441910 Re: [理工] 離散_p3-18範例5Honor1984 [理工] 離散_p3-18範例5fmtshk Re: [理工] 線代 1-74Honor1984 [理工] 線代 1-74paruru48 Re: 離散題庫5-59題Honor1984 [理工] 向量空間的問題abcd012345