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

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 在G 中。

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

G_1 位于 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，if (a(v), a(w)) \in E_2 否则为 0。

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