查看“︁扩展图”︁的源代码

在[[组合数学]]中，'''扩展图'''（{{lang-en|Expander graph}}）是一种具有强[[连通图|连通]]性质的[[稀疏图]]，可用[[边 (图论)|边]]扩展性、[[顶点 (图论)|顶点]]扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在[[计算复杂性理论]]、[[计算机网络]]设计和[[编码理论]]上有诸多应用<ref>{{harvtxt|Hoory|Linial|Widgerson|2006}}</ref>。

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

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

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

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

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

: <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial S|}{|S|}</math>

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

=== 顶点扩展性 ===
图 <math>G</math> 的顶点扩展性 <math>h_{\text{out}}(G)</math> 定义为

: <math>h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}</math>

此处 <math>\partial_{\text{out}}(S) := \{v \not\in S \mid \exists u \in S: \{u,v\} \in E\}</math> 是集合 <math>S</math> 的外边缘<ref name="BobkovHoudre2">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref>。顶点扩展性有一种变体，称作「唯一邻点扩展性」（{{lang|en|unique neighbor expansion}}），在这里 <math>\partial_{\text{out}}(S) := \{v \not\in S \mid \exists! u \in S: \{u,v\} \in E\}</math><ref name="AlonCapalbo2">{{harvtxt|Alon|Capalbo|2002}}</ref>。

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

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

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

: <math>h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).</math>

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

=== Cheeger不等式 ===
对于''d''-正则图，Dodziuk{{Sfn|Dodziuk|1984}}和[[Noga Alon|Alon]]、[[Vitali Milman|Milman]]{{Sfn|Alon|Spencer|2011}} 证明了

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

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

== 注解 ==
{{Reflist}}

==参考来源==
{{Refbegin|colwidth=25em}}
''' 教科书和文献综述 '''
* {{cite book|title=The Probabilistic Method|first1=N.|last1=Alon|first2=Joel H.|last2=Spencer|publisher=John Wiley & Sons|year=2011|edition=3rd|chapter=9.2. Eigenvalues and Expanders|ref=harv}}
* {{Citation|last=Chung|first=Fan R. K.|title=Spectral Graph Theory|series=CBMS Regional Conference Series in Mathematics|volume=92|publisher=[[American Mathematical Society]]|year=1997|isbn=0-8218-0315-8}}
* {{Citation|first1=Guiliana|last1=Davidoff|first2=Peter|last2=Sarnak|first3=Alain|last3=Valette|title=Elementary number theory, group theory and Ramanujan graphs|publisher=[[Cambridge University Press]]|series=LMS student texts|volume=55|year=2003|isbn=0-521-53143-8}}
* {{Citation|first1=Shlomo|last1=Hoory|first2=Nathan|last2=Linial|first3=Avi|last3=Widgerson|title=Expander graphs and their applications|journal=Bulletin (New series) of the American Mathematical Society|volume=43|issue=4|pages=439–561|url=http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf|year=2006|doi=10.1090/S0273-0979-06-01126-8|accessdate=2017-08-16|archive-date=2021-01-26|archive-url=https://web.archive.org/web/20210126211027/https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf|dead-url=no}}
* {{Citation|first1=Mike|last1=Krebs|first2=Anthony|last2=Shaheen|title=Expander families and Cayley graphs: A beginner's guide|publisher=Oxford University Press|year=2011|isbn=0-19-976711-4}}
''' 研究论文'''
* {{Citation|last1=Ajtai|first1=M.|last2=Komlós|first2=J.|last3=Szemerédi|first3=E.|chapter=An O(n log n) sorting network|title=Proceedings of the 15th Annual ACM Symposium on Theory of Computing|pages=1–9|year=1983|doi=10.1145/800061.808726|isbn=0-89791-099-0}}
* {{Citation|first1=M.|last1=Ajtai|first2=J.|last2=Komlós|first3=E.|last3=Szemerédi|title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing|pages=132–140|year=1987|work=ACM|doi=10.1145/28395.28410|isbn=0-89791-221-7}}
* {{Cite book|last1=Alon|first1=N.|last2=Capalbo|first2=M.|doi=10.1109/SFCS.2002.1181884|chapter=Explicit unique-neighbor expanders|title=The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings|url=https://archive.org/details/43rdannualieeesy0000symp|pages=[https://archive.org/details/43rdannualieeesy0000symp/page/73 73]|year=2002|isbn=0-7695-1822-2|pmid=|pmc=}}
* {{Citation|last1=Bobkov|first1=S.|last2=Houdré|first2=C.|last3=Tetali|first3=P.|title=λ<sub>∞</sub>, vertex isoperimetry and concentration|journal=Combinatorica|volume=20|issue=2|year=2000|doi=10.1007/s004930070018|pages=153–172}}.
* {{Citation|last=Dinur|first=Irit|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|year=2007|doi=10.1145/1236457.1236459|pages=12–es}}.
* {{Citation|first=D.|last=Gillman|title=A Chernoff Bound for Random Walks on Expander Graphs|journal=SIAM Journal on Computing|volume=27|issue=4,|pages=1203–1220|year=1998|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/S0097539794268765}}
* {{Citation|first=Oded|last=Goldreich|title=Basic Facts about Expander Graphs|journal=Studies in Complexity and Cryptography|year=2011|pages=451–464|doi=10.1007/978-3-642-22670-0_30|ref=harv}}
* {{Citation|first=Omer|last=Reingold|title=Undirected connectivity in log-space|journal=Journal of the ACM|year=2008|volume=55|issue=4|pages=Article 17, 24 pages|doi=10.1145/1391289.1391291}}
* {{Citation|first=Amir|last=Yehudayoff|title=Proving expansion in three steps|journal=ACM SIGACT News|year=2012|volume=43|issue=3|pages=67–84|doi=10.1145/2421096.2421115|ref=harv}}
{{Refend}}

== 外部链接 ==

* [http://www.ams.org/notices/200407/what-is.pdf Brief introduction in Notices of the American Mathematical Society] {{Wayback|url=http://www.ams.org/notices/200407/what-is.pdf |date=20190930072850 }}
* [http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf Introductory paper by Michael Nielsen] {{Wayback|url=http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf |date=20160817025506 }}
* [https://web.archive.org/web/20160629170338/http://www.math.ias.edu/~boaz/ExpanderCourse/ Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)]
* [http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html Lecture notes from a course on expanders (by Prahladh Harsha)] {{Wayback|url=http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html |date=20190128134541 }}
* [https://web.archive.org/web/20070523090323/http://www.yann-ollivier.org/specgraph/specgraph.html Definition and application of spectral gap]

*

{{DEFAULTSORT:Expander Graph}}
[[Category:图论]]