带对角线边的网格图节点着色：要求节点的邻接点颜色互不相同

你遇到的核心问题是：普通图着色（包括NetworkX的greedy_color）仅保证相邻节点颜色不同，但不约束「同一节点的多个邻接点之间颜色互不相同」。要满足后者，需要对原图的**平方图（幂图）**进行着色，因为平方图会把原图中距离≤2的节点设为相邻，这样平方图的着色结果就能保证：

• 任意相邻节点颜色不同
• 任意节点的所有邻接点颜色也互不相同

具体实现步骤 #

1. 构造带对角线的网格图
   先创建基础网格图，再添加对角线边：

   import networkx as nx
   
   # 创建3行5列的基础网格图（可根据需求调整行列数）
   G = nx.grid_2d_graph(3, 5)
   # 添加对角线边（右上、右下方向，避免重复添加）
   for (x, y) in G.nodes():
       # 右上对角线（(x,y) → (x+1,y+1)）
       if x + 1 < 3 and y + 1 < 5:
           G.add_edge((x, y), (x+1, y+1))
       # 右下对角线（(x,y) → (x+1,y-1)）
       if x + 1 < 3 and y - 1 >= 0:
           G.add_edge((x, y), (x+1, y-1))
   

2. 生成原图的平方图
   平方图G_square中，两个节点相邻当且仅当它们在原图中的距离≤2，这样就能把需要异色的节点（比如(1,3)和(1,5)）变成相邻节点，强制着色时必须不同：

   G_square = nx.power(G, 2)
   

3. 对平方图执行贪心着色
   使用greedy_color时建议选择largest_first策略，优先给度数高的节点着色，能得到更优的颜色数：

   # 生成满足需求的着色结果
   coloring = nx.greedy_color(G_square, strategy="largest_first")
   

4. 验证结果
   以节点(1,4)为例，检查其所有邻接点的颜色是否互不相同：

   target_node = (1, 4)
   neighbors = list(G.neighbors(target_node))
   neighbor_colors = [coloring[n] for n in neighbors]
   # 输出验证结果
   print(f"节点{target_node}的邻接点颜色: {neighbor_colors}")
   print(f"邻接点颜色是否全不同: {len(set(neighbor_colors)) == len(neighbor_colors)}")
   

关键说明 #

• 普通着色无法满足你的需求，因为原图中(1,3)和(1,5)并不相邻，普通算法不会约束它们的颜色；而平方图将这两个节点设为相邻，就强制了它们必须异色。
• 平方图的着色需要更多颜色，具体数量取决于原图中节点的最大邻域大小（即某个节点的所有邻接点的数量），这是满足需求的必要条件。

内容的提问来源于stack exchange，提问作者Sundar Santhanam