[理工] 離散_平面圖一小題

作者: fmtshk (fmtshk)   2019-10-22 16:22:49
https://i.imgur.com/qgr3ri0.png
這題是不是True呢?
還是我搞錯題目意思了?
加入loop應該是不影響
加入degree為2的點,是說G中加入個點,然後任意跟兩點相連對吧?
有人能提供個反例嗎?
作者: ekids1234 (∵:☆星痕╭☆)   2019-10-22 19:32:00
true
作者: DLHZ ( )   2019-10-23 02:10:00
他沒說加是怎樣加我覺得有點模糊 如果像你說的加一個點去連圖上任兩點 那就是false 反例滿明顯的
嗯...當我沒說原本是平面圖所以滿足r=e-v+2 因為是連圖上兩點 所以r會多1由原式可知 r+1=e+2-v-1+2 如果是同樣的方法加入cycle也是一樣的方法 同樣多一個r 若cycle有n個邊則r+1=e+n-v-(n-1)+2

Links booklink

Contact Us: admin [ a t ] ucptt.com