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

定義

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

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

用數學語言表達如下:若一張圖圖有   個頂點、最大 、擴展性為  ,那麼就稱它為 -擴展圖。  越小(即圖越稀疏)且   越大(即擴展性越強),則擴展圖的性質越優異。

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

邊擴展性

包含   個頂點的圖   的邊擴展性   定義為

 

其中   為子集   的邊界。注意在此定義中,最小值取於所有非空且大小不超過   的頂點集[2]

頂點擴展性

  的頂點擴展性   定義為

 

此處   是集合   的外邊緣[3]。頂點擴展性有一種變體,稱作「唯一鄰點擴展性」(unique neighbor expansion),在這裡  [4]

譜擴展性

 d-正則圖時,可以藉助線性代數中的特徵值理論來定義擴展性,稱作譜擴展性。具體而言,設   是圖  鄰接矩陣,其中   記錄了頂點   之間的邊數[5]。因為   是實對稱矩陣,根據譜定理知道它有   個實特徵值  。可以證明它們都落在區間  內。

由於   是正則圖,所以   上的均勻分布   是矩陣   的特徵向量,對應特徵值  ,即  。圖   的譜間距(spectral gap)定義為  ,它可以用作擴展性的量度。

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

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

 

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

Cheeger不等式

對於d-正則圖,Dodziuk[6]AlonMilman[7] 證明了

 

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

註解

  1. ^ Hoory, Linial & Widgerson (2006)
  2. ^ Definition 2.1 in Hoory, Linial & Widgerson (2006)
  3. ^ Bobkov, Houdré & Tetali (2000)
  4. ^ Alon & Capalbo (2002)
  5. ^ cf. Section 2.3 in Hoory, Linial & Wigderson (2006)
  6. ^ Dodziuk 1984.
  7. ^ Alon & Spencer 2011.

參考來源

教科書和文獻綜述

研究論文

外部連結