平面图递归实现的6个颜色定理

Question

我目前正在练习我的递归技巧，并遇到了 6 色定理，该定理指出：

每个平面图都可以用 6 种颜色着色。

该定理是根据观察得出的，即每个平面图 G 的顶点 v 的度数小于或等于 5。

思路很简单：选择次数小于或等于5的v。归纳地给G-v上色。 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

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

Answer 1

Is this pseudo code correct

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

and can I transform every inductive proof into a recursive algorithm?

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

平面图递归实现的6个颜色定理

6 color theorem on planar graphs recursive implementation

algorithm

recursion

graph

planar-graph