power

power(G, k)

返回指定幂次的图。

简单图 \(G\) 的第 \(k\) 次幂，记作 \(G^k\)，是一个具有相同节点集的图，其中两个不同的节点 \(u\) 和 \(v\) 在 \(G^k\) 中相邻当且仅当 \(G\) 中 \(u\) 和 \(v\) 之间的最短路径距离不超过 \(k\)。

Parameters:

G图

一个 NetworkX 简单图对象。

k正整数

要提升图 G 的幂次。

Returns:

NetworkX 简单图

G 的 k 次幂。

Raises:

ValueError

如果指数 k 不是正数。

NetworkXNotImplemented

如果 G 不是简单图。

Notes

这个“幂图”的定义来自 Bondy 和 Murty 所著的《图论》中的练习 3.1.6 [1]。

References

[1]

10. 1. Bondy, U. S. R. Murty, Graph Theory. Springer, 2008.

Examples

当连续取幂时，边的数量永远不会减少：

>>> 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)]

如果 k 至少为 n // 2 ，则具有 n 个节点的循环图的第 k 次幂是完全图：

>>> 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