跳转到内容

扩展图

维基百科,自由的百科全书

组合数学中,扩展图(英语: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.

参考来源

教科书和文献综述

研究论文

外部链接