作者sevfouyu11 (sevfouyu11)
看板Grad-ProbAsk
标题[理工] 离散 Hamilton cycle证明
时间Sun Aug 23 17:18:16 2020
https://i.imgur.com/pImgXOB.jpg
想请问定理6-10证明最後一行的与已知矛盾是和哪一项已知矛盾呢？
如果从原设“若G中无Hamilton cycle”证到最後一行“deg(a)+deg(b)<n”不是反而符合~q
→~p吗
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.82.52.162 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1598174298.A.E3E.html
※ 编辑: sevfouyu11 (111.82.52.162 台湾), 08/23/2020 17:23:08
1F：→ Ricestone: 跟"deg(x)+deg(y)>=n,for any 不相邻的x,y"矛盾08/23 17:29
2F：→ Ricestone: 这句话是前提08/23 17:29
意思是说“deg(x)+deg(y)>=n, for any x, y属於V, x, y不相邻”这个条件在它证明一开
始假设G中无Hamilton cycle时就要符合了是吗？
※ 编辑: sevfouyu11 (111.82.52.162 台湾), 08/23/2020 20:21:40
3F：→ Ricestone: 是08/23 20:44
4F：→ Ricestone: 我们想从前提P推出结论Q，於是先假设~Q，证出一个跟P不08/23 20:45
5F：→ Ricestone: 相容的R，所以~Q是错的 这边要注意的是这个R不一定是08/23 20:46
6F：→ Ricestone: ~P，实际上这题"deg(a)+deg(b)<n"就不是~P了 08/23 20:47
那这样我了解了，感谢你
另外想再请问一下这题~P的完整叙述是“存在相邻的x, y属於V, deg(x)+deg(y)<n”吗？
※ 编辑: sevfouyu11 (111.82.52.162 台湾), 08/23/2020 22:18:12
7F：→ Ricestone: "存在不相邻的x,y属於V" 08/24 03:26
好 感谢
※ 编辑: sevfouyu11 (223.138.233.175 台湾), 08/24/2020 14:49:04