创建图形的所有适当着色的集合

Question

给定一个图 G(V,E)，其中 |V|=n 和 k<n（此处 k 对应于颜色数），我正在尝试创建所有正确的集合它在 Python 中的着色，即 V 中的每个 v 的颜色都与其邻居的颜色不同。

我的尝试：我想先创建一个包含所有可能颜色的列表（有 k^n 个），然后遍历此列表以应用约束以获得正确颜色的列表。在数据结构方面，我正在考虑为每种着色使用一个字典，其中顶点号是键，值是列表的列表。这个列表的第一个元素是顶点的颜色，第二个是它的邻居列表。为了创建所有的颜色，是否有一种递归的方法来生成这些颜色？随机图的代码是：

def Graph(n):
    g={}
    for i in range(n):
        r=random.choice([i+1 for i in range(n)])
        v=[i for i in range(n)]
        v.remove(i)
        g[i]=random.sample(v,r)

    return g

Answer 1

def fillRemainingColors(coloringSoFar,g):
    if all colors filled:
        return [coloringSoFar]
    else:
       Pick a uncolored spot to color
       coloringsToReturn = []
       For each possible color for that spot:
           newColoring = fill(coloringSoFar, spot, color)
           coloringsToReturn += fillRemainingColors(newColoring,g)
       return coloringsToReturn

创建图形的所有适当着色的集合

Creating the set of all proper colorings of a graph

python

recursion