P92 - 优雅树标号

Graceful tree labeling
官方模块：Problems.P92　核心函数：gracefulTree

定义

含 $n$ 个顶点的树若能用 $1..n$ 双射标号，并让 $n-1$ 条边两端标号差的绝对值恰好组成 $1..n-1$ ，这个标号就是优雅标号。

实现

方法一：枚举完整排列

 1import Data.List (delete, permutations)
 2
 3gracefulTree :: G -> Maybe (Map.Map Vertex Int)
 4gracefulTree graph
 5  | not (isTree graph) = Nothing
 6  | otherwise = firstJust
 7      [Just labeling | labels <- permutations [1..n]
 8                     , let labeling = Map.fromList (zip vertices labels)
 9                     , graceful labeling]
10  where
11    (vs,es) = canonical graph
12    vertices = Set.toList vs
13    n = length vertices
14    graceful labeling =
15      Set.fromList [abs (labeling Map.! u - labeling Map.! v)
16                   | (u,v) <- Set.toList es]
17      == Set.fromList [1..n-1]
18
19firstJust [] = Nothing
20firstJust (Just value:_) = Just value
21firstJust (Nothing:rest) = firstJust rest

这个版本直接枚举所有 $n!$ 个双射，代码短且定义清楚。实用版本应优先标记高度数顶点，并在部分标号产生重复边差时立即回溯。

方法二：部分标号回溯

 1import Data.List (delete, sortOn)
 2import Data.Ord (Down(..))
 3
 4gracefulTreeBacktracking :: G -> Maybe (Map.Map Vertex Int)
 5gracefulTreeBacktracking graph
 6  | not (isTree graph) = Nothing
 7  | otherwise = assign orderedVertices Map.empty Set.empty [1..n]
 8  where
 9    vertices = Set.toList (fst (canonical graph))
10    n = length vertices
11    orderedVertices = sortOn
12      (Down . Set.size . (`neighbors` graph)) vertices
13
14    assign [] labeling _ _ = Just labeling
15    assign (vertex:rest) labeling usedDifferences availableLabels =
16      firstJust
17        [assign rest
18                (Map.insert vertex label labeling)
19                (Set.union usedDifferences newDifferences)
20                (delete label availableLabels)
21        | label <- availableLabels
22        , let newDifferences = Set.fromList
23                [abs (label - neighborLabel)
24                | neighbor <- Set.toList (neighbors vertex graph)
25                , Just neighborLabel <- [Map.lookup neighbor labeling]]
26        , Set.size newDifferences == length
27            [() | neighbor <- Set.toList (neighbors vertex graph)
28                , Map.member neighbor labeling]
29        , Set.null (Set.intersection usedDifferences newDifferences)
30        ]

每给一个顶点标号，就计算它与已标号邻居产生的新边差。新边差内部重复或与此前边差冲突时立即回溯。优先处理高度数顶点可以更早形成约束。

方法对比

方法	检查时机
完整排列	n 个顶点全部标号后检查
部分标号回溯	每加入一个标号就检查新边差

测试

1>>> let path4 = toG (Paths [[1,2,3,4]])
2>>> fmap (const True) (gracefulTree path4)
3Just True
4>>> gracefulTree (toG (Paths [[1,2,3,1]]))
5Nothing
6>>> fmap (const True) (gracefulTreeBacktracking path4)
7Just True

不同枚举顺序可能返回不同但同样正确的标号，测试应验证标号集合和边差集合，而不是固定某一映射。

参考

← P91 骑士巡游 | P93 算术谜题 →