hkn_harary_graph#
- hkn_harary_graph(k, n, create_using=None)[源码]#
返回具有给定节点连通性和节点数的 Harary 图。
Harary 图 \(H_{k,n}\) 是在给定节点连通性 \(k\) 和节点数 \(n\) 的情况下，使所需边数最小的图。
已知这个最小的边数是 ceil(\(kn/2\)) [1]。
- 参数:
- k: integer
生成图的节点连通性
- n: integer
生成图包含的节点数
- create_usingNetworkX 图构造函数, 可选 图类型
用于创建图 (default=nx.Graph)。如果是图实例，则在填充前清空。
- 返回:
- NetworkX 图
Harary 图 \(H_{k,n}\)。
另请参阅
备注
此算法以 \(O(kn)\) 的时间复杂度运行。它是根据参考文献 [2] 实现的。
参考文献
[1]Weisstein, Eric W. “Harary Graph.” 选自 MathWorld–A Wolfram Web Resource. https://mathworld.net.cn/HararyGraph.html。
[2]Harary, F. “The Maximum Connectivity of a Graph.” Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962.