en:Expander_graph

在组合数论中，扩展图（英語：Expander graph）是一种具有强连通性质的疏松图，具体而言，看可用边、顶点或图谱扩展性（expansion）三种方式定义。扩展图的构造问题引导了多个数学分支上的研究，它还在计算复杂性理论、计算机网络设计和编码理论上有诸多应用^[1]。

简而言之，扩展图是一个有限无向多重图，其中每一组不「太大」的顶点均具有「很大」的边界（boundary）。不同的具体定义给出了不同种类的扩展图，下文将讨论边扩展图、顶点扩展图和谱扩展图（spectral expander）三个概念。

非连通图不是扩展图，因为每一个连通分量都没有边界——分量周围没有边进出，每一个连通图都是扩展图，只是他们的扩展性强弱不同。完全图具有最强的扩展性，但却很稠密（dense）。一个好的扩展图应具有强扩展性，并且顶点度数较小。

包含 ${\displaystyle n}$ 个顶点的图 ${\displaystyle G}$ 的边扩展度 ${\displaystyle h(G)}$ 定义为

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2))}{\frac {|\partial S|}{|S|)),}$

其中 ${\displaystyle \partial S:=\{(u,v)\in E(G)\ :\ u\in S,v\in V(G)\setminus S\}.}$ 为子集 ${\displaystyle S}$ 的边界。

注意在此一定义中，最小值取于所有非空、但包含不超过 ${\displaystyle n/2}$ 个顶点的子集^[2]。

图 G 的顶点扩展度 ${\displaystyle h_{\text{out))(G)}$ 定义为

${\displaystyle h_{\text{out))(G)=\min _{0<|S|\leq {\frac {n}{2))}{\frac {|\partial _{\text{out))(S)|}{|S|)),}$

此处 ${\displaystyle \partial _{\text{out))(S)}$ 是集合 ${\displaystyle S}$ 的外边缘，即所有不在 ${\displaystyle S}$ 中但与一个 ${\displaystyle S}$ 中的顶点相邻的顶点^[3]。顶点扩展度这一概念的一个变体称作「唯一邻点扩展度」（unique neighbor expansion），在这里 ${\displaystyle \partial _{\text{out))(S)}$ 指全部仅有一个相邻顶点在 ${\displaystyle S}$ 中的顶点^[4]。

• Brief introduction in Notices of the American Mathematical Society
• Introductory paper by Michael Nielsen
• Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
• Lecture notes from a course on expanders (by Prahladh Harsha)
• Definition and application of spectral gap