[理工] [離散]關於cycle的定義

看板Grad-ProbAsk作者 (Just do it)時間14年前 (2011/07/23 20:38), 編輯推噓0(0推 0噓 5→)
留言5則, 2人參與, 最新討論串1/1
在小黃離散的書裡面寫到 cycle必須要包涵至少三個邊 那麼若是p=v1,v2,v1的狀況 這個path就不算一個cycle? 但是在證明 e為bridge <=> e 不在任何cycle中的證明裡 (<=):若e為{x,y}不為bridge 則x有path p 到 y在G-e 所以p加上e形成G之一cycle －><－ 這也只包涵兩個邊為何算是cycle? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.218.249.7
→
07/24 17:29, , 1F
1.不是CYCLE 因為只含兩個邊(v1,v2)(v2,v1)
07/24 17:29, 1F
→
07/24 17:30, , 2F
2.作矛盾正法時 你假設的那CYCLE是已經符合定義的CYCLE
07/24 17:30, 2F
→
07/24 17:32, , 3F
也就是含3邊以上的CYCLE
07/24 17:32, 3F
→
07/24 21:00, , 4F
喔! 感謝 我懂了 之前看他圖一直想成multigraph的狀
07/24 21:00, 4F
→
07/24 21:01, , 5F
況想說找到反例不是推翻證明了 忘記都不討論multi的.
07/24 21:01, 5F
‣ 更多 hunter199129 的文章
文章代碼(AID): #1EAi2x3C (Grad-ProbAsk)