6-2 貪欲彩色と退化度
前提知識：グラフ彩色、平面性判定の構造
greedy算法の成否は順序で決まる
「グラフ彩色」では、頂点を一つずつ見て、既に塗られた隣接頂点が使っていない最小の色を選ぶgreedy coloringを導入しました。最大次数を $\Delta$ とすれば、どの順序でも高々 $\Delta+1$ 色です。
しかし同じgraphでも順序を変えると使用色数は変わります。重要なのは「各頂点を塗る時点で、先に塗られた隣接頂点が何個いるか」です。退化度は、全ての部分graphに必ず低次数頂点があることを使い、そのような良い順序を後ろから作ります。
順序付きgreedy bound
頂点順序
$$
v_1,v_2,\ldots,v_n
$$
に対して、$v_i$ より前に置かれた隣接頂点の個数
$$
b_i=\bigl|N(v_i)\cap\{v_1,\ldots,v_{i-1}\}\bigr|
$$
を $v_i$ の後方次数|backward degreeという。
順序 $v_1,\ldots,v_n$ に沿ってgreedy coloringを行うと、使用色数は
$$
1+\max_i b_i
$$
以下である。
$v_i$ を塗る時点で既に色をもつ隣接頂点は、順序で前にあるものだけです。その個数は $b_i$ なので、禁止される色は高々 $b_i$ 個です。
従って色 $1,2,\ldots,b_i+1$ の中には少なくとも一色、禁止されていないものがあります。greedy算法は使用可能な最小色を選ぶので、$v_i$ の色は高々 $b_i+1$ です。全頂点について最大を取れば結論を得ます。□
最大次数上界 $\chi(G)\le\Delta(G)+1$ は、$b_i\le\deg(v_i)\le\Delta(G)$ と置いた特別な場合です。順序を工夫すれば $\Delta$ よりずっと小さい上界が得られます。
二部を
$$
A=\{a_1,\ldots,a_r\},\qquad B=\{b_1,\ldots,b_r\}
$$
とし、$a_i b_j$ を $i\ne j$ のとき全て結ぶcrown graphを考えます。二部graphなので、本当の彩色数は2です。
ところが
$$
a_1,b_1,a_2,b_2,\ldots,a_r,b_r
$$
の順でfirst-fit greedy coloringを行うと、$a_i,b_i$ はともに色 $i$ になります。実際、$a_i$ は先に塗られた $b_1,\ldots,b_{i-1}$ と全て隣接するため色 $1,\ldots,i-1$ を使えず、$b_i$ も同様に $a_1,\ldots,a_{i-1}$ と隣接します。一方 $a_i,b_i$ は非隣接なので同じ色 $i$ を使えます。
したがって2-colorable graphでも、悪い順序ならgreedy算法は $r$ 色を使います。退化順序はこの危険を一様に抑えます。
退化度
非負整数 $k$ に対して、graph $G$ が $k$-degenerateであるとは、$G$ の全ての非空部分graphが次数 $k$ 以下の頂点をもつことをいう。
$G$ が $k$-degenerateとなる最小の $k$ を退化度といい、
$$
d(G)
$$
と書く。
「全ての部分graph」を調べる定義は強く見えますが、頂点を一つずつ削る順序と同値です。
有限graph $G$ と非負整数 $k$ に対して次は同値である。
- $G$ は $k$-degenerateである。
- 頂点を
$$ u_1,u_2,\ldots,u_n $$
と並べ、各 $u_i$ が後ろの集合 $\{u_{i+1},\ldots,u_n\}$ に高々 $k$ 個の隣接頂点しかもたないようにできる。 - 頂点を
$$ v_1,v_2,\ldots,v_n $$
と並べ、各頂点のbackward degreeを高々 $k$ にできる。
1を仮定します。$G$ 自身に次数 $k$ 以下の頂点があるので、それを $u_1$ として削除します。残った誘導部分graphも $G$ の部分graphなので、再び次数 $k$ 以下の頂点 $u_2$ があります。これを空になるまで繰り返します。
$u_i$ を選んだ時点で残っているのは $u_i,u_{i+1},\ldots,u_n$ です。従って $u_i$ の後ろの隣接頂点数は、その時点の次数であり高々 $k$ です。よって2です。
2の順序を逆にして
$$
v_i=u_{n+1-i}
$$
と置きます。$v_i$ より前の頂点は、元の $u$ 順序で $u_{n+1-i}$ より後ろにあった頂点です。その隣接数は高々 $k$ なので3です。
3を仮定し、$H$ を任意の非空部分graphとします。$H$ の頂点のうち、順序で最も後ろにあるものを $v_j$ とします。$H$ 内の他の全頂点は $v_j$ より前にあるため、
$$
\deg_H(v_j)\le b_j\le k.
$$
従って全ての非空部分graphに次数 $k$ 以下の頂点があり、1です。□
証明はそのまま算法です。現在次数が最小の頂点を削除してstackへ積み、最後にstackを逆順で取り出せば退化順序が得られます。
退化度のmin--max表示
部分graph $H$ の最小次数を $\delta(H)$ と書きます。
有限graph $G$ に対して
$$
d(G)=\max_{\varnothing\ne H\subseteq G}\delta(H).
$$
右辺では全ての非空部分graphを動かす。
右辺を $r$ とします。全ての非空部分graph $H$ で $\delta(H)\le r$ なので、各 $H$ は次数 $r$ 以下の頂点をもちます。従って $G$ は $r$-degenerateであり、
$$
d(G)\le r.
$$
一方、最大値を達成する部分graph $H_0$ では全頂点次数が少なくとも $r$ です。もし $G$ が $(r-1)$-degenerateなら、$H_0$ に次数 $r-1$ 以下の頂点が必要となり矛盾します。従って $d(G)\ge r$ です。両不等式から等号を得ます。□
任意の部分graph $H$ を、その頂点集合が誘導するgraph $G[V(H)]$ へ置き換えると辺は増えるだけなので最小次数は下がりません。従って最大値は誘導部分graphだけを調べても同じです。
treeに二頂点以上あれば、全ての非空部分forestは孤立頂点またはleafをもつので $d(T)\le1$ です。辺を含む部分graphの最小次数は1なので $d(T)=1$ です。
cycle $C_n$ は全頂点次数2なので $d(C_n)\ge2$、最大次数も2なので $d(C_n)=2$ です。
完全graph $K_n$ は最小次数 $n-1$ なので
$$
d(K_n)=n-1.
$$
完全二部graph $K_{p,q}$ では、$p\le q$ とすると全体の最小次数は $p$ です。一方、どの部分graphにも $q$ 側由来の頂点があればその次数は高々 $p$ なので
$$
d(K_{p,q})=p=\min\{p,q\}.
$$
退化度から彩色する
有限graph $G$ は
$$
d(G)+1
$$
色でproperに頂点彩色できる。特に
$$
\chi(G)\le d(G)+1\le\Delta(G)+1.
$$
$k=d(G)$ とし、退化順序の特徴づけからbackward degreeが高々 $k$ の順序を取ります。この順序でgreedy coloringを行えば、ordering greedy boundにより高々 $k+1$ 色です。
また任意の部分graphの最小次数はその最大次数以下なので
$$
d(G)=\max_H\delta(H)\le\Delta(G).
$$
従って二つ目の不等式も得られます。□
$G$ のclique numberを $\omega(G)$ とすると
$$
\omega(G)\le d(G)+1.
$$
$r$ 頂点clique $K_r$ は $G$ の部分graphで、その最小次数は $r-1$ です。min--max公式から
$$
d(G)\ge r-1.
$$
最大の $r=\omega(G)$ を取れば結論を得ます。□
この下界と彩色上界が一致するgraphもありますが、一般には一致しません。例えば奇cycleは $d=2$ で3色必要なので一致し、偶cycleは同じ退化度2でも2色で足ります。
$k$-coreとpeeling
graph $G$ の $k$-core（k-core）とは、最小次数が少なくとも $k$ である極大な誘導部分graphをいう。空graphになる場合も許す。
$G$ の $k$-coreは一意であり、次数 $k$ 未満の頂点をなくなるまで任意の順序で削除して得られる。
最小次数が少なくとも $k$ の誘導部分graph $G[A]$ と $G[B]$ があるとします。$A$ の頂点は $A\cup B$ 内でも $A$ 内にいた少なくとも $k$ 個の隣接頂点を保ち、$B$ の頂点も同様です。従って $G[A\cup B]$ の最小次数も少なくとも $k$ です。
したがって、その性質をもつ全頂点集合の和集合が最大の一つを作り、$k$-coreは一意です。
peelingで削除される頂点 $v$ は、削除時点の残存graphで次数 $k$ 未満です。もし $v$ がある最小次数 $k$ 以上の誘導部分graph $H$ に属したなら、$v$ より先に削除された $H$ の頂点を最初のものとして取ると、その削除時点では他の $H$ 頂点が全て残っており、次数は少なくとも $k$ のはずで矛盾します。従って削除頂点はどの候補coreにも属しません。
停止時に残った誘導部分graphは最小次数が少なくとも $k$ です。削除頂点は最大候補へ入れず、残存頂点は候補を作るので、それが一意な $k$-coreです。削除順序によらないことも従います。□
$d(G)$ は、非空な $k$-coreが存在する最大の $k$ に等しい。
非空な $k$-coreがあれば、それは最小次数 $k$ 以上の部分graphなのでmin--max公式から $d(G)\ge k$ です。
逆に $d(G)=r$ なら、最小次数 $r$ の部分graphが存在します。その頂点集合が誘導するgraphも最小次数 $r$ 以上なので、$r$-coreは非空です。従って最大値は $r$ です。□
$k$-coreはnetworkの「互いに少なくとも $k$ 本の接続を保つ密な中心部」を抽出します。退化度は、そのcoreが何段階まで残るかを一つの数にまとめたものです。
acyclic orientationとの同値
無向graphの各辺へ向きを付けて有向cycleが生じないとき、その向き付けを非巡回向き付け|acyclic orientationという。
有限graph $G$ に対して
$$
d(G)=
\min_{\mathcal O}
\max_{v\in V(G)}\deg_{\mathcal O}^+(v),
$$
ここで $\mathcal O$ は全acyclic orientationを動き、$\deg_{\mathcal O}^+(v)$ はoutdegreeである。
$k=d(G)$ とし、各頂点が後ろに高々 $k$ 個の隣接頂点をもつ退化順序 $u_1,\ldots,u_n$ を取ります。各辺を順序の前から後ろへ向けます。添字は有向辺に沿って真に増えるので有向cycleはありません。各 $u_i$ のoutdegreeは後ろの隣接頂点数であり高々 $k$ です。従って右辺は $k$ 以下です。
逆にacyclic orientation $\mathcal O$ を取り、最大outdegreeを $r$ とします。有限acyclic digraphにはsourceを順に削除するtopological ordering
$$
u_1,\ldots,u_n
$$
があり、全arcは前から後ろへ向きます。従って各 $u_i$ の後ろの隣接頂点数はoutdegree以下で、高々 $r$ です。退化順序の特徴づけから $d(G)\le r$ です。全orientationで最小を取れば右辺は $d(G)$ 以上となり、等号です。□
順序・peeling・core・acyclic orientationは同じ疎性を別の言葉で見ています。問題に合う表現へ切り替えられることが抽象化の利点です。
planar graphへの適用
頂点数3以上のsimple planar graphは5-degenerateである。さらにtriangle-freeなら3-degenerateである。
simple planar graphの任意の部分graphもsimple planarです。頂点数 $n_H\ge3$ の非空部分graph $H$ に対して、「平面グラフ」の辺数評価から
$$
|E(H)|\le3|V(H)|-6.
$$
従って平均次数は
$$
\frac{2|E(H)|}{|V(H)|}<6.
$$
全頂点次数が6以上なら平均も6以上になるので、$H$ は次数5以下の頂点をもちます。頂点数1または2でも次数は高々1です。従って元のgraphは5-degenerateです。
triangle-freeの場合、任意の部分graphもtriangle-freeであり、
$$
|E(H)|\le2|V(H)|-4
$$
です。頂点数3以上なら平均次数は4未満なので次数3以下の頂点があります。小さい場合も同様です。従って3-degenerateです。□
simple planar graphは退化順序に沿うgreedy算法で6-colorableであり、triangle-freeなら4-colorableである。
前定理とdegeneracy coloring theoremを順に使えば
$$
\chi(G)\le5+1=6
$$
および
$$
\chi(G)\le3+1=4
$$
です。証明中の低次数頂点削除を記録し、逆順にgreedy彩色すれば実際の彩色を構成できます。□
一般の平面graphで6色を5色へ減らすには、次数5の頂点の五つの隣接色を単に数えるだけでは足りません。
計算量
隣接list、現在次数、次数ごとのbucketを用意します。次数最小の頂点をbucketから取り出して削除し、その隣接頂点の次数を1ずつ下げます。各頂点は一度削除され、各辺は端点削除時に定数回だけ調べられるため、退化順序と全core numberを
$$
O(|V|+|E|)
$$
時間で計算できます。
得た順序の逆順greedy coloringも各辺を定数回見るので線形時間です。したがって退化度上界は存在証明であるだけでなく、彩色を出力する算法でもあります。
演習
cycle $C_n$ の全頂点へ新しい中心頂点を接続したwheel $W_{n+1}$（$n\ge4$）の退化度を求めよ。
rim頂点の次数は3、中心の次数は $n$ なので、全体の最小次数は3です。従って $d(W_{n+1})\ge3$ です。
任意の部分graphを考えます。中心を含まなければcycleの部分graphなので次数2以下の頂点があります。中心を含む場合も、rim側の誘導部分がcycle全体でなければ端に当たるrim頂点の部分graph内次数は中心への一本を加えて高々2です。cycle全体を含めばrim頂点次数は3です。従って全ての部分graphに次数3以下の頂点があり、$d(W_{n+1})\le3$ です。ゆえに退化度は3です。□
頂点順序 $u_1,\ldots,u_6$ で、各 $u_i$ が後ろに高々2個の隣接頂点をもつ。どの順序でgreedy彩色すれば3色上界が得られるか説明せよ。
順序を逆にして
$$
u_6,u_5,\ldots,u_1
$$
の順で塗ります。$u_i$ を塗る時点で既に塗られた隣接頂点は、元の順序で $u_i$ より後ろにあったものだけなので高々2個です。従って禁止色は高々2色で、三色のうち少なくとも一色を使えます。□
path $P_5$ に、その中央三頂点が作る三角形となるよう両端以外の三頂点間へ不足辺を加えたgraphを考える。1-core、2-core、3-coreを求めよ。
graphに孤立頂点はないので1-coreは全graphです。
2-coreを求めるには次数1の両端を削除します。残る中央三頂点は三角形で各次数2なので停止し、2-coreはこの三角形です。
3-coreでは、まず両端を削除した後の三角形の各次数が2で3未満なので全て削除されます。従って3-coreは空です。最大の非空core番号は2なので、退化度も2です。□
$G$ が $K_6$ を部分graphとして含むとき、$d(G)$ と $\chi(G)$ への下界を求めよ。
$K_6$ の最小次数は5なので、退化度のmin--max公式から
$$
d(G)\ge5.
$$
またcliqueの六頂点は互いに隣接し、全て異なる色が必要なので
$$
\chi(G)\ge6.
$$
退化度彩色定理は上界 $\chi(G)\le d(G)+1$ を与えますが、ここでは $d(G)$ の正確な値が不明なので、それだけから上界6とは言えません。□
あるgraphに最大outdegree2のacyclic orientationが与えられた。退化度と彩色数への上界を証明せよ。
degeneracy orientation formulaから
$$
d(G)\le2.
$$
またdegeneracy coloring theoremから
$$
\chi(G)\le d(G)+1\le3.
$$
構成的にはorientationのtopological orderingを取り、逆順にgreedy彩色すれば各頂点を見る時点の既彩色隣接頂点は高々2個です。□
頂点数 $n\ge3$ のtriangle-free simple planar graphで、次数3以下の頂点が必ず存在することを、平均次数から直接証明せよ。
各face境界長が少なくとも4なので、「平面グラフ」のEuler公式による評価から
$$
|E|\le2|V|-4
$$
です。従って平均次数は
$$
\frac{1}{|V|}\sum_v\deg(v)
=\frac{2|E|}{|V|}
\le4-\frac{8}{|V|}
<4.
$$
全頂点次数が4以上なら平均次数も4以上となるので矛盾します。従って少なくとも一頂点の次数が3以下です。□
本章で得たもの
退化度は次の四つを同じ数で結びます。
- 全ての部分graphに現れる低次数頂点
- 頂点を削るpeeling順序
- 非空な $k$-coreの最大段階
- acyclic orientationで抑えられる最大outdegree
この同値性から、$d$-degenerate graphはgreedy算法で $d+1$ 色に塗れます。simple planar graphには $d\le5$、triangle-free planar graphには $d\le3$ が成り立つため、六色・四色の構成的上界が得られました。
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
