[理工] 離散第六章圖論

[jimmy1112111 (仔仔)]

https://i.imgur.com/GqtRv1p.jpg

想問一下a題(<-)的證明，我並不是用矛盾，而是以下

https://i.imgur.com/EXVi9Jt.jpg

因為證明有點弱無法看出自己正確與否，感謝各位







--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.3.53 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1572804760.A.04D.html
※ 編輯: jimmy1112111 (180.177.3.53 臺灣), 11/04/2019 02:17:16
推 mi981027: https://i.imgur.com/WmN82Lo.jpg
推 b10007034: 我看到n會想induction on edge耶，另外樓上bridge的定
→ b10007034: 定義是那樣嗎?我一開始也有想到像日字的圖，但後來覺得
→ b10007034: 無法把V(set)切成兩半形成兩坨除了v1,v2沒有edge相連的
→ b10007034: set
→ b10007034: 另外想問原PO這個證明怎麼想到的阿，感覺很有新意
推 mi981027: 我的意思是根據原po算法(寫法是有n個cycle就取走n個邊)
→ mi981027:  那這樣遇到日字，如果看成3個 就得取走3個邊 這樣可能
→ mi981027: 會造成圖斷開 那後續要怎麼討論呢
→ mi981027: 不是指這是bridge ><
→ jimmy1112111: m大感謝，日字型的舉例真很清楚
→ jimmy1112111: 一開始是想說既然是bridge，根據定義，cut set就只
→ jimmy1112111: 有它而已，再來就是湊條件
推 b10007034: 喔喔感謝