作者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/cn.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