Research Space for Linear Algebra & Discrete Mathematics
有限制的@@!那兩個公式是去根據每個cycle至少幾個邊去做判斷的不是有一個公式是e<=(k/k-2)*(v-2) K就是每個cycle至少幾個邊而衍生出來的公式
恩 今天上課老師有講到，這個公式只能判斷不是平面圖，如果帶進去是對的並不代表他是平面圖，還是要重畫。所以我重畫的結果一定要讓他變成K5或K33的同胚嗎?
可以用子圖去看!!有個定理是這樣的 G is planar graph iff G不具子圖與K5或K33同胚!!這個定理的證明就老師有畫一個Peterson Graph 去證出他的子圖與K33同胚 所以他不是planar
嗯, 就像你們討論的, "e≦3v-6" 只是 planar graph 的必要條件, 是單向的, 因為我們都知道若 p 則 q 不代表若 q 則 p, 所以符合 e≦3v-6 並不能保證 G 為平面圖; 然而因為 "G 不含子圖與 K_5 或 K_3,3 同胚" 是平面圖的充要條件, 所以這個敘述的成立與否都可以用來判斷 G 是否為平面圖
懂了～
張貼留言
5 則留言:
有限制的@@!
那兩個公式是去根據每個cycle至少幾個邊去做判斷的不是有一個公式是
e<=(k/k-2)*(v-2) K就是每個cycle至少幾個邊而衍生出來的公式
恩 今天上課老師有講到，這個公式只能判斷不是平面圖，如果帶進去是對的並不代表他是平面圖，還是要重畫。所以我重畫的結果一定要讓他變成K5或K33的同胚嗎?
可以用子圖去看!!
有個定理是這樣的
G is planar graph iff G不具子圖與K5或K33同胚!!
這個定理的證明就老師有畫一個Peterson Graph 去證出他的子圖與K33同胚 所以他不是planar
嗯, 就像你們討論的, "e≦3v-6" 只是 planar graph 的必要條件, 是單向的, 因為我們都知道若 p 則 q 不代表若 q 則 p, 所以符合 e≦3v-6 並不能保證 G 為平面圖; 然而因為 "G 不含子圖與 K_5 或 K_3,3 同胚" 是平面圖的充要條件, 所以這個敘述的成立與否都可以用來判斷 G 是否為平面圖
懂了～
張貼留言