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について考える.すると,この問題は「頂点数 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を課しても一般性は失われない.この制約を,一意性制約と呼ぼう*1.これらの条件をまとめると,次のようになる.
 \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

ある 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}に関して最大であるとき,すべての a, bについて, x_b - x_a \leq 1.

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

さらに, f(\boldsymbol{x}) x_1, x_2, \dots , x_nに関して対称なので, f(\boldsymbol{x})の最大化にあたって一意性制約 x_i \leq x_j \;\; (1 \leq i \leq j \leq n)(すなわち, x_1 \leq x_2 \leq \dots \leq x_n)を課しても一般性は失われない. \boldsymbol{x}の各成分の値の昇順による整列の一意性より,頂点数制約・染色数制約・一意性制約のもとでは,補題3で示された必要条件を満たす \boldsymbol{x}が常に一意に存在する.ここで,すべての制約を同時に満たす \boldsymbol{x}を与えるアルゴリズムのひとつを示す.

アルゴリズム1
  • give  \; m, n
  •  i := n
  •  s := 0
  •  \boldsymbol{x} := \boldsymbol{0} \;\; (\boldsymbol{x} \in \mathbb{N}^n)
  • while  s < m do
    •  s := s + 1
    •  x_i := x_i + 1
    •  i := i - 1
    • if  i = 0 then  i := n
  • return  \boldsymbol{x}

アルゴリズム中のループ回数と \boldsymbol{x}の各成分の値の変化を見ることより,アルゴリズム1によって得られた \boldsymbol{x}が各制約を満たすことは容易に確認できる.
また, \boldsymbol{x}の各成分は次の表示をもつ.
 {\displaystyle x_i = \left\lfloor \frac{m + i - 1}{n} \right\rfloor .}

補題3に示された必要条件を満たすベクトル \boldsymbol{x}が常に一意に存在するので, fによる値を最大化するベクトルは \boldsymbol{x}である.

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

アルゴリズム2
  • give  \; m, n
  •  G := (V, E), |V| = m, E := \emptyset
  •  m, n から  fによる値を最大化するベクトル \boldsymbol{x} \;\; (\boldsymbol{x} \in \mathbb{N}^n) を計算する
  •  |S_i| = x_i \;\; (1 \leq i \leq n) を満たすよう頂点集合 V n個の独立集合 S_1, S_2, \cdots , S_nに分割する
  • 異なる独立集合に属するすべての2頂点の組み合わせ (v_1, v_2) \in V^2, \;\; v_1 \in S_i, \;\; v_2 \in S_j, \;\; i \neq jに対して, v_1 v_2の間に辺を作成する
  • グラフ Gを出力

また,これらの制約を満たすグラフのうち辺の数が最大であるすべてのグラフは互いに同型である.

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