作者jasonliao89 (宅宅)
看板Grad-ProbAsk
標題[理工] 離散 Hamiltonian Cycle 證明
時間Sun Aug 29 23:05:38 2021
https://i.imgur.com/3CGuxlf.jpg
https://i.imgur.com/T1ZMXNb.jpg
是我的證法，課本是用Gray code證的，我看起來跟我寫的思路差不多。我自己覺得我的
寫法是對的但有些不嚴謹。
我的思路是固定Q^k的HC順序，然後按照HC順序在兩邊走，以k=3為例
https://i.imgur.com/vSLC4he.jpg
想問一下我的這個證法是對的嗎，如果錯的話是錯在哪呢，那如果是對的請問考試可以這
樣寫嗎，謝謝。
然後我想順便問一下這題
https://i.imgur.com/huAeNSv.jpg
我的理解是安排13個工作且一個人不能連續工作兩天，然後總共不能做超過7個。解答我
看的懂，但我覺得不用這麼複雜
假設有A,B兩個工人，那麼工作安排就是
ABABABABABABAB，故得證可以
這樣不是就好了嗎，請問我這樣想正確嗎，謝謝。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.44.145 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1630249540.A.802.html
※ 編輯: jasonliao89 (180.217.44.145 臺灣), 08/30/2021 01:05:44
→ BusterButter: 第二題直覺上反而會想用鴿籠原理，把連續的兩個分為 08/30 04:22
→ BusterButter: 一組（剩下的一個自己為一組） 所以13個人有7組，所 08/30 04:22
→ BusterButter: 以一個人最少要選8個才會保證選到2個同組的 08/30 04:22
→ BusterButter: 反過來說就是如果不保證選到同組的，那每個人都必須 08/30 04:25
→ BusterButter: 選少於8個 08/30 04:25
→ BusterButter: 我覺得你的證明不夠general，證明不能用舉例子除非 08/30 04:27
→ BusterButter: 你把所有可能性都列出來 08/30 04:27
→ BusterButter: 我後來想一下我覺得我的證明有錯XD，這樣證好像只證 08/30 04:41
→ BusterButter: 了必要，沒有證明到充要 08/30 04:41