2005 年度 冬学期 離散情報論

2005 年 10 月 3 日

Lecture 1 (辺彩色)
教員: 岩田 覚 助教授

文責: 小林 佑輔

本講義では主に離散最適化に関する話題を扱う. 教科書は [3] である.

1

辺彩色
無向グラフ G = (V, E) が与えられたときに, 各枝に色を付けることを辺彩色という. ただし, 端点を共有する枝同士は異なる色を付けることとする. このとき, 最小の色数による辺彩色を求めることを考える.
辺彩色に必要な最小色数を γ とし, 頂点 v ∈ V の次数を d(v) とする. v に接続する枝はすべて異なる色が付けられているので, γ ≥ d(v), ∀v ∈ V が成り立つ. すなわち, d∗ = max{d(v)|v ∈ V } として, γ ≥ d∗ が成り立つ. この不等式から, γ = d∗ という等式が予想されるが, これは一般グラフにおいては正しくない. 例
えば, 図 1 において, γ = 3, d∗ = 2 である.

図 1: γ = d∗ の成り立たない例.
しかし, 2 部グラフにおいてはこの等式が成り立つことが知られている.
定理 1 (König, 1916). G が 2 部グラフならば, γ = d∗ が成り立つ.

Proof. M1 , M2 , . . . , Md∗ を互いに素なマッチングで, 枝数の合計が最大なものとする. 辺彩色を考えたときに, 同じ色の付いた枝の集合は, グラフのマッチングに対応しているので, E = M1 ∪ M2 ∪ · · · ∪ Md∗ を示せばよい. 枝が Mi の要素であることを, 枝の色が i であると呼ぶことにする.

e ∈ E \ (M1 ∪ M2 ∪ · · · ∪ Md∗ ) なる, u と v を結ぶ枝 e が存在すると仮定する. すると, u に接続する枝はe 以外に高々d∗ − 1 本しかないので, 1, 2, . . . , d∗ の中で, u に接続する枝に付いていない色 i が存在する. 同様にして, v に接続する枝に付いていない色 j が存在する.

1. i = j のとき. e を Mi に加えることができるので, M1 , M2 , . . . , Md∗ の最大性に矛盾.
2. i 6= j のとき. Mi ∪ Mj ∪ {e} を枝集合とする G の部分グラフ G0 を考える. G0 において各点の次数は2 以下であるから, 各連結成分はパスかサイクルである.
e を含むサイクルが存在するとすると, e 以外の枝は Mi の枝と Mj の枝が交互に現れ, また, e の両側の枝に付いた色が異なることから, このサイクルは奇数長さとなり, G が 2 部グラフであることに矛盾1する. よって e を含む連結成分はパスである. このパスの端の枝から順に, i, j の色が交互になるように色を付け直せば, より多くの枝の彩色が得られる. よって, M1 , M2 , . . . , Md∗ の最大性に矛盾する.
以上より, E = M1 ∪ M2 ∪ · · · ∪ Md∗ である.
この証明は構成的なものであり, 証明の方針で d∗ 色での彩色を求めると, O(nm) の計算時間で求められる. ただし, グラフの頂点数を n, 枝数を m とする. なお, 現在では Schrijver による計算時間 O(md∗ ) のアルゴリズム [2] や, それを改良した, Cole 等による計算時間 O(m log d∗ ) のアルゴリズム [1] が知られている.

2アルゴリズム
この節では Schrijver のアルゴリズムについて述べる. Schrijver のアルゴリズムは以下の命題に基づくものである.
命題 2 (Hall の定理). k-正則 2 部グラフには完全マッチングが存在する. ただし, k-正則とは, すべての頂点の次数が k であることをいう.

