跳至內容

擴展圖

維基百科,自由的百科全書

組合數學中,擴展圖(英語: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.

參考來源

[編輯]

教科書和文獻綜述

研究論文

外部連結

[編輯]