[理工] 離散 圖論

看板Grad-ProbAsk作者 (洨霸丸)時間7年前 (2018/12/24 22:29), 7年前編輯推噓5(5推 0噓 20→)
留言25則, 3人參與, 7年前最新討論串11/16 (看更多)
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
→
12/24 22:43, 7年前 , 1F
g2 是k6,3 所以不是
12/24 22:43, 1F
→
12/24 22:43, 7年前 , 2F
第三題我在上一篇有回哦
12/24 22:43, 2F
推
12/24 22:49, 7年前 , 3F
卡第四題啊啊啊啊 哪位大大幫幫忙QAQ
12/24 22:49, 3F
→
12/24 23:06, 7年前 , 4F
喔喔看到了 感謝L大
12/24 23:06, 4F
推
12/24 23:52, 7年前 , 5F
第四題要用反證法 搭配Ore's thm 和kappa min deg
12/24 23:52, 5F
→
12/24 23:52, 7年前 , 6F
*kappa小於等於
12/24 23:52, 6F
推
12/25 00:38, 7年前 , 7F
我知道G的vertex當中最小degree小於n/2但是這樣相加也無法
12/25 00:38, 7F
→
12/25 00:38, 7年前 , 8F
大於n，不太知道怎麼用ore's theorem,還請L大提點
12/25 00:38, 8F
→
12/25 00:50, 7年前 , 9F
沒有哦 題目這樣說不保証deg會是什麼數字
12/25 00:50, 9F
→
12/25 00:50, 7年前 , 10F
先假設length小於2*kappa
12/25 00:50, 10F
→
12/25 00:51, 7年前 , 11F
再一直加邊讓length更長 直到那個剛好會等於的臨界點
12/25 00:51, 11F
→
12/25 00:52, 7年前 , 12F
(就是用上課時證明的那個概念
12/25 00:52, 12F
→
12/25 00:53, 7年前 , 13F
再去湊各種條件 去證它其實是以為是臨界的那個length是有
12/25 00:53, 13F
→
12/25 00:53, 7年前 , 14F
等於2kappa的 所以矛盾
12/25 00:53, 14F
→
12/25 00:54, 7年前 , 15F
*其實以為是
12/25 00:54, 15F
→
12/25 00:57, 7年前 , 16F
如何證大概就是臨界的那個狀態有Hamiltonian cycle且必有
12/25 00:57, 16F
→
12/25 00:57, 7年前 , 17F
一點不在cycle上 然後繼續推下去
12/25 00:57, 17F
推
12/25 00:59, 7年前 , 18F
先點到這 我先睡惹 作業加油QQ
12/25 00:59, 18F
→
12/25 01:04, 7年前 , 19F
再補充一下好了 臨界點的length上的點數=length+1
12/25 01:04, 19F
→
12/25 01:05, 7年前 , 20F
*path
12/25 01:05, 20F
→
12/25 01:06, 7年前 , 21F
<= 2kappa <= 兩點deg相加
12/25 01:06, 21F
→
12/25 01:10, 7年前 , 22F
講了那麼多還是附一下題目好了orz
12/25 01:10, 22F
→
12/25 01:10, 7年前 , 23F
12/25 01:10, 23F
→
12/25 01:11, 7年前 , 24F
這篇的第二張圖
12/25 01:11, 24F
推
12/25 16:26, 7年前 , 25F
了解了，感謝!
12/25 16:26, 25F
‣ 更多 zqAI3yGOAT 的文章
文章代碼(AID): #1S8ErHjD (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 16 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共16篇)
‣ 更多 zqAI3yGOAT 的文章
文章代碼(AID): #1S8ErHjD (Grad-ProbAsk)