Re: [圖論] 三角形, 補圖, NPC
※ 引述《wsx02 ()》之銘言：
: 1&2. http://ppt.cc/xPZh
: 請問有人知道這兩題該怎麼證嗎?
1.
設六點為a,b,c,d,e,f, 則ab,ac,ad,ae,af中必有三邊同色,可設ab,ac,ad為藍色.
若bc,bd,cd中有一邊為藍色, 則有藍色的三角形.
若bc,bd,cd均為紅色, 則有紅色的三角形.
故必有單色三角形, 可設abc為藍色三角形.
若d連出3個藍邊, 則有非abc的藍三角形或紅三角形.
若d連出3個紅邊, 且da,db,dc並非均為紅邊, 則有含d的紅三角形或非abc的藍三角形.
故可設a,b,c與d,e,f之間均以紅邊相連, 則有非abc的藍三角形或紅三角形.
2.
找邊數較多的那一個圖, 則 e ≧ C(n,2)/2 = n(n-1)/4.
當 n≧11 時, 若此圖為平面圖, 則 2e≧3f.
由Euler公式,
2 ≦ n-e+f ≦ n-e/3 ≦ n-n(n-1)/12 = n(13-n)/12 < 2, 矛盾.
故此圖不為平面圖.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.204.109
推
10/20 21:29, , 1F
10/20 21:29, 1F
→
10/20 21:30, , 2F
10/20 21:30, 2F
→
10/20 21:30, , 3F
10/20 21:30, 3F
→
10/20 21:31, , 4F
10/20 21:31, 4F
→
10/20 21:50, , 5F
10/20 21:50, 5F
※ 編輯: XII 來自: 118.166.204.109 (10/20 22:34)
推
10/21 00:26, , 6F
10/21 00:26, 6F
→
10/21 00:26, , 7F
10/21 00:26, 7F
→
10/21 00:26, , 8F
10/21 00:26, 8F
→
10/21 00:26, , 9F
10/21 00:26, 9F
推
10/21 00:46, , 10F
10/21 00:46, 10F
→
10/21 00:46, , 11F
10/21 00:46, 11F
→
10/21 01:29, , 12F
10/21 01:29, 12F
→
08/13 17:10, , 13F
08/13 17:10, 13F
→
09/17 15:05, , 14F
09/17 15:05, 14F