问题标签 [isomorphism]

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

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

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

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

两棵二叉树同构是什么意思？我一直在网上寻找，似乎找不到明确的解释。

据我了解，如果两棵树具有相同的形状，它们就是同构的。所以我猜测两个相同的树可以在节点中包含不同的值。

我正在用 Java 编写代码，该代码使用无序的有根树，其中每个节点可能有任意数量的子节点。给定一棵树 T 和一个子树 S，我希望能够找到 T 中与 S 匹配的所有子树（即 T 中与 S 同构的所有子树）。

如果 S 的节点可以映射到 T 的节点，使得 S 的边映射到 T 中的边，则 T 的子树与 S 同构。

上一个问题已被问及如何查找树是否包含另一个子树，但是我希望能够在 T 中找到与 S 匹配的所有子树。此外，我希望能够从 T 中每个匹配项中的每个节点映射到S 中的对应节点。

也就是说，当找到匹配项时，它不仅应该作为指向 T 中与 S 匹配的树的根节点的指针返回，而且应该作为指向节点的指针对列表 [ (T1,S1),(T2,S2),...(Tn,Sn)] 这样 T1 是指向 T 中的节点的指针，该节点映射到子树中的节点 S1 等等。

或者，可以简单地返回值对的列表，因为树 T 中的每个节点和子树 S 具有与之关联的唯一整数标识符。

例如：

给定树 T 如下：

和子树 S 为：

应返回以下匹配列表：

[(a,x),(b,y),(c,z)] [(b,x),(d,y),(e,z)]

唯一匹配由 T 中的节点集确定，而不是T 和 S 中的节点之间的映射。

所以下面的匹配：

[(a,x),(b, z ),(c, y )]

被认为是重复的

[(a,x),(b, y ),(c, z )]

因为它们具有来自 T (a,b,c) 的相同节点集，所以应该只返回一个匹配项。

作为另一个例子，给定树 T：

和子树 S：

应返回以下匹配列表：

[(a,x),(b,y),(c,z)] [(a,x),(b,y),(d,z)] [(a,x),(c,y) ,(d,z)]

谁能给出如何做到这一点的任何示例代码？

编辑（关于 Chris Kannon 的评论）：

我在想你想要有人为你编码答案吗？你走了多远？你写了什么代码？– 克里斯·坎农 1 小时前

我有以下代码，当运行时，它会建立一个指向树中与给定子树匹配的子树根节点的指针列表（matchesList）。但是，可能有多个子树以同一节点为根，目前每个节点最多只能添加一次到 matchesList，无论有多少匹配项在那里根。

此外，我无法弄清楚如何在子树中的节点和原始树中找到的匹配节点之间建立上述映射。

上面的代码尝试在以下位置找到所有子图：

哪个匹配：

该代码成功检测到存在以第一棵树的顶部节点和第一棵树的第三个子节点为根的匹配项。然而，实际上有 3 个匹配根植于顶部节点，而不仅仅是一个。此外，代码没有在树中的节点和子树中的节点之间建立映射，我无法弄清楚如何做到这一点。

任何人都可以就如何做到这一点提供任何建议吗？

在 Python 中创建 UUID 时，如下所示：

怎么能将该 UUID 映射为由大写字母 AZ 减去字符 D、F、I、O、Q 和 U，再加上数字，再加上字符“+”和“=”组成的字符串。即从整数或字符串到 32 个（相对 OCR 友好）字符集：

我将其称为OCRf集合（对 OCR 友好）。

我想要一个同构函数：

我的第一个想法是完成将uuid更改为base 32的过程。例如

但是，我想知道这种方法是否是进行这种转换的最佳和最快的方法 - 或者是否有更简单和更快的方法（例如内置、更智能的算法或更好的方法）。

我很感谢你的意见。谢谢你。

假设我有一个大的（几千个节点）有向图G和一个小得多的（3-5 个节点）有向图g。我想计算在G中有多少g的同构。换句话说，我想知道 G 中有多少独特的节点集与g匹配。我意识到这是子图同构问题的一个实例，因此是 NP 完全的。但是，鉴于您可能假设g很小，是否有任何合理有效的算法可以做到这一点？

我在哪里可以找到 O(N) 中树同构问题的代码，其中 N 是节点数？

我假设我们有 2 个标记图 G 和 T 并且算法确定 G 是否是 T 的子图以及主图 T 中的相应顶点和子图 G 应该具有相同的标签

我正在尝试找到用于搜索与定向图中指定模式相对应的部分的工具/算法，例如：

A->B->C 或 或 A<->B->C

请建议我搜索的方向。

我的意思是模式匹配。我需要找到与指定模式匹配的所有节点和边组

我正在使用 SmartClient 8.1 并使用 XML 数据源进行 GET 和 PUT 操作。

以下是我获取的数据示例。

当我更新值并提交表单时，SmartClient 将以下数据作为 PUT 有效负载发送。

在 PUT 有效负载中，更新的值在没有组元素（扁平化）的情况下与组中的旧值一起发送。此处不需要/不需要这些分组的旧值。

谁能告诉它为什么会发生以及我应该怎么做才能从 PUT 有效负载中删除这些值？

这与 DynamicForm.submit() 与 DynamicForm.saveData() 有关吗？

我在 SmartClient 论坛上问过这个问题，但仍然没有答案。我希望有人可以在这里帮助我。

有人能用简单的话解释一下图同构的 VF2 算法的步骤吗？我正在学习这个算法，但是没有一个可行的例子就很苛刻。有人可以引导我正确的方向吗？谢谢你。