[理工] 离散证明题 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大这个方法更好! 谢谢!

继续阅读