作者fmtshk (fmtshk)
看板Grad-ProbAsk
標題[理工] 離散_平面圖一小題
時間Tue Oct 22 16:22:49 2019
https://i.imgur.com/qgr3ri0.png
這題是不是True呢？
還是我搞錯題目意思了？
加入loop應該是不影響
加入degree為2的點，是說G中加入個點,然後任意跟兩點相連對吧？
有人能提供個反例嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.215.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1571732571.A.626.html
※ 編輯: fmtshk (111.241.215.41 臺灣), 10/22/2019 16:24:45
推 ekids1234: true 10/22 19:32
→ DLHZ: 他沒說加是怎樣加我覺得有點模糊 如果像你說的加一個點去連 10/23 02:10
→ DLHZ: 圖上任兩點 那就是false 反例滿明顯的 10/23 02:11
→ DLHZ: 嗯...當我沒說 10/23 02:16
→ DLHZ: 原本是平面圖所以滿足r=e-v+2 因為是連圖上兩點 所以r會多1 10/23 02:25
→ DLHZ: 由原式可知 r+1=e+2-v-1+2 如果是同樣的方法加入cycle也是一 10/23 02:25
→ DLHZ: 樣的方法 同樣多一個r 若cycle有n個邊則r+1=e+n-v-(n-1)+2 10/23 02:25