[理工] 離散證明題 triumphant10 PTT批踢踢實業坊

作者: triumphant10 (yu12510) 2018-12-18 20:59:21

各位好
想問一下大神有沒有這些證明的頭緒
https://imgur.com/a/d5wUNhM
https://imgur.com/a/uuizLKh
這裡的k(G)是指 : The size of the 「smallest」 vertex cut
謝謝

作者: cks116 2018-12-19 00:56:00

作者: DLHZ ( ) 2018-12-19 01:01:00

作者: cks116 2018-12-19 06:20:00

抱歉匆忙看錯題目這才對 https://i.imgur.com/iFN3s3M.jpg更正 https://i.imgur.com/x3JxrRf.jpg抱歉啊寫錯一直改

作者: ponponjerry (ponpon) 2018-12-19 08:28:00

G不是connect，不能帶e<=3v-6 而且應該是3/2v<=e<=3v-6

作者: anonimo (unknown) 2018-12-19 10:15:00

G應該是connect 不然題目不會給min vertex cut=5

作者: cks116 2018-12-19 14:30:00

因為是k(G)=5 所以一定是connect 且每點degree 至少為5

作者: ponponjerry (ponpon) 2018-12-19 16:46:00

抱歉～沒看清楚，直覺以為那代表components個數

作者: triumphant10 (yu12510) 2018-12-19 20:49:00

請問c大為什麼每個點的degree至少為5？

作者: anonimo (unknown) 2018-12-19 23:13:00

如果有一點deg<=4 那把他連出去的vertex都拿掉即形成一個cut 與題目條件矛盾所以一定>=5

作者: triumphant10 (yu12510) 2018-12-20 00:56:00

對齁，感謝anonimo !請問 G的補集中，為什麼deg(v)=6 ?喔~ 我知道了，是因為sum的deg(v) = 2e = 2*C12取22*12*11/2=132，132-60=72(補集)，72/12=6=deg(v)

作者: cks116 2018-12-20 08:01:00

可以這樣想總node為12則每點最多11邊 G有5邊那補圖就是6了

作者: triumphant10 (yu12510) 2018-12-20 11:39:00

c大這個方法更好! 謝謝!

繼續閱讀