跳转到内容

英文维基 | 中文维基 | 日文维基 | 草榴社区

用户:Nnn009nnn/Sandbox 1

维基百科,自由的百科全书
这是维基百科用户尝试创建页面的地方。这不是一个百科全书条目。

en:Expander_graph

组合数论中,扩展图(英语:Expander graph)是一种具有强连通性质的疏松图,具体而言,看可用边、顶点或图谱扩展性(expansion)三种方式定义。扩展图的构造问题引导了多个数学分支上的研究,它还在计算复杂性理论计算机网络设计和编码理论上有诸多应用[1]

定义

[编辑]

简而言之,扩展图是一个有限无向多重图,其中每一组不“太大”的顶点均具有“很大”的边界(boundary)。不同的具体定义给出了不同种类的扩展图,下文将讨论边扩展图、顶点扩展图和谱扩展图(spectral expander)三个概念。

非连通图不是扩展图,因为每一个连通分量都没有边界——分量周围没有边进出,每一个连通图都是扩展图,只是他们的扩展性强弱不同。完全图具有最强的扩展性,但却很稠密(dense)。一个好的扩展图应具有强扩展性,并且顶点度数较小。

边扩展度

[编辑]

包含 个顶点的图 的边扩展度 定义为

其中 为子集 的边界。

注意在此一定义中,最小值取于所有非空、但包含不超过 个顶点的子集[2]

顶点扩展度

[编辑]

图 G 的顶点扩展度 定义为

此处 是集合 的外边缘,即所有不在 中但与一个 中的顶点相邻的顶点[3]。顶点扩展度这一概念的一个变体称作“唯一邻点扩展度”(unique neighbor expansion),在这里 指全部仅有一个相邻顶点在 中的顶点[4]

脚注

[编辑]

参考来源

[编辑]

教科书和文献综述

研究论文

外部连结

[编辑]