拉普拉斯矩阵
图论的数学领域中的拉普拉斯矩阵（也被称为导纳矩阵，吉尔霍夫矩阵或离散拉普拉斯）是图的矩阵表示。
拉普拉斯矩阵 结合 吉尔霍夫理论 可以用来计算图的最小生成树的个数。拉普拉斯矩阵还可用来寻找图的其他属性：谱图理论spectral graph theory.
黎曼几何的Cheeger不等式有涉及了拉普拉斯矩阵的离散模拟。这或许是谱图理论中最重要的定理也是在算法应用中最有用的facts.它通过拉普拉斯矩阵的第二特征值来近似图的最小割。
拉普拉斯矩阵是
属性：
1.拉普拉斯矩阵是半正定矩阵。
2.特征值中0出现的次数就是图连通区域的个数。
3.最小特征值永远是0，因为每个拉普拉斯矩阵对应特征向量[1,1,1,1,...,1]Lv=0.
4.最小的非0特征值称为谱隙spectral gap.
5.
6.最小非零特征值是图的代数连通度。
谱图理论
在数学中，谱图理论是研究图的属性与邻接矩阵或拉普拉斯矩阵的特征多项式，特征值，特征向量的关系。
无向图拥有对称邻接矩阵，因此有实特征值完全正交特征向量
谱聚类
在多元统计和数据聚类中，谱聚类技术利用了相似矩阵的光谱（特征值）来进行数据降维。相似矩阵是一组量化评估数据集中每对点之间的相对相似性。
其中一个谱聚类技术是：normalized cuts algorithm，用于图像分割。它根据拉普拉斯矩阵的非零最小特征值所对应的特征向量将点分为两个集合。另一种相关的算法是根据特征向量对应的最大的k个特征值所对应的特征向量进行聚类，例如采用k-means clustering算法。
SPAN算法 spectral neighborhood algorithm有效的提高了spectral clustering算法的可扩展性，它不需要明确的计算相似矩阵。
谱聚类与k-means的关系