無向グラフに関する頂点数・染色数制約下での辺数の最大化
この記事で扱う問い
無向グラフの染色数をと表すとき,グラフに対する頂点数についての制約および染色数についての制約を同時に満たす無向グラフのうちで,辺数が最大であるものはいかなるグラフであろうか.ただし,
特殊なに対する答え
まず,特殊なについて考えよう.
について考える*1.すると,この問題は「頂点数,染色数である無向グラフのうち,辺数最大なるグラフとはどのようなものか?」という問いになる.
染色数がであるから,グラフの頂点集合はちょうど個の独立集合への分割をもつはずである.さらに,とおくと,制約を満たすグラフのうち辺数が最大となるについて,辺数はのみによって決まる.まずはこのことを確認しよう.
関数を定義する.補題1により,グラフの辺数の最大化問題はに関するの最大化問題に帰着される.
次に,この最大化問題を解こう.制約条件をに関する等式・不等式で表すことを考える.グラフの頂点数がであることから,染色数がであることから,これらの制約を,頂点数制約・染色数制約と呼ぼう.さらに,はに関して対称なので,の最大化にあたって制約を課しても一般性は失われない.この制約を,一意性制約と呼ぼう*2.これらの条件をまとめると,次のようになる.
これらの条件に当てはまるすべての整数の組に対して,を計算すると,次のようになる.
よって,では最大値をとる.であったから,頂点集合を個の要素からなる部分集合と個からなる部分集合に分割し,すべてのに対してとの間に辺を作成したグラフが求めるグラフである.また,その辺数はである.
グラフの図示は次のようになる.また,ここでは独立集合も同時に示した.
一般のに対する答え
特殊なについての考察を踏まえ,一般のについても考えよう.
染色数がであるから,グラフの頂点集合はちょうど個の独立集合への分割をもつ.さらに,とおくと,制約を満たすグラフのうち辺数が最大となるについて,辺数はのみによって決まる.これは補題1を一般化した次の補題2を確認することで確かめられる.
以下,とかき,これをベクトルとして扱う.ただし,その各成分として自然数のみをとりうることに注意.
関数を定義する.補題2により,グラフの辺数の最大化問題はに関するの最大化問題に帰着される.
次に,この最大化問題を解くことを考える.制約条件をに関する等式・不等式で表そう.グラフの頂点数がであることから,染色数がであることから,これらの頂点数制約・染色数制約をまとめると,次のようになる.
次に,がに関して最大であることの必要条件を次の補題3で示す.
補題3
頂点数制約・染色数制約を満たすベクトルを考え,あるについて,が成立すると仮定する.さらに,の第成分をに,第成分をにそれぞれ置き換えたベクトルを新たにとおく.すると,ベクトルもまた頂点数制約・染色数制約を満たす.さらに,
したがって,
仮定よりだから,
以上のことから,
よって,あるについて,が成立するとき,の値よりものほうが大きいから,の値はに関して最大でない.
対偶をとれば,の値がに関してで最大であるとき,すべてのについて, すなわち,ベクトルの最大の成分と最小の成分に対して,したがって,
さらに,であることから,
ところで,ベクトルの成分の平均について,最大の成分および最小の成分との間に次の関係が成り立つ.
したがって,
ここで,と仮定するとが導かれ,さらに最小値・最大値・平均値の関係からが得られる.ところが,これはとした仮定に矛盾するから,
したがって,
よって,はを超えない最大の整数だから,
以上のことを合わせて,
これで,がに関して最大であることの必要条件が示された.
さらに,はに関して対称なので,の最大化にあたって一意性制約(すなわち,)を課しても一般性は失われない.また,頂点数制約・染色数制約・一意性制約のもとでは,補題3で示された必要条件を満たすベクトルが常に一意に存在し,をによって陽に表示することができる.このことを示そう.
よりが上に有界であることと補題4から,はによる値を最大化する.またの値は,の表式に補題4の結果を代入,整理することより,次のようになる.
特に,この式にを代入するととなり,この記事の初めに取り上げた特殊なの例に対する結論に一致する.
以上のことから,グラフに対する頂点数についての制約および染色数についての制約を同時に満たす無向グラフのうちで,辺数が最大であるものの一つは次のアルゴリズムにより得られる.
また,ベクトルの一意性とアルゴリズム1によるグラフの作り方から,各制約を満足するグラフのうち辺の数が最大であるすべてのグラフは互いに同型である.