作者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/m.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