12

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

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

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

这种匹配同构还是单态？也许完全是别的东西？

4

4 回答 4

13

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

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

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

这是来自comp.lang.python的一个很好的包描述。

于 2009-01-20T01:45:34.007 回答
3

单态。

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

该示例是说任何 n 顶点路径（“链”）对于 n 顶点循环都是单态的。对于 n+1 个顶点循环，它也是单态的，或者对于任何 k 都是 n+k。

于 2009-01-20T01:45:49.123 回答
2

当顶点上的 h 是单射函数时，无向图同态 h: H -> G 被称为单态。作为图同态 h 当然将边映射到边，但不要求边 h(v0)-h(v1) 反映在 H 中。

有向图的情况类似。

于 2012-06-19T03:24:20.663 回答
1

这里的数学和 CS 术语之间存在差异。从数学中你得到两个术语：

  1. 子图同构：设 H = (VH, EH) 和 G = (V, E) 是图。f : VH → V 是一个子图同构如果 (u, v) ∈ EH, 那么 (f(u), f(v)) ∈ E. H 同构于 G 的一个子图

  2. 诱导子图同构：设 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) 相同，这表明我遗漏了一些东西。

于 2015-10-17T08:45:16.163 回答