跳到内容

生成图的自同构群的集合

来源：R/topology.R
automorphism_group.Rd

计算图的自同构群的生成集合。

用法

automorphism_group(
  graph,
  colors = NULL,
  sh = c("fm", "f", "fs", "fl", "flm", "fsm"),
  details = FALSE
)

参数

graph

输入的图，被视为无向图。

colors

图中各个顶点的颜色；只有颜色相同的顶点才允许在自同构中相互匹配。如果省略，igraph 将使用顶点的 color 属性，或者，如果没有这样的顶点属性，则简单地假设所有顶点都具有相同的颜色。如果图具有 color 顶点属性但您不想使用它，请显式传递 NULL。

sh

BLISS 算法的分裂启发式方法。可能的值包括：“f”：第一个非单元素单元格，“fl”：第一个最大的非单元素单元格，“fs”：第一个最小的非单元素单元格，“fm”：第一个最大非平凡连接的非单元素单元格，“flm”：第一个最大的最大非平凡连接的非单元素单元格，“fsm”：第一个最小的最大非平凡连接的非单元素单元格。

details

指定是否在结果中提供有关 BLISS 内部机制的更多详细信息。

值

当 details 为 FALSE 时，返回形成输入图的自同构群的生成集合的顶点置换列表。当 details 为 TRUE 时，返回具有两个成员的命名列表

generators

返回生成器本身

info

有关 BLISS 内部机制的其他信息。有关更多详细信息，请参见 count_automorphisms()。

详细信息

图的自同构是其顶点的置换，它使图保持不变。图的自同构形成一个群，并且存在该群的一个子集（即一组置换），使得每个其他置换都可以表示为这些置换的组合。这些置换称为自同构群的生成集合。

此函数使用 BLISS 算法计算图的自同构的可能生成集合。另请参见 BLISS 主页：http://www.tcs.hut.fi/Software/bliss/index.html。计算出的生成集合不一定是最小的，并且可能取决于 BLISS 使用的分裂启发式方法。

参考文献

Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.

参见

canonical_permutation(), permute(), count_automorphisms()

其他图自同构：count_automorphisms()

作者

Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) for BLISS, Gabor Csardi csardi.gabor@gmail.com for the igraph glue code and Tamas Nepusz ntamas@gmail.com for this manual page.

automorphism_group().

示例


## A ring has n*2 automorphisms, and a possible generating set is one that
## "turns" the ring by one vertex to the left or right
g <- make_ring(10)
automorphism_group(g)
#> [[1]]
#> + 10/10 vertices, from 92a9ace:
#>  [1]  1 10  9  8  7  6  5  4  3  2
#> 
#> [[2]]
#> + 10/10 vertices, from 92a9ace:
#>  [1]  2  3  4  5  6  7  8  9 10  1
#>