To AI: (c)這邊在證的是(a),(b)一定其中一種情形會發生, 而不管是哪一種, 反正結論就是G中具有一個cycle, 找出cycle以後下面就那一段就在證明, 利用那個cycle我們就可以一步步的建構出Hamiltonian path
2. 和上題意思差不多, 如果 b 在 H 中具有 k 個neighbor, 其中這 k 個neighbor必定是取值於{v3,...,vn}, 則根據前面證出來的結果, 在{v2,...,v(n-1)}裡會有 k 個點不與 a 相鄰, 再把a與vn相鄰考慮進來, 可知 a 的degree最多為(n-2)-k+1 = n-1-k, 所以 a 和 b 在 H 中的degree和最多為(n-1-k)+k = n-1
我想是因為他是說v1 "或" vm
回覆刪除只與v2至vm-1相連
很顯然 她是假設v1
而你證v1其實連vm也證了
但我搞不懂為何證c部分就可以把all case包進去了> <
我只看到她說這樣就不連通orz
至於下一題我們已知道
{b,vi}{a,vi-1}不可能同時為H的邊
這樣就證出他們不會相連囉
而H是沒有HC的
於是deg(a)+deg(b)<n
這一段意思大概是這樣
這是我的推想 有錯誤或不夠完備再麻煩助教修正了
就算是v1 "或" vm、在證單邊時應該還是m-2阿，因為|S|=m-2、一個degree是(m-2)-k、另一個是k、還是不懂為什麼是m-1?
回覆刪除{b,vi}{a,vi-1}不可能同時為H的邊確實已經證出來了。但ab不相連是已知的假設、H沒有HC也是假設、這要如何推出deg(a)+deg(b)<n ？
望助教與大大解答~
1. 這個沒有差, 要寫deg(vm)≦(m-2)-k也可以, 只是不用寫到那麼緊也可以得證
回覆刪除To AI: (c)這邊在證的是(a),(b)一定其中一種情形會發生, 而不管是哪一種, 反正結論就是G中具有一個cycle, 找出cycle以後下面就那一段就在證明, 利用那個cycle我們就可以一步步的建構出Hamiltonian path
2. 和上題意思差不多, 如果 b 在 H 中具有 k 個neighbor, 其中這 k 個neighbor必定是取值於{v3,...,vn}, 則根據前面證出來的結果, 在{v2,...,v(n-1)}裡會有 k 個點不與 a 相鄰, 再把a與vn相鄰考慮進來, 可知 a 的degree最多為(n-2)-k+1 = n-1-k, 所以 a 和 b 在 H 中的degree和最多為(n-1-k)+k = n-1
原來是可以的、謝謝助教的解答。
回覆刪除