图的边不交的生成树和最大状态圈的数目

发布时间：2019-09-30 12:19

【摘要】：图G=(V,E)的媒体图就是顶点集为E,边集为{ef|e,f是G中两条相邻的边且在同一面内}的图,用M(G)表示.链环L是将一维平面S1上的图嵌入到三维空间E3上形成的圈的不交并.链环图D(G)是链环L的平面表示.对于平面图G,可以通过它的媒体图M(G)来构造链环图D(G).基于无向的交错链环的亏格理论,Jin在[9]中引进了平面图的最大状态圈的数目.对链环图D(G)的每个交点选择A-分裂或B-分裂,使得圈的数目最大时的状态称为最大状态,该状态下的圈数记为S_(max)(G),并得出其中H跑遍G的所有生成子图,c(H)是H的连通分支数.在这篇文章中,我们利用Jin的结论,证明了对于任何图G(不需要平面),S_(max)(G)当G的生成子图H的每个连通分支都是G的有两个边不交生成树的极大子图时取得,并证明了这个生成子图是唯一的.在第三章,给出了一个多项式时间算法,来找出满足S_(max)(G)的生成子图H,以便快速算出图G的最大状态圈的数目S_(max)(G)。
【学位授予单位】：新疆大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
，

本文编号：2544287