[理工] 離散 Hamiltonian Cycle 證明/應用

作者: jasonliao89 (宅宅)   2021-08-29 23:05:38
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,故得證可以
這樣不是就好了嗎,請問我這樣想正確嗎,謝謝。
作者: BusterButter (奶油巴斯特)   2021-08-30 04:22:00
第二題直覺上反而會想用鴿籠原理,把連續的兩個分為一組(剩下的一個自己為一組) 所以13個人有7組,所以一個人最少要選8個才會保證選到2個同組的反過來說就是如果不保證選到同組的,那每個人都必須選少於8個我覺得你的證明不夠general,證明不能用舉例子除非你把所有可能性都列出來我後來想一下我覺得我的證明有錯XD,這樣證好像只證了必要,沒有證明到充要

Links booklink

Contact Us: admin [ a t ] ucptt.com