用户:Nnn009nnn/Sandbox 1
这是维基百科用户尝试创建页面的地方。这不是一个百科全书条目。 |
在组合数论中,扩展图(英语:Expander graph)是一种具有强连通性质的疏松图,具体而言,看可用边、顶点或图谱扩展性(expansion)三种方式定义。扩展图的构造问题引导了多个数学分支上的研究,它还在计算复杂性理论、计算机网络设计和编码理论上有诸多应用[1]。
定义
简而言之,扩展图是一个有限无向多重图,其中每一组不“太大”的顶点均具有“很大”的边界(boundary)。不同的具体定义给出了不同种类的扩展图,下文将讨论边扩展图、顶点扩展图和谱扩展图(spectral expander)三个概念。
非连通图不是扩展图,因为每一个连通分量都没有边界——分量周围没有边进出,每一个连通图都是扩展图,只是他们的扩展性强弱不同。完全图具有最强的扩展性,但却很稠密(dense)。一个好的扩展图应具有强扩展性,并且顶点度数较小。
边扩展度
包含 个顶点的图 的边扩展度 定义为
其中 为子集 的边界。
注意在此一定义中,最小值取于所有非空、但包含不超过 个顶点的子集[2]。
顶点扩展度
图 G 的顶点扩展度 定义为
此处 是集合 的外边缘,即所有不在 中但与一个 中的顶点相邻的顶点[3]。顶点扩展度这一概念的一个变体称作“唯一邻点扩展度”(unique neighbor expansion),在这里 指全部仅有一个相邻顶点在 中的顶点[4]。
脚注
- ^ Hoory,Linial & Widgerson (2006)
- ^ Definition 2.1 in Hoory,Linial & Widgerson (2006)
- ^ Bobkov,Houdré & Tetali (2000)
- ^ Alon & Capalbo (2002)
参考来源
教科书和文献综述
- Alon, N.; Spencer, Joel H. 9.2. Eigenvalues and Expanders. The Probabilistic Method 3rd. John Wiley & Sons. 2011.
- Chung, Fan R. K., Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92, American Mathematical Society, 1997, ISBN 0-8218-0315-8
- Davidoff, Guiliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory and Ramanujan graphs, LMS student texts 55, Cambridge University Press, 2003, ISBN 0-521-53143-8
- Hoory, Shlomo; Linial, Nathan; Widgerson, Avi, Expander graphs and their applications (PDF), Bulletin (New series) of the American Mathematical Society, 2006, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8
- Krebs, Mike; Shaheen, Anthony, Expander families and Cayley graphs: A beginner's guide, Oxford University Press, 2011, ISBN 0-19-976711-4
研究论文
- Ajtai, M.; Komlós, J.; Szemerédi, E., An O(n log n) sorting network, Proceedings of the 15th Annual ACM Symposium on Theory of Computing: 1–9, 1983, ISBN 0-89791-099-0, doi:10.1145/800061.808726
- Ajtai, M.; Komlós, J.; Szemerédi, E., Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, 1987: 132–140, ISBN 0-89791-221-7, doi:10.1145/28395.28410
- Alon, N.; Capalbo, M. Explicit unique-neighbor expanders. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002: 73. ISBN 0-7695-1822-2. doi:10.1109/SFCS.2002.1181884.
- Bobkov, S.; Houdré, C.; Tetali, P., λ∞, vertex isoperimetry and concentration, Combinatorica, 2000, 20 (2): 153–172, doi:10.1007/s004930070018.
- Dinur, Irit, The PCP theorem by gap amplification, Journal of the ACM, 2007, 54 (3): 12–es, doi:10.1145/1236457.1236459.
- Gillman, D., A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing (Society for Industrial and Applied Mathematics), 1998, 27 (4,): 1203–1220, doi:10.1137/S0097539794268765
- Goldreich, Oded, Basic Facts about Expander Graphs, Studies in Complexity and Cryptography, 2011: 451–464, doi:10.1007/978-3-642-22670-0_30
- Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
- Yehudayoff, Amir, Proving expansion in three steps, ACM SIGACT News, 2012, 43 (3): 67–84, doi:10.1145/2421096.2421115