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

[jerry900287 ()]

我的想法是

平面圖有個定理 :
                                           _
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
推 b10007034: 8我有畫出來，很噁就是了
→ b10007034: 更正，還不算畫出…
推 JKLee: https://goo.gl/EQ9Fre
推 JKLee: https://goo.gl/SRFZav
推 JKLee: 不曉得是否有好方法可找到所有的self-complementary graph
推 b10007034: 所以可以說在G'的情況下是畫不出平面圖的
→ b10007034: 我這樣說對嗎？所以解答只能用點映射點的方式證明同構
→ JKLee: 他把G'畫成這樣,應是為了方便我們看出是complementary gra
→ JKLee: ph
→ JKLee: G與G'同構,G'當然可以畫成G(planar graph)的樣子
→ b10007034: 我換個說法好了，頂點位置不變，畫得出平面圖嗎？
→ JKLee: 同一個graph要怎麼畫都可以，只要不影響點與邊的關係
→ JKLee: 點與邊或點與點的關係為graph G(V,E)的E集合
→ JKLee: 若存在一種畫法，使G被畫在平面上時，沒有重疊發生，則G為
→ JKLee: 平面圖。
→ JKLee: 上面提到的畫法，當然不會改變G(V,E)
→ JKLee: G'頂點位置不變畫不出平面圖不等於G'不是平面圖
→ JKLee: G'是平面圖也不等於頂點位置隨便點都可畫出平面圖