细分

更新时间:2022-01-14 13:24

若某两个图都能从同一个图经细分后得到,则称它们同胚,图的同胚是两个图之间的一种关系。

概念

定义一

设G是一个平面图,通过删除G的一条边(x,y),并且添加一个新结点a和两条边(x,a)与(a,y)(所获得的任何图也是平面图)。这样的操作称为初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2,称G1和G2是同胚的(homeomorphism)。

如图1、图2、图3所示的三个图G1、G2和G3都是同胚的。

定义二

设G=(V,E)是一个图,e=uv是图G的一条边,w不是G的顶点,则当增加二度点w且用uw和vw代替边e时,就称边e被细分.若图H是由G经过一系列边的细分而得到,则称H为图G的剖分图(或细分图).若两个图都是某一个图的剖分图,则这两个图称为同胚的(或二度顶点内同胚).简单图G收缩边wuv是将G的边uv去掉,并将顶点u和v合并成一个新顶点.图G可收缩成图H.是指G可经过一系列的边收缩而变成H.如果H是G的剖分图,则G一定是H通过收缩一系列2度点所得到的收缩图.

相关定理

Kuratowski定理 图G是可平面的,当且仅当 和 的任何细分图都不是G的子图

根据对细分图的描述,我们知道不仅 和 是不允许作为子图出现的,而且它们的任何边细分图也是不允许的子图,记住这一点很重要:违禁子图不应被归纳出来。如果它们的确出现了,G就是不可平面的。

例题

例1 证明Peterson图是不可平面的。

证明 我们首先尝试使用定理“如果G是n结点(n≥3)q边的可平面图,则q≤3n一6”。Peterson图有q=15条边和n=10个结点。代入定理中的不等式 和 的任何细分图都有度为4的结点,且Peterson图是3一正则图,所以我们只需要寻找 的细分图。图4(a)是有标记Peterson图,(b)是它的子图同时也是 的细分图,我们将这个子图重画为(c)以澄清它确实是 的子图。因此,根据定理,Peterson图的确是不可平面图。

例2 用Kuratowski定理说明图5所示图G不是平面图。

解 将从图G中找出一个同胚于 的子图。图G中结点a、b、f和e的度数均为4.删去G中边(a,b)与(f,e)得到图G的一个子图 ,且 中每个结点的度数均为3。再删去图 中边(g,h)得到图 ,图 当然是图G的子图,且图 中有两个2度结点g与f,而图 同胚于 ,因此图G不是平面图。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}