[理工] 100台科離散

看板Grad-ProbAsk作者 (J)時間14年前 (2012/01/15 23:47), 編輯推噓9(9推 0噓 19→)
留言28則, 6人參與, 最新討論串1/1
證明有8個頂點及13個邊的平面圖不能2種顏色就畫完. (Hint:從這個圖一定有個三角形開始證起) 這題我只想到直接把圖畫出來然後再頂點上分別標示1,2,3 代表至少要3種顏色才可以畫完,不知道這樣畫圖證明可不可以@@? 另外想問 平面圖形成cycle至少要4個邊 這個要如何證明呢? -- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.34.232.57
推
01/16 00:00, , 1F
我會想用雙分圖為 2color反證欸 不知可行否
01/16 00:00, 1F
推
01/16 00:03, , 2F
你要先用由拉證e<=2v-4再用他去證 此圖必含三角形
01/16 00:03, 2F
→
01/16 00:04, , 3F
含三角形就不可能2 colorable
01/16 00:04, 3F
推
01/16 00:06, , 4F
平面圖 幾乎都是尤拉大絕
01/16 00:06, 4F
→
01/16 00:15, , 5F
有三角形能證出e<=2v-4嗎? (混亂中...
01/16 00:15, 5F
推
01/16 00:16, , 6F
不是那樣 你先用矛盾假設他沒三角形
01/16 00:16, 6F
→
01/16 00:16, , 7F
沒三角形 就可以代e<=2v-4 2v-4=12 他13個邊 就矛盾了
01/16 00:16, 7F
→
01/16 00:17, , 8F
不過那題10分 直接用2v-4寫太少了 最好事先證e<=2v-4
01/16 00:17, 8F
→
01/16 00:23, , 9F
!!!沒有三角形證出的e<=2v-4沒想到這麼好用 謝謝>"<
01/16 00:23, 9F
推
01/16 01:02, , 10F
pikachu大超威XD 如果也是考生的話 榜單是從前面找起了!!
01/16 01:02, 10F
推
01/16 15:30, , 11F
補充一下pikachu~是r<=2v-4唷 3r<=2e<=3v-6 能夠這麼靈活
01/16 15:30, 11F
→
01/16 15:30, , 12F
運用真的很厲害!!!
01/16 15:30, 12F
推
01/16 22:14, , 13F
樓上 e <= 2v-4沒錯 還有 你右邊的公式
01/16 22:14, 13F
→
01/16 22:14, , 14F
應該是 3/2r <= e <= 3v-6
01/16 22:14, 14F
→
01/16 22:15, , 15F
你那樣寫 會變成 3r <= 3v-6 這樣整個式子就不對了
01/16 22:15, 15F
→
01/16 22:16, , 16F
補充: e為邊數 r為region數 v為點數
01/16 22:16, 16F
推
01/17 00:06, , 17F
樓上說的對 我想說2e比較好表示 結果手殘= =....
01/17 00:06, 17F
→
01/17 00:07, , 18F
不過我不是用這個想法解的@@ 我是假設S為繞行所有區域邊的
01/17 00:07, 18F
→
01/17 00:08, , 19F
總和 S=2e 假設平面圖沒有三角形 所以S>=4r
01/17 00:08, 19F
→
01/17 00:10, , 20F
可以推得2e>=4r 得到13>=14 矛盾 所以圖形必有三角型@@"
01/17 00:10, 20F
→
01/17 00:12, , 21F
另外可以教我一下e<=2v-4是怎麼得來的嗎? 苦惱~"~ 謝謝~
01/17 00:12, 21F
推
01/17 01:33, , 22F
令N=2e為所有Region degree和 又G沒三角形
01/17 01:33, 22F
→
01/17 01:34, , 23F
則每個Region的degree必大於等於4 =>2e>=4r
01/17 01:34, 23F
→
01/17 01:35, , 24F
=> r<=1/2e 然後將這個代尤拉公式 v-e+r=2
01/17 01:35, 24F
→
01/17 01:36, , 25F
2+e-v=r<=1/2e ==>1/2e<=v-2 ==>e<=2v-4
01/17 01:36, 25F
→
01/17 01:37, , 26F
尤拉公式只有 在連通平面圖可以用 但e<=2v-4不連通
01/17 01:37, 26F
→
01/17 01:38, , 27F
也可以用
01/17 01:38, 27F
→
09/11 14:46, , 28F
有三角形能證出e<=2 https://daxiv.com
09/11 14:46, 28F
‣ 更多 Demonic221 的文章
文章代碼(AID): #1F4lKPKX (Grad-ProbAsk)