图自同构

在图论中，图自同构（graph automorphism）是保持自身的顶点与边的连接关系的对称。

正式地说，图 $G=(V,E)$ 的自同构是顶点集的置换 $\sigma$ ，使得顶点对 $(u,v)$ 组成一条边当且仅当 $(\sigma (u),\sigma (v))$ 也组成一条边。也就是说， $\sigma$ 是 $G$ 到自身的图同构。自同构的这个定义对有向图和无向图都适用。两个自同构的复合仍是自同构，并且给定一个图，其所有自同构的集合在复合运算下构成群，称为这个图的自同构群。反过来，根据Frucht定理，所有群都可以表示成连通图的自同构群^[1]^[2]。

计算复杂度

构造自同构群至少与图同构问题一样难（在计算复杂度的意义下），图同构问题就是判定两个给定的图是否同构。因为， $G$ 与 $H$ 同构当且仅当 $G$ 与 $H$ 的不交并有一个自同构交换两个分支^[3]。事实上，仅仅是计算自同构的数目，就和图同构问题以多项式时间等价^[4]。

图自同构问题就是判定一个图是否有非平凡的自同构。它属于计算复杂度的NP类。与图同构问题类似，仍不知道是否有多项式时间的算法^[5]。对于顶点度有一个常数上限的图，相应的图自同构问题有多项式时间的算法^[3]。图自同构问题可以通过多项式时间的算法多对一归约成图同构问题，但反过来的归约是否存在仍不清楚^[4]^[6]^[7]。与之不同的是，对于某些特殊类型的自同构，相应问题的难度是知道的；例如判定是否存在无不动点的自同构是NP完全的，而计算这样的自同构的个数是#P完全的^[5]^[7]。

根据自同构定义的图族

不对称图是没有非平凡自同构的无向图。
对称图是每一对邻接的顶点都可以通过一个自同构变成任何其他一对邻接顶点的图。
反对称图是有一个顶点的置换 $\sigma$ 把边变成反方向的边的有向图，而且要求 $\sigma$ 是对合。

另见

代数图论

参考资料

^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
^ 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.
^ ^3.0 ^3.1 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.
^ ^4.0 ^4.1 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.
^ ^5.0 ^5.1 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.
^ 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
^ ^7.0 ^7.1 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

外部链接

埃里克·韦斯坦因 "Graph Automorphism"（页面存档备份，存于互联网档案馆）MathWorld

[1] Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.

[2] 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.

[Luks,_Eugene_M.-3] 3.0 ^3.1 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.

[Mathon,_R._(1979)-4] 4.0 ^4.1 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.

[Lubiw,_Anna_(1981)-5] 5.0 ^5.1 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.

[6] 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

[Jacobo-7] 7.0 ^7.1 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]