関係かんけいrelationの合成ごうせいcompositionと閉包へいほうclosure

1導入どうにゅう

関係かんけいrelationを一回いっかいだけ確認かくにんするのではなく、「関係かんけいを続つづけて使つかうとどこへ到達とうたつできるか」を扱あつかいたい場合ばあいがある。たとえば、駅えきどうしの直通ちょくつうの関係かんけいが与あたえられたとき、乗のり換かえを許ゆるせばどこへ行いけるかを知しりたい。この発想はっそうが関係かんけいrelationの合成ごうせいcompositionである。

閉包へいほうclosureは、ある性質せいしつpropertyを満みたすために不足ふそくしている順序対じゅんじょついordered pairを最小限さいしょうげん追加ついかする操作そうさである。

合成ごうせいcompositionでは「1 回かいで行いける」ことと「何回なんかいか使つかえば行いける」ことを区別くべつする。閉包へいほうclosureは元もとの関係かんけいrelationを含ふくんだまま性質せいしつを満みたすようにするので、既存きそんの順序対じゅんじょついordered pairは失うしなわれない。

2用語ようごと定義ていぎ：合成ごうせいcomposition

$$R\subseteq A\times B$$R\subseteq A\times B、$$S\subseteq B\times C$$S\subseteq B\times C を関係かんけいrelationとする。合成関係ごうせいかんけいcomposite relation $$S\circ R\subseteq A\times C$$S\circ R\subseteq A\times C を

で定義ていぎする。これは「$$a$$a から $$b$$b へ $$R$$R で進すすみ、$$b$$b から $$c$$c へ $$S$$S で進すすめる」ことを表あらわす。

3用語ようごと定義ていぎ：恒等関係こうとうかんけいidentity relationと逆関係ぎゃくかんけいinverse relation

$$A$$A 上うえの恒等関係こうとうかんけいidentity relationを

と書かく。また、$$R\subseteq A\times B$$R\subseteq A\times B に対たいする逆関係ぎゃくかんけいinverse relation $$R^{-1}\subseteq B\times A$$R^{-1}\subseteq B\times A を

で定義ていぎする。

4閉包へいほうclosureとは何なにか

この節せつでは $$R\subseteq A\times A$$R\subseteq A\times A を $$A$$A 上うえの関係かんけいrelationとする。

反射閉包はんしゃへいほうreflexive closureは、反射性はんしゃせいreflexivityを満みたすために必要ひつような $$(a,a)$$(a,a) を追加ついかした関係かんけいrelationである。

対称閉包たいしょうへいほうsymmetric closureは、逆向ぎゃくむきの順序対じゅんじょついordered pairを追加ついかした関係かんけいrelationである。

推移閉包すいいへいほうtransitive closureは、$$aRb$$aRb と $$bRc$$bRc から必要ひつようになる $$aRc$$aRc を繰くり返かえし追加ついかした最小さいしょうの推移的すいいてきtransitiveな関係かんけいrelationであり、$$R^{+}$$R^+ と書かく。

5方針ほうしん

閉包へいほうclosureを作つくるときは、「性質せいしつを満みたすまで何なにを追加ついかするか」を追跡ついせきする。ただし、元もとの関係かんけいrelationを壊こわしてはいけない。閉包へいほうclosureは削除さくじょではなく追加ついかの操作そうさである。

ここで経路けいろpathとは、$$aRb$$aRb、$$bRc$$bRc のように関係かんけいrelationの矢印やじるしを有限回ゆうげんかい続つづけて辿たどる列れつである。有向ゆうこうグラフdirected graphという語ごは、元げんelementを点てん、順序対じゅんじょついordered pairを矢印やじるしとして描えがく見方みかただけを指さす。

反射閉包はんしゃへいほうreflexive closureは対角成分たいかくせいぶんを追加ついかし、対称閉包たいしょうへいほうsymmetric closureは矢印やじるしを逆向ぎゃくむきにも追加ついかし、推移閉包すいいへいほうtransitive closureは経路けいろで到達とうたつできる先さきを直接ちょくせつの関係かんけいrelationとして追加ついかする。

最小さいしょうの追加ついかminimal additionであることも閉包へいほうの一部いちぶである。つまり、元もとの関係かんけいrelationを含ふくみ、求もとめる性質せいしつを満みたすどの関係かんけいrelationにも、閉包へいほうで追加ついかした順序対じゅんじょついordered pairは含ふくまれる。

6直感的ちょっかんてきな説明せつめい

関係かんけいrelationを有向ゆうこうグラフとして見みると、合成ごうせいcompositionは 2 本ほんの矢印やじるしを続つづけて進すすむことである。推移閉包すいいへいほうtransitive closureは、何本なんぼんかの矢印やじるしを辿たどって到達とうたつできるなら、直接ちょくせつの矢印やじるしも追加ついかしたものと考かんがえられる。

