[理工] 離散圖論 zqAI3yGOAT PTT批踢踢實業坊

[理工] 離散圖論

作者: zqAI3yGOAT (小霸丸) 2018-12-24 22:29:34

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

作者: Leaving 2018-12-24 22:43:00

g2 是k6,3 所以不是第三題我在上一篇有回哦

作者: b05703 (blue) 2018-12-24 22:49:00

卡第四題啊啊啊啊哪位大大幫幫忙QAQ

作者: zqAI3yGOAT (小霸丸) 2018-12-24 23:06:00

喔喔看到了感謝L大

作者: Leaving 2018-12-24 23:52:00

第四題要用反證法搭配Ore's thm 和kappa min deg*kappa小於等於

作者: b05703 (blue) 2018-12-25 00:38:00

我知道G的vertex當中最小degree小於n/2但是這樣相加也無法大於n，不太知道怎麼用ore's theorem,還請L大提點

作者: Leaving 2018-12-25 00:50:00

沒有哦題目這樣說不保証deg會是什麼數字先假設length小於2*kappa再一直加邊讓length更長直到那個剛好會等於的臨界點(就是用上課時證明的那個概念再去湊各種條件去證它其實是以為是臨界的那個length是有等於2kappa的所以矛盾*其實以為是如何證大概就是臨界的那個狀態有Hamiltonian cycle且必有一點不在cycle上然後繼續推下去先點到這我先睡惹作業加油QQ再補充一下好了臨界點的length上的點數=length+1*path<= 2kappa <= 兩點deg相加講了那麼多還是附一下題目好了orz#1S6Eyixb這篇的第二張圖

作者: b05703 (blue) 2018-12-25 16:26:00

了解了，感謝!

繼續閱讀

[理工] NP-Complete NPC (更新題目)OforU [理工] AVL Tree Rotation次數maple205 [理工] 演算法 fractional knapsackMarcolod [理工] 計組virtual addresses和VPN的關聯?ArthurJack [理工] OS題庫2-33！Aa841018 [理工] [工數][矩陣重根]Kimtzuy [理工] 矩陣乘法次數TEPLUN [理工] 101交大資演 hash tableparalyzation [理工] 計組資料路徑imadog [理工] 離散數學的證明題triumphant10

[理工] 離散 圖論

[理工] 離散圖論