２００５年度 冬学期 離散情報論

２００６年１２月１２日

Lecture 8 (Nash-Williams の定理)
教員： 岩田 覚 助教授

文責： 小嶋大起，岡野原大輔

1 Nash-Williams の定理
無向グラフ G = (V, E) において，各点 v の次数を d(v) とする．全ての点 v ∈ V で b(v) ≤ d(v) となる写像 b : v → Z を考える．この時，G に対する b-分離*1 を以下のように定義する．
定義 1.1. b-分離
各点 v ∈ V を b(v) 個に分け，各枝は適当な点に接続させる．ここでの適当な点とは，b-分離以前に，枝が接続していた点の分割後のどれかの点を指す．
図 1 に，b-分離の例を示す．

頂点の横の数字が b v( )

2211

分離前

分離後
図1b-分離の例

b-分離について，以下の定理が成り立つ．
定理 1.2. Nash-Williams(1985)
連結グラフ G = (V, E) に連結な b-分離が存在する必要十分条件は，∀X ⊆ V, b(X) + c(G\X) ≤ e(X) + 1が成立することである．ただし，b(X) =P(1)v∈V b(v)，c(G\X) は G から X を削除した後の連結成分数，e(X)は X に接続する枝の本数である．
*1 原著では b-detachment

1VX

図2

X に接続する枝の例

図 2 に，X に接続する枝の例を示す．

