之前老師有上課有談過 可是後來又看不懂了 orz
想問的是 :
1.
做出漢米爾頓 critical 然後不能連接 deg(b)的前面一點 的原因是什麼呢?
是不是如果連了 就會做成一個漢米爾頓 cycle 然後可以不經過邊 {a,b}
矛盾原本的 漢米爾頓 critical
所以 "走過 { a b} 且具HC的圖其 degree<=n-1"
矛盾原本的deg(a)+deg>n 才有HC
所以> n必具HC
請問是矛盾這個地方吗?
而且原本是ab不相鄰
這樣造出來的HC不是必經ab
好像怪怪的?
不知哪個環節出錯
勞請大家指教囉 謝謝
3 則留言:
deg(a)+deg(b)>=n 是已知
假設G不具HC，導出deg(a)+deg(b)<=n-1矛盾
(假設一個True的東西是錯的，導出矛盾)
我覺得這題用反證法去想比較簡單。
這題證明中好像還有用到一小段的矛盾證，
去證明a不與b所相連的前一個點相連，所以容易搞混。
我在想你說的，
「所以"走過{a,b}且具HC的圖其 degree<=n-1"」，
應該是錯的，
應該是「不經過{a,b}且deg(a)+deg(b)<=n-1」，
要證到最後才矛盾。
我的淺見，有錯請指正，謝謝。
所以其實{a b}並沒有相鄰
這樣才符合不連deg(b)前面的點
因為連了就有HC了
所以找到不具HC的 hamiltonian critical
=>其兩點不相鄰DEGREE合小於n-1
就是我們矛盾的東西了
我大概知道我哪搞混了
謝謝 Jargo :)
我還擔心說寫的太亂你看不懂，
解答這題後，
我更知道我筆記在寫什麼。
張貼留言