图的无符号拉普拉斯谱半径及平衡划分问题研究

论文摘要

本文包括两方面的内容.第一部分研究简单图和平面图的无符号拉普拉斯谱半径的上界.如果一个图存在定向满足其最大出度△+不超过最大度△的一半,则通过估计图的半边路径（semi-edge walk）的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界：第二部分研究简单图和平面图的平衡划分上界问题.给定一个图,通过该图的邻接矩阵,将平衡划分的边割数用矩阵表示,得到平衡划分的最小割的新上界：其中m和n分别是该图的边数和顶点数.进而对于平面图,得到当边数小于顶点数的两倍时,一定存在平衡划分使得边割数不超过顶点数.

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 无符号拉普拉斯谱半径的研究
• 1.2 图的平衡划分问题
• 1.3 符号说明
• 第二章 无符号拉普拉斯谱半径
• 2.1 基本概念
• 2.2 主要结果
• 2.3 平面图中的应用
• 第三章 平衡划分的最小割的上界
• 3.1 相关概念
• 3.2 主要结果
• 3.3 平面图中的应用
• 结论
• 参考文献
• 致谢
• 个人简历、在学期间的研究成果及发表的学术论文