R igraph 手册页

girth {igraph}

R 文档

图的周长

描述

图的周长是其中最短圆的长度。

用法

girth(graph, circle = TRUE)

参数

图	输入图。它可以是有向图，但该算法会搜索无向环。
circle	逻辑标量，是否返回最短的环本身。

详细信息

当前的实现仅适用于无向图，有向图被视为无向图。循环边和多重边将被忽略。如果该图是森林（即无环），则返回零。

此实现基于 Alon Itai 和 Michael Rodeh：Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing, 1-10, 1977。此函数的第一个实现由 Keith Briggs 完成，感谢 Keith。

值

一个具有两个组件的命名列表

girth	整数常量，图的周长，如果图是无环的，则为 0。
circle	具有最短环中顶点 ID 的数值向量。

作者

Gabor Csardi csardi.gabor@gmail.com

参考

Alon Itai 和 Michael Rodeh：Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing, 1-10, 1977

示例

# No circle in a tree
g <- make_tree(1000, 3)
girth(g)

# The worst case running time is for a ring
g <- make_ring(100)
girth(g)

# What about a random graph?
g <- sample_gnp(1000, 1/1000)
girth(g)

---