茶年 · 中文维基百科

扩展图

Wikipedia · 2026-06-18 维基百科 👁 0 阅读

在组合数学中，扩展图（）是一种具有强连通性质的稀疏图，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。

定义
对于有限、无向、连通的多重图，扩展性是一种能够衡量其连通强弱的指标。直观而言，扩展性较强意味着图中任何「不太大」的顶点集均有较大的边界，也就是说集合内外的交互很强。

连通图的扩展性有的弱，有的强。例如道路的扩展性很弱，而完全图的扩展性最强。可以看出，稠密图比稀疏图更“容易”具备强扩展性。但人们希望构造一类鱼与熊掌兼得的图：既能保持稀疏性，又具备很强的扩展性。具备这样“矛盾”属性的图就是一张扩展图；矛盾对立越深，扩展图越优良。

用数学语言表达如下：若一张图图有 n 个顶点、最大度为 d、扩展性为 h，那么就称它为(n,d,h)-扩展图。d 越小（即图越稀疏）且 h 越大（即扩展性越强），则扩展图的性质越优异。

作为扩展图定义中的关键参数之一，“扩展性”的精确概念可用不同方式来量化。下文将讨论边扩展性、顶点扩展性和谱扩展性三种量化方式。

边扩展性
包含 n 个顶点的图 G = (V,E) 的边扩展性 h(G) 定义为

: h(G) = \min_{0

其中 \partial S := \{ \{u,v\} \in E \mid u \in S, v \in V \setminus S \} 为子集 S 的边界。注意在此定义中，最小值取于所有非空且大小不超过 n/2 的顶点集。

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

: h_{\text{out}}(G) = \min_{0

此处 \partial_{\text{out}}(S) := \{v \not\in S \mid \exists u \in S: \{u,v\} \in E\} 是集合 S 的外边缘。顶点扩展性有一种变体，称作「唯一邻点扩展性」（），在这里 \partial_{\text{out}}(S) := \{v \not\in S \mid \exists! u \in S: \{u,v\} \in E\}。

谱扩展性
当 G 是d-正则图时，可以借助线性代数中的特征值理论来定义扩展性，称作谱扩展性。具体而言，设 A 是图 G 的邻接矩阵，其中 A(i,j) 记录了顶点 i, j 之间的边数。因为 A 是实对称矩阵，根据谱定理知道它有 n 个实特征值 \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}。可以证明它们都落在区间 [-d,d]内。

由于 G 是正则图，所以 \mathbb{R}^n 上的均匀分布 \mathbf{u} := (1/n, 1/n, \dots, 1/n) 是矩阵 A 的特征向量，对应特征值 d = \lambda_1，即 A\mathbf{u} = d\mathbf{u}。图 G 的谱间距（spectral gap）定义为 d - \lambda_2，它可以用作扩展性的量度。

三种扩展性度量之间的关系
上面定义的三种量化方式虽然形式上有差别，但在本质上相互联系。对于d-正则图，我们有

: h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).

因此，当度是常数时，前两种量化方式并无实质区别。

Cheeger不等式
对于d-正则图，Dodziuk和Alon、Milman 证明了

: \tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}

这一不等式与马尔可夫链的Cheeger不等式有本质联系。

[上界]

上界則（漸近地）由環 C_n 達到，其中
h(C_n) = 4/n = \Theta(1/n)，
而 d - \lambda_2 = 2 - 2\cos(2\pi/n) \approx (2\pi/n)^2 = \Theta(1/n^2)。
此外，文獻給出了更緊的上界：
:h(G) \le \sqrt{d^2 - \lambda_2^2}

[下界]

事實上，此下界是緊的。以超立方體 Q_n 為例，
其正則度為 d = n，且其特徵值為
\lambda_k = n - 2k（k = 0, 1, \ldots, n），
故第二大特徵值為 \lambda_2 = n - 2，
譜隙為 d - \lambda_2 = 2，下界為 \tfrac{1}{2}(d - \lambda_2) = 1。
又 h(Q_n) = 1，因此無論維度 n 為何，下界恰好取等。

這些不等式與馬爾可夫鏈的Cheeger bound密切相關，
也可視為黎曼幾何中Cheeger不等式的離散版本。

類似地，頂點等周數與譜隙之間的關聯也已被研究
:h_{\text{out}}(G) \le \sqrt{(4(d - \lambda_2) + 1)^2 - 1}
:h_{\text{in}}(G) \le \sqrt{8(d - \lambda_2)}
漸近而言，h^2/d、h_{\text{out}} 與 h_{\text{in}}^2
均以譜隙 O(d - \lambda_2) 為上界。

構造策略
要實際構造出擴展圖家族，目前有四種主要策略。
在介紹各種構造方法之前，先定義構造的目標——。

(1) 代數與群論

(2) 分析方法，使用堆壘數論

(3) 組合方法，使用及相關圖積

(4) （又稱 lift）

Margulis–Gabber–Galil
基於凱萊圖的代數構造適用於擴展圖的各種變體。
以下構造由 Margulis 提出，並由 Gabber 與 Galil 分析。

對每個自然數 n，考慮頂點集為 \mathbb{Z}_n \times \mathbb{Z}_n 的圖
G_n。

其中 \mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}。
對每個頂點 (x, y) \in \mathbb{Z}_n \times \mathbb{Z}_n，
其八個相鄰頂點為
:\{(x \pm 2y,\ y),\quad (x \pm (2y+1),\ y),\quad (x,\ y \pm 2x),\quad (x,\ y \pm (2x+1))\}.

則有以下定理：

;定理
:對所有 n，圖 G_n 的第二大特徵值滿足 \lambda(G_n) \le 5\sqrt{2}。

Ramanujan圖
由 ，所有足夠大的 d-正則圖均滿足
:\lambda_2 \ge 2\sqrt{d-1} - o(1)
其中 \lambda_2 為絕對值意義下的第二大特徵值。
可直接得出：對每個固定的 d 與 \lambda ，
滿足條件的 (n, d, \lambda)-圖僅有有限個。

是使上述界恰好取等的 d-正則圖，滿足
:\lambda = \max_{n}\right|
\leq \lambda\sqrt.

(n,d,\lambda)-圖的許多性質都是擴展混合引理的推論，包括以下幾點。

  • 圖的獨立集是不含任兩相鄰頂點的頂點子集。在 (n,d,\lambda)-圖中，任一獨立集的大小至多為 \lambda n/d。
  • 圖 G 的圖色數 \chi(G) 是使任兩相鄰頂點顏色不同所需的最少顏色數。

Hoffman 證明了d/\lambda \leq \chi(G)，
而 Alon、Krivelevich 與 Sudakov 證明：若 d ，則
\chi(G) \le O\left(\frac{d}{\log\left(1 + \frac{d}{\lambda}\right)}\right).

  • 圖的直徑R是任兩頂點之間最短路徑長度的最大值。

\operatorname{diam}(G) = \max_{u,v \in V} \operatorname{dist}(u,v)。
Chung 證明，(n,d,\lambda)-圖的直徑至多為
\left\lceil {\log \frac{n}{{\log (\frac{d}{\lambda})}}} \right\rceil.

注解
参考来源
教科书和文献综述
*
*
*
*
*
研究论文
*
*
*

  • .
  • .

*
*
*
*

外部链接

*

#图论

评论 (0)

  • 还没有评论，来抢沙发吧。