德布鲁因图

德布鲁因图是标记图，表示字符串的重叠。

用法

make_de_bruijn_graph(m, n)

de_bruijn_graph(...)

参数

m

整数标量，字母表的大小。参见以下详细信息。

n

整数标量，标签的长度。参见以下详细信息。

...

传递给 make_de_bruijn_graph()。

值

一个图对象。

详细信息

德布鲁因图表示字符串之间的关系。 使用 m 个字母的字母表，并考虑长度为 n 的字符串。 一个顶点对应于每个可能的字符串，并且存在从顶点 v 到顶点 w 的有向边，如果 v 的字符串可以通过删除其第一个字母并在其后附加一个字母来转换为 w 的字符串。

请注意，该图将具有 m 的 n 次方个顶点，甚至更多的边，因此您可能不想为 m 和 n 提供太大的数字。

德布鲁因图具有一些有趣的属性，请参阅其他来源，例如 Wikipedia 了解详细信息。

参见

make_kautz_graph()，make_line_graph()

作者

Gabor Csardi csardi.gabor@gmail.com

示例

# de Bruijn graphs can be created recursively by line graphs as well
g <- make_de_bruijn_graph(2, 1)
make_de_bruijn_graph(2, 2)
#> IGRAPH d29be59 D--- 4 8 -- De-Bruijn graph 2-2
#> + attr: name (g/c), m (g/n), n (g/n)
#> + edges from d29be59:
#> [1] 1->1 1->2 2->3 2->4 3->1 3->2 4->3 4->4
make_line_graph(g)
#> IGRAPH 2bb7f8b D--- 4 8 -- Line graph
#> + attr: name (g/c)
#> + edges from 2bb7f8b:
#> [1] 1->1 3->1 1->2 3->2 2->3 4->3 2->4 4->4