Nash-Williams の定理のうち、必要性については簡単に示せるので，それを以下に示す．
証明. (必要性）

VXb( x ) ୘䈱ὐㅪ⚿

図 3 b-分離後の無効グラフ

連結な b-分離後の無向グラフ G = (V, E) を考える．G\X の各連結成分を縮約した後のグラフ G0 =(V 0 , E 0 ) について

|V 0 | = b(X) + c(G\X)，|E 0 | = e(X)(2)が成り立つ．G0 が連結であるためには，b(X) + c(G\X) ≤ e(X) + 1 が必要．（= のときには G0 は全域木となる）．
以下に，Nash-Williams の定理を証明する．
証明. 無向グラフ G = (V, E) に対し各点 v ∈ V に対して，b(v) 個のコピーをつくり，各枝 e = uv, e ∈E, u, e ∈ V に対して，u のコピーと v のコピーの間に b(u)b(v) 本の枝を引く．こうして得られるグラフを
Γ = (W, Γ(E)) とする．(図 4)G㰰2211
図4GとΓ2各枝 e のコピーとして得られた Γ の枝に色 e0 を付ける．この時，Γ 上で各色の枝を丁度一本を使う連結全域部分グラフが連結な b-分離に対応する．ここで，連結な b-分離が存在するための必要十分条件は，Γ 上で各色の枝を高々一本しか使わない全域木が存在することであり，このような全域木が存在するための必要十分条件
は Γ のグラフ的マトロイドの基で，かつ色分けによる分割マトロイドの独立集合となるものが存在（グラフ的マトロイドの基の階数は |W | − 1 である．また，全域木で各色の枝を高々一本しか使えないことから分割マトロイドとしては独立集合）することである．
補題 1.3. Γ のグラフ的マトロイドの基で，かつ色分けによる分割マトロイドの独立集合となるものが存在するための必要十分条件は，∀F ⊆ E, Γ(E)\Γ(F ) が高々 |F | + 1 個の連結成分を持つことである．
証明. 分割マトロイドの階数関数を π ，独立集合族を I とし，Γ のグラフ的マトロイドの階数関数を ρ，独立集合族を F とする．第 7 回の講義で示した定理より，¯¯max{|I|¯I ∈ I ∩ F } = min{π(X) + ρ(Γ(E)\Y )¯Y ⊆ Γ(E)}(3)が言える．ここで，E と Γ(E) を端点に持つ 2 部グラフを考える．これを図 5 に示す．

Γ(E)EYF

図5E と Γ(E) の 2 部グラフ

2 部グラフ上の分割マトロイドの階数関数を π とすると，図 5 において，灰色で囲まれた部分を Y としても，実線で囲まれた部分を Y としても π(Y ) = |F | となる．これは，Γ(F ) の分割マトロイドの階数関数と等しい．つまり，π(Γ(F )) = |F | である．ゆえに，Y として常に Γ(F ) を選んでよい．つまり¯¯max{|I|¯I ∈ I ∩ F } = min{|F | + ρ(Γ(E)\Γ(F ))¯F ⊆ E}(4)である．
一方，Γ 上のグラフ的マトロイドの基となるためには，|I| = |W | − 1 であればよい．ゆえに，∀F ⊆ E, ρ(Γ(E)\Γ(F )) + |F | ≥ |W | − 1．

(5)

また，c(X) が X というグラフの連結成分を表すとして，

ρ(Γ(E)\Γ(F )) = |W | − c(Γ(E)\Γ(F ))(6)を得られるが，式 (5) を用いて整理すると，∀F ⊆ E, c(Γ(E)\Γ(F )) ≤ |F | + 13(7)得る．式 (7) は言い換えると ∀F ⊆ E, c(Γ(E)\Γ(F )) が高々 |F | + 1 個の連結成分を持つということである．
よって，補題は示された．

Γ のグラフ的マトロイドの基で，かつ色分けによる分割マトロイドの独立集合となるものが存在することが，連結な b-分離が存在するための必要十分条件だったことを思い出すと，補題より，連結な b-分離が存在するための必要十分条件は，∀F ⊆ E, c(Γ(E)\Γ(F )) ≤ |F | + 1(8)∀F ⊆ E, c(Γ(E)\Γ(F )) ≤ |F | + 1(9)∀X ⊆ V, b(X) + C(G\X) ≤ e(X) + 1(10)であるといえる．後はとが同値であることを示せば Nash-Williams の定理は示される．

HF :Γ(E)\Γ(F )IF :G\F の孤立点の集合とする．
E䌜Fc(G\F ) と c(Γ(E)\Γ(F )) において，孤立点でない

㰰(E)䌜 㰰(F)

連結部分の数は変わらず，孤立点は b(IF ) 個となっているので，c(G\F ) においての孤立点の二重数えに気をつけるとc(HF ) = c(G\F ) + b(IF ) − |IF |(11)を得られる．この式と

ㅪ⚿c(Γ(E)\Γ(F )) ≤ |F | + 1, ∀F ⊆ E

(12)

ቅ┙ὐ

b(v ) 䈮Ⴧ䈋䉎

図 6 Γ(E)\Γ(F ) の連結数

より，

c(G\F ) − |F | + b(IF ) − |IF | ≤ 1, ∀F ⊆ E(13)を得る．ここで，IF を孤立点とするのにちょうどいい枝集合 F 0 を考える．つまり，

IF 0 = IF
F0 ⊆ Fである．この集合を考えることにより，はc(G\F ) − |F | + b(IF ) − |IF | ≤ 1, ∀F ⊆ E(14)c(G\F 0 ) − |F 0 | + b(IF ) − |IF | ≤ 1, ∀F ⊆ E(15)4となる．一方c(G\F 0 ) − |IF | = c(G\IF 0 ) = c(G\IF )(16)|F | = IF 0 に接続する枝の数 = IF に接続する枝の数

(17)

0

なので，式 (15)(16)(17) よりc(G\IF ) − IF に接続する枝の数 + b(IF ) ≤ 1, ∀F ⊆ E(18)を得る．∀F に対して IF は構成できるので，式 (18) の IF を X ，さらに X に接続する枝の数を e(X) とす
れば，c(G\X) − X に接続する枝の数 + b(X) ≤ 1, ∀X ⊆ V(19)となる．これにより Nash-Williams の定理は示された．

2 Nash-Williams の定理の拡張
Nash-Williams の定理をより一般化させた定理として次が成り立つ．
Pk定理 2.1. G に連結 b-分離が存在するならば，σ(v) = (σ1 (v) . . . σk (v)), k = b(v),i=1 σi (v) = d(v)を満たす任意の σ(v) に対して次数列が σ(v) に一致する連結な b-分離が存在する．

P証明. Γ において，各色を丁度一回ずつ使う連結全域部分グラフ Q で，s∈W |dQ (s) − σ(s)| が最小のものを考える．

dQ (s) = σ(s), ∀s ∈ W(20)が成り立たないと仮定する．この時，ある v ∈ V に対して，dQ (s) > σ(s)dQ (s) < σ(t)を満たす v のコピー s, t ∈ W, が存在する．

e ∈ Q:禁止枝 ⇐⇒ Q\e で s と t が非連結とする．今，W を u のコピーとして下図のような状況を考える．

s には高々一本しか禁止枝が接続しない．ここで，sには禁止枝でない枝 e が接続しているとする．この枝G

㰰0を Q から除き，今 Q には含まれない枝，e を Q に入れることを考える．すると，Q\{e} ∩ {e0 } は連結とな

UWlる．今，dQ (s) は一つ減り，dQ (t) は一つ増えているので，はPPs∈W |dQ (s) − σ(s)| は二つ減少している．これs∈W |dQ (s) − σ(s)| の最小性に反する．

よって，

P

s∈W |dQ (s) − σ(s)| は 0 であり，題意は示された．

5V
図7ee’

St

枝の付け替え3 Euler の定理の拡張
G を連結 Euler グラフとする．Euler グラフであることから，
d(v)(v ∈ V )2(21)σ(v) = (2, 2, . . . , 2)(22)b(v) =であり，かつ，次数列がに一致するような b-分離を考えることができる．このとき，Nash-Williams の定理より，b(X) + c(G\X) ≤ e(X) + 1が成立する．ここで，b(X) =X d(v)v∈X

2= e(X) −d(X, E\X)
2(23)(24)が成り立つので，式 (23)(24) より

c(G\X) ≤1d(X, E\X) + 12(25)となる．しかし，等号が成り立つのは b-分離が全域木の場合であり，今回の分離は木ではない（サイクル）ので，c(G\X) <1d(X, E\X) + 12(26)が成り立つ．さらに Euler グラフより，d(X, E\X) は偶数であることから，

2c(G\X) ≤ d(X, E\X)が得られる．

6(27)