第3节图的平面性检测.pptVIP

第三节 图的平面性检测 定义1 图G的H片:设H是G的子图，在E(G)-E(H)上定义二元关系R如下：xRy?在G-E(H)中存在一条链W使得:（1）W的第一条边为x，最后一条边为y； （2）W中只有两个端点属于H(即W的内部点不属于H). R是E(G)-E(H)上的等价关系。R确定E(G)-E(H)上的一个划分设为S={ S1、S2、…Sm}由Si导出的 G-E(H)的子图 B1、B2、…Bm 称为G的H片。 图G的平面检测的DMP算法 DMP算法是由Demoucron,Malgrange,Pertuiset提供的. 在介绍该算法前,先对图G进行如下预处理: (1)若G不连通,分别检测每一个连通分支.当且仅当所 有的连通分支都是平面图,G就是平面图. (2)若G有割点,分别检测每一块.当且仅当每一块是平 面图.(3)删去G中的环.(4)用一条边代替G中2度点和与 之相关联的两条边.(5)删去平行边. 反复交错使用(4)与(5),直到不能使用为止.在做了 上述简化后,在简单图G中利用(6)和(7)两个基本判断 法:(6)若e9或v5,则G是平面图;(7)若e3v-6或?5,则 G不是平面图.若不满足(6)和(7),则需进一步检测. * 定义2.若H1和H2都是图G的子图，称V（H1）? V（H2）为H1和H2在G中的接触点集。记作VG(H1,H2). 定义3 设H是可平面图G的子图， 是H的平面表示，若存在G的平面表示 ,使 ? 称 是G容许的。 G G容许的子图G1 非G容许的子图G2 若B是G的H片，f是 的面而且VG（B,H）? ，称B在f内可画出，其中 是f的边界。 定理1设 是G容许的，则对 的每一个片B， 其中 证明:若 是G容许的,则存在G的一个平面表示 .显然,H的片B所对应的 的子图 必然限制在 的一个面中,因此 . DMP算法 （1）设G1是G中的圈，求出G1 的平面表示 。令i=1. （2）若E（G）-E（Gi）=?，则停止。若E（G）-E（Gi）? ?，则确定G的所有Gi片，对每个Gi片B，求出集 （3）若存在Gi片B使 则停止，此时知G是非平面图 。若存在Gi片B使 则令{f}= ;若不存在这样的片B，则令B是任何一个Gi片并任取 。 (4)选取一条xy路Pi? B使x,y?VG（B，Gi）,令Gi+1= Gi?P,并把Pi画在的 面 f内得Gi+1的一个平面表示 ，用i+1代替并转入第2步。 *