系列链接

Spectral Graph Theory学习笔记（1）
Spectral Graph Theory学习笔记（2）

概述

这是个啥课

这是门用各种奇怪的数学姿势，研究图论问题的课，这个系列的博客，只是做做笔记

前驱知识

大概只需要：

线性代数基础
图论基础
复杂度分析

第一章

前面大概就定义了一些符号
比如图$G=(V, E)$其中$G$表示图，$V$表示点集，$E$表示边集
这个课讨论都是无向的，简单的图

1.5节

这节定义了三个重要的矩阵
第一个是邻接矩阵$A_G$
定义是：
$$
A_G(u,v) = \begin{cases}
1\; if\; (u, v) \in E \\
0\; otherwise.
\end{cases}
$$
这是个对称矩阵
第二个是度数矩阵$D_G$
定义是：
$$D_G(u,v) = \begin{cases}
d(u)\; if\; u = u\\
0\; otherwise\end{cases}$$
这是个对角矩阵，其中$d(u)$表示$u$这个结点的度数
然后是一个很重要的拉普拉斯矩阵（Laplacian matrix）
定义是：
$$L_G = D_G - A_G$$

这个东东显然是对称的，并且有性质
$$x^TL_Gx = \sum_{(u,v)\in E}(x(u) - x(v))^2 \tag{1.1}$$
其中$x\in \mathbb{R}^V$

证明是显然的，只要把$L_G$的定义带入即可证明。

1.6节

这节有个定义就是Rayleigh quotient（不知道中文是什么）：
$$\frac{x^TMx}{x^Tx}$$
其中$M$是个矩阵，$x\in \mathbb{R}^V$
这个东西有个很显然的性质

若$x$取$M$的任意特征向量$x=\psi$
有：
$$\frac{\psi^TM\psi}{\psi^T\psi}=\lambda$$
其中$\lambda$是$\psi$对应的特征值

这个Rayleigh quotient还有个性质很重要：

如果$M$是对称矩阵，并且$x$是个非0向量并且最大化Rayleigh quotient，
那么$x$就是$M$最大的特征值对应的特征向量，
此时Rayleigh quotient的值为$M$最大特征值

证明挺长的，方法大概就是不断放缩

对应的，有性质：

如果$M$是对称矩阵，并且$x$是个非0向量并且最小化Rayleigh quotient，
那么$x$就是$M$最小的特征值对应的特征向量，
此时Rayleigh quotient的值为$M$最小特征值

1.7 节

关于式(1.1)不得不说的一点就是，如果向量$x$的每个分量都是1，那么(1.1)的左边就会取到0
显然有$L_G$是正定的，故所有特征值大于等于0，则0是最小的特征值。
那么由1.6的性质，全1向量（全相等常数也可以）必然是$L_G$的特征向量，并且对应最小特征值0。

还有一个看不懂的证明，证明了，如果第二小的$\lambda_2 > 0$，当且仅当，图联通。

1.8节

一个很有意思的应用
给一个无向图，试图将这个无向图画在一张纸上，又要比较美，怎么做呢
刻画这个比较美的一个方式就是
$$\underset{x}{min}\sum_{(u, v) \in E} (x(u) - x(v)) ^ 2$$
其中$x(u)$表示$u$这个结点的坐标
这时候，显然的一个策略就是
用$L_G$第二小特征值对应的特征向量作为横坐标
用$L_G$第三小特征值对应的特征向量作为纵坐标