任意の頂点 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はパスの頂点で、パスには 4 つの頂点があります)
p iはパスを意味し、p i1と p i2は v 1と v 2の間の 2 つの頂点です。
c(p i1 ) = c(p j1 ) および c(p i2 ) = c(p j2 ) となる 2 つのパス p iおよび p jが存在してはなりません。ここで、c(v) は頂点 v の色を意味します。
簡単に言えば、v 1と v 2の間のパスは区別できる必要があります。
私たちの目標は、色の数を最小限にすることです。
上記の条件を満たす着色アルゴリズムはありますか？星の色付けは確かに条件を満たしていますが、より多くの色が必要です。
これは、私があなたの質問をどのように理解したかを考えると、私の答えです。N 個の 2 頂点パスを接続するために使用できる色の最小数を見つけようとしています。
反対の解を試してみてください: x色が与えられた場合、いくつの固有のパスを生成できるか。1 番目と 2 番目の頂点が同じ色になる可能性があるかどうかは質問から明らかではなかったので、2 つの可能性を取り上げます。
同色可（置換による順列）
指定されたx色の最大x 2個の順列を生成できます。したがって、Nパスには少なくとも√N色が必要です。
色の場合 = RGB 頂点 = RR、RG、RB、GR、GG、GB、BR、BG、BB
同色不可（差し替えなしの順列）
指定された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 色が必要です)