我现在正在练习我的递归技巧,遇到了 6 色定理:
每个平面图都可以用 6 种颜色着色。
该定理源于观察到每个平面图G都有一个顶点 v,其度数小于或等于 5。
这个想法很简单:选择度数小于或等于 5 的 v。对 Gv 进行归纳着色。对 v使用第 6种颜色。
我试图在伪代码中递归地实现该定理:
colorPlanarGraph(planar Graph G=(V, E))
if |V| <= 6 then
color every node with a different color 0, ..., 5
v = vertex with degree less than or equal to 5
G' = colorPlanarGraph(G-v)
colors = [true, true, true, true, true, true]
foreach u in Adj[v] do
colors[u.color] = false;
for i=0 to 5 do
if colors[i] then
v.color = i
break
这个伪代码是否正确,我可以将每个归纳证明转换为递归算法吗?