图的最大和次小拉普拉斯特征值

作     者：丁尚文 

作者单位：电子科技大学 

学位级别：硕士

导师姓名：张先迪

授予年度：2008年

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

主      题：拉普拉斯矩阵 最大特征值 Bethe树 线图 割点 

摘      要：设G是n阶简单连通图, D和A分别为图G的度对角矩阵和邻接矩阵,L (G )= D - A称为图G的拉普拉斯(laplacian)矩阵。研究图的拉普拉斯矩阵的特征值有着重要的图论意义和实际意义,因为它与图的许多不变量有着密切的联系。在许多应用中,往往需要知道图的拉普拉斯矩阵的最大特征值μ (G )的上界和次小特征值μn ?1 (G )的上下界。本文针对μ (G )的上界和μn ?1 (G )的上下界的估计问题做了以下几个方面的工作: 1.综述了近年来有关μ (G )的上界估计的主要结果,并作了全面的比较分析。 2.利用非负矩阵行和与它的谱半径之间的关系以及Perron-Frobenius定理等方法并结合图论性质获得了图的拉普拉斯谱半径的一些上界,并附带得到了关于有向图的谱半径估计的一些上下界。同时,对其中的一些估计式,用例子说明了其准确性和易于(编程)实现性。 3.利用矩阵理论和树的一些性质,研究了Bethe树的拉普拉斯谱半径的估计问题,得到了其具体特征多项式和它的谱集。 4.图的拉普拉斯次小特征值与图的代数连通度有关系,利用矩阵分拆技巧通过将L (G )分拆为两个矩阵和的形式再利用著名的Weyl定理,给出了一类具有割点、割边图的拉普拉斯次小特征值的上下界估计式。这些估计式具有递推特征,即估计式将高阶图类的拉普拉斯次小特征值用低阶图的拉普拉斯次小特征值来表示。