到達可能性関係・推移閉包・推移簡約とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > 到達可能性関係・推移閉包・推移簡約の意味・解説 

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

出典: フリー百科事典『ウィキペディア(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 を持つ。 推移簡約は同じ半順序を表す他のグラフ比べて辺の数少なくグラフ描画単純になるため、半順序視覚化するのに便利である。半順序ハッセ図は、推移簡約図示したもので、各辺の向きを、辺の始点頂点終点頂点よりも低い位置置いて示している。

※この「到達可能性関係・推移閉包・推移簡約」の解説は、「有向非巡回グラフ」の解説の一部です。
「到達可能性関係・推移閉包・推移簡約」を含む「有向非巡回グラフ」の記事については、「有向非巡回グラフ」の概要を参照ください。

ウィキペディア小見出し辞書の「到達可能性関係・推移閉包・推移簡約」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「到達可能性関係・推移閉包・推移簡約」の関連用語

到達可能性関係・推移閉包・推移簡約のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



到達可能性関係・推移閉包・推移簡約のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの有向非巡回グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS