random_regular_graph

random_regular_graph(d, n, seed=None, *, create_using=None)

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

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

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

参数:

dint

每个节点的度。

ninteger

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

seedinteger, random_state 或 None (默认)

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

create_using图构造函数, 可选 (默认=nx.Graph)

要创建的图类型。如果是图实例，则在填充前会被清除。不支持多重图和有向图类型，它们会引发 NetworkXError。

引发:

NetworkXError

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

注意

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

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

参考文献

[1]

A. Steger and N. Wormald, Generating random regular graphs quickly, Probability and Computing 8 (1999), 377-396, 1999. https://doi.org/10.1017/S0963548399003867

[2]

Jeong Han Kim and Van H. Vu, Generating random regular graphs, Proceedings of the thirty-fifth ACM symposium on Theory of computing, San Diego, CA, USA, pp 213–222, 2003. http://portal.acm.org/citation.cfm?id=780542.780576