图自同构 - 维基百科,自由的百科全书
此條目翻譯品質不佳。 |
在图论中,图自同构(graph automorphism)是保持自身的顶点与边的连接关系的对称。
正式地说,图的自同构是顶点集的置换,使得顶点对组成一条边当且仅当也组成一条边。也就是说,是到自身的图同构。自同构的这个定义对有向图和无向图都适用。两个自同构的复合仍是自同构,并且给定一个图,其所有自同构的集合在复合运算下构成群,称为这个图的自同构群。反过来,根据Frucht定理,所有群都可以表示成连通图的自同构群[1][2]。
计算复杂度
[编辑]构造自同构群至少与图同构问题一样难(在计算复杂度的意义下),图同构问题就是判定两个给定的图是否同构。因为,与同构当且仅当与的不交并有一个自同构交换两个分支[3]。事实上,仅仅是计算自同构的数目,就和图同构问题以多项式时间等价[4]。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/220px-Petersen1_tiny.svg.png)
图自同构问题就是判定一个图是否有非平凡的自同构。它属于计算复杂度的NP类。与图同构问题类似,仍不知道是否有多项式时间的算法[5]。对于顶点度有一个常数上限的图,相应的图自同构问题有多项式时间的算法[3]。图自同构问题可以通过多项式时间的算法多对一归约成图同构问题,但反过来的归约是否存在仍不清楚[4][6][7]。与之不同的是,对于某些特殊类型的自同构,相应问题的难度是知道的;例如判定是否存在无不动点的自同构是NP完全的,而计算这样的自同构的个数是#P完全的[5][7]。
根据自同构定义的图族
[编辑]另见
[编辑]参考资料
[编辑]- ^ 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