|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 有 ： [う, ゆう] 1. (n,vs) possession ・ 非 ： [ひ] 1. (adj-na,n,pref) faulty- 2. non- ・ 循環 ： [じゅんかん] 1. (n,vs) circulation 2. rotation 3. cycle ・ 環 ： [わ, かん] 【名詞】 1. circle 2. ring 3. link 4. wheel 5. hoop 6. loop ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、）とは、グラフ理論における閉路のない有向グラフの事。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。〔.〕〔.〕〔.〕 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ（森）に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。 == 関連項目 == * グラフ理論 * トポロジカルソート * ベイジアンネットワーク 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「有向非巡回グラフ」の詳細全文を読む スポンサード リンク
|