跳到内容

自同构的数量

来源：R/topology.R
count_automorphisms.Rd

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

用法

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

参数

graph

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

colors

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

sh

BLISS 算法的分裂启发式方法。可能的值有：'f'：第一个非单例单元格，'fl'：第一个最大的非单例单元格，'fs'：第一个最小的非单例单元格，'fm'：第一个最大程度非平凡连接的非单例单元格，'flm'：第一个最大的最大程度非平凡连接的非单例单元格，'fsm'：第一个最小的最大程度非平凡连接的非单例单元格。

值

一个具有以下成员的命名列表

group_size

输入图的自同构群的大小，以字符串形式表示。如果 igraph 是使用 GMP 库编译的，则此数字是精确的，否则是近似的。

nof_nodes

搜索树中的节点数。

nof_leaf_nodes

搜索树中的叶节点数。

nof_bad_nodes

坏节点数。

nof_canupdates

canrep 更新的数量。

max_level

最大级别。

详细信息

图的自同构是其顶点的一种排列，它使图自身保持不变。

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

参考文献

Tommi Junttila 和 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(), 和 automorphism_group() 用于自同构的紧凑表示

其他图自同构: automorphism_group()

作者

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

count_automorphisms().

示例


## 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)
count_automorphisms(g)
#> $nof_nodes
#> [1] 6
#> 
#> $nof_leaf_nodes
#> [1] 4
#> 
#> $nof_bad_nodes
#> [1] 0
#> 
#> $nof_canupdates
#> [1] 1
#> 
#> $max_level
#> [1] 2
#> 
#> $group_size
#> [1] "20"
#> 

## A full graph has n! automorphisms; however, we restrict the vertex
## matching by colors, leading to only 4 automorphisms
g <- make_full_graph(4)
count_automorphisms(g, colors = c(1, 2, 1, 2))
#> $nof_nodes
#> [1] 5
#> 
#> $nof_leaf_nodes
#> [1] 3
#> 
#> $nof_bad_nodes
#> [1] 0
#> 
#> $nof_canupdates
#> [1] 1
#> 
#> $max_level
#> [1] 2
#> 
#> $group_size
#> [1] "4"
#>