Kautz 图

Kautz 图是标记图，表示字符串的重叠。

用法

make_kautz_graph(m, n)

kautz_graph(...)

参数

m

整数标量，字母表的大小。详见下文。

n

整数标量，标签的长度。详见下文。

...

传递给 make_kautz_graph()。

值

一个图对象。

详细信息

Kautz 图是一种标记图，顶点用长度为 n+1 的字符串标记，该字符串来自具有 m+1 个字母的字母表，并且限制字符串中每两个连续的字母必须不同。如果可以通过删除第一个字母并在其后附加一个字母将顶点 v 的字符串转换为顶点 w 的字符串，则存在从顶点 v 到另一个顶点 w 的有向边。

Kautz 图有一些有趣的属性，详见例如 Wikipedia。

参见

make_de_bruijn_graph(), make_line_graph()

作者

Gabor Csardi csardi.gabor@gmail.com，R 中的第一个版本由 Vincent Matossian 编写。

示例

make_line_graph(make_kautz_graph(2, 1))
#> IGRAPH dcb41c7 D--- 12 24 -- Line graph
#> + attr: name (g/c)
#> + edges from dcb41c7:
#>  [1]  5-> 1  9-> 1  5-> 2  9-> 2  6-> 3 10-> 3  6-> 4 10-> 4  1-> 5 11-> 5
#> [11]  1-> 6 11-> 6  2-> 7 12-> 7  2-> 8 12-> 8  3-> 9  7-> 9  3->10  7->10
#> [21]  4->11  8->11  4->12  8->12
make_kautz_graph(2, 2)
#> IGRAPH a93afb9 D--- 12 24 -- Kautz graph 2-2
#> + attr: name (g/c), m (g/n), n (g/n)
#> + edges from a93afb9:
#>  [1]  1-> 5  1-> 6  2-> 7  2-> 8  3-> 9  3->10  4->11  4->12  5-> 1  5-> 2
#> [11]  6-> 3  6-> 4  7-> 9  7->10  8->11  8->12  9-> 1  9-> 2 10-> 3 10-> 4
#> [21] 11-> 5 11-> 6 12-> 7 12-> 8