[圖論] 平面圖的證明

看板Math作者 (男)時間11年前 (2012/10/10 18:25), 編輯推噓7(7推 0噓 21→)
留言28則, 3人參與, 最新討論串1/1
Let G be a planar graph show that G contains at least n/2 vertices of degree at most 11. 問題在於 我可以證明出G裡面至少有一半以上的點的degree是小於等於12 但是卻不知道怎麼證明小於等於11 麻煩能不能有人給我個hint? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.79.107
推
10/10 20:13, , 1F
可假設G是三角化過後的圖
10/10 20:13, 1F
→
10/10 20:14, , 2F
由 V-E+F=2 和 degree sum = 2E 可導出矛盾
10/10 20:14, 2F
→
10/10 20:35, , 3F
可是我用上面那兩個只能證出小於等於12耶
10/10 20:35, 3F
推
10/10 20:39, , 4F
可以證出 "不可能有一半以上大於等於12" 喔
10/10 20:39, 4F
→
10/10 20:39, , 5F
假設 "有一半以上大於等於12" 會導致矛盾
10/10 20:39, 5F
推
10/10 20:41, , 6F
你有看到 假設G是三角化過後的圖 嗎
10/10 20:41, 6F
推
10/10 20:49, , 7F
喔喔 sorry 是我弄錯了
10/10 20:49, 7F
推
10/10 20:58, , 8F
咦 你的題目就竟是 <= 11 還是 <11呢?
10/10 20:58, 8F
→
10/10 21:00, , 9F
at most 11 不就是 小於等於11 嗎?
10/10 21:00, 9F
推
10/10 21:03, , 10F
所以用上面的方法可以證到 <= 11 阿
10/10 21:03, 10F
→
10/10 21:03, , 11F
題目後面的 <11 是筆誤吧?
10/10 21:03, 11F
※ 編輯: simonjoker 來自: 140.114.79.107 (10/10 21:19)
→
10/10 21:19, , 12F
修改了一下
10/10 21:19, 12F
→
10/10 21:20, , 13F
題目是 at most 11 沒錯
10/10 21:20, 13F
推
10/10 21:21, , 14F
所以你做得出at most 11嗎? 其實我也不知道可不可
10/10 21:21, 14F
→
10/10 21:21, , 15F
改進到10
10/10 21:21, 15F
→
10/10 21:22, , 16F
不過11的確用上面的工具就做得出來
10/10 21:22, 16F
→
10/10 21:23, , 17F
我的問題在於做的出at most 12
10/10 21:23, 17F
→
10/10 21:24, , 18F
假設G是三角化的 那 3F=2E → V-E/3=2 (Euler)
10/10 21:24, 18F
→
10/10 21:24, , 19F
可是at most 11 用上面那兩個做不出來
10/10 21:24, 19F
→
10/10 21:24, , 20F
但degree sum 會導出 3V <= E
10/10 21:24, 20F
→
10/10 21:25, , 21F
e <= 3v-6 這個我有用到
10/10 21:25, 21F
→
10/10 21:25, , 22F
得到 V-E/3 <= 0 的矛盾結果
10/10 21:25, 22F
→
10/10 21:27, , 23F
假設有一半以上degree>=12 則 2E=deg sum>= 6V
10/10 21:27, 23F
→
10/10 21:27, , 24F
就會有 3V<=E 的結果
10/10 21:27, 24F
→
10/10 21:28, , 25F
(對不起我要出門了 如果看不懂只能請其他人幫忙了~)
10/10 21:28, 25F
→
10/10 21:29, , 26F
OK 我再想一想 非常謝謝你喔
10/10 21:29, 26F
→
08/13 17:08, , 27F
喔喔 sorry 是我 https://noxiv.com
08/13 17:08, 27F
→
09/17 15:03, , 28F
就會有 3V<=E 的 https://daxiv.com
09/17 15:03, 28F
‣ 更多 simonjoker 的文章
文章代碼(AID): #1GTKqFyl (Math)