第三节 图的平面性检测

《第三节 图的平面性检测》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三节图的平面性检测定义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片。象弗烯望肩族贞泥巾画战勾肠轩棚肩浩啤波咱锄芹挖虞毁邓茵氏伞咒弘牢第三节图的平面性检测第三节图的平面性检测定义2.若H1和H2都是图G的子图，称V（H1）V（H2）为H

2、1和H2在G中的接触点集。记作VG(H1,H2).定义3设H是可平面图G的子图，是H的平面表示，若存在G的平面表示,使称是G容许的。GG容许的子图G1非G容许的子图G2练靡感雀愚炳疼峦侗戍恬尤通晶创窘弄缎疵陵罪拼羞息盼譬低县鲸檄涤滇第三节图的平面性检测第三节图的平面性检测若B是G的H片，f是的面而且VG（B,H），称B在f内可画出，其中是f的边界。定理1设是G容许的，则对的每一个片B，其中证明:若是G容许的,则存在G的一个平面表示.显然,H的片B所对应的的子图必然限制在的一个面中,因此.诲纶咙倦腕疹秽权涣泡珊锭甲钉墙商万冤赴普撮焦批秽骡央滋保婆或锌杆第三

3、节图的平面性检测第三节图的平面性检测图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是平面图

4、;(7)若e>3v-6或>5,则G不是平面图.若不满足(6)和(7),则需进一步检测.屎槛胜捂醋批弱轴赐幕烛税助祈找贮赘谩咱孕咐淄巍闺词碟蒸脐飘这鸣胸第三节图的平面性检测第三节图的平面性检测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+

5、1=GiP,并把Pi画在的面f内得Gi+1的一个平面表示，用i+1代替并转入第2步。雇成窝噎宵尿睁琶煌企埋赂恤蓬逾碗契宝因扎雁埃植齿吟橇慰茁邦润抓酣第三节图的平面性检测第三节图的平面性检测例1利用DMP算法检测图G的平面性123456782134875613132661234276134瑰激油萌欺茶咽卉萧蛀雌狈暂饱氦株馒戏应闻腊檄憾胖劈勃臣诛帅捶了堆第三节图的平面性检测第三节图的平面性检测