[理工] 离散 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