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

看板Grad-ProbAsk作者時間7年前 (2018/05/14 00:08), 7年前編輯推噓1(1推 0噓 13→)
留言14則, 1人參與, 7年前最新討論串1/1
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
→
05/14 01:32, 7年前 , 1F
這個證明講述H中任兩個不相鄰的點degree合小於等於n-1
05/14 01:32, 1F
可是我不懂的是 最後是寫deg(a)+deg(b) <= n-1 a和b是相鄰的兩個點 怎麼會可以拿來證明不相鄰的兩個點degree和小於等於n-1
→
05/14 01:33, 7年前 , 2F
所以如果任兩個不相鄰的點degree合大於等於n代表他不
05/14 01:33, 2F
→
05/14 01:33, 7年前 , 3F
是上面所假設的H
05/14 01:33, 3F
→
05/14 01:37, 7年前 , 4F
不是H就不會是G 那他就是有HC的圖
05/14 01:37, 4F
※ 編輯: AAQ8 (219.70.197.208), 05/14/2018 15:34:22
推
05/14 21:04, 7年前 , 5F
ab不相鄰啊
05/14 21:04, 5F
→
05/14 21:04, 7年前 , 6F
e={a,b}不在H中
05/14 21:04, 6F
哦哦我有點頭緒了 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
→
05/15 18:35, 7年前 , 7F
首先e=ab不在H中，再來有推論出Vi與b相連則a必定不與V
05/15 18:35, 7F
→
05/15 18:35, 7年前 , 8F
i-1相連，因此可以由上圖算出兩個點的deg合的上限
05/15 18:35, 8F
→
05/15 18:42, 7年前 , 9F
這個證明用矛盾證法在一開始假設一個無HC的圖會存在
05/15 18:42, 9F
→
05/15 18:42, 7年前 , 10F
兩個不相鄰的點deg和大於等於n，而最後與結果矛盾，因
05/15 18:42, 10F
→
05/15 18:42, 7年前 , 11F
此得到一個小結 任一個無HC的圖其中任意不相鄰的兩點d
05/15 18:42, 11F
→
05/15 18:42, 7年前 , 12F
eg和必定小於n，再用反證法得證任意不相鄰兩點deg和若
05/15 18:42, 12F
→
05/15 18:42, 7年前 , 13F
大於等於n則必定存在HC
05/15 18:42, 13F
→
05/15 18:42, 7年前 , 14F
我的講法可能很繞，但我覺得這樣講很好理解
05/15 18:42, 14F
我懂了 謝謝T大 非常感謝 ※ 編輯: AAQ8 (219.70.197.208), 05/15/2018 19:26:38
‣ 更多 AAQ8 的文章
文章代碼(AID): #1Q-6BY8A (Grad-ProbAsk)