第
4章 Kasteleyn行
列 57(a)υ
=υ
2を とす る とυ21‑lυ2を ∈ν ′である。 また,υ2を に接続 す るMの辺 は υ2をυ2,+1のみである。 これ は除去 され るか らν ′に含 まれない。つ ま り
,M′
の辺で のメこ接続するのはυ2を‑lυ2̀∈ ν ′ のみ となる。(b)υ
=υ
21+1と す る と υ21+lυ21+2∈ ν ′で あ る。 また,υ2″+1に
接続 す る ノ の辺 は υ21υ2二十1のみであ る。 これ は除去 され るからν ′に含 まれない。つ ま り
,ν
′の辺で υ21+1に接続す るのは υ2̀+lυ2を+2∈ ν ′のみ となる。以上 よ り
,任
意 の υ∈yl Ⅱ y2に対 して υに接続す る ν ′の辺 がただ l つ存在す るため ν ′も完全マ ッチ ング となる。 □命題
4.4.42部
グラフσ=(ylⅡ y2,0の
任意の完全マッチ ング ν,M′ ⊂Eに
対 し,あ
る互 いに辺 を共有 しない ν の交互閉路o,… .,Cが
あつて,Mに
q,.…
,色 で順 にマ ッチ ングの回転 をす る とM′ になる。証明 σ =(yl Ⅱ y2,E)に おいて ,Cの 頂点を yl={υ
l,・…
,吻0, 72=
{bl,・
…
,bN}と表し ,順序を定める。このとき
,ρ
=ν ,
σ=ν
′oM
とす る。σを互 い に素 な巡 回置換 の積 で表 して
σ
=(jF)...j段ャ ⇒
)(jr)。… 嘱ャ が
.… (づF)・ ..う展
s))とお く。 この とき
r=1,…
。,sに 対 してα =し ,%け … 鵠 知粉
とおくと ,α は閉路である。実際,任意の
%∫→∈ yl(t=1,…
,π(r))に対して
,ρ=″ であるから ,電 P%0→
)∈νとなるしよって ,%P,%c→
)
は隣接する。また ,任 意の
%∫■ に対して
,σ=ル ド lo″ ょりρ
oケ1='
であるか ら
%←P)=%σ‑1←
∫ ■ )=b♭ C乳
)となる。よって
,%(t̀→)%∫?1∈
ν′ となり
,%(をs→),陽̀ム
は隣接する。さ らに ,オ
)。…寃ヤ
r)tま互いに異なるため ,tr)'…
:,υづ
,し)は互いに暴なり
,。
2)第
4章 Kasteleyn行
列 58ρは全単射であるか ら
,%(.)),―
・,%(礁ヤ→
)も
互いに異なる。以上の こと か らの は閉路であることが分かる。次 に,Mを
o,… .,aで
回転 す る と ν ′にな る こ とを示 す。 ここで,ν
=ρ
,M′=ρ
oσ 1なのでν
={υあ 01に 1,̲,Ⅳ
}M′ ={υ
を ら。 σ
‑lo lづ=1,…
,Ⅳ} に注意す る。 あ とは1.の
がMの交互閉路である。2.ν
をQ,…
.,色 で回転 した完全マッチ ングは ノ ′の辺 をすべて含む。の
2つ
が示 されれ ば命題 は証 明で きる。1.について
,簡
略のため頂点の番号 を置 き換 えてα 圭←雌
,し(⇒,… .,υπ
,ら(m))とおく。このとき
(1,…。
,π)(π ≧ 2か つ
1,…。
,πは互いに異なる )は σを分解した巡回置換なので ,鶴 ≠りを
+1(づ=1,… 。 ,m)に 注意する。ま ず ,Cの 1つ おきの各辺について
υをbρ(ぅ
)=υ
づb訪(を)∈M
で あ る。 仮 に
bp(。)υを+1∈ ν
とすると場
bp(→∈ν かつυ
・≠鶴+1で あるから ,Mが 完全マッチングで
あることに矛盾する。つまり
ら
Oυl+1￠■ イ であり ,cは
Mの交互閉路である。
2.について,Mを
Q,…
。,aで
回転 したマ ッチ ングを ν ″とす る。任意の
M′の元りを しについて,鶴 りが Mrrに 含まれることを示す。
(a)づ =づ
∫ →となる
r,tがないときσ
(j)=りである。つまり ,ル
「
loM(り
)=
をより
ブ
=ν′
(づ)=ν(づ)=ρ
(づ)第 4章 Kasteleyn行 列 59
となる。またσ
(づ)=うということは鶴ら oは q,…
.,色に現れない。
つまりυ
ibρOは Q,̲,Cの 回転で除去されない。よって,υ島
=υぅ
bρ(ぅ)∈ν″となる。
(b)づ =j∫r)と
なる
r,ιがあるとき
の =い 物 彎 矩)%司
と表 され る。M″ は
Q,… ,Qで
ν を回転 したものだか ら%(Pl)鶴 P∈ ν″
であ る。 い ま(4.3)よ り
. ρ
(づ
∫ 21)=ρ
(σ‑1(j∫r)))弗苗 %ν ′ °―
づ ∫
r))=ゴよ り
吻し
=ὺ∫
→ 可
(ぅ∫
21)∈ M″とな る。
以上 よ り
,命
題 が成 り立つ。4。
5
εの条件任意 の ν ∈ングに対 して εの条件
sgn(め ε
(ν)が
Mによらず一定
となるためには,任
意 の ν,M′ ∈%グ についてSgn(M)ε
(M)=Sgn(M′
)εOグ
) (4.4)が成 り立てば よい。 ここで
,命
題4.4。4よ
り,任
意のM,M′
∈彪グに対 し て,あ
る互いに辺 を共有 しないMの交互閉路Q,… .,aが
あつて,Mに□
第
4章 Kasteleyn行
列 600,…
.,色 で順 にマ ッチ ングの回転 をす ると ν ′になる。 この ことか ら,任意 の ν ∈ ン と ν の任 意 の交互 閉路 σ に対 して,Mを θ で回転 し て も
Sgn(y)ε
(M)
が不変であれば(4.4)が成 り立つ。以下
,正
方格子2部
グ ラフGπ,π の各単位正方形Fに
対 して,Fの境 界(反時計 回 り)の 閉路 を ∂Fと
表す。 また,∂Fや
Gれ,れ 上の閉路 σ に対して
eは
Π くの
σ の辺Π ε
"),
eは∂Fの辺
をそれぞれ ε(∂F),ε(σ)と表 す。
定理
4.5.1正
方格子2部
グラフGm,π =(zE)において,写
像 ε:E→
{±
1)が ,Gれ
,れ の各単位正方形Fに
ついて ε(∂F)=‑1を満たす とす る。つ ま り
,Gれ
,っ の各単位正方形の4辺
の うち εの値が‑1
とな るのは奇数 とす る。 この とき,εの条件 が成 り立つ。
この定理 を
,い
くつかの補題 を準備 して証 明す る。補題
4.5.2正
方格子2部
グラフ上の閉路 σ について,θ
がある完全 マ ッ チ ングの交互閉路であるな らば,θ
の内部の頂点の個数 は偶数個 となる。証 明 σ の内部 の頂点が奇数個 であ り
,か
つ,σ =(υ
l,ら1,.… ,υJ,仇)が
ある完全 マ ッチ ングMの交互閉路 とす る。 この とき,Mの 元 はυlbl,02b2,… 。,t」JbJ または らlυ2,b2υ3,…・,bJυl
となる。 よって σの内部の頂点 を端点 とするMの辺のも う一方の端点が θ上の頂点 となることはで きないか ら,Mの辺 は σの内部の頂点 どうし をつな ぐことにな る。 しか し
,こ
れ は σ の内部の頂点が奇数個 であることに矛盾する。っまり ,σ の内部の頂点の個数は偶数個となる。 □
補題
4。5.3工 方格子 2部 グラフ
Gれ,π=(И E)の 各単位正方形 Fに つい てε
(∂F)=‑1が成 り立つとする。このとき ,Gπ
,π上の任意の閉路 σに ついて ,σ 内部の面積
(単位正方形の個数
)を sとおくと
ε(θ
)=(‑1)S
第
4章 Kasteleyn行
列 61が成 り立つ。
証明 仮定 よ りσ 内部の面積 が
sで
あ るか ら,σ
の内部 の単位正 方形 を それぞれFl,… .,民 とす る。 また,ε(∂F)=‑1であるか らε(∂Fl)。 …ε(∂FЭ =(‑1)3 (4.5)
と表 され る。 この とき∂Fl,… 。,∂民 は σ の辺 および σの内部の辺 を含 む が,Cの内部 の辺 は
2度
ずつ現れ るのでε(∂Fl)・ …ε(∂民)
の値 に寄与せず
,こ
の値 は ε(σ)に 一致す る。 よって,(4.5)よ りε(σ)=(‑1)Sが
成 り立つ。 □補題
4.5.4正
方格子2部
グラフ σれ,れ=(yl
Ⅱy2,E)の
完全 マ ッチ ングM⊂
Eの
交互閉路 σ=(η
,υl,・ …,υ2̲1)に対 して,σ
の長 さを2ι とし,Mを σで回転 した完全 マ ッチ ングをM′ とする。 この とき
,次
の式が成 り立つ。証明 σ =(71 Ⅱ
y2,E)において ,Cの 頂点をyl={υ
l,・…
,υⅣ }, 72=
{bl,・
…
,bN}とする。また,こ こでは議論を簡単にするためにσを
σ ={υ
l,bl,υ 2,b2,…・
,吻,仇}とする。すると
M={υlbl,υ2万,・
・
1,石ι 仇
,̲}動 「 ′ ={扇
,b2υ 3,…・
,bJυl.…}={υ
lbJ,1あ可
,….,υJbz̲1.… }であるか ら
,置
換 ル弓i豫 について,も
との元 とその行 き先 を上下 に対応 させ て記す とsgn(a=sgn(2)× ←
1ソー
1ヽ １ １ ノ