P94 - 生成非同构正则图

Generate regular graphs
官方模块：Problems.P94　核心函数：regularGraphs

题目描述

生成含 $n$ 个顶点的所有非同构 $k$ -正则简单图。每个顶点度数都必须是 $k$ ；握手定理要求 $nk$ 为偶数。

实现

方法一：标准实现

 1import Data.List (nubBy)
 2import qualified Data.Map.Strict as Map
 3
 4regularGraphs :: Int -> Int -> [G]
 5regularGraphs n k
 6  | n < 0 || k < 0 || (n > 0 && k >= n) || odd (n*k) = []
 7  | otherwise = nubBy isomorphic
 8      [graph | chosen <- combinations edgeCount possibleEdges
 9             , let graph = toG (Lists (vertices, chosen))
10             , all ((== k) . Set.size . (`neighbors` graph)) vertices]
11  where
12    vertices = [1..n]
13    possibleEdges = [(u,v) | u <- vertices, v <- vertices, u < v]
14    edgeCount = n * k `div` 2

先用握手定理固定边数，再过滤度数，最后用 P85 去除同构副本。

方法二：剩余度数剪枝

 1regularGraphsBacktracking :: Int -> Int -> [G]
 2regularGraphsBacktracking n k
 3  | n < 0 || k < 0 || (n > 0 && k >= n) || odd (n * k) = []
 4  | otherwise = nubBy isomorphic
 5      [toG (Lists (vertices, chosen))
 6      | chosen <- search possibleEdges initialDegrees []]
 7  where
 8    vertices = [1..n]
 9    possibleEdges = [(u, v) | u <- vertices, v <- vertices, u < v]
10    initialDegrees = Map.fromList [(vertex, 0) | vertex <- vertices]
11
12    search remaining degrees chosen
13      | any impossible vertices = []
14      | null remaining =
15          [reverse chosen | all ((== k) . degree) vertices]
16      | otherwise = withoutEdge ++ withEdge
17      where
18        degree vertex = Map.findWithDefault 0 vertex degrees
19        incident vertex (u, v) = vertex == u || vertex == v
20        impossible vertex =
21          degree vertex > k
22          || degree vertex + length (filter (incident vertex) remaining) < k
23
24        edge@(u, v) = head remaining
25        rest = tail remaining
26        withoutEdge = search rest degrees chosen
27        withEdge
28          | degree u >= k || degree v >= k = []
29          | otherwise = search rest
30              (Map.adjust (+ 1) u (Map.adjust (+ 1) v degrees))
31              (edge : chosen)

这个版本逐条决定边是否存在，并维护每个顶点的当前度数。如果某个顶点已经超过 $k$ ，或者剩余相邻边全部加入也达不到 $k$ ，立即剪掉整棵搜索子树。

方法对比

方法	剪枝
固定边数组合	选满 nk/2 条边后检查所有度数
剩余度数回溯	每次选边后检查上限和可达下限

测试

1>>> length (regularGraphs 6 3)
22
3>>> length (regularGraphs 4 2)
41
5>>> regularGraphs 5 3
6[]
7>>> length (regularGraphsBacktracking 4 2)
81

这是穷举实现，候选数为 $\binom{n(n-1)/2}{nk/2}$ ，只适合小图。增量构边并限制剩余度数能显著提前剪枝。

参考

← P93 算术谜题 | P95 英文数字单词 →