Re: [理工] 離散圖論漢米爾頓環路

看板Grad-ProbAsk作者befdawn (蜜蜂P助)時間7年前 (2018/10/13 13:14)推噓2(2推 0噓 2→)

留言4則, 2人參與討論串2/2 (看更多)

※ 引述《Russ0116 (Russ0116)》之銘言 : https://i.imgur.com/iv5yIYF.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來使用(一般矛盾證法會用到來協助證明)，所以這題他說是反證，而不是矛盾證法。應該是這個意思，如果上述有錯還麻煩大神告知。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.78.245 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539407668.A.D21.html

推

b10007034

10/14 11:52, 7年前 , 1^F

10/14 11:52, 1^F

→

b10007034

10/14 11:53, 7年前 , 2^F

10/14 11:53, 2^F

→

b10007034

10/14 11:53, 7年前 , 3^F

10/14 11:53, 3^F