[理工] 離散 圖論

[zqAI3yGOAT (洨霸丸)]

https://imgur.com/a/eA9jUdf
1我把所有edges列出就看出degree不同
2則是以(1,2)用Ore’s thm去說明 (似乎不夠正式？？？)
然後希望有人可以提點我第三題orz謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.243.245
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545661777.A.B4D.html
※ 編輯: zqAI3yGOAT (140.112.243.245), 12/24/2018 22:33:01
→ Leaving: g2 是k6,3 所以不是
→ Leaving: 第三題我在上一篇有回哦
推 b05703: 卡第四題啊啊啊啊 哪位大大幫幫忙QAQ
→ zqAI3yGOAT: 喔喔看到了 感謝L大
推 Leaving: 第四題要用反證法 搭配Ore's thm 和kappa min deg
→ Leaving: *kappa小於等於
推 b05703: 我知道G的vertex當中最小degree小於n/2但是這樣相加也無法
→ b05703: 大於n，不太知道怎麼用ore's theorem,還請L大提點
→ Leaving: 沒有哦 題目這樣說不保証deg會是什麼數字
→ Leaving: 先假設length小於2*kappa
→ Leaving: 再一直加邊讓length更長 直到那個剛好會等於的臨界點
→ Leaving: (就是用上課時證明的那個概念
→ Leaving: 再去湊各種條件 去證它其實是以為是臨界的那個length是有
→ Leaving: 等於2kappa的 所以矛盾
→ Leaving: *其實以為是
→ Leaving: 如何證大概就是臨界的那個狀態有Hamiltonian cycle且必有
→ Leaving: 一點不在cycle上 然後繼續推下去
推 Leaving: 先點到這 我先睡惹 作業加油QQ
→ Leaving: 再補充一下好了 臨界點的length上的點數=length+1
→ Leaving: *path
→ Leaving: <= 2kappa <= 兩點deg相加
→ Leaving: 講了那麼多還是附一下題目好了orz
→ Leaving: #1S6Eyixb
→ Leaving: 這篇的第二張圖
推 b05703: 了解了，感謝!