您如何验证两个图表是否相同？

Question

假设我们想用图表来表示分子,其中每个节点都是原子,每个边是原子之间的连接.什么算法来决定两个图(代表分子)是否相等.由于分子被表示,每个节点都需要一个属性来定义它是哪个分子(碳,氮,氧等).

为了使其更容易,假设每个图形从相同的根原子氮分支,我们可以将其用作算法的起始节点.

例如.NX,NY,NZ.其中N是根氮节点,X,Y,Z是图的其余部分.

Answer 1

那是图同构问题 ;

图同构问题是属于NP的计算复杂性理论中的少数标准问题之一,但不知道它属于其众所周知的(和,如果P≠NP,不相交)子集:P和NP完全.它是Garey&Johnson(1979)中列出的12个问题中仅有的两个问题之一,其复杂性仍未得到解决,另一个是整数分解.

换句话说,在一般情况下解决它很难.

Answer 2

我同意约阿希姆·伊萨克森的回答,即一般情况 - 即使是一个不那么普遍的案例 - 很难解决.但是我想提出一个策略来解决具有指定起始元素的分子树图的相对狭窄的情况.[请注意,这相当于Peter de Rivaz的答案,该答案是在我处理此答案时发布的.]

首先,让我们定义一种形式或语言来描述该图独有的分子图 - 图中只能形成一个字符串.这将允许我们比较两个字符串以确定两个图是否相同,以便您的问题减少到创建两个正确的字符串进行比较.(这种方法还具有比直接图形比较算法更容易在视觉上进行调试的好处.)我通常看到以H ₂ O和H ₂ SO ₄等形式描述的分子,但这种方法不能保留图形.这些分子不能用于比较(H ₂ O可能是水或其他元素非常奇怪的排列).因此,让我们根据这些规则使用类似Lisp的东西来描述分子:

1. 每个图(包括子图)都以(和开头结束)
2. 任何具有子节点的节点A是新图中列出的第一个节点,并且该图以特定顺序列在其父图中(稍后确定)
3. 任何没有子节点的节点A都按其特定顺序列在其父图中(稍后确定)

有了这些启动规则,我们现在可以用类似图形的术语来描述H ₂ O:

1. O 是图的根,所以它开始一个新图: (O)
2. H是第一个孩子O,但它没有孩子,因此它在父母的原样中列出,而不是作为子图的开头:(OH)
3. H是第二个孩子O,但没有孩子,所以它在父母的原样中列出,而不是作为子图的开头:(OHH)

所以

成为(OHH).

在这种情况下订购并不重要,因为这两个H是没有孩子的,在元素上是等价的.

让我们尝试一种奇怪的,非理性的H ₂ O 形式来测试这种方法:

1. O 是图的根,所以它开始一个新图: (O)
2. H是第一个孩子O.它有一个孩子,所以它开始一个新图:(O(H))
3. H是第一个孩子H,但是没有孩子,因此它在父母的原样中列出,而不是作为子图的开头:(O(HH))

我们知道到目前为止我们的方法可以处理像H ₂ O 这样的简单情况,其中排序不是问题,但是H ₂ SO ₄如果不一致地排序O来自的元素就不会工作S.在计算子图(如果有子图)之前,不可能给孩子一个有意义的顺序,所以我们将添加一个最终规则来执行:

1. 每个图(包括子图)都以(和开头结束)
2. 任何具有子节点的节点A是新图中列出的第一个节点,并且该图以特定顺序列在其父图中(参见步骤4)
3. 任何没有子节点的节点A都按其特定顺序列在其父图中(参见步骤4)
4. 在访问了所有子节点并创建了子图(如果有)之后,按字母顺序排列父节点中的子节点/子子图

使用此新规则重新访问H ₂ O会产生相同的输出,因为两个Hs在字母顺序上是等效的,并且它们没有子项.那么让我们试试H ₂ SO ₄:

1. S 是图的根,所以它开始一个新图: (S)
2. O是第一个孩子S.它有孩子,所以它开始一个新图:(S[unsorted:](O))

3. 'H'是第一个孩子O.它没有孩子.没有其他孩子可以处理,因此不需要在此级别进行排序:(S[unsorted:](OH))

4. O是第二个孩子S.这个没有孩子:(S[unsorted:](OH)O)

5. O是第三个孩子S.它有孩子,所以它开始一个新图:(S[unsorted:](OH)O(O))

6. 'H'是第一个孩子O.它没有孩子.没有其他孩子可以处理,因此不需要在此级别进行排序:(S[unsorted:](OH)O(OH))

7. O是第四个孩子S.这个没有孩子:(S[unsorted:](OH)O(OH)O)

8. 最后,S按字母顺序对子项进行排序:( (S(OH)(OH)OO)请注意,我在字母比较中给出子图特殊处理,但这不是必需的.)

最终的结果是 (S(OH)(OH)OO)

让我们尝试一下H ₂ SO ₄的变化来看看它产生了什么.请注意,这并不能证明方法是好的,只是演示图表中的变化如何产生不同的结果.

1. S 是图的根,所以它开始一个新图: (S)
2. O是第一个孩子S.它有孩子,所以它开始一个新图:(S[unsorted:](O))
3. O是第一个孩子.它没有孩子.(S[unsorted:](O[unsorted:]O))
4. H 是第二个孩子,没有孩子. (S[unsorted:](O[unsorted:]OH))
5. 现在排序孩子O:(S[unsorted:](OHO)
6. O是第二个孩子S.它有孩子,所以它开始一个新图:(S[unsorted:](O))
7. H是第一个孩子.它没有孩子.(S[unsorted:](OHO)(O[unsorted:]H))
8. O 是第二个孩子,没有孩子. (S[unsorted:](OHO)(O[unsorted:]HO))
9. 现在排序孩子O:(S[unsorted:](OHO)(OHO))
10. 最后,S按字母顺序对子项进行排序:(S(OHO)(OHO))

该H ₂ SO ₄((S(OHO)(OHO)))与前一个((S(OH)(OH)OO))不同.

我没有试图正式证明这种方法可以保证正常工作,甚至无法正式描述,或者考虑到那里的广泛分子细节,如债券数量等.但至少,我希望这可以鼓励您尝试解决图形比较问题.我认为这是可行的.