扩展图

扩展图（也称扩张图）是一类局部连接稀疏、但整体仍具有较强连接性的图。它的核心思想是：不太大的顶点集合向集合外有足够多的邻居，因而不能轻易被一个很小的边界与其他部分隔开。

顶点扩展

设 $G=(V,E)$ 是至少有两个顶点的有限简单无向图。对 $S\subseteq V$，定义外邻居集合 $$N_{\mathrm{o}\mathrm{u}\mathrm{t}}(S)=\{v\in V\setminus S:\mathrm{\exists }u\in S,uv\in E\}.$$ 若对所有满足 $1\le |S|\le |V|/2$ 的集合，都有 $$|N_{\mathrm{o}\mathrm{u}\mathrm{t}}(S)|\ge \alpha |S|,$$ 则称它具有至少 $\alpha$ 的顶点扩展率。定义比较的是不同的外邻居数，不是跨越边界的边数。也有使用边界边数或包含集合自身的邻域的其他约定，比较常数前要先核对定义。

若一列图的顶点数趋于无穷、最大度有统一上界，并且都具有同一个正的扩展率下界，称其为一个有界度的顶点扩展图族。“度有统一上界”与“扩展率有统一正下界”是两个独立要求。

环与完全图

考虑八顶点环 $C_8$。取连续四个顶点 $S=\{1,2,3,4\}$，它在外部只有顶点 5 和 8 两个邻居，故该集合的扩展比为 $$\frac{|N_{\mathrm{o}\mathrm{u}\mathrm{t}}(S)|}{|S|}=\frac{2}{4}=\frac{1}{2}.$$ 对于一般的 $C_n$，取约一半连续顶点时，集合外仍只有两个邻居，故其扩展率至多为 $2/\lfloor n/2\rfloor$，随着 $n$ 增大趋于零。因此环图族虽然每个顶点都只有两个邻居且图连通，却不满足统一正扩展率要求。

集合 S 有四个顶点、两个外邻居；其扩展比是二分之一。

对于完全图 $K_n$，任何非空 $S$ 的所有外部顶点都是它的外邻居。因此当 $|S|\le n/2$ 时，$|N_{\mathrm{o}\mathrm{u}\mathrm{t}}(S)|=n-|S|\ge |S|$。完全图有很强的顶点扩展，但其度为 $n-1$，随着规模增长而增长，不能作为有界度扩展图族的例子。

连通性与应用

若 $\alpha >0$，扩展图必须连通。否则取一个大小不超过顶点总数一半的连通分量作 $S$，它没有外邻居，违反扩展条件。反过来，连通图不一定有统一正的扩展率，环图族就是反例。

扩展性质用于构造稳健网络、纠错码和快速混合的随机游走。顶点扩展、边扩展和邻接矩阵谱之间有定量联系，但系数依赖度数和使用的归一化方式；不能在未说明条件时互相替换常数。