老師在6.4的筆記中有給一題95彰師的題目
G=(V,E),V=n=>3
若E=e=>C(n-1,2)+2，證G具HC
老師給的證法是任取2個不相鄰的點x,y來證
不過當n=3的時候，好像會有問題
因為e也會等於3，那好像找不到不相鄰的兩點
我稍微檢查了一下好像要4之後才找的到不相鄰的兩點
請問是不是證明的時候要考慮到三呢
比如，改成這樣:
n=3時，顯然成立
考慮n=>4時，再套老師的證法
Research Space for Linear Algebra & Discrete Mathematics
7 則留言:
有道理~
n=3時並不適用老師的證明
如果相鄰就不符合老師的證明
會重覆多減到邊
但還是等其它人來確認一下好了
我也不敢確定怕哪邊想漏了
因為手上沒有老師的證明, 我猜測是用你們學過的一個定理:
G=(V,E), |V|=n >= 3, 若 當u,v不相鄰, 有 deg(u)+deg(v) >=n , 則 G 為 Hamiltonian.
(註: 這個叫 Ore's condition)
再來討論一個 logic 問題,
if P, then Q ( P => Q)
當 P 為 True, Q 為 True 的話, (P=>Q) 這件事為 True, 因此 P=>Q 可以想成 (~P)or(P and Q). 也就是說, 當 P 為 false 或是 P,Q 都是 true 的話, P=>Q 為 true.
回到你的提問, 使用的定理說, 若對所有 u,v 不相鄰, u,v 滿足 ore's condition的話, 則 G 為 Hamiltonian. 所以套用剛剛的 logic 討論, u,v 相鄰的時候, 我們不用驗證 ore's condition.
凱大的意思是說這個ore condition就跟若p則q是一樣，只有當p為True的時候才需要驗證q是否為true
所以當一個圖找不到所謂的兩個不相鄰的點，根本不需驗證他是否滿足這個條件，因為他一定是true
不知道有沒有誤會您的意思呢
就是驗證 degree sum 是否至少 n 只需對不相鄰的pair, 試想, 如果一個圖找不到不相鄰的 pair, 即此圖任兩點都相鄰, 那會是一個什麼樣的圖呢？這個圖又是不是 Hamiltonian 呢？留給你思考..
發表一下我的拙見!!
這題用到的定理是...
G=(V,E),|V|=n
若G中任二不相鄰之點x,y使得deg(x)+deg(y)≧n
=>G具H.C(Hamilton Cycle)
這個定理是一個若p則q的命題
因此在3個點的時候並不會有不相鄰之二點
所以在3個點的時候不二不相鄰之點的條件就錯了
那麼後面的結果就一定是對的
那麼3個點的時候自然就是成立的
發表一下，有錯請指正
張貼留言