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

参数:

G, H: NetworkX图

将进行模块积运算的图。

返回:

M: NetworkX图

G和H的模块积。

引发:

NetworkXNotImplemented

如果G不是简单图。

注意

模块积在[1]中定义，最初被引入时称为弱模块积。

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

参考文献

[1]

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

[2]

H. G. Barrow and R. M. Burstall, “子图同构、关系结构匹配和极大团”, 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, “将同构和同构入口问题归约到寻找图非密度的问题。” Proc. Third All-Union Conference on Problems of Theoretical Cybernetics. 1974.

示例

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