https://nkhrlab.hatenablog.com/entry/2017/07/27/235102

この記事で扱う問い

無向グラフ $G = (V, E)$ の染色数を $\chi(G)$ と表すとき，グラフ $G$ に対する頂点数についての制約 $|V| = m$ および染色数についての制約 $\chi(G) = n$ を同時に満たす無向グラフのうちで，辺数が最大であるものはいかなるグラフであろうか．ただし， $2 \leq n \leq m.$

特殊な $m, n$ に対する答え

まず，特殊な $m, n$ について考えよう．

$m = 7, n = 2$ について考える*1．すると，この問題は「頂点数 $7$ ，染色数 $2$ である無向グラフ $G = (V, E)$ のうち，辺数最大なるグラフとはどのようなものか？」という問いになる．

染色数が $2$ であるから，グラフ $G$ の頂点集合 $V$ はちょうど $2$ 個の独立集合への分割 $S \in 2^{2^V}, S = \{S_1, S_2\}$ をもつはずである．さらに， $|S_1| = x_1, |S_2| = x_2$ とおくと，制約を満たすグラフのうち辺数が最大となる $G$ について，辺数は $x_1, x_2$ のみによって決まる．まずはこのことを確認しよう．

補題1

明らかに， $S_1$ に属する頂点は制約下において許されるすべての頂点，すなわち $S_2$ に属するすべての頂点との間に辺をもつから，その次数はいずれも $x_2$ となる．逆に， $S_2$ に属する頂点は $S_1$ に属するすべての頂点との間に辺をもつから，その次数はいずれも $x_1$ となる．よって，すべての頂点の次数の総和は頂点の次数を表す関数 $d(v)$ によって
$\begin{eqnarray*} \sum_{v \in V} d(v) &=& \sum_{v \in S_1} d(v) + \sum_{v \in S_2} d(v) \\ &=& \sum_{v \in S_1} x_2 + \sum_{v \in S_2} x_1 \\ &=& 2 x_1 x_2. \end{eqnarray*}$
と表せる．一方で，無向グラフに関する握手補題によれば，
$\sum_{v \in V} d(v) = 2|E|.$
であるから，これらの式から
$|E| = x_1 x_2.$
を得る．
以上のことから， $|E| = x_1 x_2.$ また，式の形を見ることより， $|E|$ は $x_1$ と $x_2$ に関して対称となる．

関数 $f(x_1, x_2) = x_1 x_2 = |E|$ を定義する．補題1により，グラフ $G$ の辺数 $|E|$ の最大化問題は $x_1, x_2$ に関する $f(x_1, x_2)$ の最大化問題に帰着される．

次に，この最大化問題を解こう．制約条件を $x_1, x_2$ に関する等式・不等式で表すことを考える．グラフ $G$ の頂点数が $7$ であることから， $x_1 + x_2 = 7.$ 染色数が $2$ であることから， $1 \leq x_1, 1 \leq x_2.$ これらの制約を，頂点数制約・染色数制約と呼ぼう．さらに， $f(x_1, x_2)$ は $x_1, x_2$ に関して対称なので， $f(x_1, x_2)$ の最大化にあたって制約 $x_1 \leq x_2$ を課しても一般性は失われない．この制約を，一意性制約と呼ぼう*2．これらの条件をまとめると，次のようになる．
$\begin{eqnarray*} x_1 + x_2 = 7. \\ 1 \leq x_1 \leq x_2. \end{eqnarray*}$
これらの条件に当てはまるすべての整数の組 $(x_1, x_2)$ に対して， $f(x_1, x_2)$ を計算すると，次のようになる．
$\begin{eqnarray*} (x_1, x_2) = (1, 6) &\Rightarrow& f(x_1, x_2) = 6. \\ (x_1, x_2) = (2, 5) &\Rightarrow& f(x_1, x_2) = 10. \\ (x_1, x_2) = (3, 4) &\Rightarrow& f(x_1, x_2) = 12. \end{eqnarray*}$
よって， $(x_1, x_2) = (3, 4)$ で $f(x_1, x_2)$ は最大値 $12$ をとる． $x_1 = |S_1|, x_2 = |S_2|, f(x_1, x_2) = |E|$ であったから，頂点集合を $3$ 個の要素からなる部分集合 $S_1$ と $4$ 個からなる部分集合 $S_2$ に分割し，すべての $(v_1, v_2) \in S_1 \times S_2$ に対して $v_1$ と $v_2$ の間に辺を作成したグラフ $G = (V, E)$ が求めるグラフである．また，その辺数は $12$ である．

