P85 - 判断图同构

Graph isomorphism
官方模块：Problems.P85　核心函数：isomorphic

题目描述

若存在顶点双射，使一张图中的边映射后恰好等于另一张图的边，两图同构。顶点编号本身没有意义。

实现

方法一：标准实现

先比较顶点数、边数和度数多重集，排除显然不可能的情况，再枚举顶点双射并检查边集。进一步优化时可以只枚举相同度数顶点之间的对应。

 1import Data.List (permutations, sort)
 2
 3isomorphic :: G -> G -> Bool
 4isomorphic left right
 5  | Set.size lvs /= Set.size rvs = False
 6  | Set.size les /= Set.size res = False
 7  | degrees left /= degrees right = False
 8  | otherwise = any preservesEdge candidateMappings
 9  where
10    (lvs,les) = canonical left
11    (rvs,res) = canonical right
12    lvertices = Set.toList lvs
13    rvertices = Set.toList rvs
14    candidateMappings = map (Map.fromList . zip lvertices)
15      (permutations rvertices)
16    preservesEdge mapping = Set.map (rename mapping) les == res
17    rename mapping (u,v) = normalize (mapping Map.! u, mapping Map.! v)
18
19degrees graph = sort
20  [Set.size (neighbors v graph) | v <- Set.toList (fst (canonical graph))]

度数过滤不会改变正确性，却能提前排除大量不可能情况。进一步优化可在构造映射时增量检查已映射边。

方法二：部分映射回溯

 1import Data.List (sortOn)
 2import Data.Ord (Down(..))
 3
 4isomorphicBacktracking :: G -> G -> Bool
 5isomorphicBacktracking left right
 6  | Set.size leftVertices /= Set.size rightVertices = False
 7  | Set.size leftEdges /= Set.size rightEdges = False
 8  | degrees left /= degrees right = False
 9  | otherwise = search orderedLeft Map.empty rightVertices
10  where
11    (leftVertices, leftEdges) = canonical left
12    (rightVertices, rightEdges) = canonical right
13    orderedLeft = sortOn
14      (Down . Set.size . (`neighbors` left))
15      (Set.toList leftVertices)
16
17    search [] _ _ = True
18    search (vertex:rest) mapping unused = any try candidates
19      where
20        wantedDegree = Set.size (neighbors vertex left)
21        candidates =
22          [candidate | candidate <- Set.toList unused
23                     , Set.size (neighbors candidate right) == wantedDegree]
24
25        try candidate =
26          consistent candidate mapping
27          && search rest (Map.insert vertex candidate mapping)
28                         (Set.delete candidate unused)
29
30        consistent candidate mapping = and
31          [Set.member (normalize (other, vertex)) leftEdges
32            == Set.member (normalize (mappedOther, candidate)) rightEdges
33          | (other, mappedOther) <- Map.toList mapping]

先处理高度数顶点，只尝试映射到同度数的未用顶点。每增加一对映射，就比较它与所有已映射顶点之间的“有边/无边”关系；一旦不一致立即回溯，不再枚举剩余排列。

方法对比

方法	搜索单位	剪枝时机
全排列	完整双射	映射完成后比较全部边
部分映射回溯	一对顶点	每加入一对立即检查已映射关系

测试

1>>> isomorphic (toG (Paths [[1,2,3],[2,4]]))
2...            (toG (Paths [[1,2,3],[1,4]]))
3False
4>>> isomorphic (toG (Paths [[1,2,3,1]]))
5...            (toG (Paths [[4,5,6,4]]))
6True
7>>> isomorphicBacktracking (toG (Paths [[1,2,3,1]]))
8...                        (toG (Paths [[4,5,6,4]]))
9True

朴素枚举最坏为 $O(n!\cdot m)$ ，这正是本题困难所在。

参考

← P84 最小生成树 | P86 图着色 →