読者です 読者をやめる 読者になる 読者になる

Dominator Treeの記事で飛ばしたとこ

ここまで読むなんて偉い、けどここを読むくらいなら元論文を読んだほうがいいと思うよ
Them1がないのは元論文ではdominator treeの性質のとこがthem1になってたからです.

Lem1:
v,w∈Gでv≦wなら,vからwへの任意のpathはTにおけるvとwの共通祖先のうち少なくともひとつを通る.
(証明は,wがvの子孫ならvがそれ,そうでないならdfs木のより上にあるところが祖先になってるはず.)
後の証明にちょくちょく使います.

Lem2:
w(≠r)∈Gに対し,idom(w) →+ w

それはそう( (0)から明らか)


Lem3:
w(≠r)∈Gに対し,sdom(w) →+ w

こっちはそこまで自明ではない.
Tにおけるwの親をpとおく.明らかにp<w. p→wはpathであるので,sdomの定義から,sdom(w)≦p あわせてsdom(w)<w.
さらに(1)にあるsdom(w)からwへのpathを取ってくる.
Lem1より,このpath上にはsdom(w)とwの共通祖先が存在する.一つ適当にvとおく.祖先なのでv≦sdom(w).
(1)より1≦i≦k-1に対して vi>w>sdom(w) であるから,これらはvではありえない.
従って残りのsdom(w)かwがvになるが,sdom(w)<wとv≦sdom(w)よりwではありえない.従ってv=sdom(w).
すなわちsdom(w)はwの祖先であり,wとは異なる.よって示された.


Lem4:
w(≠r)∈Gに対し,idom(w) →* sdom(w)

こんどは*なので一致し得ることに注意.idom(w)をi,sdom(w)をsと省略します.あと子孫とか先祖という時は自分自身を含みません.

まずLem2,3から,Tでのrからwへのpath上にiもsもある.根付き木上でのpathなのでiがsの子孫,sがiの子孫,一致のどれかが成り立つ.
Lem4を示すためにはiがsの子孫にならないことを言えば良い.これは次のように示される.
r→*sというpathと,(1)によるs→*wというpathをくっつける.
後半の方のpathでは,定義より,sの子孫をw以外通らないはずである(∵sの子孫≦wであるから,(1)と矛盾してしまう)
iがsの子孫であったとすると,上記のようなpathによってr→*wでiを通らないものが出てきてしまう.これはidomの定義に反する.よって示された.


Lem5:
v,w(ともに≠r)∈Gに対しv→*wとする.
この時, v→*idom(w) もしくは idom(w)→* idom(v) の少なくともどちらかが成り立つ.
idom(v)の子孫でありvの先祖であるものを任意に一つ取ってくる.これをxとおく.そうすると次の図のような状況になる.
f:id:sigma425:20151224145244j:plain
黒い部分はこれまでのことと定義より明らか.
赤い線は何を意図しているかというと,rからxを避けてwに向かってるpathです.なぜxを避けられるかというと,絶対にxを通らなければいけないとすると,xもwのdominatorになってしまい,しかもidom(w)よりwに近いからidomの定義に反しちゃうからです.
で、これで何が言えるかというと,r→+wであってxを通らないものが存在する.従ってx≠idom(w).
idom(w)がこの図の中に入るのは明らか(rからwへのpathだから)なので,この間に入れないならrとidom(v)の間か,vとwの間に入るしかない.
これはそれぞれこのLemの主張の後者と前者に対応する.よって示された.


はい,補題はここまでです.ステートメントはわりとすっきりしてるものばかりだと思います.正直何も言わずにこっちから説明すると読む気なくすだろうなあと思って飛ばした,やればできるし.
これらの補題から有用な定理を示していきます.

Them2:
w≠rとする.wが,
{ \displaystyle
\forall u \ such\ that\ ( sdom(w)\overset{+}{\rightarrow}u\overset{*}{\rightarrow}w),\ sdom(u)\geq sdom(w)
}
を満たしていると仮定する.
この時idom(w)=sdom(w)である.

一応説明しとくと,条件部分は,「任意の~を満たすuが~を満たす」です.
証明はちょっと大変.

Lem4より,sdom(w)がwをdominateしていることを示せば十分である.
/*
MADA KAITE NAI
/

Them3:
w≠rとする.uを,「sdom(w)→+ u→* wをみたす」もののうち,sdom(u)が最小のもの(のうち任意のひとつ)とする.
この時 sdom(u)≦sdom(w) かつ idom(u)=idom(w)

なにこれは・・・
// MADA KAITE NAI

Cor1:
w,uをThem3と同じように取る.この時,
{ \displaystyle
idom(w)=
\begin{cases}
sdom(w) & (sdom(w)=sdom(u))\\
idom(u) & otherwise
\end{cases}
}

これはThem2,3から明らか


Them4:
w≠rとする.
{ \displaystyle
sdom(w)=min( \{ v|(v,w)∈E ∧ v < w \} \cup \{ sdom(u)|u>w ∧ 「u→* v かつ(v,w)∈Eなるvがとれる」\})
}

//GANBARUTO SHOUMEI DEKIRU




おわりです.読んでも意味が無いといったのはまあそういうことです.