问题标签 [isomorphism]

例如，假设我有一个图 G，它包含所有蓝色节点和一个红色节点。我还有一个图 F，它有一个全蓝色和一个红色节点。

我可以运行什么算法来验证这两个图关于它们的彩色节点是同构的？

我是学习图论的大一新生。我现在正在学习（子）图同构。有两个重要的算法：Ullmann 算法和vf2。

我读过 Ullmann`s: An algorithm for Subgraph Isomorphism 的论文。我也google了一下，google给了我很多应用，但是我看不懂算法的过程。

你能给我一个简单的解释吗？

我对 VF2 算法实现有疑问。在许多情况下，一切似乎都运行良好，但是有一个问题我无法解决。

该算法不适用于下面的示例。在此示例中，我们正在比较两个相同的图表（见下图）。起始顶点为 0。在 s0 内计算的集合 P 存储所有顶点对的幂集。

下面是关于 VF2 的出版物中包含的伪代码，我的实现正是基于该伪代码。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs。 pdf

/*右边的注释描述了我理解代码的方式：

我不确定创建 P() 集是否有效，如下所述。对的幂集按字典顺序依次通过对的第一个值和第二个值进行迭代。

当算法进入 s4 时，从函数返回时，它会丢失有关良好顶点匹配的信息。它导致搜索子图同构 ({(0,0),(1,1),(2,2),(5,3),(6,4)}) - 即使图是同构的。

我在这里做错了什么？

我已经连续在互联网上搜索了大约两三天，但到目前为止还没有运气。

我知道在野外有很多用于子图同构的库和实现，但它们都适用于未加权图。例如，两种最流行的算法是 VF2 和 Uleman 算法。在这里，我的问题是：是否有任何方法可以给出一个图（G）和一个查询图（g），是否可以找到 g 是否是 G 的子图（并且同构）？（请注意，以下是图的边缘列表表示。）

在这种情况下，g 是一个子图并且与 G 同构，但是如果我们有这样的东西：

现在 g 不再是 G 的子图并且不是同构的。

更新：两个图都是无向的。

我想使用 NetworkXGraph对象作为 Python 中的键dict。但是，我不希望使用默认行为进行比较（即，通过对象的地址）。相反，我希望同构图指的是dict.

这种行为是否已经在某处实施？我在这个方向上找不到任何信息。

如果我必须自己实施，以下评估是否现实？

• 包networkx.Graph进一个班级。
• 定义__eq__这样它调用is_isomorphic.
• 以某种方式定义__hash__（欢迎提出建议）。

我认为我必须使这个包装的 Graph 不可变，因为：

如果一个类定义了可变对象并实现了一个__eq__()方法，那么它就不应该实现__hash__()，因为可哈希集合的实现要求一个键的哈希值是不可变的（如果对象的哈希值发生变化，它将在错误的哈希桶中）。

我有点卡在这个涉及返回字符串数组中同构对的数量的java问题上。我编写的代码不断返回错误数量的同构词对。

同构词的定义如下：如果一个词中的字母可以重新映射得到第二个词，则两个词称为同构词。重新映射一个字母意味着用另一个字母替换所有出现的字母。字母的顺序保持不变。没有两个字母可以映射到同一个字母，但一个字母可以映射到它自己。例如，单词“abca”和“zbxz”是同构的，因为我们可以将“a”映射到“z”，“b”映射到“b”，“c”映射到“x”。我不包括我在函数中调用的 getMap 方法。getMap 方法将任意字符串作为输入，并返回一个映射，其中键是字符串中的字母，对应的值是字母在字符串中出现的次数。

我真的很感激你能给我关于这段代码的任何反馈。

谢谢，朱奈德

阅读 Chuusai 的这篇博文，它说：

Either[Int, String] 可以对联合类型 Int ∨ String 建模，因为这两种类型及其值之间存在同构

“两种类型及其值之间存在同构”是什么意思？

我正在寻找一种算法来匹配相似图中的节点。节点的数量不相等，但每个图确实代表同一个系统。

所以，我正在寻找相似或模糊的图形匹配或模式识别。

我从哪说起呢？

无向顶点标记的多图加权稀疏节点：2,172 边：3,000

节点有许多独立的属性。边有一个属性，类似于长度。两个图之间对应的节点和边的节点和边属性不相同。

这个问题在技术论文中被描述为部分同构、图对齐和最大公共子图

The Subgraph Isomorphism (SI) problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.

This is a NP-Complete problem .

I want to know its relation with the SAT problem.
In particular, I want instances of this problem can be solved throughout SAT Solver(like miniSAT).I need an alorithm which can do a mapping from SI to SAT problem in polynomial time and then SAT assignment can be used to find a mapping from nodes of G to nodes of H .

Any idea ???

这必须是一个经过充分研究的问题，但我正在努力研究它。

我从这里开始，但我正在寻找算法来研究和实现。 http://en.wikipedia.org/wiki/Graph_isomorphism_problem

例如，如果我有两个 DAG（有向无环图），我想标记/删除其中一个，因为它只是第一个的旋转/反射。在同一个自同构组中意味着它们可以被旋转/反射以具有完全相同的邻接矩阵，对吗？