作者:
befdawn (橙花雨露)
2018-10-13 13:14:25※ 引述《Russ0116 (Russ0116)》之銘言
: https://i.imgur.com/iv5yIYF.jpg
: https://i.imgur.com/E2vuHQK.jpg
: 想請問一下 中間證明我都看得懂
: 但不太知道為什麼最後會矛盾
我把問題分成這樣:
p → q
p: (若) 任意不相鄰兩點 x y 滿足 deg 和 ≧ n
q: (則) 有 hamiltonian cycle
反證
~q → ~p
~q: (若) 不具 hamiltonian cycle
~p: (則) 任意不相鄰兩點 x y 滿足 deg 和 ＜ n (也就是 和 ≦ n-1)
矛盾
已知p，~q → ~p 或與既定事實違背
p: (已知) 任意不相鄰兩點 x y 滿足 deg 和 ≧ n
~q: (若) 不具 hamiltonian cycle
~p: (則) 任意不相鄰兩點 x y 滿足 deg 和 ＜ n (也就是 和 ≦ n-1)
所以證明從取 a b 在 G 為不相鄰兩點開始，證到 deg 和必 ≦ n-1，就得證。會說矛
盾是矛盾已知的 p，也就是得出 ~p，只是因為過程沒有用到已知的p來使用(一般矛盾
證法會用到來協助證明)，所以這題他說是反證，而不是矛盾證法。
應該是這個意思，如果上述有錯還麻煩大神告知。