扩展图

约定. 在本文中,

• 图指有限的简单无向图.
• $A^{\mathrm{c}}$ 表示集合 $A$ 的补集.
• $\Delta (G)$ 表示图 $G$ 的顶点的最大度数.

扩展图是一类连通性较强的图, 在计算复杂性和编码理论中有所应用.

1定义

扩展图不是定性概念而是定量概念. 下面是几种不完全相同而又差不多的定义图的扩展度的方式:

定义 1.1 (边扩展度). 图 $G$ 的边扩展度, 或称 Cheeger 常数, 指$$h(G)=\underset{\varnothing ⊊A⊊V(G)}{\min }\frac{|E(A,A^{\mathrm{c}})|}{\min \{|A|,|A^{\mathrm{c}}|\}},$$其中 $E(A,A^{\mathrm{c}})$ 指一个顶点在 $A$ 另一个顶点在 $A^{\mathrm{c}}$ 的边组成的集合. 对 $\epsilon \in {\mathbb{R}}_{+}$, $\mathbf{\epsilon }$-边扩展图指边扩展度至少是 $\epsilon$ 的图.

边扩展度是意义最明显的定义, 大致衡量了图的 “瓶颈”, 即把图切成两个不小的块至少要切多少边. 单说 “扩展度” 和 “扩展图” 通常都指边扩展度和边扩展图.

定义 1.2 (点扩展度). 图 $G$ 的点扩展度指$$h_{点}(G)=\underset{A\subseteq V(G),0<|A|\le |V(G)|/2}{\min }\frac{{\partial }_{外}(A)}{|A|},$$其中 ${\partial }_{外}(A)$ 指在 $A$ 外但与 $A$ 相邻的点组成的集合. 对 $\epsilon \in {\mathbb{R}}_{+}$, $\mathbf{\epsilon }$-点扩展图指点扩展度至少是 $\epsilon$ 的图.

容易发现 $\frac{h(G)}{\Delta (G)}\le h_{点}(G)\le \Delta (G)h(G)$. 即对于度数 $O(1)$ 的图, 点扩展度和边扩展度没有渐进差别.

定义 1.3 (谱隙). 设 $n$ 阶图 $G$ 的谱隙指其 Laplace 算子的次小特征值, 计重数.

由于 Cheeger 不等式, 谱隙也可视为一种扩展度. 正则图还有一种谱扩展性, 对 Laplace 的最大特征值也提出要求.

定义 1.4 ($(n,d,\lambda )$-图). 设 $n$ 阶 $d$-正则图 $G$ 的邻接矩阵的特征值为 $d={\lambda }_1\ge {\lambda }_2\cdots \ge {\lambda }_n$, 计重数. 记$$\lambda (G)=\max \{{\lambda }_2,-{\lambda }_n\}.$$对二部的 $G$, ${\lambda }_n=-d$, 此时记$${\lambda }_{二部}(G)=\max \{{\lambda }_2,-{\lambda }_{n-1}\}.$$对 $\lambda \in {\mathbb{R}}_{+}$, $(\mathbf{n},\mathbf{d},\mathbf{\lambda })$-(二部) 图指 ${\lambda }_{(二部)}(G)\le \lambda$ 的图.

2例子

•	显然, 不连通图的边扩展度、点扩展度、谱隙都是 $0$.

3相关概念

•	Alon–Boppana 界
•	Ramanujan 图
•	扩展复形

术语翻译

扩展图 • 英文 expander graph

边扩展度 • 英文 edge expansion

点扩展度 • 英文 vertex expansion

谱隙 • 英文 spectral gap