判断给定图形是否是另一个图形的子图的简单方法是什么？

Question

我正在寻找一种算法来检查给定的图是否是另一个给定图的子图。

我有一些条件使这个NP完全问题更加可行：

- 图形具有约20个顶点。 - 图形是DAG。 - 所有顶点都没有唯一标签，并且主图和子图中对应的顶点应该具有相同的标签。我不知道是否使用了正确的术语（因为我没有学过图论课程...）。它将是这样的：

线图A--B是A--B--A的子图，但A--A不是A--B--A的子图。

任何建议都可以。这不是作业问题。 :D

- Jeeyoung Kim

---

你提到的这个折线图是什么？你是说较小的图形总是一条简单路径吗？ - polygenelubricants

@Jeeyoung：顺便提一下，这被称为子图同构问题。带标签的话，我相信它被称为带标签的子图同构问题。 - Aryabhatta

Answer 1

如果标签是唯一的，对于大小为N的图形，假设在每对顶点之间没有自环或多个边缘，则有O(N^2)条边。 让我们使用E表示边数。

如果将父图中的集合边缘哈希化，则可以遍历子图的边缘，检查每个边缘是否在哈希表中（如果需要，还要检查正确数量）。 您正在为每个边缘执行此操作，因此，O(E)。

让我们将图形称为G（具有N个顶点），可能的子图称为G_1（具有M个顶点），您想找到G_1在G中。

由于标签不是唯一的，因此可以使用动态规划构建子问题 - 而不是为每个子图拥有O(2^N)个子问题，您可以使用O(M 2^N)个子问题 - 对于G_1中的每个顶点（具有M个顶点）和每个可能的子图。 G_1在G中= isSubgraph(0,空位掩码) 并且状态设置如下：

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

基本情况是index = M，并且您可以检查边缘相等性，给定比特掩码（和隐式标签映射）。或者，您也可以在if语句中进行检查 - 只需检查给定当前index，当前子图G_1 [0..index]是否等于G [bitmask]（具有相同的隐式标签映射）然后递归。

对于N = 20，这应该足够快。

（添加您的备忘录，或者您可以使用自底向上DP重新编写此内容）。

- Larry

---

我认为这种方法不会奏效，因为我加入了第三个限制条件——顶点标签不唯一。例如，当你有一个节点循环{A，A，A，B}和一个线图A--A--B时，我怎么知道A是如何映射在一起的？ - Jeeyoung Kim

@Larry：isSubgraph 需要在向 bitmask 添加顶点之前检查边缘，在递归调用之前。 - outis

谢谢，实际上我把它作为基本情况了，但在打字时忘了。 - Larry

Answer 2

好的，我必须问一个明显的问题。 1.你有二十个顶点。按字母顺序在同级别节点中深度优先遍历每个图以获取字符串。 2.如果一个字符串包含另一个字符串，则一个图是另一个图的子图。

那么，还有什么隐含在问题规范中使得这个问题不可行呢？

- Charles Merriam

Answer 3

你可以将这看作是一个对齐问题。基本上，你想要得到一个单射映射a，将V_1中的每个顶点映射到V_2中的一个顶点。一个对齐映射a可以按以下方式进行评分：

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

其中 \sigma(v, w, a(v), a(w)) = 1，如果 (a(v), a(w)) \in E_2，则为1，否则为0。

我认为这可以用整数线性规划的形式来表述。

- sisis