确定给定图是否是其他图的子图的简单方法？

Question

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

我没有什么条件可以让这个 NP 完全问题变得更加可行。

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

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

任何建议都很好。顺便说一句，这不是一个家庭作业问题。：D

Answer 1

如果标签是唯一的，则对于尺寸图 N, ， 有 O(N^2) 边，假设每对顶点之间没有自循环或多条边。让我们使用 E 为边数。

如果对父图中的集合边进行散列，则可以遍历子图的边，检查每条边是否在散列表中（如果需要，则检查数量是否正确）。您要为每个边执行一次此操作，因此， O(E).

我们称该图为 G （和 N 顶点）和可能的子图 G_1 （和 M 顶点），并且你想找到 G_1 is in G.

由于标签不是唯一的，因此您可以使用动态编程来构建子问题 - 而不是 O(2^N) 子问题，每个子图一个，你有 O(M 2^N) 子问题 - 每个顶点一个 G_1 （和 M 顶点）与每个可能的子图。

G_1 is in G = isSubgraph( 0, empty bitmask)

各州的设置如下：

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 重写此内容）。

Answer 2

好吧，我必须问一个显而易见的问题。1.你有二十个顶点。首先深入地行走每个图，在兄弟姐妹之间的字母顺序以获取字符串。2.一个图是另一个图的子图，当且仅当一个字符串在另一个字符串中。

那么，问题规范中还隐藏了哪些内容，导致这种情况不可行呢？

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 否则为 0。

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