确定给定图是否是其他图的子图的简单方法?
-
23-09-2019 - |
题
我正在寻找一种算法来检查给定图是否是另一个给定图的子图。
我没有什么条件可以让这个 NP 完全问题变得更加可行。
- 这些图大约有 <20 个顶点。
- 这些图是 DAG。
- 所有顶点都是非唯一标记的,并且主图和子图中对应的顶点应该具有相同的标记。我不知道我是否使用了正确的术语(因为我没有上过图论课程......)。它会是这样的:
线图 A--B 是 A--B--A 的子图,但 A--A 不是 A--B--A 的子图。
任何建议都很好。顺便说一句,这不是一个家庭作业问题。:D
解决方案
如果标签是唯一的,则对于尺寸图 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 重写此内容)。
其他提示
好吧,我必须问一个显而易见的问题。1.你有二十个顶点。首先深入地行走每个图,在兄弟姐妹之间的字母顺序以获取字符串。2.一个图是另一个图的子图,当且仅当一个字符串在另一个字符串中。
那么,问题规范中还隐藏了哪些内容,导致这种情况不可行呢?
您可以将此视为对齐问题。基本上你想提出一个单射映射 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。
我认为这可以用整数线性规划的形式表示。