子图同构和子图单态有什么区别？
在我从事的一个项目中，主题 同构与单态出现了。
一点背景知识：我不是图论方面的专家，也没有接受过正式的培训。 但这个主题在化学中非常重要，化学家期望在他们使用的结构搜索系统中发生特定类型的子图匹配。
如果目标图 A 有 n 个节点和 m 个边，那么化学家将接受其中查询图 B 有 n 个节点和 m-1 个边的子图匹配。 唯一的要求是 B 中的每条边都应出现在 A 中。例如，6 个节点的线性链应与 6 个节点的循环匹配。
这种匹配是同构还是单态呢？ 也许完全是别的什么？
In one of the projects I've worked on, the subject of 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
设G1、G2分别是由顶点和边V1、V2和E1、E2的集合组成的图。
G2 与 G1 的子图同构，当且仅当 V2 的每个顶点与 V1 中的顶点之间以及 E2 中的每条边与 E1 中的某些边之间存在一对一映射。 因此，要实现同构，您需要精确匹配，包括图是否在节点之间包含多个边。
G2 是单态的，当且仅当顶点之间存在这样的映射，并且 V2 中的所有顶点之间存在一条边，而 V1 中也有一条对应的边。 但只要至少存在一条边，就足够了。
这是来自 comp.lang.python。
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.
这里数学和计算机科学术语之间存在差异。
从数学中你可以得到两个术语：
子图同构：
设 H = (VH, EH) 和 G = (V, E) 为图形。 f : VH → V 是子图同构，如果 (u, v) ∈ EH，则 (f(u), f(v)) ∈ E。
H 同构于 G 的子图
引起的子图同构的子图：
设 H = (VH, EH) 和 G = (V, E) 为图形。 f : VH → V 是诱导子图同构，如果 (u, v) ∈ EH，则 (f(u), f(v)) ∈ E。如果 (u, v) 不是 EH 的元素，则 ( f(u), f(v)) 不是 E 的元素。
H 是 G 诱导子图同构的
定义来自 http://theory.stanford.edu /~virgi/cs267/lecture1.pdf。
它们相当于我在“图论第一课程”中找到的内容。
请注意，这两者都是图之间的单射同态，也称为图单态。
转向 CS，特别是子图同构问题。 据我所知，子图同构算法确定是否存在满足上面的 (2) 的函数。
图单态性符合 (1)。
CS的定义来自VF2算法，我不知道这种用法有多广泛。 在为项目寻找正确的算法时，似乎仍然存在一些模糊性，并且并非所有项目都使用相同的定义。
对这个答案持保留态度 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf
在引言中将单同态与图子图同构分开，但在第 2 节中将图子图同构定义为在概念上与 (1) 相同，这表明我遗漏了一些东西。
There is a discrepancy between Math and CS terms here.
From math you get two terms:
subgraph isomorphism:
Let H = (VH, EH) and G = (V, E) be graphs. f : VH → V is a subgraph isomorphism if (u, v) ∈ EH, then (f(u), f(v)) ∈ E.
H is isomorphic to a subgraph of G
induced subgraph isomorphism:
Let H = (VH, EH) and G = (V, E) be graphs. f : VH → V is an induced subgraph isomorphism if (u, v) ∈ EH, then (f(u), f(v)) ∈ E. And if (u, v) is not and element of EH, then (f(u), f(v)) is not an element of E.
H is isomorphim to an induced subgraph of G
Definitions from http://theory.stanford.edu/~virgi/cs267/lecture1.pdf.
They are equivalent to what I found in "A First Course in Graph Theory."
Note that both of these are injective homomorphisms between graphs aka a graph monomorphism.
Moving to CS and specifically the subgraph isomorphism problem. To the best of my understanding a subgraph isomorphism algorithm determines if a function exists that satisfies (2) from above.
Graph monomorphism matches (1).
The CS definitions are from the VF2 algorithm, I do not know how widespread that usage is. While searching for the correct algorithm for a project it seems like there is still some ambiguity and not all projects use the same definitions.
Take this answer with a grain of salt http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf
lists monomorphism as seperate from graph-subgraph isomorphism in the introduction, but in section 2 defines graph-subgraph isomorphism as conceptually identical to (1) which indicates I am missing something.
单态性。
从一个图（“B”）到另一个图（“A”）的单态相当于从 B 到 A 的子图的同构。
这个例子是说任何 n 个顶点路径（“链”）对于一个 n 都是单态的。顶点循环。 它对于 n+1 顶点循环或对于任何 k 来说也是单态的。
Monomorphism.
A monomorphism from one graph ("B") to another graph ("A") is equivalent to an isomorphism from B to a subgraph of A.
The example is saying that any n vertex path ("chain") is monomorphic to an n vertex cycle. It would also be monomorphic to a n+1 vertex cycle, or n+k for any k.
无向图同态h：H→ 当顶点上的 h 是单射函数时，G 被称为单态。 作为图同态 h 当然将边映射到边，但不要求边 h(v0)-h(v1) 反映在 H 中。
有向图的情况类似。
An undirected graph homomorphism h: H -> G is said to be a monomorphism when h on vertices is an injective function. As a graph homomorphism h of course maps edges to edges but there is no requirement that an edge h(v0)-h(v1) is reflected in H.
The case of directed graphs is similar.