graphscope.nx.generators.harary_graph.hkn_harary_graph

graphscope.nx.generators.harary_graph.hkn_harary_graph(k, n, create_using=None)[源代码]

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

Harary图$H_{k,n}$是在给定节点连通度$k$和节点数量$n$的条件下，所需边数最少的图。

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

Parameters:

  • k (整数) – 生成图的节点连通度

  • n (整数) - 生成图包含的节点数量

  • create_using (NetworkX 图构造函数, 可选图类型) – 用于创建(默认为nx.Graph)。如果是图实例，则会在填充前被清空。

Returns:

Harary图 $H_{k,n}$。

Return type:

NetworkX 图

另请参阅

hnm_harary_graph

备注

该算法的时间复杂度为$O(kn)$。 其实现参考了文献[2]。

参考文献