重要图类的独立数研究

发布时间：2021-07-16 08:33

　　图论中,图的独立数为图论中重要的图参数。独立数研究在预测新化合物、合成新药品方面有很重要的应用。本文主要研究了两种特殊图类的独立数问题,分别为梯形图和凸多面体图。其中在梯形中我们主要研究了广义梯形图,Mobius梯形图和循环梯形图。对于凸多面体图,我们主要研究了凸多面体图类An,Qn,Rn。在本文中,我们还给出了求解图类独立数问题的一般算法。对于梯形图,得到广义梯形图,Mobius梯形图和循环梯形图的独立数的精确值,并得到了三种图形独立集的总和NI的精确计算公式,并运用转换矩阵的思想设置程序验证结果。对于凸多面体图,我们主要研究了三种凸多面体图类,分别为An,Rn和Qn。我们求出来三种图类的独立数,并且求出凸多面体图类An的独立集总和NI的精确计算公式。因为凸多面体图类Rn和Qn结构较为复杂和一般化,我们很难求出NI的精确计算公式,所以我们给出它们的上界或者下界。对于任意图,我们给出了一般算法。可以计算任意图的NI问题。利用二部图和左部图对其进行验证。选出两个特殊图,如:K5,4,3,2和K5,4,3,2,4。得到NI（K5,4,3,2）=319,NI（K5,4,3,2,4）=757。... 

【文章来源】：中国地质大学(北京)北京市 211工程院校 教育部直属院校

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

七桥问题

印度数学中的 Virahanka 数字。（[16][17][18]）LiberAbaci 中描述的顺序开始1 = 1。定义 1.8.（卢卡斯数）（Startek，2009）设nL 为第 n 个卢卡斯数，则有0L =2，1且1 2= +n n nL L L ( n ≥ 2)，卢卡斯数列通项公式如下：1 5 1 5+2 2n nnL + = ( n ≥ 2). （1-5）定义 1.9.（k（边）连通图）（Bondy，1984）若 κ ( G )≥ k( κ′ ( G )≥ k)，则称为 k（边）连通的。所有非平凡连通图都是 1 连通的。

图 1-3 （a）一个连通图 （b）一个具有两个分支的不连通图定义 1.10.大多数（但不是全部）图表有许多可视化的表示形式，通常称为嵌入。为了说明上述定义，我们使用下面的图表：G = {{ A, B , C , D , E } , {{ A, B} , { B , C } , {C , D} , {C , E } , { D , E } , { D ,A}}}.图G 的边集 E ( G )为 {{ A, B} , { B , C } , {C , D} , {C , E } , { D , E } , { D ,A} }。图G 的顶点集 V ( G )为{ A, B , C , D ,E }。 V ( G )=5， E ( G )=6。如图 1 所示，为图 G 的两种可能的嵌入：

【参考文献】：
期刊论文
[1]图论中数学归纳法的应用[J]. 杨迪.  技术与市场. 2016(01)
[2]关于独立数问题的一些结果[J]. 董茜.  四川兵工学报. 2010(01)
[3]反证法及其在图论中的应用[J]. 达瓦,边巴扎西.  中国电力教育. 2007(S4)
[4]合成图的独立数与控制数[J]. 李炜.  黄冈师专学报. 1997(01)

硕士论文
[1]图论的历史发展研究[D]. 王丽丽.山东大学 2012
[2]图的独立数、连通度与Hamilton连通性[D]. 张秀玲.华中师范大学 2008
[3]树的Merrifield-Simmons指数与独立多项式[D]. 吴继春.湖南师范大学 2008



本文编号：3286665