[理工] Hamilton cycle證明
想請問定理6-10證明最後一行的與已知矛盾是和哪一項已知矛盾呢？
如果從原設“若G中無Hamilton cycle”證到最後一行“deg(a)+deg(b)<n”不是反而符合~q
→~p嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.52.162 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1598174298.A.E3E.html
※ 編輯: sevfouyu11 (111.82.52.162 臺灣), 08/23/2020 17:23:08
→
08/23 17:29,
5年前
, 1F
08/23 17:29, 1F
→
08/23 17:29,
5年前
, 2F
08/23 17:29, 2F
意思是說“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
→
08/23 20:44,
5年前
, 3F
08/23 20:44, 3F
→
08/23 20:45,
5年前
, 4F
08/23 20:45, 4F
→
08/23 20:46,
5年前
, 5F
08/23 20:46, 5F
→
08/23 20:47,
5年前
, 6F
08/23 20:47, 6F
那這樣我了解了，感謝你
另外想再請問一下這題~P的完整敘述是“存在相鄰的x, y屬於V, deg(x)+deg(y)<n”嗎？
※ 編輯: sevfouyu11 (111.82.52.162 臺灣), 08/23/2020 22:18:12
→
08/24 03:26,
5年前
, 7F
08/24 03:26, 7F
好 感謝
※ 編輯: sevfouyu11 (223.138.233.175 臺灣), 08/24/2020 14:49:04