[理工] 離散第六章圖論

看板Grad-ProbAsk作者 (仔仔)時間6年前 (2019/11/04 02:12), 6年前編輯推噓4(4推 0噓 10→)
留言14則, 3人參與, 6年前最新討論串1/1
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
推
11/04 02:49, 6年前 , 1F
11/04 02:49, 1F
推
11/04 09:20, 6年前 , 2F
我看到n會想induction on edge耶，另外樓上bridge的定
11/04 09:20, 2F
→
11/04 09:21, 6年前 , 3F
定義是那樣嗎?我一開始也有想到像日字的圖，但後來覺得
11/04 09:21, 3F
→
11/04 09:22, 6年前 , 4F
無法把V(set)切成兩半形成兩坨除了v1,v2沒有edge相連的
11/04 09:22, 4F
→
11/04 09:22, 6年前 , 5F
set
11/04 09:22, 5F
→
11/04 09:23, 6年前 , 6F
另外想問原PO這個證明怎麼想到的阿，感覺很有新意
11/04 09:23, 6F
推
11/04 11:49, 6年前 , 7F
我的意思是根據原po算法(寫法是有n個cycle就取走n個邊)
11/04 11:49, 7F
→
11/04 11:49, 6年前 , 8F
那這樣遇到日字，如果看成3個 就得取走3個邊 這樣可能
11/04 11:49, 8F
→
11/04 11:49, 6年前 , 9F
會造成圖斷開 那後續要怎麼討論呢
11/04 11:49, 9F
→
11/04 11:49, 6年前 , 10F
不是指這是bridge ><
11/04 11:49, 10F
→
11/04 11:57, 6年前 , 11F
m大感謝，日字型的舉例真很清楚
11/04 11:57, 11F
→
11/04 12:02, 6年前 , 12F
一開始是想說既然是bridge，根據定義，cut set就只
11/04 12:02, 12F
→
11/04 12:02, 6年前 , 13F
有它而已，再來就是湊條件
11/04 12:02, 13F
推
11/04 13:36, 6年前 , 14F
喔喔感謝
11/04 13:36, 14F
‣ 更多 jimmy1112111 的文章
文章代碼(AID): #1TlnYO1D (Grad-ProbAsk)