到達可能性関係推移閉包推移簡約

ウィキペディア小見出し辞書

到達可能性関係・推移閉包・推移簡約

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 02:16 UTC 版)

「有向非巡回グラフ」の記事における「到達可能性関係・推移閉包・推移簡約」の解説

DAG における到達可能性（英語版）関係は、 DAG の頂点の半順序 ≤ として形式化できる。この半順序では、頂点 u と頂点 v は、DAG 内に u から v への有向パスが存在するとき、すなわち v が u から到達可能なときに、 u ≤ v として順序づけられる。しかし、異なる DAG から、同じ到達可能性関係と同じ半順序集合が得られる場合もある。例えば、2 つの辺 a → b、b → c を持つ DAG は、3 つの辺 a → b、b → c、a → c を持つ DAG と同じ到達可能性関係を持ち、どちらも頂点が a ≤ b ≤ c の順に並んだ半順序集合を持つ。 .mw-parser-output .tmulti .thumbinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;align-items:center}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}} 有向非巡回グラフ G G の推移簡約 DAG G の推移閉包は、G と同じ到達可能性関係を表す DAG の中で、最も多くの辺を持つものである。これは、頂点 u から v に到達できるときには必ず辺 u → v を持つ。つまり、G の到達可能性関係において異なる要素の関連するペア u ≤ v は必ず辺を持つので、到達可能性関係 ≤ をグラフ理論的に直訳したものと考えてよい。この方法はより一般的に有効で、全ての有限半順序集合（S、≤）に対して、S の各メンバーに頂点を持ち、u ≤ v で関連する要素のペアに辺を持つグラフは、自動的に DAG の推移閉包となり、（S、≤）を到達可能性関係として持つ。このようにして、全ての有限半順序集合は、DAG の到達可能性関係として表すことができる。 DAG G の推移簡約（英語版）とは、G と同じ到達可能性関係を表す DAG の中で、最も少ない辺を持つものである。これは G のサブグラフであり、G が u から v に至るより長いパスを持つ場合に辺 u → v を廃棄することで形成される。推移閉包と同様、推移簡約も DAG に対して一意に定義される。一方、DAG 以外の有向グラフでは、同じ到達可能性関係を持つ最小部分グラフが複数存在する場合がある。 DAG G が半順序 ≤ で表される到達可能性関係を持つとき、G の推移簡約は G サブグラフであり、≤ の被覆関係（英語版） にある全てのペアに対し辺 u → v を持つ。 推移簡約は同じ半順序を表す他のグラフに比べて辺の数が少なく、グラフの描画が単純になるため、半順序を視覚化するのに便利である。半順序のハッセ図は、推移簡約を図示したもので、各辺の向きを、辺の始点の頂点を終点の頂点よりも低い位置に置いて示している。