[理工] 離散數學 圖論證明

[AAQ8 ()]

https://i.imgur.com/0FYQsPV.jpg
https://i.imgur.com/5FHakou.jpg

不好意思我字有點醜

我想問的是這個定理的前提是說

"若G中任兩個不相鄰的點x,y，滿足x和y的degree總和大於等於n，則G具有HC"

不過黃子嘉上課證明時假設的a和b是相鄰的

這樣不是違反前提了嗎

不太懂為什麼可以這樣子





--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.70.197.208
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1526227682.A.20A.html
→ TMDTMD2487: 這個證明講述H中任兩個不相鄰的點degree合小於等於n-1
可是我不懂的是

最後是寫deg(a)+deg(b) <= n-1

a和b是相鄰的兩個點

怎麼會可以拿來證明不相鄰的兩個點degree和小於等於n-1

→ TMDTMD2487: 所以如果任兩個不相鄰的點degree合大於等於n代表他不
→ TMDTMD2487: 是上面所假設的H
→ TMDTMD2487: 不是H就不會是G  那他就是有HC的圖
※ 編輯: AAQ8 (219.70.197.208), 05/14/2018 15:34:22
推 TMDTMD2487: ab不相鄰啊
→ TMDTMD2487: e={a,b}不在H中
哦哦我有點頭緒了

https://i.imgur.com/NNkH7PD.jpg

可是為什麼一開始已經說e不在G和H中了

最後一段的證明還可以說在G和H中 deg(a)+deg(b)<=n-1
※ 編輯: AAQ8 (219.70.197.208), 05/15/2018 12:16:50
→ TMDTMD2487: 首先e=ab不在H中，再來有推論出Vi與b相連則a必定不與V
→ TMDTMD2487: i-1相連，因此可以由上圖算出兩個點的deg合的上限
→ TMDTMD2487: 這個證明用矛盾證法在一開始假設一個無HC的圖會存在
→ TMDTMD2487: 兩個不相鄰的點deg和大於等於n，而最後與結果矛盾，因
→ TMDTMD2487: 此得到一個小結 任一個無HC的圖其中任意不相鄰的兩點d
→ TMDTMD2487: eg和必定小於n，再用反證法得證任意不相鄰兩點deg和若
→ TMDTMD2487: 大於等於n則必定存在HC
→ TMDTMD2487: 我的講法可能很繞，但我覺得這樣講很好理解
我懂了

謝謝T大

非常感謝
※ 編輯: AAQ8 (219.70.197.208), 05/15/2018 19:26:38