《图的平面性检测》PPT课件.ppt

第三节第三节 图的平面性检测图的平面性检测定义定义1 1 图图G G的的H H片片: :设设H H是是G G的子图，在的子图，在E(G)-E(H)E(G)-E(H)上定上定义二元关系义二元关系R R如下：如下：xRyxRy在在G-E(H)G-E(H)中存在一条链中存在一条链W W使得使得: :（（1 1））W W的第一条边为的第一条边为x x，，最后一最后一条边为条边为y y；；（（2 2））W W中只有两个端点属于中只有两个端点属于H(H(即即W W的内部点不属于的内部点不属于H).H). R R是是E(G)-E(H)E(G)-E(H)上的等价关系上的等价关系R R确定确定E(G)-E(H)E(G)-E(H)上上的一个划分设为的一个划分设为S={ SS={ S1 1、、S S2 2、、……S Sm m} }由由S Si i导出的导出的 G-E(H)G-E(H)的子图的子图 B B1 1、、B B2 2、、……B Bm m 称为称为G G的的H H片定义定义2.2.若若H H1 1和和H H2 2都是图都是图G G的子图，称的子图，称V V（（H H1 1））  V V（（H H2 2）为）为H H1 1和和H H2 2在在G G中的接触点集。

记作中的接触点集记作V VG G(H(H1 1,H,H2 2).).定义定义3 3 设设H H是可平面图是可平面图G G的子图，的子图， 是是H H的平面表示，若存的平面表示，若存在在G G的平面表示的平面表示 , ,使使   称称 是是G G容许的GG容许的子图G1非G容许的子图G2若若B是是G的的H片，片，f是是 的面而且的面而且VG（（B,H））  ，称，称B在在f内可画出，其中内可画出，其中 是是f的边界定理定理1设设 是是G容许的，则对容许的，则对 的每一个片的每一个片B，， 其中其中 证明证明: :若若 是是G G容许的容许的, ,则存在则存在G G的一个平面表示的一个平面表示 . .显然显然,H,H的片的片B B所对应的所对应的 的子图的子图必然限制在 的一个面中,因此 . 图图G的平面检测的的平面检测的DMP算法算法DMP算法是由算法是由Demoucron,Malgrange,Pertuiset提供的提供的.在介绍该算法前在介绍该算法前,先对图先对图G进行如下预处理进行如下预处理:(1)若若G不连通不连通,分别检测每一个连通分支分别检测每一个连通分支.当且仅当所当且仅当所有的连通分支都是平面图有的连通分支都是平面图,G就是平面图就是平面图.(2)若若G有割点有割点,分别检测每一块分别检测每一块.当且仅当每一块是平当且仅当每一块是平面图面图.(3)删去删去G中的环中的环.(4)用一条边代替用一条边代替G中中2度点和度点和与与之相关联的两条边之相关联的两条边.(5)删去平行边删去平行边. 反复交错使用反复交错使用(4)与与(5),直到不能使用为止直到不能使用为止.在做在做了了上述简化后上述简化后,在简单图在简单图G中利用中利用(6)和和(7)两个基本判断两个基本判断法法:(6)若若e<9或或v<5,则则G是平面图是平面图;(7)若若e>3v-6或或 >5,则则G不是不是平面图平面图.若不满足若不满足(6)和和(7),则需进一步检测则需进一步检测.DMPDMP算法算法（（1 1）设）设G G1 1是是G G中的圈，求出中的圈，求出G G1 1 的平面表示的平面表示 。

令令i=1.i=1.（（2 2）若）若E E（（G G））-E-E（（G Gi i））= = ，，则停止若则停止若E E（（G G））-E-E（（G Gi i））   ，，则确定则确定G G的所有的所有G Gi i片片，对每个，对每个G Gi i片片B B，，求出集求出集 （（3 3）若存在）若存在G Gi i片片B B使使 则停止，此时知则停止，此时知G G是非平是非平面图面图 若存在G Gi i片片B B使使 则令则令{f}= ;{f}= ;若若不存在这样的片不存在这样的片B B，则令，则令B B是任何一个是任何一个G Gi i片并任取片并任取 4)(4)选取一条选取一条xyxy路路P Pi i  B B使使x,yx,y V VG G（（B B，，G Gi i））, ,令令G Gi+1i+1= = G Gi i P P, ,并把并把P Pi i画在的画在的 面面 f f内得内得G Gi+1i+1的一个平面表示的一个平面表示 ，用，用i+1i+1代替并转入第代替并转入第2 2步。

步 例1利用DMP算法检测图G的平面性123456782134875613132661234276134。