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