Proof. k-正則 2 部グラフ G において, d∗ = k であるから, 定理 1 より, k 色による辺彩色が存在する. ある色が付いている枝の集合を M とすると, M はマッチングである. また, すべての頂点には各色の枝が 1 本ずつ接続しているので, M は完全マッチングである.
∗2 部グラフの頂点集合を A, B とする. 次数 d2 以下の頂点が A, B の片方に 2 点以上あれば 2 点を 1 つの頂∗点に縮約することで, A, B のそれぞれに次数 d2 以下の頂点が高々1 点であるようにする. 次にダミーの頂点を加えることで, |A| = |B| となるようにし, 枝を適当に加えて (多重枝も許す), d∗ -正則なグラフを作る. このグラフにおける辺彩色を見つけることができれば, 元のグラフの辺彩色が得られる.
そこで, d∗ -正則なグラフの辺彩色のアルゴリズムを述べる. 単純な方法としては, 完全マッチングを 1 つずづ求め, それを順に取り除いていくという方法が考えられるが, 効率的ではない. 効率的に求めるために,以下のような分割統治法によるアルゴリズムが考えられる.

1. d∗ が奇数のとき. 完全マッチングを 1 つ求めて取り除くことにより, 次数 d∗ − 1 の問題に帰着する.
2. d∗ が偶数のとき. すべての頂点の次数は偶数なので, オイラー閉路を見つけて, 枝を 1 つおきに取る∗∗ことでできる 2 つの部分グラフを考える. これらは d2 -正則なグラフなので, 次数 d2 の問題 2 つに分割できる.
このアルゴリズムにおいては, k-正則 2 部グラフの完全マッチングを効率的に求めることが重要となる.
以下のアルゴリズムは Schrijver [2] によるものであり, k-正則 2 部グラフの完全マッチングを O(mk) で求めるものである. アルゴリズム 1 を用いることにより, d∗ -正則なグラフの彩色が O(md∗ ) で求めることができる.
アルゴリズム 1
1. w(e) = 1, ∀e ∈ E と初期化する.

2

2. E ∗ = {e ∈ E|w(e) > 0} とし, E ∗ 中の閉路を探し, 存在しないならば E ∗ が完全マッチングであるので終了する. 存在するとき, 閉路を C とし, C = M ∪ N (M, N はマッチング, w(M ) ≥ w(N )) とする.
w(e) + 1 (e ∈ M ),w(e) :=w(e) − 1 (e ∈ N )と更新して, 2 を繰り返す.

定理 3. アルゴリズム 1 は, k-正則グラフの完全マッチングを O(mk) で見出す.

Proof. まず, アルゴリズムが終了するときに, E ∗ が完全マッチングであることを示す. 初期状態においては各頂点に接続する枝の重み w の和はすべて k であり, これはアルゴリズムの中で変化しない. また, 重みは常に非負である. 終了するときには E ∗ を枝集合とする部分グラフは森をなすが, 各連結成分の葉 (1 つの枝にしか接続しない点) v に注目すると, v に接続する枝 e = (uv) の重みは k であり, もう一方の e の端点 u からは E ∗ の枝は e 以外に出ていないとわかる (図 2). これは E ∗ がマッチングであることを表し, また, すべuev
図 2: E ∗ がマッチングであることの証明.ての頂点には E ∗ の枝が少なくとも 1 本は接続しているので, E ∗ は完全マッチングである.
∑2
次に反復について考える.
e∈E w(e) という量を考えると, 1 回の反復における増加量は,∑((w(e) + 1)2 − w(e)2 ) +e∈M∑((w(e) − 1)2 − w(e)2 ) = 2w(M ) + |M | − 2w(N ) + |N | ≥ |C|e∈Nである. この量は初期状態においては m であり, 終了するときには mk である. サイクル C を見つけ, 更新をするのにかかる時間は O(|C|) であるから, このアルゴリズムにかかる時間は O(mk) である.

参考文献
[1] R. Cole, K. Ost, S. Schirra: Edge coloring bipartite multigraphs in O(E log D) time, Combinatorica,
21 (2001), pp. 5–12.
[2] A. Schrijver: Bipartite edge coloring in O(∆m) time, SIAM Journal on Computing, 28 (1998), pp.
841–846.
[3] A. Schrijver: Combinatorial Optimization. Springer-Verlag, 2003.

3