random_regular_graph

random_regular_graph(d, n, seed=None)

返回一个包含 \(n\) 个节点的随机 \(d\)-正则图。

正则图是指每个节点具有相同数量邻居的图。

生成的图没有自环或平行边。

Parameters:

dint

每个节点的度数。

ninteger

节点数量。\(n \times d\) 的值必须是偶数。

seedinteger, random_state, 或 None (默认)

随机数生成状态的指示器。 参见 随机性 。

Raises:

NetworkXError

如果 \(n \times d\) 是奇数或 \(d\) 大于等于 \(n\)。

Notes

节点编号从 \(0\) 到 \(n - 1\)。

Kim 和 Vu 的论文 [2] 表明，当 \(d = O(n^{1 / 3 - \epsilon})\) 时，该算法以渐近均匀的方式从随机图空间中采样。

References

[1]

A. Steger 和 N. Wormald, 快速生成随机正则图, 概率与计算 8 (1999), 377-396, 1999. https://doi.org/10.1017/S0963548399003867

[2]

Jeong Han Kim 和 Van H. Vu, 生成随机正则图, 第三十五届 ACM 理论计算研讨会论文集, 圣地亚哥, CA, 美国, 第 213–222 页, 2003. http://portal.acm.org/citation.cfm?id=780542.780576