四种特殊图类的Merrified-Simmons指标研究

发布时间：2018-10-29 20:49

【摘要】：在图论中,图的独立点集的总和称为图G的Merrified-Simmons指标(简记为MS指标),MS指标在预测、合成新的化合物、新的药品方面有很重要的应用.本文主要研究了四种特殊图类的MS指标,分别为完全K部图、似星树、特殊单圈图和毛毛虫树.其中特殊单圈图是化学分子常见的结构,而似星树和毛毛虫树则是常见的网络结构图.对于完全多部图,得到了K部图具体的MS指标的计算表达式:2m1+2m2+…+2mk+1-k,并通过证明验证了结果的正确性.对于单圈图,由于其结构的普遍性,很难求得一般单圈图的MS指标的表达式,扩展定义了两种特殊的单圈图,利用独立多项式和斐波那契数列的递推关系,比较特殊的两种单圈图,得到的特殊单圈图的上下界.得出特殊单圈图中使MS指标最大的图G必为Gn3Sn-3,使MS指标最小的图必为Gn(3,3,3,…,3+p).对于似星树,主要比较有不同分支的似星树的MS指标,并对有相同分支的似星树按照MS指标进行排序,重复使用便可以刻画出似星树的极图.对于毛毛虫图,由于其结构的复杂性,很难得出一般毛毛虫树的MS指标表达式.本文构造了一种特殊的毛毛虫树,通过分析其结构特征,利用组合推理的方法,计算出其MS指标的具体表达式为研究了该特殊毛毛虫树关于MS指标的计数表达式并验证结果的正确性.
[Abstract]:In graph theory, the sum of independent point sets of graphs is called the Merrified-Simmons index of graph G (abbreviated as MS index,), MS index has important applications in predicting, synthesizing new compounds and new drugs. In this paper, the MS indexes of four special graphs are studied, which are complete K graph, star like tree, special monocycle graph and caterpillar tree. The special unicyclic graph is a common structure of chemical molecules, while the star like tree and caterpillar tree are common network structure diagrams. For the complete multipartite graph, the calculation expression of the specific MS index of the K part graph is obtained: 2m1 2m2. 2mk 1-k. the correctness of the results is verified by proving. For unicyclic graphs, because of the universality of their structure, it is difficult to obtain the expression of the MS index of general unicyclic graphs. Two special monocyclic graphs are extended and defined. The recursive relations between independent polynomials and Fibonacci series are used. The upper and lower bounds of special unicyclic graphs are obtained by comparing two special monocyclic graphs. It is concluded that the graph G of the special unicyclic graph which makes the maximum MS index G must be Gn3Sn-3, and the smallest graph of MS index must be Gn. , 3 p). For starlike trees, the MS indices of starlike trees with different branches are compared, and the starlike trees with the same branches are sorted according to the MS index, and the polar graphs of starlike trees can be depicted by repeated use. For the caterpillar graph, it is difficult to get the MS index expression of the general caterpillar tree because of the complexity of its structure. In this paper, a special caterpillar tree is constructed. The concrete expression of calculating the MS index is to study the counting expression of the special caterpillar tree about the MS index and verify the correctness of the result.
【学位授予单位】：中国地质大学(北京)
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】