hkn_harary_graph#

hkn_harary_graph(k, n, create_using=None)[source]#

返回具有给定节点连通性和节点数量的Harary图。

Harary图 \(H_{k,n}\) 是在给定节点连通性 \(k\) 和节点数量 \(n\) 的情况下，最小化边数所需的图。

已知这个最小的边数为 ceil(\(kn/2\)) [1]。

Parameters:

k: 整数: 生成图的节点连通性
n: 整数: 生成图要包含的节点数量
create_usingNetworkX图构造函数, 可选图类型: 用于创建的图类型（默认=nx.Graph）。如果是图实例，则在填充前清空。

Returns:

NetworkX图: Harary图 \(H_{k,n}\)。

See also

hnm_harary_graph

Notes

该算法运行时间为 \(O(kn)\)。它是通过遵循参考文献 [2] 实现的。

References

[1]

Weisstein, Eric W. “Harary Graph.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/HararyGraph.html.

[2]

Harary, F. “The Maximum Connectivity of a Graph.” Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962.