subgraph - 子图同构和子图同构之间有什么区别？

Question

在我从事的项目之一中，主题isomorphism versus monomorphism came up。

一些背景知识:我不是图论方面的专家，也没有接受过正式的培训。但是，这个主题在化学中非常重要，化学家期望化学子在他们使用的结构搜索系统中发生特定类型的子图匹配。

如果目标图A具有n个节点和m个边，则化学家将接受子图匹配，其中查询图B具有n个节点和m-1个边。唯一的要求是B中的每个边都应出现在A中。例如，一个6个节点的线性链应匹配6个节点的循环。

这种匹配是同构还是同构？也许还有别的吗？

Answer 1

令G1，G2为分别由顶点和边V1，V2和E1，E2组成的图。

如果在V2的每个顶点和V1中的顶点之间以及E2的每个边与E1的某个边之间存在一一对应关系，则G2与G1的子图同构。因此，要实现同构，您需要具有完全匹配的条件，包括图形是否在节点之间包含多个边的情况。

如果顶点之间存在这样的映射，则G2是单态的，并且V2中所有顶点之间都存在边，而V1中存在对应的边。但是，只要至少存在一条边缘，就足够了。

这是comp.lang.python的一个不错的软件包说明。