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

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_1M

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