グラフ $G$ の図示は次のようになる．また，ここでは独立集合 $S_1, S_2$ も同時に示した．
f:id:nkhrlab:20170726234333p:plain

一般の $m, n$ に対する答え

特殊な $m, n$ についての考察を踏まえ，一般の $m, n \;\; (2 \leq n \leq m)$ についても考えよう．

染色数が $n$ であるから，グラフ $G$ の頂点集合 $V$ はちょうど $n$ 個の独立集合への分割 $S \in 2^{2^V}, S = \{S_1, S_2, \dots , S_n \}$ をもつ．さらに， $|S_i| = x_i \;\; (1 \leq i \leq n)$ とおくと，制約を満たすグラフのうち辺数が最大となる $G$ について，辺数は $x_i \;\; (1 \leq i \leq n)$ のみによって決まる．これは補題1を一般化した次の補題2を確認することで確かめられる．

補題2

$S_i \;\; (1 \leq i \leq n)$ に属する頂点は制約下において許されるすべての頂点，すなわち $V \backslash S_i$ に属するすべての頂点との間に辺をもつから，その次数はいずれも $|V \backslash S_i| = m - x_i$ となる．よって，すべての頂点の次数の総和は頂点の次数を表す関数 $d(v)$ によって
$\begin{eqnarray*} \sum_{v \in V} d(v) &=& \sum_{i = 1}^{n} \sum_{v \in S_i} d(v) \\ &=& \sum_{i = 1}^{n} \sum_{v \in S_i} (m - x_i) \\ &=& \sum_{i = 1}^{n} x_i(m - x_i) \\ &=& m\sum_{i = 1}^{n} x_i - \sum_{i = 1}^{n} x_i^2 \\ &=& m^2 - \sum_{i = 1}^{n} x_i^2. \end{eqnarray*}$
と表せる．無向グラフに関する握手補題とあわせて，
$|E| = \frac{1}{2}\left(m^2 - \sum_{i = 1}^{n} x_i^2\right).$
を得る．
よって， $|E| = \frac{1}{2}\left(m^2 - \sum_{i = 1}^{n} x_i^2 \right).$ また，式の形を見ることより， $|E|$ は $x_i \;\; (1 \leq i \leq n)$ に関して対称となる．

以下， $\boldsymbol{x} = (x_1, x_2, \dots , x_n)$ とかき，これをベクトルとして扱う．ただし，その各成分として自然数のみをとりうることに注意．
関数 $f(\boldsymbol{x}) = \frac{1}{2}\left(m^2 - \sum_{i = 1}^{n} x_i^2 \right) = |E|$ を定義する．補題2により，グラフ $G$ の辺数 $|E|$ の最大化問題は $\boldsymbol{x}$ に関する $f(\boldsymbol{x})$ の最大化問題に帰着される．

次に，この最大化問題を解くことを考える．制約条件を $\boldsymbol{x}$ に関する等式・不等式で表そう．グラフ $G$ の頂点数が $m$ であることから， $\sum_{i = 1}^{n} x_i = m.$ 染色数が $n$ であることから， $1 \leq x_i \;\; (1 \leq i \leq n).$ これらの頂点数制約・染色数制約をまとめると，次のようになる．
$\begin{eqnarray*} \sum_{i = 1}^{n} x_i &=& m. \\ 1 \leq &x_i& \;\; (1 \leq i \leq n).\end{eqnarray*}$
次に， $f(\boldsymbol{x})$ が $\boldsymbol{x}$ に関して最大であることの必要条件を次の補題3で示す．

補題3

