在我曾经工作的一个项目中，出现了同构与单态的主题 。
一些背景：我不是图论方面的专家，也没有正式的培训。但这个主题在化学中非常重要，在那里化学家期望他们使用的结构搜索系统发生特定类型的子图匹配。
如果目标图A具有n个节点和m条边，则化学家将接受查询图B具有n个节点和m-1条边的子图匹配。唯一的要求是B中的每条边都应存在于A中。例如，6个节点的线性链应该与6个节点的环匹配。
这种匹配是同构还是单态？或者完全是其他什么东西？
4个回答
14
假设G1、G2是由顶点集合V1、V2和边集合E1、E2组成的图形。
当且仅当存在一一对应关系将V2中的每个顶点映射到V1中的一个顶点，将E2中的每个边映射到E1中的某条边时，G2就是G1的子图同构。因此，要实现同构，需要确保完全匹配，包括图中节点之间有多条边的情况。
当且仅当存在这样的顶点映射，并且V2中每个顶点都与与之对应的V1中的顶点之间存在边时，G2是单态图。但只要至少存在一条边，就足以满足条件。
以下是来自comp.lang.python的一个很好的软件包描述。
- Charlie Martin
4
这里的数学术语和计算机科学术语有差异。
从数学中，你可以得到两个术语：
请注意，这两者都是图之间的单射同态，也称为图单同态。
转到计算机科学，特别是子图同构问题。据我所知，子图同构算法确定是否存在满足上述（2）的函数。
图单同态匹配（1）。
CS定义来自VF2算法，我不知道该使用的普及程度如何。在寻找项目的正确算法时，似乎仍然存在一些歧义，并非所有项目都使用相同的定义。
将此答案视为参考http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf，在介绍中将单同态列为与图-子图同构分开的概念，但在第2节中将图-子图同构定义为概念上等同于（1），这表明我错过了某些内容。
子图同构： 设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的诱导子图
请注意，这两者都是图之间的单射同态，也称为图单同态。
转到计算机科学，特别是子图同构问题。据我所知，子图同构算法确定是否存在满足上述（2）的函数。
图单同态匹配（1）。
CS定义来自VF2算法，我不知道该使用的普及程度如何。在寻找项目的正确算法时，似乎仍然存在一些歧义，并非所有项目都使用相同的定义。
将此答案视为参考http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf，在介绍中将单同态列为与图-子图同构分开的概念，但在第2节中将图-子图同构定义为概念上等同于（1），这表明我错过了某些内容。
- Fishy314
3
单态性。
从一个图形（“B”）到另一个图形（“A”）的单态性等同于从 B 到 A 的子图同构。
这个例子说明任何 n 个顶点路径（“链”）都是单态性的，可以对应于一个 n 个顶点的环。它也可以对应于 n+1 个顶点的环，或者对于任何 k，n+k 个顶点的环。
- Captain Segfault
3
当无向图同态h: H -> G的顶点映射为单射时，称其为单同态。作为图同态，h将边映射到边，但没有要求H中反映边h(v0)-h(v1)。
有向图的情况类似。
- David B. Benson
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接