R igraph 手册页

自同构 {igraph}

R 文档

自同构的数量

描述

计算图的自同构数量，即与自身同构的数量。

用法

automorphisms(graph, colors, sh = c("fm", "f", "fs", "fl", "flm", "fsm"))

参数

图	输入图，被视为无向图。
颜色	图中各个顶点的颜色；只有颜色相同的顶点才允许在自同构中相互匹配。如果省略，igraph 将使用顶点的 color 属性，或者，如果没有此类顶点属性，则简单地假设所有顶点都具有相同的颜色。如果该图具有 color 顶点属性，但您不想使用它，请显式传递 NULL。
sh	BLISS 算法的分裂启发式方法。可能的值为：‘f’：第一个非单例单元格，‘fl’：第一个最大的非单例单元格，‘fs’：第一个最小的非单例单元格，‘fm’：第一个最大非平凡连通的非单例单元格，‘flm’：第一个最大的最大非平凡连通的非单例单元格，‘fsm’：第一个最小的最大非平凡连通的非单例单元格。

详细信息

图的自同构是其顶点的一种排列，该排列将图映射到自身。

此函数使用 BLISS 算法计算图的自同构数量。另请参见 BLISS 主页 http://www.tcs.hut.fi/Software/bliss/index.html。如果您需要自同构本身，请使用 automorphism_group 来获得自同构群的紧凑表示。

值

一个命名列表，包含以下成员

group_size	输入图的自同构群的大小，作为一个字符串。如果 igraph 是使用 GMP 库编译的，则此数字是精确的，否则是近似的。
nof_nodes	搜索树中的节点数。
nof_leaf_nodes	搜索树中的叶节点数。
nof_bad_nodes	坏节点的数量。
nof_canupdates	Canrep 更新的数量。
max_level	最大级别。

作者

Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) 为 BLISS，Gabor Csardi csardi.gabor@gmail.com 为 igraph 胶水代码和本手册页。

参考

Tommi Junttila 和 Petteri Kaski：工程一种用于大型稀疏图的高效规范标签工具，《第九届算法工程和实验研讨会和第四届分析算法与组合学研讨会论文集》。2007。

参见

canonical_permutation, permute, 以及 automorphism_group 用于所有自同构的紧凑表示

示例

## A ring has n*2 automorphisms, you can "turn" it by 0-9 vertices
## and each of these graphs can be "flipped"
g <- make_ring(10)
automorphisms(g)

## A full graph has n! automorphisms; however, we restrict the vertex
## matching by colors, leading to only 4 automorphisms
g <- make_full_graph(4)
automorphisms(g, colors=c(1,2,1,2))

---