algorithm - 6 平面图上的颜色定理递归实现

Question

我现在正在练习我的递归技巧，遇到了 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

这个伪代码是否正确，我可以将每个归纳证明转换为递归算法吗？

标签： algorithmrecursiongraphplanar-graph

Answer 1

这个伪代码是否正确

我觉得很好。我们必须查看细节才能理解它的复杂性，但这当然是有道理的。

我可以将每个归纳证明转换为递归算法吗？

我不确定这个问题是否有意义。证明不一定转化为可以用算法描述的东西。这可能适用于存在定理的证明。（在这里我们证明了 6 色的存在。）但我什至不确定。在其他情况下，我不知道这意味着什么。