4

假设我们想用图来表示分子，其中每个节点是一个原子，每个边是原子之间的连接。什么是确定两个图（代表分子）是否等价的算法。由于正在表示分子，因此每个节点都需要一个属性来定义它是哪个分子（碳、氮、氧等）。

为了更容易，假设每个图都从同一个根原子 Nitrogen 分支出来，我们可以将其用作算法的起始节点。

例如。NX，纽约，新西兰。其中 N 是根 Nitrogen 节点，X,Y,Z 是图的其余部分。

4

3 回答 3

10

这就是图同构问题；

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

换句话说，在一般情况下解决它是困难的。

于 2012-10-06T19:59:40.187 回答
5

我同意Joachim Isaksson 的回答，即一般情况 - 哎呀，即使是不太一般的情况 - 也很难解决。但我想提出一种策略来解决具有指定起始元素的分子树图的相对狭窄情况。[请注意，这相当于我在处理此答案时发布的Peter de Rivaz 的答案。]

首先让我们定义一种形式或语言来描述该图所独有的分子图——该图只能形成一个字符串。这将允许我们比较两个字符串以确定两个图表是否相同，从而将您的问题简化为创建两个正确的字符串进行比较。（这种方法的好处是比直接的图形比较算法更容易在视觉上进行调试。）我通常看到以 H 2 O 和 H 2 SO 4等形式描述的分子，但这种方法并不能保留图形性的分子，因此不能用于比较（H 2O 可能是水或其他一些非常奇怪的元素排列）。所以让我们根据这些规则使用类似 Lisp 的东西来描述分子：

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

有了这些起始规则，我们现在可以用更多类似图形的术语来描述 H 2 O：

  1. O是图的根，因此它开始一个新图：(O)
  2. H是 的第一个孩子O，但它没有孩子，因此它按原样列在其父级中，而不是作为子图的开头：(OH)
  3. H是 的第二个孩子O，但 is 没有孩子，因此它按原样列在其父级中，而不是作为子图的开头：(OHH)

所以

H2O 图表

变成(OHH).

在这种情况下排序无关紧要，因为这两个Hs 是无子元素且在元素上是等价的。

让我们尝试一种奇怪的、非理性的 H 2 O 形式来测试这种方法：

OHH 图

  1. O是图的根，因此它开始一个新图：(O)
  2. H是 的第一个孩子O。它有一个孩子，所以它开始一个新的图表：(O(H))
  3. H是 的第一个子级H，但 is 没有子级，因此它按原样列在其父级中，而不是作为子图的开头：(O(HH))

我们知道到目前为止，我们的方法可以处理像 H 2 O 这样的简单情况，其中排序不是问题，但是如果没有一致地对从. 在计算子图（如果有的话）之前，不可能给一个子图一个有意义的命令，所以我们将添加一个最终规则来执行：OS

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

用这个新规则重新访问H 2 O 会产生相同的输出，因为这两个Hs 在字母上是等价的并且它们没有孩子。所以让我们试试 H 2 SO 4：

h2so4 图表

  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 2 SO 4的变体，看看它会产生什么。请注意，这并不能证明该方法是好的，只是演示图表中的变化如何产生不同的结果。

一些奇怪的 H2SO4 图表

  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 2 SO 4 ( (S(OHO)(OHO))) 与前一个 ( (S(OH)(OH)OO)) 不同。

我没有试图正式证明这种方法可以保证有效，甚至没有正式描述它，或者解释那里广泛的分子细节，如债券计数等。不过，至少，我希望这能鼓励您尝试解决图形比较问题。我认为这是可行的。

于 2012-10-06T21:32:07.930 回答
3

您的问题被标记为“树”，这可能意味着图中没有循环？

如果是这种情况，那么就有一种有效的算法来确定分子是否等价。

给定根原子，想象这是向下延伸的树的顶部。

这个想法是从树的底部迭代地计算出哪些子树是等效的。

从底部开始并标记两个分子中的所有等效原子。对该列表进行排序并检查两个列表是否匹配。（在底层，这只是简单地计算每种原子的数量是否相同。）

然后工作到下一个最低水平。对于每个原子，给它一个基于原子类型的标签，以及它连接到的子树的排序标签。

再次对该列表进行排序并检查列表是否匹配。

当您到达根节点时，如果所有检查均已通过，则分子是同构的。

于 2012-10-06T21:26:10.353 回答