Spectral Graph Theory学习笔记（2）

系列链接

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

第二章

这一章感觉没什么重点

2.3节

就是之前说的那个画图的方法

2.4节

定义了一个boundary的概念，如果$S$是图$G$的一个点子集，那么定义$S$的boundary为：
$$\partial (S) = \{(u, v)\in E:u\in S,v\notin S\}$$
然后定义了一个比值：isoperimetric ratio：
$$\theta(S)=\frac{|\partial(S)|}{|S|}$$
接下来是定义了一个图的isoperimetric，取所有点子集的最小$\theta(S)$:
$$\theta_G=\underset{|S|\le n/2}{min}\theta(S)$$

对于这个isoperimetric有个性质：

对于$S\subset V$，有：
$$\theta(S)\ge \lambda_2(1-s)$$
这里$s$表示$|S|/|V|$
对于一个图有：
$$\theta_G\ge \lambda_2/2$$

又是一个看不懂的证明T_T

2.5节

这节提出了几个特殊图的拉普拉斯矩阵的性质

完全图

完全图的$L_G$有两个特征值，一个是0，一个是$n$
其中0是1重，$n$是$n-1$重

星图

的$L_G$有三个特征值，一个是1，一个是0，一个是$n$
1是$n-2$重，0是1重，$n$是1重