頂点数制約・染色数制約を満たすベクトル $\boldsymbol{x} = (x_1, x_2, \dots , x_n)$ を考え，ある $a, b \;\; (1 \leq a \leq n, 1 \leq b \leq n, a \neq b)$ について， $x_b - x_a \geq 2$ が成立すると仮定する．さらに， $\boldsymbol{x}$ の第 $a$ 成分を $x_a + 1$ に，第 $b$ 成分を $x_b - 1$ にそれぞれ置き換えたベクトルを新たに $\boldsymbol{x^{\ast}}$ とおく．すると，ベクトル $\boldsymbol{x^{\ast}}$ もまた頂点数制約・染色数制約を満たす．さらに，
$\begin{eqnarray*} f(\boldsymbol{x}) &=& \frac{1}{2}\left(m^2 - \sum_{i = 1}^{n} x_i^2 \right) \\ &=& \frac{1}{2}\left(m^2 - \sum_{\substack{i = 1 \\ i \neq a, b}}^{n} x_i^2 \right) - \frac{1}{2}\left(x_a^2 + x_b^2 \right). \\ f(\boldsymbol{x^{\ast}}) &=& \frac{1}{2}\left(m^2 - \sum_{\substack{i = 1 \\ i \neq a, b}}^{n} x_i^2 \right) - \frac{1}{2}\left((x_a + 1)^2 + (x_b - 1)^2 \right) \\ &=& \frac{1}{2}\left(m^2 - \sum_{\substack{i = 1 \\ i \neq a, b}}^{n} x_i^2 \right) - \frac{1}{2}\left(x_a^2 + x_b^2 \right) + (x_b - x_a) - 1.\end{eqnarray*}$
したがって，
$f(\boldsymbol{x^{\ast}}) - f(\boldsymbol{x}) = (x_b - x_a) - 1.$
仮定より $x_b - x_a \geq 2$ だから，
$f(\boldsymbol{x^{\ast}}) - f(\boldsymbol{x}) \geq 1.$
以上のことから，
$f(\boldsymbol{x}) < f(\boldsymbol{x^{\ast}}).$
よって，ある $a, b$ について， $x_b - x_a \geq 2$ が成立するとき， $f(\boldsymbol{x})$ の値よりも $f(\boldsymbol{x^{\ast}})$ のほうが大きいから， $f(\boldsymbol{x})$ の値は $\boldsymbol{x}$ に関して最大でない．
対偶をとれば， $f(\boldsymbol{x})$ の値が $\boldsymbol{x}$ に関して $\boldsymbol{x} = \hat{\boldsymbol{x}} = (\hat{x_1}, \hat{x_2}, \dots , \hat{x_n})$ で最大であるとき，すべての $a, b$ について， $\hat{x_b} - \hat{x_a} \leq 1.$ すなわち，ベクトル $\hat{\boldsymbol{x}}$ の最大の成分 $\hat{x_{\mathrm{max}}}$ と最小の成分 $\hat{x_{\mathrm{min}}}$ に対して， $\hat{x_{\mathrm{max}}} - \hat{x_{\mathrm{min}}} \leq 1.$ したがって， $\hat{x_{\mathrm{max}}} \leq \hat{x_{\mathrm{min}}} + 1.$
さらに， $\hat{x_{\mathrm{min}}} \leq \hat{x_i} \leq \hat{x_{\mathrm{max}}} \;\; (1 \leq i \leq n)$ であることから， $\hat{x_{\mathrm{min}}} \leq \hat{x_i} \leq \hat{x_{\mathrm{min}}} + 1 \;\; (1 \leq i \leq n).$
ところで，ベクトル $\hat{\boldsymbol{x}}$ の成分の平均 $\frac{1}{n}\sum_{i = 1}^{n} \hat{x_i} = \frac{m}{n}$ について，最大の成分および最小の成分との間に次の関係が成り立つ．
$\hat{x_{\mathrm{min}}} \leq \frac{m}{n} \leq \hat{x_{\mathrm{max}}}.$
したがって，
$\hat{x_{\mathrm{min}}} \leq \frac{m}{n} \leq \hat{x_{\mathrm{min}}} + 1 .$
ここで， $\frac{m}{n} = \hat{x_{\mathrm{min}}} + 1$ と仮定すると $\hat{x_{\mathrm{max}}} \leq \frac{m}{n}$ が導かれ，さらに最小値・最大値・平均値の関係から $\hat{x_{\mathrm{min}}} = \hat{x_{\mathrm{max}}} = \frac{m}{n}$ が得られる．ところが，これは $\frac{m}{n} = \hat{x_{\mathrm{min}}} + 1$ とした仮定に矛盾するから， $\frac{m}{n} \neq \hat{x_{\mathrm{min}}} + 1 .$
したがって，
$\hat{x_{\mathrm{min}}} \leq \frac{m}{n} < \hat{x_{\mathrm{min}}} + 1 .$
よって， $\hat{x_{\mathrm{min}}}$ は $\frac{m}{n}$ を超えない最大の整数だから，
$\hat{x_{\mathrm{min}}} = \left\lfloor \frac{m}{n} \right\rfloor .$
以上のことを合わせて，
$\left\lfloor \frac{m}{n} \right\rfloor \leq \hat{x_i} \leq \left\lfloor \frac{m}{n} \right\rfloor + 1 \;\; (1 \leq i \leq n).$

これで， $f(\boldsymbol{x})$ が $\boldsymbol{x}$ に関して最大であることの必要条件が示された．

