问题标签 [isomorphism]

假设我有两个名为的函数f :: a -> b，并且它是相反g :: b -> a的f . g ≡ id。

现在不是g . f ≡ id吗？（因此暗示同构）

我试图写一个类似的例子并想出了这个：

在 ghci 中：

但似乎反函数并不意味着同构。那么有人可以指出我在这里做错了什么吗？

我有点卡在我的图表问题上，而且不是这个主题的专家，我想我会求助于互联网。我有两个图 A 和 B，我想检查 B 是否是 A 的子图。我尝试使用 igraph 执行此操作，但它似乎声称 B 是 A 的子图，即使它不是。这是一个说明这一点的例子：

程序打印“[[0, 2], [1, 3]]”

我认为 B 不是 A 的子同构，因为从顶点 0 开始的 color=1 线没有连接到顶点 2，但 igraph 似乎忽略了这一点。我做错了什么还是igraph中的错误？我将 python-igraph 0.6.5 与 Python 2.6.5 一起使用

编辑：我认为这里可以忽略颜色。我的问题是，在图 A 中，存在从第 0 个顶点到第一个顶点的链接，因此 B 不是子图，因为这需要（在图 A 中）第 0 个顶点直接连接到第二个顶点。

Edit2：我怀疑我真正想要的是“诱导子图同构”。

本题以 Hogan 为例，但适用于任何模板。

我正在尝试制作同构的东西（在客户端和服务器上都可以使用）。如果我在胡子文件中需要，在客户端上：

然后 browserify + a transform 检测到这是一个扩展的胡子文件，并且tpl是一个对象，其中一个功能是.render.

如果我要使用 NodeJS 运行上述行，我希望得到完全相同的结果。

默认情况下，Node 只希望这个文件是一个 javascript 文件，所以结果看起来像这样并且错误：

是否有一种未经许可的算法，用于以紧凑、清晰的方式放置节点/顶点，节点彼此靠近而没有重叠且边缘短，并且具有许多链接的节点不都在中心等，即所有这些都重要图表？

换句话说，我如何在排列最清晰的位置对图形进行同构？

哦，节点是矩形（正如我所说，它是用于图表）的大小可以根据它们的内容而有所不同

我有 15M（百万）个 DAG（有向无环图 - 实际上是有向超立方体）的集合，我想从中删除同构。常见的算法是什么？每个图都相当小，一个维度为 N 的混合立方体，其中 N 为 3 到 6（目前），导致在 N=6 情况下每个节点有 64 个节点的图。

使用networkx和python，我像这样实现了它，它适用于像300k（千）这样的小集合很好（在几天内运行）。

一种更好的方法是将每个图转换为其规范排序，对集合进行排序，然后删除重复项。这绕过了检查二进制 is_isomophic() 测试中的每一个 15M 图，我相信上面的实现类似于 O(N!N) （不考虑同构时间），而干净地将所有转换为规范排序和排序应该需要O(N) 用于转换 + O(log(N)N) 用于搜索 + O(N) 用于删除重复项。O(N!N) >> O(log(N)N)

我发现这篇关于规范图标记的论文，但它用数学方程非常简洁地描述，没有伪代码：“McKay 的规范图标记算法” - http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

tldr：我有大量的图要通过二元同构检查来检查。我相信这样做的常用方法是通过规范排序。是否存在任何打包的算法或发布的直接实现算法（即有伪代码）？

我在 Coq 中定义时遇到了一些问题，尤其是在使用 CHI 定义时。我已经设法获得了对基本原则的理解，但是当我尝试定义这一点时”

我一无所获，因为它一直告诉我：
"Error: The type of this term is a product while it is expected to be "C"。
我已经尝试过我之前在脚本中使用过的常用策略，并且我确信必须使用相同的方法（有趣）来解决这个问题，但是我似乎正在尝试的一切都以该错误消息结尾。有小费吗？

关联矩阵中任意两行或两列的排列仅对应于重新标记同一图的顶点和边。相反，两个图 X 和 Y 是同构的当且仅当它们的关联矩阵 A(X) 和 A(Y) 仅在行和列的排列上有所不同。

有人可以举例说明这是什么意思吗？“任意两行或两列的排列”到底是什么意思？

给定两个图，如何在这两个图中找到同构的子图。目前，我只是发现igraph已经实现了igraph_subisomorphic_vf2，它有两个图G和H作为输入，并确定G是否包含与H同构的子图。

由于我在 igraph 中没有找到任何其他可以直接解决我的问题的函数，我目前认为一种方法是从给定图中枚举所有可能的子图，然后使用函数 igraph_subisomorphic_vf2 来确定子图是否与另一个同构给定的图表。

对于我数据集中的图，平均节点数为 40。我想知道这是否是解决问题的可行方法？

有没有更好的方法在给定的两个或多个图中找到最大子图？

谢谢！

如何在 Coq 中定义同构类？

假设我有一个记录 ToyRec：

以及 ToyRec 类型的两个对象之间的同构定义，说明如果存在保留映射元素标签的双射 f:T1.(X)->T2.(X)，则两个对象 T1 和 T2 是同构的。

现在我想定义一个函数，它接受一个对象 T1 并返回一个包含所有与 T1 同构的对象的集合。

在 coq 中怎么做这样的事情？我知道我可能在这里推理过于理论化，但是同构类的正确类型理论概念是什么？或者更基本的是，如何定义满足给定属性的所有元素的集合（或类型）？

有人可以给我一个在 MATLAB 中工作的 Ullman 的图同构问题实现，或链接到它。或者，如果您至少有 C 语言，那么我会尝试在 MATLAB 中实现它。

谢谢