用户:Nnn009nnn/Sandbox 1

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

en:Expander_graph

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

定义

编辑

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

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

边扩展度

编辑

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

 

其中   为子集   的边界。

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

顶点扩展度

编辑

图 G 的顶点扩展度   定义为

 

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

脚注

编辑

参考来源

编辑

教科书和文献综述

研究论文

外部连结

编辑