modular_product

modular_product(G, H)

返回 G 和 H 的模积图。

G 和 H 的模积图是图 \(M = G \nabla H\)，由节点集 \(V(M) = V(G) \times V(H)\) 组成，这是 G 和 H 节点集的笛卡尔积。进一步地，M 包含边 ((u, v), (x, y))：

• 如果 u 在 G 中与 x 相邻且 v 在 H 中与 y 相邻，或者

• 如果 u 在 G 中与 x 不相邻且 v 在 H 中与 y 不相邻。

更正式地：

E(M) = {((u, v), (x, y)) | ((u, x) in E(G) and (v, y) in E(H)) or

((u, x) not in E(G) and (v, y) not in E(H))}

Parameters:

G, H: NetworkX 图

要计算模积的图。

Returns:

M: NetworkX 图

G 和 H 的模积图。

Raises:

NetworkXNotImplemented

如果 G 不是简单图。

Notes

模积 在 [1] 中定义，最初作为 弱模积 引入。

模积将 G 和 H 中计数同构子图的问题简化为在 M 中计数团的问题。由 M 中团的节点诱导的 G 和 H 的子图是同构的 [2] [3]。

References

[1]

R. Hammack, W. Imrich, 和 S. Klavžar, “Handbook of Product Graphs”, CRC Press, 2011.

[2]

H. G. Barrow 和 R. M. Burstall, “Subgraph isomorphism, matching relational structures and maximal cliques”, Information Processing Letters, vol. 4, issue 4, pp. 83-84, 1976, https://doi.org/10.1016/0020-0190(76)90049-1.

[3]

V. G. Vizing, “Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph.” Proc. Third All-Union Conference on Problems of Theoretical Cybernetics. 1974.

Examples

>>> G = nx.cycle_graph(4)
>>> H = nx.path_graph(2)
>>> M = nx.modular_product(G, H)
>>> list(M)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
>>> print(M)
Graph with 8 nodes and 8 edges