推 gn00618777:嗯 我完全懂那兩個公式了 3q 10/26 23:55
※ 引述《gn00618777 (123)》之銘言：
: 通常我們來檢驗是否為平面圖用 e<=3v-6
: 但是有時候符合了 e<=3v-6 也不一定是平面圖
: k
: 所以必須要另一個檢驗 e<=(----)(v-2)
: k-2
: k
: 所以代表e<=(----)(v-2)是最高級的嗎？只要是任何圖都可以用這來判別？
: k-2
: 還是說他只能拿來判別Petersen?
: 另外，一直聽老師說Petersen Petersen.... 叫做Petersen的圖是不是只有
: 那個五邊型裡面是一個小星星，還是Petersen是一個類別，不只一個圖且
: 包含很多類似這種的圖？
檢驗graph是否為planar實在沒什麼好方法, 只有一些單向的定理
e<=3v-6 只是 e<=(v-2)*k/(k-2) 在 k=3 時的特例
在G=(V,E)中若每個cycle都至少有k個edge,
若G為planar, 則可以保證 e<=(v-2)*k/(k-2),
亦即當 e>(v-2)*k/(k-2) 時可保證G不為planar
但 e<=(v-2)*k/(k-2) 並不能保證G是planar
Petersen graph 在 k=5, v=10, e=15 時, 式子不成立, 所以不為planar
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.207.117
※ 編輯: bennylu 來自: 140.113.207.117 (10/26 01:19)