系列链接
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)$$