algorithm - 恰好 k 种颜色的图形着色

Question

考虑具有 V 个顶点和 E 个边的图 G(V,E)。我们想用恰好 K 种颜色给顶点图着色。

着色图是指以两个相邻顶点不应该具有相同颜色的方式为每个节点分配颜色。

我们如何实现这个问题？

Answer 1

首先让我们注意2个假设:

1. 如果|V| < k 那么这是不可能的 - 所以假设 |V| >= k。
2. 如果我们可以用少于 k 种颜色和 |v| 给图上色> k 然后也可以使用恰好 k 种颜色 - 我们可以将重复的颜色与我们尚未使用的颜色切换。

我们可以使用贪心算法来解决这个问题。

让我们为每种颜色分配编号 [1,2,...,k] - 让我们用 Ci 表示颜色 i。从任意节点v1开始，给他赋值C1。现在让每个节点在图形上运行 BSF，选择其调整节点中不存在的最小颜色 - 如果另一个节点没有颜色，则忽略它们。如果 d(v) > k 并且他所有的调整都是不同的颜色则返回 false。

伪代码:

// v.color init as 0 for all V
Queue <- new Queue(v1)
While Queue not empty:
    current <- Queue.pop
    if (current.color != 0 )
         continue
    adjs <- current.getAdj()
    colors = new Set
    for each adjs as adj:
        colors.add(adj.colors)
    for i = 1 to k:
        if i not in colors: //found lowest color avilable
             current.color <- C[i]
             break
    if current.color == 0 return false // cannot assign any color
    Queue.insert(adjs)