查看“︁图自同构”︁的源代码

{{rough translation}}
在[[图论]]中，'''图自同构'''（graph automorphism）是保持自身的[[顶点 (图论)|顶点]]与边的连接关系的对称。

正式地说，图<math>G=(V,E)</math>的自同构是[[顶点 (图论)|顶点]]集的[[置換|置换]]<math>\sigma</math>，使得顶点对<math>(u,v)</math>组成一条边当且仅当<math>(\sigma(u),\sigma(v))</math>也组成一条边。也就是说，<math>\sigma</math>是<math>G</math>到自身的[[图同构]]。自同构的这个定义对[[图 (数学)|有向图]]和[[無向圖|无向图]]都适用。两个自同构的复合仍是自同构，并且给定一个图，其所有自同构的集合在复合运算下构成[[群]]，称为这个图的[[自同构|自同构群]]。反过来，根据Frucht定理，所有群都可以表示成连通图的自同构群<ref>Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804. </ref><ref>Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987. </ref>。

== 计算复杂度 ==
构造自同构群至少与[[图同构问题]]一样难（在[[計算複雜性理論|计算复杂度]]的意义下），图同构问题就是判定两个给定的图是否同构。因为，<math>G</math>与<math>H</math>同构当且仅当<math>G</math>与<math>H</math>的不交并有一个自同构交换两个分支<ref name="Luks, Eugene M.">Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5. </ref>。事实上，仅仅是计算自同构的数目，就和图同构问题以多项式时间等价<ref name="Mathon, R. (1979)">Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8: 131–132. doi:10.1016/0020-0190(79)90004-8. </ref>。
[[File:Petersen1 tiny.svg|缩略图|[[佩特森圖|佩特森图]]的这种画法显示出其对称的一个[[子群]]，同构于[[二面體群|二面体群]]<math>D_5</math>，但这个图还有其他的对称性没有体现在这种画法中。例如，因为这个图是[[对称图|对称]]的，所有边都是等价的。]]
'''图自同构问题'''就是判定一个图是否有非平凡的自同构。它属于计算复杂度的[[NP (複雜度)|NP类]]。与图同构问题类似，仍不知道是否有[[多項式時間|多项式时间]]的算法<ref name="Lubiw, Anna (1981)">Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600. </ref>。对于[[顶点 (图论)|顶点]]度有一个常数上限的图，相应的图自同构问题有多项式时间的算法<ref name="Luks, Eugene M."></ref>。图自同构问题可以通过多项式时间的算法多对一归约成图同构问题，但反过来的归约是否存在仍不清楚<ref name="Mathon, R. (1979)"></ref><ref>Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287 </ref><ref name="Jacobo">Jacobo Torán, "On the hardness of graph isomorphism", SIAM Journal on Computing, vol. 33 (2004), no. 5, pp. 1093-1108, doi:10.1137/S009753970241096X </ref>。与之不同的是，对于某些特殊类型的自同构，相应问题的难度是知道的；例如判定是否存在无[[不动点]]的自同构是NP完全的，而计算这样的自同构的个数是[[#P完全]]的<ref name="Lubiw, Anna (1981)"></ref><ref name="Jacobo"></ref>。

<br />

== 根据自同构定义的图族 ==

* [[不对称图]]是没有非平凡自同构的无向图。
* [[对称图]]是每一对邻接的[[顶点 (图论)|顶点]]都可以通过一个自同构变成任何其他一对邻接顶点的图。
* [[反对称图]]是有一个顶点的置换<math>\sigma</math>把边变成反方向的边的有向图，而且要求<math>\sigma</math>是[[對合|对合]]。

== 另见 ==

* [[代数图论]]

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

== 外部链接 ==

* [[埃里克·韦斯坦因]][http://mathworld.wolfram.com/GraphAutomorphism.html "Graph Automorphism"]{{Wayback|url=http://mathworld.wolfram.com/GraphAutomorphism.html |date=20190402193638 }}[[MathWorld]]

[[Category:代数图论]]