作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1571732571.A.626.html
※ 编辑: fmtshk (111.241.215.41 台湾), 10/22/2019 16:24:45
1F：推 ekids1234: true 10/22 19:32
2F：→ DLHZ: 他没说加是怎样加我觉得有点模糊 如果像你说的加一个点去连 10/23 02:10
3F：→ DLHZ: 图上任两点 那就是false 反例满明显的 10/23 02:11
5F：→ DLHZ: 嗯...当我没说 10/23 02:16
6F：→ DLHZ: 原本是平面图所以满足r=e-v+2 因为是连图上两点 所以r会多1 10/23 02:25
7F：→ DLHZ: 由原式可知 r+1=e+2-v-1+2 如果是同样的方法加入cycle也是一 10/23 02:25
8F：→ DLHZ: 样的方法 同样多一个r 若cycle有n个边则r+1=e+n-v-(n-1)+2 10/23 02:25