子图同构和子图同构之间有什么区别? [英] What's the Difference Between Subgraph Isomorphism and Subgraph Monomorphism?
让G1，G2是分别由顶点和边V1，V2和E1，E2组成的图.
如果在V2的每个顶点与V1中的顶点之间以及E2的每个边缘与E1的某个边缘之间存在一一对应关系，则G2与G1的子图同构.因此，要实现同构，您需要具有完全匹配的条件，包括图形是否在节点之间包含多个边的情况. 如果在顶点之间存在这样的映射，则G2是单态的，并且V2中所有顶点之间都存在一条边，而V1中存在对应的边.但是只要至少存在一条边缘，就足够了.
这是isomorphism versus monomorphism came up.
A little background: I'm no expert on graph theory and have no formal training in it. But this topic is very important in chemistry, where chemists expect a particular kind of subgraph matching to take place in the structure search systems they use.
If a target graph A has n nodes and m edges, then a chemist would accept subgraph matches in which a query graph B had n nodes and m-1 edges. The only requirement would be that every edge in B should be present in A. For example, a linear chain of 6 nodes should match a cycle of 6 nodes.
Is this kind of matching isomorphism or monomorphism? Maybe something else altogether?
Let G1, G2 be graphs composed of sets of vertices and edges V1, V2 and E1, E2 respectively.
G2 is isomorphic to a subgraph of G1 iff there exists a one-one mapping between each vertex of V2 and a vertex in V1, and between each edge in E2 and some edge in E1. So to be isomorphic, you need to have an exact match, including if the graph includes more than one edge between nodes.
G2 is monomorphic iff there's such a mapping between vertices, and there exists an edge between all vertices in V2 for which there is a corresponding edge in V1. But so long as at least one edge exists, that's sufficient.
Here's a nice package description from comp.lang.python.
这篇关于子图同构和子图同构之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
