图的规范拉普拉斯谱的若干研究

The book, written by F. K. Chung in 1997, proposed the normalized Laplacian matrix of a graph, and introduced the properties of normalized Laplacian spectrum and its applications. Normalized Laplacian spectrum, as one of the important spectrum of graph matrices, not only contain much good structural information of graphs, but also can be applied for spectral clustering and image segmentation. This project will focus on the study of relations between normalized Laplacian spectrum and graph parameters, including the following three parts: (1). Characterizing the graph with the maximal normalized Laplacian spectral radius among all connected non-bipartite graphs with fixed order; (2). Determining the minimal normalized algebraic connectivity with the corresponding extremal graphs among all connected graphs; (3). Looking for the graphs (such as complete multipartite graphs and lollipop graphs, etc.) which are determined by their normalized Laplacian spectrum. We will use the methods from graph theory and matrix theory, combine computer experiment analysis and theoretical argumentation to promote the above problems solved successfully, in order to develop the theory on normalized Laplacian spectrum.

1997年，F. K. Chung教授在其撰写的专著中提出了图的规范拉普拉斯矩阵，并介绍了规范拉普拉斯谱的基本性质以及在其他领域的应用。规范拉普拉斯谱作为一种重要的图矩阵谱，其不仅包含了丰富的图的结构信息，而且在谱聚类算法以及图像分割有着广泛的应用。本项目拟研究图的规范拉普拉斯谱与图的不变量之间的关系，主要从以下三个方面展开研究：（1）刻画具有最大规范拉普拉斯谱半径的连通非二部分图；（2）确定连通图的规范代数连通度的最小值以及其对应的极图；（3）寻找由其规范拉普拉斯谱所确定的特殊图类，如完全多部图，棒棒糖图等。本项目将运用图论和矩阵论等方法，结合计算机实验分析和理论论证推导，来推动上述问题的顺利解决，以促进图的规范拉普拉斯谱理论的发展。

1997年，F. K. Chung教授在其撰写的专著中提出了图的规范拉普拉斯矩阵，并介绍了规范拉普拉斯谱的基本性质以及在其他领域的应用。规范拉普拉斯谱作为一种重要的图矩阵谱，其不仅包含了丰富的图的结构信息，而且在谱聚类算法以及图像分割有着广泛的应用。本项目研究图的规范拉普拉斯谱与图的不变量之间的关系，主要从以下三个方面开展研究：（1）建立图的规范谱半径与某些图的不变量的内在关系；（2）刻画具有较少不同规范特征值的图类；（3）延伸至图的谱半径极值问题。本项目执行期间，得到了图的规范谱半径与图的重要参数之间的关系，也对具有较少规范特征值图类的进行了部分刻画，并由此启发攻克了其他图矩阵谱的3个猜想；同时利用部分已取得的结果应用到复杂网络中的关键节点选取中，利用数值模拟验证新方法具有更好的效果。相信在不久的将来，这些图谱理论中的成果会在各个领域大放异彩。