3

我想为图着色，以便对于任何顶点 v 1和 v 2，如果它们之间有 n 条路径：

p 1 = (v 1 , p 11 ,p 12 ,v 2 )
p 2 = (v 1 , p 21 ,p 22 ,v 2 )
...
p n = (v 1 , p n1 ,p n2 ,v 2 )

（p 11 ,p 12是路径的顶点，路径有四个顶点）

p i表示一条路径， p i1和 p i2是 v 1和 v 2之间的两个顶点。

不能存在两条路径 p i和 p j使得 c(p i1 ) = c(p j1 ) 和 c(p i2 ) = c(p j2 )，其中 c(v) 表示顶点 v 的颜色。

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

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

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

4

1 回答 1

1

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

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

  1. 允许相同的颜色（置换置换）

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

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

  2. 不允许相同颜色（无替换排列）

    给定x颜色 max x P 2可以生成排列。即 x 2 -x ≥ N。求解二次不等式会给你

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

    x = 地板((1 + √(1 + 4 N ))/2)

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

于 2013-10-30T14:56:19.513 回答