|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 推移 ： [すいい] 1. (n,vs) transition 2. change
推移閉包（すいいへいほう、）は、集合 ''X'' における二項関係 ''R'' に対して、''R'' を含む ''X'' 上の最小の推移関係を意味する。 例えば、''X'' が人間（生死を問わない）の集合、''R'' が親子関係としたとき、''R'' の推移閉包とは「''x'' は ''y'' の先祖である」という関係である。あるいは、''X'' が空港の集合、''xRy'' が「空港 ''x'' から空港 ''y'' への直通便が存在する」ことを意味するとき、''R'' の推移閉包は「''x'' から ''y'' まで一回または複数の航空便で行くことができる」という関係である。 == 解説 == 任意の関係 ''R'' について、''R'' の推移閉包は常に存在する。これを示すため、任意の推移関係の族の共通部分が推移的であることに注意する。さらに少なくとも1つの自明な ''R'' を含む推移関係 ''X'' × ''X'' が存在する。''R'' の推移閉包は、''R'' を含む全ての推移関係の共通部分である。 ''R'' の推移閉包は次のように厳密に記述される。''X'' 上の関係 ''T'' を ''xTy'' としたとき、''x'' = ''x''0 であるような要素 (''x''''i'') の有限列が存在し、次が成り立つ。 :''x''0''Rx''1, ''x''1''Rx''2, …, ''x''''n''−1''Rx''''n'', かつ ''x''''n''''Ry'' :形式記述: 関係 ''T'' が ''R'' を含み、かつ推移的であるかどうかを調べるのは容易である。さらに、''R'' を含む任意の推移関係は ''T'' も含むので、''T'' は ''R'' の推移閉包である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「推移閉包」の詳細全文を読む スポンサード リンク
|