作者triumphant10 (yu12510 )
看板Grad-ProbAsk
標題[理工] 離散證明題
時間Tue Dec 18 20:59:21 2018
各位好
想問一下大神有沒有這些證明的頭緒
https://imgur.com/a/d5wUNhM
https://imgur.com/a/uuizLKh
這裡的k(G)是指 : The size of the 「smallest」 vertex cut
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.1.40
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545137964.A.EE5.html
2F：→ cks116: iJ.jpg12/19 00:56
5F：→ cks116: 抱歉 匆忙看錯題目12/19 06:20
8F：→ cks116: 抱歉啊 寫錯一直改12/19 06:25
9F：推 ponponjerry: G不是connect，不能帶e<=3v-6 而且應該是3/2v<=e<=12/19 08:28
10F：→ ponponjerry: 3v-612/19 08:28
11F：→ anonimo: G應該是connect 不然題目不會給min vertex cut=512/19 10:15
12F：→ cks116: 因為是k(G)=5 所以一定是connect 且每點degree 至少為512/19 14:30
13F：推 ponponjerry: 抱歉～沒看清楚，直覺以為那代表components個數12/19 16:46
14F：→ ponponjerry: 推c大，我寫出來也是那樣12/19
16:46
15F：→ triumphant10: 請問c大為什麼每個點的degree至少為5？12/19 20:49
※ 編輯: triumphant10 (1.164.1.40), 12/19/2018 20:49:59
16F：→ anonimo: 如果有一點deg<=4 那把他連出去的vertex都拿掉即形成一個 12/19 23:13
17F：→ anonimo: cut 與題目條件矛盾 所以一定>=5 12/19 23:13
18F：→ triumphant10: 對齁，感謝anonimo ! 12/20 00:56
19F：→ triumphant10: 請問 G的補集中，為什麼deg(v)=6 ? 12/20 01:02
20F：→ triumphant10: 喔~ 我知道了，是因為sum的deg(v) = 2e = 2*C12取2 12/20 01:10
21F：→ triumphant10: 2*12*11/2=132，132-60=72(補集)，72/12=6=deg(v) 12/20 01:13
22F：→ cks116: 可以這樣想 總node為12則每點最多11邊 G有5邊 那補圖就是6 12/20 08:01
23F：→ cks116: 了 12/20 08:01
24F：→ triumphant10: c大這個方法更好! 謝謝! 12/20 11:39