さらに， $f(\boldsymbol{x})$ は $x_1, x_2, \dots , x_n$ に関して対称なので， $f(\boldsymbol{x})$ の最大化にあたって一意性制約 $x_i \geq x_j \;\; (1 \leq i \leq j \leq n)$ (すなわち， $x_1 \geq x_2 \geq \dots \geq x_n$ )を課しても一般性は失われない．また，頂点数制約・染色数制約・一意性制約のもとでは，補題3で示された必要条件を満たすベクトル $\boldsymbol{x} = \hat{\boldsymbol{x}}$ が常に一意に存在し， $\hat{\boldsymbol{x}}$ を $m, n$ によって陽に表示することができる．このことを示そう．

補題4

補題3より，各成分 $\hat{x_i} \;\; (1 \leq i \leq n)$ について， $\hat{x_i} = \left\lfloor \frac{m}{n} \right\rfloor$ または $\hat{x_i} = \left\lfloor \frac{m}{n} \right\rfloor + 1.$
一意性制約のもとでは， $\hat{x_i} \;\; (1 \leq i \leq n)$ の成分は整数 $c \;\; (0 \leq c \leq n)$ によって次のようにかける．
$\begin{equation*} \hat{x_i} = \begin{cases} \left\lfloor \frac{m}{n} \right\rfloor + 1 & (1 \leq i \leq c) \\ \left\lfloor \frac{m}{n} \right\rfloor & (c + 1 \leq i \leq n) \end{cases} \end{equation*}$
さらに，頂点数制約より，
$\begin{eqnarray*} m = \sum_{i = 1}^{n} \hat{x_i} &=& c \left(\left\lfloor \frac{m}{n} \right\rfloor + 1 \right) + (n - c)\left\lfloor \frac{m}{n} \right\rfloor \\ &=& c + n\left\lfloor \frac{m}{n} \right\rfloor. \end{eqnarray*}$
よって，
$c = m - n\left\lfloor \frac{m}{n} \right\rfloor.$ ( $m$ を $n$ で割った剰余に等しい．)
$m, n$ に対して $c$ が常に一意に存在することから，頂点数制約・染色数制約・一意性制約のもとでは，補題3で示された必要条件を満たすベクトル $\hat{\boldsymbol{x}}$ が常に一意に存在する．
また， $\hat{\boldsymbol{x}}$ の各成分は次の表示をもつ．
$\hat{x_i} = \left\lfloor \frac{m - i}{n} \right\rfloor + 1 \;\; (1 \leq i \leq n).$

$f(\boldsymbol{x}) = |E| \leq |V|^2$ より $f(\boldsymbol{x})$ が上に有界であることと補題4から， $\hat{\boldsymbol{x}}$ は $f$ による値を最大化する．また $f(\hat{\boldsymbol{x}})$ の値は， $f(\boldsymbol{x})$ の表式に補題4の結果を代入，整理することより，次のようになる．
$f(\hat{\boldsymbol{x}}) = \frac{1}{2} \left( m^2 - \left(2 \left\lfloor \frac{m}{n} \right\rfloor + 1 \right)m + n \left\lfloor \frac{m}{n} \right\rfloor \left(\left\lfloor \frac{m}{n} \right\rfloor + 1 \right) \right).$

特に，この式に $m = 7, n = 2$ を代入すると $f(\hat{\boldsymbol{x}}) = 12$ となり，この記事の初めに取り上げた特殊な $m, n$ の例に対する結論に一致する．

以上のことから，グラフ $G$ に対する頂点数についての制約 $|V| = m$ および染色数についての制約 $\chi(G) = n$ を同時に満たす無向グラフのうちで，辺数が最大であるものの一つは次のアルゴリズムにより得られる．

アルゴリズム1

give $\; m, n$

$G := (V, E), |V| = m, E := \emptyset$

$m, n$ から $f$ による値を最大化するベクトル $\hat{\boldsymbol{x}} \;\; (\hat{\boldsymbol{x}} \in \mathbb{N}^n)$ を補題4により計算する

$|S_i| = \hat{x_i} \;\; (1 \leq i \leq n)$ を満たすよう頂点集合 $V$ を $n$ 個の独立集合 $S_1, S_2, \cdots , S_n$ に分割する

異なる独立集合に属するすべての2頂点の組み合わせ $\{v_1, v_2\} \subset V^2, \;\; v_1 \in S_i, \;\; v_2 \in S_j, \;\; i \neq j$ に対して， $E := E \cup \left\{\{v_1, v_2\}\right\}$

グラフ $G$ を出力，このとき $|E| = \frac{1}{2} \left( m^2 - m\left(2 \left\lfloor \frac{m}{n} \right\rfloor + 1 \right) + n \left\lfloor \frac{m}{n} \right\rfloor \left(\left\lfloor \frac{m}{n} \right\rfloor + 1 \right) \right).$