膨胀图族的锯齿积构造分析研究 数学与应用数学专业VIP专享VIP免费

目录第1章膨胀图………………………………………………………2第2章G=Z\s\up7(8)群的概念…………………………………………2第3章邻接算子………………………………………………3第4章CAYLEY图介绍……………………………………………3第5章锯齿积………………………………………………………4第5．1节的来源……………………………………………4第5．2节一个实际的膨胀图族…………………………………6摘要在组合学中，膨胀图是一个具有强连通性的稀疏图，由顶点，边和频谱扩展可以确定．膨胀图的发展进一步推动了计算机网络的发展，在设计算法，错误校正码等许多方面都取得不少突破．单个膨胀图的用处并不大，人们更多的是对一族膨胀图进行研究．目前构造膨胀图族的主流方法有三种，本文中重点讨论的是锯齿积(Zig-zagProduct)构造．Incombinatorics,anexpandergraphisasparsegraphthathasstrongconnectivityproperties,quantifiedusingvertex,edgeorspectralexpansionasdescribedbelow．Expanderconstructionshavespawnedresearchinpureandappliedmathematics,withseveralapplicationstocomplexitytheory,designofrobustcomputernetworks,andthetheoryoferror-correctingcodes．Therearethreegeneralstrategiesforconstructingfamiliesofexpandergraphs．[11]Thefirststrategyisalgebraicandgroup-theoretic,thesecondstrategyisanalyticandusesadditivecombinatorics,andthethirdstrategyiscombinatorialandusesthezig-zagandrelatedgraphproducts．NogaAlonshowedthatcertaingraphsconstructedfromfinitegeometriesarethesparsestexamplesofhighlyexpandinggraphs．关键词膨胀图(ExpanderGraph),锯齿积(Zig-zagProduct)前言目前，学术界对膨胀图及锯齿积进行了大量的研究和实践，取得了一批具有启发性，建设性的成果，为用锯齿积构造膨胀图族构建了完善的理论参考．本段对国内外部分学者的有关研究进行了梳理和总结．膨胀图是一个具有强连通性的稀疏图．每一个连通图都是一个膨胀图．但是，不同的连通图具有不同的膨胀参数，例如点膨胀[4]，边膨胀[7]，谱膨胀[7]．膨胀图的发展进一步加深了对数学与应用数学的研究．最初研究膨胀图的动机是建立稳固的节约成本的网络，目前膨胀图在计算科学领域有大量应用，在设计算法，错误校正码[7]，提取器，伪随机数生成器，排序网络[1]和稳固计算机网络方面都取得了不少突破．它们同样被使用来证明复杂计算理论中的许多重要结论，例如SL=L[10]和PCP定理[5]．在密码系统中，膨胀图族被用来构造散列函数．下面的一些膨胀图族的特性在许多领域都被证明很有用，例如膨胀图混合引理(Expandermixinglemma)，膨胀图回路抽样(Expanderwalksampling)[2][6]，脑图膨胀特性．目前构造一族膨胀图的主流方法有三种[11]．第一种方法是利用代数和群理论构造，第二种通过分析法和加法论来构造，第三种即为本文中将要证明的锯齿积构造法，NogaAlon证明了有限几何学上构造的一族特定的图即为膨胀图族的一个极佳的例子[3]．锯齿积是由Reingold，Vadhan&Wigderson[8]首次提出的．在2002年，OmerReingold，SalilVadhan和AviWigderson给出了一个简单明确的构造一族有固定度数的膨胀图族的方法．构造法是迭代的，并且需要一个满足相关条件的基础图．在每次迭代过程中，锯齿积被用来生成另一个保持原有性质不变的图，通过不断迭代，最终生成一族膨胀图．再后来又被用来证明复杂计算理论中symmetriclogspace和logspace是相等的[9]．本文中重点描述的是如何通过给定的基础图来构造一族膨胀图，并且验证构造过程是合理的．正文第1章膨胀图X=(V，E)为图，V为它的顶点集，E为它的边集．如果没有特别声明，总假定X是无圈的有限图．定义1．1X=(V，E)为有限图，记为X的膨胀常数(还可以称为等周常数或Cheeger常数)．这里AV，A为A的邻居，也就是不在A中，但与A中的点相连接的那些点．定义1．2X为正则有限图(即每个顶点的度为恒定的k)．对于，X称为-膨胀图如果．对于连通图而言，若顶点数为，取，那么对任何非空的且，总有，因此膨胀图的定义对单个图而言意义并不十分大．人们...