※ 引述《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)