重要图类的独立数研究

作     者：张述平 

作者单位：中国地质大学(北京) 

学位级别：硕士

导师姓名：王海英

授予年度：2018年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：独立数 梯形图 凸多面体图 NI值 独立集 

摘      要：图论中,图的独立数为图论中重要的图参数。独立数研究在预测新化合物、合成新药品方面有很重要的应用。本文主要研究了两种特殊图类的独立数问题,分别为梯形图和凸多面体图。其中在梯形中我们主要研究了广义梯形图,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。与利用一般性公式算出的结果完全一致。但一般算法的应用仍然具有一定的局限性,如,将图转换为矩阵的形式。相信随着计算机网络的飞速发展,这一问题将不再是问题,极大推动重要图类独立数问题的研究。