跳转到内容

代数图论：修订间差异

维基百科，自由的百科全书
以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
添加{{no footnotes}}标记到条目 (TW)
Changsu Wang（留言 | 贡献）
75次编辑
小 添加行内引用，优化图片排版
 
第1行： 第1行：
⚫
[[File:Petersen1 tiny.svg|缩略图|[[佩特森圖|佩特森图]]，一种高度对称的图。它的直径为2。其自同构群有120个元素，事实上就是[[对称群 (n次对称群)|对称群]]<math>S_5</math>。]]
{{no footnotes|time=2019-04-01T16:30:33+00:00}}
'''代数图论'''（algebraic graph theory）是用[[代数]]方法处理图论问题的数学分支。这不同于[[几何图论|几何]]、[[组合数学|组合]]或算法的方法。代数图论有三个主要分支，分别使用[[线性代数]]，使用[[群论]]，以及研究图不变量。
'''代数图论'''（algebraic graph theory）是用[[代数]]方法处理图论问题的数学分支。这不同于[[几何图论|几何]]、[[组合数学|组合]]或算法的方法。代数图论有三个主要分支，分别使用[[线性代数]]，使用[[群论]]，以及研究图不变量。


第5行： 第5行：


=== 使用线性代数 ===
=== 使用线性代数 ===
代数图论的第一个分支用线性代数来研究图，特别是研究图的[[邻接矩阵]]或[[拉普拉斯矩阵]]的[[特征分解|谱]]（这部分代数图论也被称为谱图理论）。以[[佩特森圖|佩特森图]]为例，邻接矩阵的谱为(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通过一些定理把谱的性质与图的其他性质联系起来。举一个简单的例子，对于直径为D的[[连通图]]，它的谱至少有D+1个不同的值。图的谱可用于分析网络的[[同步]]。
代数图论的第一个分支用线性代数来研究图，特别是研究图的[[邻接矩阵]]或[[拉普拉斯矩阵]]的[[特征分解|谱]]（这部分代数图论也被称为谱图理论）。以[[佩特森圖|佩特森图]]为例，邻接矩阵的谱为(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通过一些定理把谱的性质与图的其他性质联系起来。举一个简单的例子，对于直径为D的[[连通图]]，它的谱至少有D+1个不同的值<ref name="Biggs, Norman">Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8 </ref>。图的谱可用于分析网络的[[同步]]。


=== 使用群论 ===
=== 使用群论 ===
⚫
[[File:TruncatedTetrahedron.gif|缩略图|[[交错群]]<math>A_4</math>的[[凱萊圖|凯莱图]]，在三维空间中构成了[[截角四面體|截角四面体]]。]]
⚫
代数图论的第二个分支用群论来研究图，尤其是自同构群以及[[几何群论]]。重点是根据对称性对图进行分类，以及不同类别之间的包含关系。某些特殊类别的图足够少，可以把它们列举出来。根据Frucht定理，所以的群都可以表示成连通图的自同构群。另外，给定一个群，可以作出相应的[[凱萊圖|凯莱图]]，凯莱图有一些性质与群的结构相关。<gallery>

⚫
File:TruncatedTetrahedron.gif|[[交错群]]<math>A_4</math>的[[凱萊圖|凯莱图]]，在三维空间中构成了[[截角四面體|截角四面体]]。
⚫
代数图论的第二个分支用群论来研究图，尤其是自同构群以及[[几何群论]]。重点是根据对称性对图进行分类，以及不同类别之间的包含关系。某些特殊类别的图足够少，可以把它们列举出来。根据Frucht定理，所以的群都可以表示成连通图的自同构群<ref>R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949. </ref>。另外，给定一个群，可以作出相应的[[凱萊圖|凯莱图]]，凯莱图有一些性质与群的结构相关<ref name="Biggs, Norman"></ref>。
</gallery><gallery>

⚫
File:Petersen graph 3-coloring.svg|用三种颜色对佩特森图的顶点进行着色。根据[[色多项式]]，有120种3着色。
</gallery>代数图论的第二个分支与第一个分支有联系，因为图的对称性在图的谱中也有反映。尤其是，对于高度对称的图，例如佩特森图，不同的特征值的数目很少（佩特森图有3个不同的特征值，在直径相等的图中是最少的）。凯莱图的谱与群的结构直接相关，尤其是与[[特徵標理論|不可约特征标]]相关。
代数图论的第二个分支与第一个分支有联系，因为图的对称性在图的谱中也有反映。尤其是，对于高度对称的图，例如佩特森图，不同的特征值的数目很少<ref name="Biggs, Norman"></ref>（佩特森图有3个不同的特征值，在直径相等的图中是最少的）。凯莱图的谱与群的结构直接相关，尤其是与[[特徵標理論|不可约特征标]]相关<ref name="Biggs, Norman"></ref><ref>Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Grötschel, M; Lovász, L, Handbook of Combinatorics, Elsevier </ref>。
<gallery>
⚫
File:Petersen1 tiny.svg|[[佩特森圖|佩特森图]]，一种高度对称的图。它的直径为2。其自同构群有120个元素，事实上就是[[对称群 (n次对称群)|对称群]]<math>S_5</math>。
</gallery>
=== 研究图不变量 ===
=== 研究图不变量 ===
⚫
[[File:Petersen graph 3-coloring.svg|缩略图|用三种颜色对佩特森图的顶点进行着色。根据[[色多项式]]，有120种3着色。]]
最后，代数图论的第三个分支研究图不变量的代数性质，尤其是[[色多项式]]、Tutte多项式与扭结不变量。例如，图的色多项式计算了[[图着色问题|顶点着色]]的个数。佩特森图的色多项式为<math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>。这意味着佩特森图不能用1种或2种颜色着色，但可以用3种颜色着色，且着色方式有120种。代数图论的这一领域的许多工作都是为了证明[[四色定理]]而启发。可是仍然有许多未解决的问题，例如如何判定两个图的色多项式相同，以及如何判定一个多项式是不是某个图的色多项式。
最后，代数图论的第三个分支研究图不变量的代数性质，尤其是[[色多项式]]、Tutte多项式与扭结不变量。例如，图的色多项式计算了[[图着色问题|顶点着色]]的个数。佩特森图的色多项式为<math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math><ref name="Biggs, Norman"></ref>。这意味着佩特森图不能用1种或2种颜色着色，但可以用3种颜色着色，且着色方式有120种。代数图论的这一领域的许多工作都是为了证明[[四色定理]]而启发。可是仍然有许多未解决的问题，例如如何判定两个图的色多项式相同，以及如何判定一个多项式是不是某个图的色多项式。


== 另见 ==
== 另见 ==
第27行： 第25行：


== 参考资料 ==
== 参考资料 ==
<references/>

* R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
* Godsil, Chris; Royle, Gordon (2001), ''Algebraic Graph Theory'', Graduate Texts in Mathematics, '''207''', New York: Springer-Verlag.
* Godsil, Chris; Royle, Gordon (2001), ''Algebraic Graph Theory'', Graduate Texts in Mathematics, '''207''', New York: Springer-Verlag.


2019年4月5日 (五) 07:24的最新版本

佩特森图，一种高度对称的图。它的直径为2。其自同构群有120个元素，事实上就是对称群。

代数图论（algebraic graph theory）是用代数方法处理图论问题的数学分支。这不同于几何、组合或算法的方法。代数图论有三个主要分支，分别使用线性代数，使用群论，以及研究图不变量。

代数图论的分支

[编辑]

使用线性代数

[编辑]

代数图论的第一个分支用线性代数来研究图，特别是研究图的邻接矩阵或拉普拉斯矩阵的谱（这部分代数图论也被称为谱图理论）。以佩特森图为例，邻接矩阵的谱为(-2, -2, -2, -2, 1, 1, 1, 1, 1, 3)。通过一些定理把谱的性质与图的其他性质联系起来。举一个简单的例子，对于直径为D的连通图，它的谱至少有D+1个不同的值[1]。图的谱可用于分析网络的同步。

使用群论

[编辑]
交错群的凯莱图，在三维空间中构成了截角四面体。

代数图论的第二个分支用群论来研究图，尤其是自同构群以及几何群论。重点是根据对称性对图进行分类，以及不同类别之间的包含关系。某些特殊类别的图足够少，可以把它们列举出来。根据Frucht定理，所以的群都可以表示成连通图的自同构群[2]。另外，给定一个群，可以作出相应的凯莱图，凯莱图有一些性质与群的结构相关[1]。

代数图论的第二个分支与第一个分支有联系，因为图的对称性在图的谱中也有反映。尤其是，对于高度对称的图，例如佩特森图，不同的特征值的数目很少[1]（佩特森图有3个不同的特征值，在直径相等的图中是最少的）。凯莱图的谱与群的结构直接相关，尤其是与不可约特征标相关[1][3]。

研究图不变量

[编辑]
用三种颜色对佩特森图的顶点进行着色。根据色多项式，有120种3着色。

最后，代数图论的第三个分支研究图不变量的代数性质，尤其是色多项式、Tutte多项式与扭结不变量。例如，图的色多项式计算了顶点着色的个数。佩特森图的色多项式为[1]。这意味着佩特森图不能用1种或2种颜色着色，但可以用3种颜色着色，且着色方式有120种。代数图论的这一领域的许多工作都是为了证明四色定理而启发。可是仍然有许多未解决的问题，例如如何判定两个图的色多项式相同，以及如何判定一个多项式是不是某个图的色多项式。

另见

[编辑]

参考资料

[编辑]
  1. ^ 1.0 1.1 1.2 1.3 1.4 Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
  2. ^ R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
  3. ^ 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.
检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=代数图论&oldid=53886911”