power#

返回图的指定幂次。

一个简单图 \(G\) 的 \(k\) 次幂，记为 \(G^k\)，是一个与 \(G\) 具有相同节点集合的图。在 \(G^k\) 中，两个不同的节点 \(u\) 和 \(v\) 相邻当且仅当它们在 \(G\) 中的最短路径距离不大于 \(k\)。

参数:

G图: 一个 NetworkX 简单图对象。
k正整数: 计算图 G 的幂次。

返回:

NetworkX 简单图: 图 G 的 k 次幂。

引发:

ValueError: 如果指数 k 不是正数。
NetworkXNotImplemented: 如果 G 不是一个简单图。

说明

“幂图”的定义来自 Bondy 和 Murty 的《图论》（Graph Theory）练习 3.1.6 [1]。

参考文献

[1]

1. Bondy, U. S. R. Murty，《图论》（Graph Theory）。Springer，2008。

示例

连续取幂时，边的数量不会减少

>>> G = nx.path_graph(4)
>>> list(nx.power(G, 2).edges)
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
>>> list(nx.power(G, 3).edges)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

一个具有 n 个节点的环图的 k 次幂是具有 n 个节点的完全图，如果 k 不小于 n // 2。

>>> G = nx.cycle_graph(5)
>>> H = nx.complete_graph(5)
>>> nx.is_isomorphic(nx.power(G, 2), H)
True
>>> G = nx.cycle_graph(8)
>>> H = nx.complete_graph(8)
>>> nx.is_isomorphic(nx.power(G, 4), H)
True