この見方みかたでは、推移閉包すいいへいほうtransitive closureは到達可能性とうたつかのうせいを記録きろくする関係かんけいrelationである。元もとの関係かんけいrelationは「1 歩ぽで行いける」、推移閉包すいいへいほうtransitive closureは「何なに歩ぽかで行いける」を表あらわす。

経路けいろpathの長ながさで考かんがえると、反射閉包はんしゃへいほうreflexive closureは長ながさ 0 の移動いどうを許ゆるし、推移閉包すいいへいほうtransitive closureは正せいの長ながさの経路けいろで到達とうたつできる先さきを直接ちょくせつの関係かんけいとして加くわえる。

7例題れいだい：推移閉包すいいへいほうtransitive closureを作つくる

7.1問題もんだい

$$A=\{1,2,3\}$$A=\{1,2,3\} 上うえの関係かんけいrelation $$R=\left\{\right(1,2),(2,3\left)\right\}$$R=\{(1,2),(2,3)\} の推移閉包すいいへいほうtransitive closureを求もとめよ。

7.2解説かいせつ

$$1R2$$1R2 かつ $$2R3$$2R3 なので、推移性すいいせいtransitivityを満みたすには $$1R3$$1R3 が必要ひつようである。したがって $$(1,3)$$(1,3) を追加ついかする。

追加後ついかごの関係かんけいrelationは

である。これ以上いじょう新あたらしく追加ついかする順序対じゅんじょついordered pairはない。よってこれが推移閉包すいいへいほうtransitive closureである。

8証明しょうめい補足ほそく：推移閉包すいいへいほうtransitive closureの最小性さいしょうせい

集合しゅうごう $$A$$A 上うえの関係かんけい $$R$$R に対たいして、$$R$$R の反復はんぷくを

と再帰的さいきてきに定義ていぎする。$$(a,b)\in R^n$$(a,b)\in R^n は、$$a$$a から $$b$$b へ $$R$$R の矢印やじるしをちょうど $$n$$n 本ほん辿たどる経路けいろpathがあることを意味いみする。この記法きほうを用もちいると、推移閉包すいいへいほうtransitive closureは

と書かける。

$$R^{+}$$R^+ は $$R$$R を含ふくむ。また、$$(a,b)\in R^{+}$$(a,b)\in R^+、$$(b,c)\in R^{+}$$(b,c)\in R^+ なら、ある $$m,n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$m,n\ge 1 が存在そんざいして $$(a,b)\in R^m$$(a,b)\in R^m、$$(b,c)\in R^n$$(b,c)\in R^n である。経路けいろpathを連結れんけつすれば $$(a,c)\in R^{m+n}$$(a,c)\in R^{m+n} なので $$(a,c)\in R^{+}$$(a,c)\in R^+ である。

さらに、$$S\subseteq A\times A$$S\subseteq A\times A が $$R\subseteq S$$R\subseteq S を満みたす $$A$$A 上うえの推移的すいいてきな関係かんけいなら、すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge1 について $$R^n\subseteq S$$R^n\subseteq S であることを数学的帰納法すうがくてききのうほうmathematical inductionで示しめせる。基底段階きていだんかいでは $$R^1=R\subseteq S$$R^1=R\subseteq S である。帰納法きのうほうの仮定かてい $$R^n\subseteq S$$R^n\subseteq S のもとで $$(a,c)\in R^{n+1}=R\circ R^n$$(a,c)\in R^{n+1}=R\circ R^n とすると、ある $$b\in A$$b\in A が存在そんざいして $$(a,b)\in R^n\subseteq S$$(a,b)\in R^n\subseteq S かつ $$(b,c)\in R\subseteq S$$(b,c)\in R\subseteq S となる。$$S$$S の推移性すいいせいより $$(a,c)\in S$$(a,c)\in S なので、$$R^{n+1}\subseteq S$$R^{n+1}\subseteq S である。よって $$R^{+}\subseteq S$$R^+\subseteq S であり、$$R^{+}$$R^+ は $$R$$R を含ふくむ推移的すいいてきな関係かんけいの中なかで最小さいしょうである。

9見分みわけ方かたと関連かんれんリンク

• 関係かんけいを続つづけて使つかうなら、合成ごうせいcompositionを考かんがえる。
• 足たりない自己じこループを追加ついかするなら、反射閉包はんしゃへいほうreflexive closureである。
• 逆向ぎゃくむきの矢印やじるしを追加ついかするなら、対称閉包たいしょうへいほうsymmetric closureである。
• 到達可能性とうたつかのうせいを直接ちょくせつの関係かんけいrelationとして記録きろくするなら、推移閉包すいいへいほうtransitive closureである。

10演習えんしゅうリンク