作者jimmy1112111 (仔仔)
看板Grad-ProbAsk
标题[理工] 离散第六章图论
时间Mon Nov 4 02:12:38 2019
https://i.imgur.com/GqtRv1p.jpg
想问一下a题(<-)的证明，我并不是用矛盾，而是以下
https://i.imgur.com/EXVi9Jt.jpg
因为证明有点弱无法看出自己正确与否，感谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.177.3.53 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1572804760.A.04D.html
※ 编辑: jimmy1112111 (180.177.3.53 台湾), 11/04/2019 02:17:16
2F：推 b10007034: 我看到n会想induction on edge耶，另外楼上bridge的定 11/04 09:20
3F：→ b10007034: 定义是那样吗?我一开始也有想到像日字的图，但後来觉得 11/04 09:21
4F：→ b10007034: 无法把V(set)切成两半形成两坨除了v1,v2没有edge相连的 11/04 09:22
5F：→ b10007034: set 11/04 09:22
6F：→ b10007034: 另外想问原PO这个证明怎麽想到的阿，感觉很有新意 11/04 09:23
7F：推 mi981027: 我的意思是根据原po算法(写法是有n个cycle就取走n个边) 11/04 11:49
8F：→ mi981027: 那这样遇到日字，如果看成3个 就得取走3个边 这样可能 11/04 11:49
9F：→ mi981027: 会造成图断开 那後续要怎麽讨论呢 11/04 11:49
10F：→ mi981027: 不是指这是bridge >< 11/04 11:49
11F：→ jimmy1112111: m大感谢，日字型的举例真很清楚 11/04 11:57
12F：→ jimmy1112111: 一开始是想说既然是bridge，根据定义，cut set就只 11/04 12:02
13F：→ jimmy1112111: 有它而已，再来就是凑条件 11/04 12:02
14F：推 b10007034: 喔喔感谢 11/04 13:36