在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻 接矩阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等。这些矩阵与图都有着自然 的联系。代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵 的代数性质反映出来。这里所指的矩阵的代数性质，主要指矩阵的特征值。 在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩 阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不变 量，图的邻接矩阵及其特征值是代数图论的一个基本的研究课题。对于图的拉 普拉斯矩阵的特征值而言，在过去的几十年中，人们对图的邻接矩阵的特征值 已经进行了大量的研究(见文献[6，13，14])。和图的邻接矩阵相比，由于在拉 普拉斯矩阵中含有图的顶点度的信息，因此图的拉普拉斯矩阵的特征值与图的 很多不变量有着更加密切的联系。正如Mohar[79]所说：图的拉普拉斯矩阵的 特征值更能反映它的图论性质。所以，对图的拉普拉斯矩阵的特征值的研究越 来越受到人们的广泛关注。 人们对拉普拉斯矩阵的研究，可以追溯到160多年以前。拉普拉斯矩阵最 著名的应用是在1847年Kirchhoff研究电流理论时所发现的如下矩阵-树定理 中： 矩阵-树定理：设G是一个有n个顶点的连通图且L(G)是 它的拉普拉斯矩阵，去掉L(G)的第i行及j列得到一个 n-1阶的子矩阵，记为L(i|j)。则L(i|j)的行列式的绝对 值等于图G的生成树的个数。 因此，图的拉普拉斯矩阵有时被称为Kirchhoff矩阵。又因为拉普拉斯矩阵 在人们研究电路网络时有着重要应用，因此，该矩阵也被称为容许矩阵。在数 学物理上，由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情形[79]，故 在数学上，该矩阵一般被称为拉普拉斯矩阵。图的拉普拉斯矩阵的特征值被称 为图的拉普拉斯特征值。 图的拉普拉斯特征值有很多的应用。例如，在物理和化学的很多问题中， 拉普拉斯特征值起到中心的作用(见[19，20，21，22，23])。拉普拉斯特征值也可 以被用来给出图的几何表示(见[35]P.284)，而这与图论中近来最重要的进展之 一-图的Colin de Verdi(e)re数有着密切的关系[53]。因此，拉普拉斯特征值不仅 引起了数学家的关注，而且也引起了不少物理学家和化学家的重视。 本文的研究内容主要分如下五个方面：一是对拉普拉斯特征多项式的研 究；二是对拉普拉斯谱半径的研究；三是对代数连通度的研究；四是对树的拉 普拉斯特征值的研究;最后是对图的其它拉普拉斯特征值的研究。 众所周知，图的邻接矩阵的特征多项式在研究邻接矩阵的特征值时有着非 常重要的作用。然而，目前我们对图的拉普拉斯矩阵的特征多项式知之甚少。 在第1章中，我们介绍了与拉普拉斯矩阵有关的基本概念以及矩阵论中的一些 基本定理。更主要的是，在第1章中，我们对图的拉普拉斯矩阵的特征多项式 进行了研究，得到了一些基本的公式。在后面的几章中，我们将发现图的拉普 拉斯矩阵的特征多项式在研究图的拉普拉斯特征值的时候将起到非常关键的作 用。 对图的拉普拉斯特征值而言，最重要的两个特征值分别是最大的拉普拉斯 特征值和第二小的拉普拉斯特征值。在第2章和第3章中，我们将分别讨论图 的这两个拉普拉斯特征值。 图的拉普拉斯谱半径是指图的拉普拉斯矩阵的最大特征值。最近，人们发 现拉普拉斯谱半径在理论化学上有重要的应用[48，49]。在第2章中，我们给出 了拉普拉斯谱半径的可达的上下界；考虑了在各种扰动下(例如：加边运算，嫁 接运算，剖分运算等等)，拉普拉斯谱半径的变化情况；研究了拉普拉斯谱半径 的极限点。作为我们所得结果的应用，在本章的最后，我们考察了具有n个顶点 和k个悬挂点的单圈图以及双圈图的拉普拉斯谱半径。 图的代数连通度是指图的拉普拉斯矩阵的第二小特征值。最近，人们利用 图的代数连通度来研究一些困难的图论问题，得到了很好的结果，例如图的扩 展性质[1]，等周数[76，77]，最大割问题[78]，以及图的直径[11]等等。在第3章 中，我们研究了图的代数连通度：考察了对图进行嫁接运算后，图的代数连通 度的变化情况；进一步，利用该结果及我们在第1章中所发展的图的拉普拉斯 特征多项式理论，我们完全解决了Fallat和Kirkland在1998年提出的关于具有 固定围长的连通图的代数连通度的一个猜想(见[24，25])。 作为最简单的连通图，在研究一些困难的图论问题时，树通常起到特殊的 作用。在第4章中，我们系统地研究了树的拉普拉斯特征值：包括具有固定直 径的树的拉普拉斯谱半径；树的第二大的拉普拉斯特征值以及树的第k大的拉普 拉斯特征值等等。 在最后一章中，我们考虑了图的其它的拉普拉斯特征值，包括图的第三大 的拉普拉斯特征值以及图的拉普拉斯特征值的重数等等。 关键词： 图，拉普拉斯矩阵，邻接矩阵，拉普拉斯特征值，特征多项式，特征 向量，树，拉普拉斯谱半径，代数连通度，极限点，直径，上(下)界，单圈 图，双圈图，分布，加边运算，嫁接运算，剖分运算。