代数图论(algebraic graph theory)是用代数方法处理图论问题的数学分支。这不同于、组合或算法的方法。代数图论有三个主要分支,分别使用线性代数,使用群论,以及研究图不变量。
![image](https://www.wiki2.zh-cn.nina.az/image/aHR0cHM6Ly93d3cud2lraTIuemgtY24ubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODVMemt4TDFCbGRHVnljMlZ1TVY5MGFXNTVMbk4yWnk4eU1qQndlQzFRWlhSbGNuTmxiakZmZEdsdWVTNXpkbWN1Y0c1bi5wbmc=.png)
代数图论的分支
使用线性代数
代数图论的第一个分支用线性代数来研究图,特别是研究图的(邻接矩阵)或(拉普拉斯矩阵)的(谱)(这部分代数图论也被称为谱图理论)。以(佩特森图)为例,邻接矩阵的谱为(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通过一些定理把谱的性质与图的其他性质联系起来。举一个简单的例子,对于直径为D的连通图,它的谱至少有D+1个不同的值。图的谱可用于分析网络的同步。
使用群论
![image](https://www.wiki2.zh-cn.nina.az/image/aHR0cHM6Ly93d3cud2lraTIuemgtY24ubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekJtTDFSeWRXNWpZWFJsWkZSbGRISmhhR1ZrY205dUxtZHBaaTh5TWpCd2VDMVVjblZ1WTJGMFpXUlVaWFJ5WVdobFpISnZiaTVuYVdZPS5naWY=.gif)
代数图论的第二个分支用群论来研究图,尤其是自同构群以及(几何群论)。重点是根据对称性对图进行分类,以及不同类别之间的包含关系。某些特殊类别的图足够少,可以把它们列举出来。根据Frucht定理,所以的群都可以表示成连通图的自同构群。另外,给定一个群,可以作出相应的(凯莱图),凯莱图有一些性质与群的结构相关。
代数图论的第二个分支与第一个分支有联系,因为图的对称性在图的谱中也有反映。尤其是,对于高度对称的图,例如佩特森图,不同的特征值的数目很少(佩特森图有3个不同的特征值,在直径相等的图中是最少的)。凯莱图的谱与群的结构直接相关,尤其是与(不可约特征标)相关。
研究图不变量
![image](https://www.wiki2.zh-cn.nina.az/image/aHR0cHM6Ly93d3cud2lraTIuemgtY24ubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODVMemt3TDFCbGRHVnljMlZ1WDJkeVlYQm9Yek10WTI5c2IzSnBibWN1YzNabkx6SXlNSEI0TFZCbGRHVnljMlZ1WDJkeVlYQm9Yek10WTI5c2IzSnBibWN1YzNabkxuQnVadz09LnBuZw==.png)
最后,代数图论的第三个分支研究图不变量的代数性质,尤其是(色多项式)、Tutte多项式与扭结不变量。例如,图的色多项式计算了(顶点着色)的个数。佩特森图的色多项式为。这意味着佩特森图不能用1种或2种颜色着色,但可以用3种颜色着色,且着色方式有120种。代数图论的这一领域的许多工作都是为了证明(四色定理)而启发。可是仍然有许多未解决的问题,例如如何判定两个图的色多项式相同,以及如何判定一个多项式是不是某个图的色多项式。
另见
- 谱图理论
- (代数组合学)
- (代数连通度)
- (邻接矩阵)
参考资料
- Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press,
- R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
- Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Grötschel, M; Lovász, L, Handbook of Combinatorics, Elsevier
- Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, New York: Springer-Verlag.
維基百科,wiki,書籍,書籍,圖書館,文章,文章,閱讀,下載,免費下載,免費下載,MP3,視頻,MP4,3GP,JPG,JPG,JPEG,JPEG,GIF,PNG,PNG,圖片,音樂,音樂,音樂,歌曲,電影,電影,書籍,書籍,遊戲,遊戲,遊戲,遊戲,手機,電話,Android,iOS,Apple,手機,三星,iPhone,Xiomi,xiaomi, 小米,Redmi,Honor,Oppo,Nokia,Sonya,MI,個人電腦,網絡,電腦