子图同构和子图单态有什么区别？

Question

在我从事的一个项目中，主题是 同构与单态的出现.

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

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

这种匹配是同构还是单态呢？也许完全是别的什么？

Answer 1

设G1、G2分别是由顶点和边V1、V2和E1、E2的集合组成的图。

G2 与 G1 的子图同构，当且仅当 V2 的每个顶点与 V1 中的顶点之间以及 E2 中的每条边与 E1 中的某些边之间存在一对一映射。因此，要实现同构，您需要精确匹配，包括图是否在节点之间包含多个边。

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

这是来自的一个很好的包描述 编译语言Python.

Answer 2

单态。

从一个图（ “B”）到另一个图表（ “A”）一个单态等同于从B到A的一个子图的同构。

在示例是说，任意n顶点的路径（“链”）是单态为n顶点周期。这也将是单态到一个n + 1个顶点周期，或者n + k中对任意k

Answer 3

这是无向图同态ħ：H - > G被说成是一个单态时上顶点h是单射函数。当然地图边缘到边缘的曲线同态ħ但没有其边缘H（V0）-h（V1）被反射H中的要求。

向图的情况下是类似的。

Answer 4

出现差异的数学和CS条款在这里。从数学你得到两个条款：

1. 子同构:让H=(VH,EH)和G=(V E)以图表。f：VH→V子同构如果(u)∈嗯，然后(f(u)f(v))∈E.H为同一子G

2. 诱子同构:让H=(VH,EH)和G=(V E)以图表。f：VH→V是一个诱导子同构如果(u)∈嗯，然后(f(u)f(v))∈E.并且如果(u)不是和元件的，嗯，然后(f(u)f(v))并不是一件E。H isomorphim一致子G

从定义 http://theory.stanford.edu/~virgi/cs267/lecture1.pdf.它们相当于什么，我发现在"第一课程在图的理论。"

注意，这些都是射同态之间的图表又名图monomorphism.

移动到CS和具体的子同构的问题。据我了解的一个子同构算法确定如果一个功能存在，满足(2)从以上。

图monomorphism相匹配(1)条。

CS的定义，从VF2算法，我不知道怎么普遍，使用率。同时寻找正确的算法为一个项目似乎仍有一些模糊，并不是所有的项目使用同一定义。

把这个回答一粒盐 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf 列出monomorphism作为单独从图的子同构的介绍，但第2节定义了图的子同构作为从概念上完全相同(1)这表明我失去了一些东西。