nkhrlab~

140字超の記事

無向グラフに関する頂点数・染色数制約下での辺数の最大化

この記事で扱う問い

無向グラフ 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*}
と表せる.一方で,無向グラフに関する握手補題によれば,
 {\displaystyle \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*}
と表せる.無向グラフに関する握手補題とあわせて,
 {\displaystyle |E| = \frac{1}{2}\left(m^2 - \sum_{i = 1}^{n} x_i^2\right).}
を得る.

よって, {\displaystyle |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)とかき,これをベクトルとして扱う.ただし,その各成分として自然数のみをとりうることに注意.
関数 {\displaystyle 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であることから, {\displaystyle \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}}の成分の平均 {\displaystyle \frac{1}{n}\sum_{i = 1}^{n} \hat{x_i} = \frac{m}{n}}について,最大の成分および最小の成分との間に次の関係が成り立つ.
 {\displaystyle \hat{x_{\mathrm{min}}} \leq \frac{m}{n} \leq \hat{x_{\mathrm{max}}}. }
したがって,
 {\displaystyle \hat{x_{\mathrm{min}}} \leq \frac{m}{n} \leq \hat{x_{\mathrm{min}}} + 1 .}
ここで, {\displaystyle  \frac{m}{n} = \hat{x_{\mathrm{min}}} + 1 }と仮定すると {\displaystyle \hat{x_{\mathrm{max}}} \leq \frac{m}{n} }が導かれ,さらに最小値・最大値・平均値の関係から {\displaystyle \hat{x_{\mathrm{min}}} = \hat{x_{\mathrm{max}}} = \frac{m}{n} }が得られる.ところが,これは {\displaystyle  \frac{m}{n} = \hat{x_{\mathrm{min}}} + 1 }とした仮定に矛盾するから, {\displaystyle  \frac{m}{n} \neq \hat{x_{\mathrm{min}}} + 1 .}
したがって,
 {\displaystyle \hat{x_{\mathrm{min}}} \leq \frac{m}{n} < \hat{x_{\mathrm{min}}} + 1 .}
よって, {\displaystyle \hat{x_{\mathrm{min}}}} {\displaystyle \frac{m}{n}}を超えない最大の整数だから,
 {\displaystyle \hat{x_{\mathrm{min}}} = \left\lfloor \frac{m}{n} \right\rfloor .}

以上のことを合わせて,
 {\displaystyle \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) について, {\displaystyle \hat{x_i} = \left\lfloor \frac{m}{n} \right\rfloor } または  {\displaystyle \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*}
よって,
 {\displaystyle c = m - n\left\lfloor \frac{m}{n} \right\rfloor. } ( m nで割った剰余に等しい.)

 m, nに対して cが常に一意に存在することから,頂点数制約・染色数制約・一意性制約のもとでは,補題3で示された必要条件を満たすベクトル \hat{\boldsymbol{x}}が常に一意に存在する.
また, \hat{\boldsymbol{x}}の各成分は次の表示をもつ.
 {\displaystyle \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の結果を代入,整理することより,次のようになる.
 {\displaystyle 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を代入すると {\displaystyle 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を出力,このとき {\displaystyle |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). }

また,ベクトル \hat{\boldsymbol{x}} の一意性とアルゴリズム1によるグラフ Gの作り方から,各制約を満足するグラフのうち辺の数が最大であるすべてのグラフは互いに同型である.

*1:この m, nの組み合わせに対する問題は大学院の入学試験でも出題例がある.

*2:ここでは,専ら考慮すべきx_1, x_2の組み合わせを減らすことを目的として導入した.