扩展图
在组合数学中,扩展图(英語:)是一种具有强连通性质的稀疏图,可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究,并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用[1]。
定义
对于有限、无向、连通的多重图,扩展性是一种能够衡量其连通强弱的指标。直观而言,扩展性较强意味着图中任何「不太大」的顶点集均有较大的边界,也就是说集合内外的交互很强。
连通图的扩展性有的弱,有的强。例如道路的扩展性很弱,而完全图的扩展性最强。可以看出,稠密图比稀疏图更“容易”具备强扩展性。但人们希望构造一类鱼与熊掌兼得的图:既能保持稀疏性,又具备很强的扩展性。具备这样“矛盾”属性的图就是一张扩展图;矛盾对立越深,扩展图越优良。
用数学语言表达如下:若一张图图有 个顶点、最大度为 、扩展性为 ,那么就称它为-扩展图。 越小(即图越稀疏)且 越大(即扩展性越强),则扩展图的性质越优异。
作为扩展图定义中的关键参数之一,“扩展性”的精确概念可用不同方式来量化。下文将讨论边扩展性、顶点扩展性和谱扩展性三种量化方式。
三种扩展性度量之间的关系
上面定义的三种量化方式虽然形式上有差别,但在本质上相互联系。对于d-正则图,我们有
因此,当度是常数时,前两种量化方式并无实质区别。
注解
- Hoory,Linial & Widgerson (2006)
- Definition 2.1 in Hoory,Linial & Widgerson (2006)
- Bobkov,Houdré & Tetali (2000)
- Alon & Capalbo (2002)
- cf. Section 2.3 in Hoory,Linial & Wigderson (2006)
- Dodziuk 1984.
- Alon & Spencer 2011.
参考来源
教科书和文献综述
- Alon, N.; Spencer, Joel H. . 3rd. John Wiley & Sons. 2011.
- Chung, Fan R. K., , CBMS Regional Conference Series in Mathematics 92, American Mathematical Society, 1997, ISBN 0-8218-0315-8
- Davidoff, Guiliana; Sarnak, Peter; Valette, Alain, , LMS student texts 55, Cambridge University Press, 2003, ISBN 0-521-53143-8
- Hoory, Shlomo; Linial, Nathan; Widgerson, Avi, (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, , Oxford University Press, 2011, ISBN 0-19-976711-4
研究论文
- Ajtai, M.; Komlós, J.; Szemerédi, E., , : 1–9, 1983, ISBN 0-89791-099-0, doi:10.1145/800061.808726
- Ajtai, M.; Komlós, J.; Szemerédi, E., , ACM, 1987: 132–140, ISBN 0-89791-221-7, doi:10.1145/28395.28410
- Alon, N.; Capalbo, M. . . 2002: 73. ISBN 0-7695-1822-2. doi:10.1109/SFCS.2002.1181884.
- Bobkov, S.; Houdré, C.; Tetali, P., , Combinatorica, 2000, 20 (2): 153–172, doi:10.1007/s004930070018.
- Dinur, Irit, , Journal of the ACM, 2007, 54 (3): 12–es, doi:10.1145/1236457.1236459.
- Gillman, D., , SIAM Journal on Computing (Society for Industrial and Applied Mathematics), 1998, 27 (4,): 1203–1220, doi:10.1137/S0097539794268765
- Goldreich, Oded, , Studies in Complexity and Cryptography, 2011: 451–464, doi:10.1007/978-3-642-22670-0_30
- Reingold, Omer, , Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
- Yehudayoff, Amir, , ACM SIGACT News, 2012, 43 (3): 67–84, doi:10.1145/2421096.2421115
外部链接
- Brief introduction in Notices of the American Mathematical Society
- Introductory paper by Michael Nielsen
- Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
- Lecture notes from a course on expanders (by Prahladh Harsha)
- Definition and application of spectral gap
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.