Research Space for Linear Algebra & Discrete Mathematics
我自己是討論某些點上必須走的邊然後選一選這些邊 連成小cycle如果你順序是這樣而不是隨便畫一個小 cycle我想就是老師上課一直強調的意思了老師一直說這邊話不能聽一半XD
某些點上必需走的邊是說， 如果點deg(v)=2的話，v的兩邊都要走的意思嗎?如果點的degree都>=3的話，我是先選一個順眼的然後選兩個邊，再擴散開選邊，這樣的話會出問題嗎?
我都是挑deg(v)=2的去刪3的話我覺得還要再討論才行也就是要再討論剩下兩組不過還是要看你圖長怎樣啦@.@
http://imageshack.us/photo/my-images/39/123456gj.jpg/其實就是這張圖因為我第一次找找不到hamiltonian cycle看答案才知道原來有
這種判斷法則是必要條件的概念, 如果具有Hamiltonian cycle, 則Hamiltonian cycle必定會包含那些邊, 當這些邊組合成一個小cycle, 這與它是Hamiltonain cycle產生矛盾, 所以我們討論degree = 2的點是因為Hamiltonain cycle必定會經過它相鄰的邊, 原因在此
雖然有點事後諸葛不過我想法是像這種對稱圖我會把起點設在中間覺得這樣比較好下手也比較不會怕畫了重複片段(例如 右到左 左到右一樣)
恩，我懂了謝謝老師跟A同學
張貼留言
7 則留言:
我自己是討論某些點上必須走的邊
然後選一選這些邊 連成小cycle
如果你順序是這樣
而不是隨便畫一個小 cycle
我想就是老師上課一直強調的意思了
老師一直說這邊話不能聽一半XD
某些點上必需走的邊是說，
如果點deg(v)=2的話，
v的兩邊都要走的意思嗎?
如果點的degree都>=3的話，
我是先選一個順眼的然後選兩個邊，
再擴散開選邊，這樣的話會出問題嗎?
我都是挑deg(v)=2的去刪
3的話我覺得還要再討論才行
也就是要再討論剩下兩組
不過還是要看你圖長怎樣啦@.@
http://imageshack.us/photo/my-images/39/123456gj.jpg/
其實就是這張圖
因為我第一次找找不到hamiltonian cycle
看答案才知道原來有
這種判斷法則是必要條件的概念, 如果具有Hamiltonian cycle, 則Hamiltonian cycle必定會包含那些邊, 當這些邊組合成一個小cycle, 這與它是Hamiltonain cycle產生矛盾, 所以我們討論degree = 2的點是因為Hamiltonain cycle必定會經過它相鄰的邊, 原因在此
雖然有點事後諸葛
不過我想法是
像這種對稱圖
我會把起點設在中間
覺得這樣比較好下手
也比較不會怕畫了重複片段
(例如 右到左 左到右一樣)
恩，我懂了
謝謝老師跟A同學
張貼留言