使用者:Nnn009nnn/Sandbox 1

這是維基百科用戶嘗試創建頁面的地方。這不是一個百科全書條目。

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

定義

簡而言之，擴展圖是一個有限無向多重圖，其中每一組不「太大」的頂點均具有「很大」的邊界（boundary）。不同的具體定義給出了不同種類的擴展圖，下文將討論邊擴展圖、頂點擴展圖和譜擴展圖（spectral expander）三個概念。

非連通圖不是擴展圖，因為每一個連通分量都沒有邊界——分量周圍沒有邊進出，每一個連通圖都是擴展圖，只是他們的擴展性強弱不同。完全圖具有最強的擴展性，但卻很稠密（dense）。一個好的擴展圖應具有強擴展性，並且頂點度數較小。

邊擴展度

包含 $n$ 個頂點的圖 $G$ 的邊擴展度 $h(G)$ 定義為

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

其中 $\partial S:=\{(u,v)\in E(G)\ :\ u\in S,v\in V(G)\setminus S\}.$ 為子集 $S$ 的邊界。

注意在此一定義中，最小值取於所有非空、但包含不超過 $n/2$ 個頂點的子集^[2]。

頂點擴展度

圖 G 的頂點擴展度 $h_{\text{out}}(G)$ 定義為

h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},

此處 $\partial _{\text{out}}(S)$ 是集合 $S$ 的外邊緣，即所有不在 $S$ 中但與一個 $S$ 中的頂點相鄰的頂點^[3]。頂點擴展度這一概念的一個變體稱作「唯一鄰點擴展度」（unique neighbor expansion），在這裡 $\partial _{\text{out}}(S)$ 指全部僅有一個相鄰頂點在 $S$ 中的頂點^[4]。

腳註

^ Hoory, Linial & Widgerson (2006)
^ Definition 2.1 in Hoory, Linial & Widgerson (2006)
^ Bobkov, Houdré & Tetali (2000)
^ Alon & Capalbo (2002)

參考來源

教科書和文獻綜述

Alon, N.; Spencer, Joel H. 9.2. Eigenvalues and Expanders. The Probabilistic Method 3rd. John Wiley & Sons. 2011.
Chung, Fan R. K., Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92, American Mathematical Society, 1997, ISBN 0-8218-0315-8
Davidoff, Guiliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory and Ramanujan graphs, LMS student texts 55, Cambridge University Press, 2003, ISBN 0-521-53143-8
Hoory, Shlomo; Linial, Nathan; Widgerson, Avi, Expander graphs and their applications (PDF), Bulletin (New series) of the American Mathematical Society, 2006, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8
Krebs, Mike; Shaheen, Anthony, Expander families and Cayley graphs: A beginner's guide, Oxford University Press, 2011, ISBN 0-19-976711-4

研究論文

Ajtai, M.; Komlós, J.; Szemerédi, E., An O(n log n) sorting network, Proceedings of the 15th Annual ACM Symposium on Theory of Computing: 1–9, 1983, ISBN 0-89791-099-0, doi:10.1145/800061.808726
Ajtai, M.; Komlós, J.; Szemerédi, E., Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, 1987: 132–140, ISBN 0-89791-221-7, doi:10.1145/28395.28410
Alon, N.; Capalbo, M. Explicit unique-neighbor expanders. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002: 73. ISBN 0-7695-1822-2. doi:10.1109/SFCS.2002.1181884.
Bobkov, S.; Houdré, C.; Tetali, P., λ_∞, vertex isoperimetry and concentration, Combinatorica, 2000, 20 (2): 153–172, doi:10.1007/s004930070018 .
Dinur, Irit, The PCP theorem by gap amplification, Journal of the ACM, 2007, 54 (3): 12–es, doi:10.1145/1236457.1236459 .
Gillman, D., A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing (Society for Industrial and Applied Mathematics), 1998, 27 (4,): 1203–1220, doi:10.1137/S0097539794268765
Goldreich, Oded, Basic Facts about Expander Graphs, Studies in Complexity and Cryptography, 2011: 451–464, doi:10.1007/978-3-642-22670-0_30
Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
Yehudayoff, Amir, Proving expansion in three steps, ACM SIGACT News, 2012, 43 (3): 67–84, doi:10.1145/2421096.2421115

外部連結

[1] Hoory, Linial & Widgerson (2006)

[2] Definition 2.1 in Hoory, Linial & Widgerson (2006)

[BobkovHoudre-3] Bobkov, Houdré & Tetali (2000)

[AlonCapalbo-4] Alon & Capalbo (2002)

[1]

[2]

[3]

[4]