algorithm - 用最少的颜色给图表着色

Question

我想给图上色，这样对于任何顶点 v₁ 和 v₂，如果它们之间有 n 条路径:

p₁ = (v₁, p₁₁,p₁₂,v_{2)
p2 = (v1, p21,p22,v2 )
...
pn = (v1, pn1,pn2,v2 )}

(p₁₁,p₁₂是路径的顶点，路径有四个顶点)

p_i表示一条路径，p_i1和p_i2是v₁和v₁之间的两个顶点v<子>2。

不能存在两条路径 p_i 和 p_j 使得 c(p_i1) = c(p _j1) 和 c(p_i2) = c(p_j2)，其中 c(v) 表示顶点 v 的颜色。

简单来说，v₁和v₂之间的路径应该是可区分的。

我们的目标是尽量减少颜色的数量。

是否有满足上述条件的着色算法？星星着色肯定满足条件，但需要更多颜色。

Answer 1

根据我对您问题的理解，这是我的回答。您正在尝试找出可用于连接 N 2 顶点路径的最少颜色数。

尝试解决相反的问题:给定 x 颜色，您可以生成多少条独特的路径。从问题中不清楚第一个和第二个顶点是否可以具有相同的颜色，所以我将采用两种可能性:

1. 允许相同的颜色(替换排列)

   给定 x 种颜色最多可以生成 x² 排列。所以 N 条路径至少需要 √N 种颜色。

   对于颜色 = RGB 顶点 = RR,RG,RB,GR,GG,GB,BR,BG,BB

2. 不允许相同的颜色(没有替换的排列)

   给定 x 种颜色，可以生成最大 ^xP₂ 个排列。那是 x²-x ≥ N. 求解二次不等式会得到

   x ≥ (1 ± √(1 + 4 N))/2

   x = floor((1 + √(1 + 4 N))/2)

   对于颜色 = RGB 顶点 = RG、RB、GR、GB、BR、BG (给定 7 条路径，你需要 4 种颜色)