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

Question

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

我几乎没有条件让这个 NP 完全问题更可行..

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

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

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

Answer 1

如果标签是唯一的，则对于 size 的图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 语句中进行检查 - 只需检查给定 current 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。

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