擴展圖

在組合數學中，擴展圖（英語：Expander graph）是一種具有強連通性質的稀疏圖，可用邊擴展性、頂點擴展性或圖譜擴展性三種方式來量化。擴展圖的構造問題引導了多個數學分支上的研究，並且在計算複雜性理論、計算機網絡設計和編碼理論上有諸多應用^[1]。

定義

對於有限、無向、連通的多重圖，擴展性是一種能夠衡量其連通強弱的指標。直觀而言，擴展性較強意味着圖中任何「不太大」的頂點集均有較大的邊界，也就是說集合內外的交互很強。

連通圖的擴展性有的弱，有的強。例如道路的擴展性很弱，而完全圖的擴展性最強。可以看出，稠密圖比稀疏圖更「容易」具備強擴展性。但人們希望構造一類魚與熊掌兼得的圖：既能保持稀疏性，又具備很強的擴展性。具備這樣「矛盾」屬性的圖就是一張擴展圖；矛盾對立越深，擴展圖越優良。

用數學語言表達如下：若一張圖圖有 ${\displaystyle n}$ 個頂點、最大度為 ${\displaystyle d}$、擴展性為 ${\displaystyle h}$，那麼就稱它為${\displaystyle (n,d,h)}$-擴展圖。${\displaystyle d}$ 越小（即圖越稀疏）且 ${\displaystyle h}$ 越大（即擴展性越強），則擴展圖的性質越優異。

作為擴展圖定義中的關鍵參數之一，「擴展性」的精確概念可用不同方式來量化。下文將討論邊擴展性、頂點擴展性和譜擴展性三種量化方式。

邊擴展性

包含 ${\displaystyle n}$ 個頂點的圖 ${\displaystyle G=(V,E)}$ 的邊擴展性 ${\displaystyle h(G)}$ 定義為

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

其中 ${\displaystyle \partial S:=\{\{u,v\}\in E\mid u\in S,v\in V\setminus S\}}$ 為子集 ${\displaystyle S}$ 的邊界。注意在此定義中，最小值取於所有非空且大小不超過 ${\displaystyle n/2}$ 的頂點集^[2]。

頂點擴展性

圖 ${\displaystyle 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):=\{v\not \in S\mid \exists u\in S:\{u,v\}\in E\}}$ 是集合 ${\displaystyle S}$ 的外邊緣^[3]。頂點擴展性有一種變體，稱作「唯一鄰點擴展性」（unique neighbor expansion），在這裏 ${\displaystyle \partial _{\text{out}}(S):=\{v\not \in S\mid \exists !u\in S:\{u,v\}\in E\}}$^[4]。

譜擴展性

當 ${\displaystyle G}$ 是d-正則圖時，可以藉助線性代數中的特徵值理論來定義擴展性，稱作譜擴展性。具體而言，設 ${\displaystyle A}$ 是圖 ${\displaystyle G}$ 的鄰接矩陣，其中 ${\displaystyle A(i,j)}$ 記錄了頂點 ${\displaystyle i,j}$ 之間的邊數^[5]。因為 ${\displaystyle A}$ 是實對稱矩陣，根據譜定理知道它有 ${\displaystyle n}$ 個實特徵值 ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$。可以證明它們都落在區間 ${\displaystyle [-d,d]}$內。

由於 ${\displaystyle G}$ 是正則圖，所以 ${\displaystyle \mathbb {R} ^{n}}$ 上的均勻分布 ${\displaystyle \mathbf {u} :=(1/n,1/n,\dots ,1/n)}$ 是矩陣 ${\displaystyle A}$ 的特徵向量，對應特徵值 ${\displaystyle d=\lambda _{1}}$，即 ${\displaystyle A\mathbf {u} =d\mathbf {u} }$。圖 ${\displaystyle G}$ 的譜間距（spectral gap）定義為 ${\displaystyle d-\lambda _{2}}$，它可以用作擴展性的量度。

三種擴展性度量之間的關係

上面定義的三種量化方式雖然形式上有差別，但在本質上相互聯繫。對於d-正則圖，我們有

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}$

因此，當度是常數時，前兩種量化方式並無實質區別。

Cheeger不等式

對於d-正則圖，Dodziuk^[6]和Alon、Milman^[7] 證明了

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}}$

這一不等式與馬爾可夫鏈的Cheeger不等式有本質聯繫。