Re: [理工] 台大電機丙 106 離散數學

看板Grad-ProbAsk作者時間8年前 (2017/09/05 13:22), 編輯推噓5(5推 0噓 13→)
留言18則, 2人參與, 最新討論串2/2 (看更多)
我的想法是 平面圖有個定理 : _ Simple Graph G , |V(G)| ≧ 11 時 則 G or G 不是 平面圖 _ 即 |V(G)| 可能為 1 ~ 10 (因為題目說 G 為平面圖 又 G 跟 G 同構) 又 |V(G)| 為 even , 故可能為 2 , 4 , 6 , 8 , 10 _ 又 |E(G)| + |E(G)| = C |V(G)| 取 2 ,再加上 互為同構 _ 所以 |E(G)| = |E(G)| = ( C |V(G)| 取 2 ) / 2 |V(G)| = 2 , 6 , 10 時 |E(G)| 皆不為整數 故 只剩 4 和 8 的情況 4情況 可以用畫的就是你算的那個圖 可是 8 我就不知道怎麼畫了... 感覺是用證明的 等待高手補充.... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.123.228 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1504588975.A.F38.html
推
09/05 13:56, , 1F
8我有畫出來，很噁就是了
09/05 13:56, 1F
→
09/05 14:04, , 2F
更正，還不算畫出…
09/05 14:04, 2F
推
09/06 01:00, , 3F
09/06 01:00, 3F
推
09/06 01:04, , 4F
09/06 01:04, 4F
推
09/06 01:08, , 5F
不曉得是否有好方法可找到所有的self-complementary graph
09/06 01:08, 5F
推
09/06 15:23, , 6F
所以可以說在G'的情況下是畫不出平面圖的
09/06 15:23, 6F
→
09/06 15:25, , 7F
我這樣說對嗎？所以解答只能用點映射點的方式證明同構
09/06 15:25, 7F
→
09/06 16:43, , 8F
他把G'畫成這樣,應是為了方便我們看出是complementary gra
09/06 16:43, 8F
→
09/06 16:43, , 9F
ph
09/06 16:43, 9F
→
09/06 16:46, , 10F
G與G'同構,G'當然可以畫成G(planar graph)的樣子
09/06 16:46, 10F
→
09/06 17:27, , 11F
我換個說法好了，頂點位置不變，畫得出平面圖嗎？
09/06 17:27, 11F
→
09/06 21:04, , 12F
同一個graph要怎麼畫都可以，只要不影響點與邊的關係
09/06 21:04, 12F
→
09/06 21:12, , 13F
點與邊或點與點的關係為graph G(V,E)的E集合
09/06 21:12, 13F
→
09/06 21:15, , 14F
若存在一種畫法，使G被畫在平面上時，沒有重疊發生，則G為
09/06 21:15, 14F
→
09/06 21:16, , 15F
平面圖。
09/06 21:16, 15F
→
09/06 21:18, , 16F
上面提到的畫法，當然不會改變G(V,E)
09/06 21:18, 16F
→
09/06 21:28, , 17F
G'頂點位置不變畫不出平面圖不等於G'不是平面圖
09/06 21:28, 17F
→
09/06 21:30, , 18F
G'是平面圖也不等於頂點位置隨便點都可畫出平面圖
09/06 21:30, 18F
‣ 更多 jerry900287 的文章
文章代碼(AID): #1PhZIlyu (Grad-ProbAsk)
‣ 更多 jerry900287 的文章
文章代碼(AID): #1PhZIlyu (Grad-ProbAsk)