第
4章 Kasteleyn行
列 54証明 ∂∈
5Nに
ついて,ν =σ
を満 たす ような ν ∈″′が存在すると す る。 この とき ・ν ={υ あ01j=1,…
.,Ⅳ}⊂E
で あ るか ら
,各
づ=1,…
.,Ⅳ につ いて 物 場(づ)はEの
元 で あ る。 よってκ
jσ(り =ε(υ・
bσ(を))≠ 0Sgn(σ)Kl∝
⇒。 …κ
N∝N)≠0Sgn(σ)Kl∝
⇒。 …κ
N∝N)≠0氏σ O≠ 0(に
1,…,Ⅳ)なので 鶴 場(ぅ)は
Eの
元 で あ る。 この ときν ={鶴陽 01̀=1,… ,N}
とす る とMは完全 マ ッチ ングで ノ
=σ
である。補題4.3.1よ り
,κ
の行列式 はdet
κ =Σ
sgnけlKl∝⇒…飾σ 0
となる。つ ま り,
が成 り立つ。
逆 に,
とす ると
と表 される。以下,
は
□
σ∈SN
Σ Sgn(め ろス⇒…鴫ス
一一
Σ Sgn(⑭
o(υl場(⇒):・・ ε
(υNbσ"リ
M∈ング
し Ｋ
ｄｅ
ると
用し
法を
の記
引 ブ ︑ ψ
／ １ｓ
ヽ を
Σ 胸 副
dd K=Σ Sgn(め く M)
M∈ング
第
4章 Kasteleyn行
列となる。 も しもこの とき
,任
意 の ν ∈ン に対 して sgnσゐε (M)が νによらず一定
であるようにε :E→
{±1}を定めることが出来れば
め ε(M)￨
Oε
(M)￨55
。
1)￨
tη =ILSgnl
=Σ
ISgn(M∈ング
=‖
ング
となる。(4。1)を εの条件 と呼ぶ。(4.1)を満たす εを用 いて定 まる行列 κ を σれ,れ のKasteleyn行列 とい う。次節か らは どの ように εを定 めれば ε の条件 を満たす ことがで きるのか述べ る。
4。
4
マ ッチ ングの回転Cm,"の 2つ
の完全マッチ ング ν,M′ を考 える。例 えば,図
4.9と図4。10 の2つ
の完全 マ ッチ ングを重ね ると,｀図4。11に示す ように ν とν ′が一 致す る ところもあるが,一
致 しない部分 はい くつかの閉路 にな る。 この 閉路上 にはMの辺 とM′ の辺が交互 に並 んでいる。図4.針 完全 マ ッチ ンの ν の 図 4。lQ完全 マ ッチ ンの ν ′ 辺 を太線 で示す の辺 を自抜線で示す
図 4。
11:図
4。9と図4。10の完全 マ ッチ ングを重ねた第
4章 Kasteleyn行
列56
定義
4.4.12部
グラフG=(71
Ⅱ y2,E)において,ν
⊂Eを
完全 マ ッチ ング とす る。C上
の閉路σ
=(η
,υl,・・.,υ2π‑1)(η
=υ%)
につ い て
,閉
路 σ が次 の式 を満 たす とき,σ
はMの
交互 閉路 で あ る とヽヽう 。
υ
2をυ
2j+1こ y, or2づ+lυ2+2￠
M(づ =0,̲,η ‑1)
例 えば
,図
4.11で 完全 マ ッチ ング ν とν ′が一致 しない部分の2つ
の 閉路 は,Mの 辺が1つ
お きに現れ るため ν の交互閉路 とな っている。定義 4.4.22部 グラフσ =(71 Ⅱ
y2,E)の完全マッチング
M⊂Eお よ
び ν の交互 閉路 σ=(υ。,υl,.… ,υ2行1)に 対 して
,M′
⊂Eを ν′ =υИ＼
{υ2をめ
̀+11づ
=0,… 。
,π‑1})∪
{υ2を+lυ2を+21̀=0,… ・
,π‑1}
とす る。つ ま り
,M′
はMに対 して θ上のMの辺 を除去 し,σ
上のMの辺でないものを加 えたものである。 このMか らν ′へ変化 させ ること を σ によるマ ッチ ングの回転 とい う。
例 えば
,図
4.11で は2つ
の完全 マ ッチ ングが一致 しない部分の閉路 は,Mの
2つ
の交互閉路 とな ってい る。図 4.11に おいて,Mか ら2つ
の交互閉路上の ν の辺 を除去 し
,そ
の後,交
互閉路上の ν の辺でないもの を加 えれ ば ν ′が得 られ る。 つ ま りν′はMの2つ
の交互 閉路 について マ ッチ ングの回転 を行 うことで ν か ら得 られる。命題
4.4.32部
グラフ σ=(71Ⅱ 72,E)の
完全 マ ッチ ング ν ⊂Eを
ν の交互閉路 σ=(η
,υl,.…,υ 2π‑1)でマ ッチ ングの回転 を したM′ もまた 完全 マ ッチング となる。証明 yl Ⅱ y2の元 υに対 して
1・
υ￠争恥
,υl,・…
,のを ‑1)の とき
ν は完全 マ ッチ ングで あるか ら,υ に接続す る c∈ Mがただ一つ
ある。υ￠
{島:υl,・…
,υ2を‑1)より cは マッチングの回転で除去され
ないか ら
,cは
ν′にも含 まれ る。 また ν か らν ′に追加 した辺 は υに接続 していないので,υ に接続す る ν ′の辺 はただ1つ
である。2.υ
∈
{η,υl,・…
,υ2を‑1)の とき
第
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→),陽̀ム