有向非巡回グラフ

数学、特にグラフ理論、およびコンピュータ科学において、有向非巡回グラフ（DAG）は、有向サイクルを持たない有向グラフです。つまり、頂点と辺（アークとも呼ばれる）から構成され、各辺はある頂点から別の頂点へと方向付けられており、その方向をたどっても閉じたループは形成されません。有向グラフがDAGであるのは、すべての辺の方向と整合する線形順序で頂点を配置することにより、位相的に順序付けできる場合に限ります。DAGは、生物学（進化、家系図、疫学）から情報科学（引用ネットワーク）、計算（スケジューリング）まで、数多くの科学的および計算的応用があります。

有向非巡回グラフは、非巡回有向グラフ^{[ 1 ]}または非巡回ダイグラフ^[²^]とも呼ばれます。

定義

グラフは頂点と、頂点同士を結ぶ辺によって構成されます。頂点は、辺によってペアで結ばれるあらゆる種類のオブジェクトです。有向グラフの場合、各辺にはある頂点から別の頂点への方向があります。有向グラフにおけるウォークとは、（有限または無限の）シーケンスのことです。 $(v_{1},v_{2},\dotsc )$ 連続する各ペアが $(v_{i},v_{i+1})$ 有向エッジで接続されている。パスとは、すべての頂点が異なるウォークである。サイクルとは、 $(v_{1},v_{2},\dotsc ,v_{n})$ 唯一の重複する頂点は $v_{n}=v_{1}$ つまり、最後の頂点が最初の頂点と等しいということです。有向非巡回グラフは、サイクルを持たない有向グラフです。^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

数学的性質

到達可能性関係、推移的閉包、推移的還元

DAG

その推移的還元

DAG の到達可能性関係は、DAG の頂点上の部分順序 ≤ として形式化できます。この部分順序では、頂点u $と$ $v$ は $、$ DAG内に $uから$ $v$ への有向パスが存在する場合、つまり $u が$ $v$ に到達できる場合(または $v が$ $u$ から到達可能である場合)にのみ、 $u \leq vと順序付けられます。$ ^[⁴^]ただし、異なる DAG でも同じ到達可能性関係と部分順序が生じる場合があります。^[⁵^]例えば、2 つのエッジ $u$ $\to$ $v$ と $v$ $\to$ $wを持つ DAG は、3 つのエッジ$ $u$ $\to$ $v$ 、 $v$ $\to$ $w$ 、および $u$ $\to$ $w$ を持つ DAG と同じ到達可能性関係を持ちます。これらの DAG はどちらも同じ部分順序を生成し、その部分順序では頂点は $u$ $\leq$ $v$ $\leq$ $w$ と順序付けられます。

DAG の推移閉包とは、DAG と同じ到達可能性関係を持つエッジが最も多いグラフのことです。DAGの到達可能性関係 $\leq$ におけるすべての頂点ペア ( $u$ , $v ) に対してエッジ$ $u \to v$ $が存在するため、到達可能性関係\leq$ をグラフ理論の用語に直接変換したものと考えることができます。部分順序を DAG に変換する同じ方法は、より一般的にも機能します。すべての有限部分順序集合 $($ $S$ $, \leq)に対して、$ $S$ のすべての要素に対応する頂点と $\leq$ のすべての要素ペアに対応するエッジを持つグラフは、自動的に推移閉 DAG となり、到達可能性関係として $($ $S$ $, \leq)$ を持ちます。このようにして、すべての有限部分順序集合を DAG として表現できます。

DAG の推移的縮小は、DAG と同じ到達可能性関係を持つ、辺の数が最も少ないグラフです。DAGの到達可能性関係 $\leqの$ 被覆関係にあるすべての頂点ペア ( $u$ 、 $v$ )に対して、辺 $u \to v$ を持ちます。これは、 DAG に $uから$ $v$ へのより長い有向パスも含まれる辺 $u$ $\to$ $v$ を破棄することによって形成される、DAG の部分グラフです。推移的閉包と同様に、推移的縮小は DAG に対して一意に定義されます。対照的に、非巡回的ではない有向グラフの場合、同じ到達可能性関係を持つ最小部分グラフが複数存在する可能性があります。^[⁶^]推移的縮小は、同じ順序を表す他のグラフよりも辺の数が少ないため、グラフの描画が単純になるため、それが表す部分順序を視覚化するのに役立ちます。部分順序のハッセ図は、推移的縮小の描画であり、すべての辺の向きは、辺の開始頂点を終了頂点よりも低い位置に配置することによって示されます。^[⁷^]

位相順序付け

有向非巡回グラフの位相順序付け：すべての辺は、順序付けの早い方（左上）から遅い方（右下）へと向かいます。有向グラフが非巡回グラフであるのは、位相順序付けを持つ場合に限ります。

青色の有向非巡回グラフに赤色の辺を追加すると、青色のグラフの推移閉包である別のDAGが生成されます。各赤色または青色の辺

u \to v

に対して、

u

から

vに

到達可能です。つまり、

uから始まり

v

で終わる青色のパスが存在します。

有向グラフのトポロジカル順序とは、頂点をシーケンスに並べた順序であり、すべてのエッジについて、そのエッジの開始頂点がシーケンスの終了頂点よりも前に現れるようにする。トポロジカル順序を持つグラフはサイクルを持つことができない。なぜなら、サイクルの最初の頂点へのエッジは間違った方向に向けられなければならないからである。したがって、トポロジカル順序を持つすべてのグラフは非巡回グラフである。逆に、すべての有向非巡回グラフは少なくとも1つのトポロジカル順序を持つ。したがって、トポロジカル順序の存在は、有向非巡回グラフの同等の定義として使用できる。それらはまさにトポロジカル順序を持つグラフである。^{[ 2 ]} 一般に、この順序は一意ではない。DAGは、すべての頂点を含む有向パスを持つ場合に限り一意のトポロジカル順序を持ち、その場合、順序はパスに頂点が現れる順序と同じである。^{[ 8 ]}

DAG の位相順序の族は、DAG の到達可能性関係の線形拡張の族と同じであるため、 ^{[ 9 ]}同じ部分順序を表す任意の 2 つのグラフは同じ位相順序の集合を持つ。

組み合わせ列挙

有向非巡回グラフの数を数えるグラフ列挙問題は、Robinson (1973) によって研究された。[ 10 ] ^n個の $ラベル$ 付き頂点を持つ DAG の数( $n = 0, 1, 2, 3, \dots$ 、これらの数が DAG のトポロジカル順序に現れる順序に制限なし) は、

1、1、3、25、543、29281、3781503、… （ OEISのシーケンスA003024）。

これらの数値は漸化式によって計算できる。

a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(nk)}a_{nk}.

^{[ 10 ]}

エリック・W・ワイススタインは、^{[ 11 ]}同じ数がすべての固有値が正の実数である (0,1) 行列の数を数えることを証明した。証明は全単射である。行列 $A$ がDAG の隣接行列であるのは、 $A$ $+$ $I$ がすべての固有値が正である (0,1) 行列である場合のみである。ここで、 $I は$ 単位行列を表す。DAG は自己ループを持つことができないため、その隣接行列は対角成分がゼロでなければならない。したがって、 $I$ を追加しても、すべての行列係数が 0 または 1 であるという性質は維持される。^[¹²^]

計算上の問題

トポロジカルソートと認識

トポロジカルソートは、与えられたDAGのトポロジカル順序を見つけるアルゴリズムの問題です。これは線形時間で解くことができます。^{[ 15 ]}トポロジカルソートのためのKahnのアルゴリズムは、頂点の順序を直接構築します。部分的に構築されたトポロジカル順序にまだ含まれていない他の頂点からの入力エッジを持たない頂点のリストを保持します。最初は、このリストは入力エッジがまったくない頂点で構成されます。次に、このリストから1つの頂点を繰り返し部分的に構築されたトポロジカル順序の末尾に追加し、その隣接頂点をリストに追加する必要があるかどうかを確認します。すべての頂点がこのように処理されると、アルゴリズムは終了します。^{[ 16 ]}あるいは、深さ優先探索グラフの走査の後順番号付けを反転することによって、トポロジカル順序を構築することもできます。^[¹⁵^]

与えられた有向グラフがDAGであるかどうかは、線形時間でチェックすることも可能で、トポロジカル順序付けを試み、各エッジについて結果として得られる順序付けが有効かどうかをテストする方法^{[ 17 ]}、または、一部のトポロジカルソートアルゴリズムでは、アルゴリズムがエラー条件を満たさずにすべての頂点を正しく順序付けすることを検証する方法^{[ 16 ]がある。}

循環グラフからの構築

任意の無向グラフは、頂点の全順序を選択し、その順序の早い端点から遅い端点まですべての辺を方向付けることで、DAG にすることができます。結果として得られる辺の向きは、非巡回向きと呼ばれます。異なる全順序で同じ非巡回向きが得られる場合があるため、 $n頂点のグラフは$ $n!$ 個未満の非巡回向きを持つ可能性があります。非巡回向きの数は $| χ (-1) |$ に等しく、ここで $χ$ は与えられたグラフの彩色多項式です。 ^{[ 18 ]}

任意の有向グラフは、フィードバック頂点集合またはフィードバック弧集合（それぞれ、すべてのサイクルに接する頂点または辺の集合）を削除することによって、DAG にすることができます。ただし、そのような最小の集合を見つけるのはNP 困難です。 ^{[ 19 ]}任意の有向グラフは、その強連結成分をそれぞれ単一のスーパー頂点に縮約することによって、その凝縮と呼ばれる DAG に変換することもできます。 ^[²⁰^]グラフがすでに非巡回である場合、その最小のフィードバック頂点集合とフィードバック弧集合は空であり、その凝縮はグラフ自体です。

推移的閉包と推移的還元

$n$ 個の頂点と $m$ 個のエッジを持つ与えられた DAG の推移閉包は、各頂点からの到達可能性を幅優先探索または深さ優先探索のいずれかを使用してテストすることにより、 $O (mn)の時間で構築できます。$ ^[²¹^]あるいは、行列乗算アルゴリズムの指数ω < 2.373 で $ある$ $O$ $($ n $ω$ $)$ $の$ $時間$ $で$ 解くこともできます。これは、密グラフの $O$ $($ $mn$ $)$ の上限に対する理論的な改善です。^[²²^]

これらの推移閉包アルゴリズムすべてにおいて、長さ2以上のパスが少なくとも1つ存在する頂点のペアと、長さ1のパスでしか接続できない頂点のペアを区別することが可能です。推移的縮小は、端点を結ぶ唯一のパスである長さ1のパスを形成するエッジで構成されます。したがって、推移的縮小は推移閉包と同じ漸近時間で構築できます。^{[ 23 ]}

閉包問題

閉包問題は、頂点重み付き有向非巡回グラフを入力として受け取り、閉包（頂点の集合Cからどの辺も出ないような集合C ）の最小（または最大）重みを求めます。この問題は、非巡回性の仮定なしに有向グラフに対して定式化できますが、この場合、グラフの縮約に関する同じ問題と同等であるため、より一般的なものではありません。最大フロー問題への還元を用いることで、多項式時間で解くことができます。^{[ 24 ]}

パスアルゴリズム

トポロジカル順序の原理に基づき、一般的なグラフではなくDAGに適用すると、一部のアルゴリズムはより単純になります。たとえば、DAGでは、頂点をトポロジカル順序で処理し、各頂点のパス長をその頂点への任意の入力エッジを介して得られる最小または最大の長さとして計算することで、与えられた開始頂点からの最短パスと最長パスを線形時間で見つけることができます。^[²⁵^]対照的に、任意のグラフでは、最短パスにはダイクストラ法やベルマン・フォード法などのより遅いアルゴリズムが必要になる場合があり、^[²⁶^]任意のグラフにおける最長パスを見つけるのはNP困難です。 ^[²⁷^]

アプリケーション

スケジュール

部分順序の有向非巡回グラフ表現は、順序制約のあるタスクシステムのスケジューリングにおいて多くの応用例がある。 ^{[ 28 ]}この種の重要な問題のクラスは、スプレッドシートのセルの 1 つが変更された後のセル、またはコンピュータソフトウェアのソースコードが変更された後のオブジェクトファイルなど、更新が必要なオブジェクトの集合に関するものである。この文脈では、依存グラフは、更新される各オブジェクトに対応する頂点と、一方のオブジェクトが他方のオブジェクトよりも先に更新される必要がある場合に 2 つのオブジェクトを接続するエッジを持つグラフである。このグラフのサイクルは循環依存と呼ばれ、サイクルに関係するタスクを一貫してスケジュールする方法がないため、一般には許可されない。循環依存のない依存グラフは DAG を形成する。^[²⁹^]

例えば、スプレッドシートのセルが1つ変更されると、変更されたセルに直接的または間接的に依存する他のセルの値を再計算する必要があります。この問題では、スケジュールするタスクは、スプレッドシートの個々のセルの値の再計算です。依存関係は、あるセルの式が別のセルの値を使用する場合に発生します。このような場合、使用される値は、それを使用する式よりも先に再計算する必要があります。依存関係グラフをトポロジー的に順序付けし、このトポロジー順序を使用してセルの更新をスケジュールすると、セルごとに1回の評価だけでスプレッドシート全体を更新できます。^{[ 30 ]}タスクの順序付けに関する同様の問題は、プログラムコンパイル用のメイクファイル^{[ 30 ]}や、低レベルのコンピュータプログラム最適化のための命令スケジューリング^[³¹^]でも発生します。

スケジュール制約のDAGベースの定式化は、DAGの初期アプリケーションの一つである大規模な人的プロジェクトの管理方法であるプログラム評価レビュー技法（PERT）でやや異なっています。この方法では、DAGの頂点は、実行すべき特定のタスクではなく、プロジェクトのマイルストーンを表します。代わりに、タスクまたはアクティビティは、タスクの開始と完了を示す2つのマイルストーンを接続するDAGのエッジで表されます。このような各エッジには、作業チームがタスクを実行するのにかかる時間の見積もりがラベル付けされています。このDAGの最長パスは、プロジェクトのクリティカルパス、つまりプロジェクトの総時間を制御するパスを表します。個々のマイルストーンは、その頂点で終わる最長パスの長さに応じてスケジュールできます。^{[ 32 ]}

データ処理ネットワーク

有向非巡回グラフは、処理要素のネットワークを表すために使用できる。この表現では、データは入力エッジを通して処理要素に入り、出力エッジを通して要素から出る。

例えば、電子回路設計では、静的組み合わせ論理ブロックは、入力の関数を計算する論理ゲートの非巡回システムとして表現できます。ここで、関数の入力と出力は個々のビットとして表現されます。一般に、これらのブロックの出力は、非巡回特性を維持するレジスタまたは状態要素によってキャプチャされない限り、入力として使用することはできません。^{[ 33 ]}紙またはデータベース上の電子回路図は、インスタンスまたはコンポーネントを使用して下位レベルのコンポーネントへの有向参照を形成する有向非巡回グラフの形式です。電子回路自体は、必ずしも非巡回または有向ではありません。

データフロープログラミング言語は、データストリームに対する操作のシステムと、一部の操作の出力と他の操作の入力との間の接続を記述します。これらの言語は、同じ非巡回的に接続された操作の集合が多数のデータ項目に適用される反復的なデータ処理タスクを記述するのに便利です。これらは並列アルゴリズムとして実行でき、各操作は別の入力セットが利用可能になるとすぐに並列プロセスによって実行されます。^{[ 34 ]}

コンパイラでは、直線コード（つまり、ループや条件分岐のないステートメントのシーケンス）は、コード内で実行される各算術演算の入力と出力を記述するDAGで表現されることがあります。この表現により、コンパイラは共通部分式の除去を効率的に実行できます。^{[ 35 ]}より高いレベルのコード編成では、非巡回依存性の原則は、大規模ソフトウェアシステムのモジュールまたはコンポーネント間の依存関係が有向非巡回グラフを形成する必要があると述べています。^{[ 36 ]}

フィードフォワードニューラルネットワークもその一例です。

因果構造

頂点が特定の時間に発生するイベントを表し、辺が常に前の時間の頂点から後の時間の頂点を指しているグラフは、必然的に有向かつ非巡回です。巡回がないのは、グラフ内の任意の有向パスをたどると頂点に関連付けられた時間が常に増加するため、パス上の頂点に戻ることができないからです。これは、因果関係とはイベントが未来にのみ影響を与え、過去には決して影響を与えないことを意味するという私たちの自然な直感を反映しており、したがって因果ループは存在しません。この種の有向非巡回グラフの例としては、量子重力に対する因果集合アプローチで見られるものがありますが、この場合、考慮されるグラフは推移的に完全です。以下のバージョン履歴の例では、ソフトウェアの各バージョンは一意の時間に関連付けられており、通常はバージョンが保存、コミット、またはリリースされた時間です。以下の引用グラフの例では、ドキュメントは一度に公開され、古いドキュメントのみを参照できます。

時には、イベントは特定の物理的な時間とは関連付けられていないことがあります。イベントのペアが純粋に因果関係にある場合、つまりエッジがイベント間の因果関係を表す場合、有向非巡回グラフが得られます。 ^{[ 37 ]}例えば、ベイジアンネットワークは、有向非巡回グラフの頂点として確率的イベントのシステムを表し、イベントの尤度はDAG内の先行イベントの尤度から計算できます。^{[ 38 ]}この文脈では、 DAGのモラルグラフは、同じ頂点のすべての親の間に（無向）エッジを追加し（結婚と呼ばれることもあります）、すべての有向エッジを無向エッジに置き換えることによって作成される無向グラフです。^{[ 39 ]}同様の因果構造を持つ別のタイプのグラフは影響図であり、その頂点は決定または未知の情報のいずれかを表し、そのエッジはある頂点から別の頂点への因果的影響を表します。^{[ 40 ]}例えば疫学では、これらの図は介入のさまざまな選択肢の期待値を推定するためによく使用されます。^{[ 41 ]}^{[ 42 ]}

その逆もまた真である。つまり、有向非巡回グラフで表されるあらゆるアプリケーションには因果構造が存在し、それは明示的な順序または時間（例）であるか、グラフ構造から導き出せる順序のいずれかである。これは、すべての有向非巡回グラフには位相順序が存在する、すなわち、頂点をある順序に並べる方法が少なくとも1つあり、その順序に沿ってすべての辺が同じ方向を向くということである。

系譜とバージョン履歴

プトレマイオス朝の家系図。近親者間の結婚が多数あったため、家系図が崩壊している。

家系図は、各家族構成員を頂点とし、各親子関係を辺とする有向非巡回グラフと見なすことができる。^{[ 43 ]}名前とは裏腹に、これらのグラフは必ずしも木構造ではない。親族間の結婚（つまり、子供が母親側と父親側の両方に共通の祖先を持つ）によって家系図が崩壊する可能性があるためである。^{[ 44 ]}母系継承（母娘関係）と父系継承（父息子関係）のグラフは、このグラフ内の木構造である。誰も自分の祖先になることはできないため、家系図は非巡回グラフである。^{[ 45 ]}

Gitなどの分散型リビジョン管理システムのバージョン履歴は、一般的に有向非巡回グラフの構造を持ち、各リビジョンに対応する頂点と、直接派生したリビジョンのペアを接続するエッジがあります。マージがあるため、これらは一般的にツリーではありません。^[⁴⁶^]

計算幾何学における多くのランダム化アルゴリズムでは、アルゴリズムは、構造に対する一連の変更の過程における幾何学的構造のバージョン履歴を表す履歴DAGを保持します。たとえば、ドロネー三角形分割のランダム化増分アルゴリズムでは、各点が追加されるたびに1つの三角形を3つのより小さな三角形に置き換えること、および三角形のペアを別の三角形のペアに置き換える「反転」操作によって三角形分割が変更されます。このアルゴリズムの履歴DAGには、アルゴリズムの一部として構築された各三角形の頂点と、各三角形からそれを置き換える他の2つまたは3つの三角形へのエッジがあります。この構造により、点位置クエリに効率的に回答できます。ドロネー三角形分割内のクエリ点 $q$ の位置を見つけるには、履歴DAG内のパスをたどり、各ステップで $qを含む置換三角形に移動します。このパスで最後に到達する三角形は、$ $q$ を含むドロネー三角形でなければなりません。^[⁴⁷^]

引用グラフ

引用グラフでは、頂点は単一の出版日を持つ文書です。エッジは、ある文書の書誌から、必然的にそれより前の文書への引用を表します。古典的な例は、1965年の論文「科学論文のネットワーク」^{[ 48 ]}で指摘された学術論文間の引用です。この論文は、後に引用ネットワークの最初のモデルであるプライスモデル^{[ 49 ]}を作成しました。この場合、論文の引用数は、引用ネットワークの対応する頂点の入次数に等しくなります。これは、引用分析において重要な尺度です。裁判所の判決も別の例であり、裁判官は、ある事件における結論を、以前の事件で下された他の判決を想起することによって裏付けています。最後の例は特許であり、特許は、現在の特許請求に関連する以前の先行技術、つまり以前の特許を参照する必要があります。有向非巡回グラフの特別な特性を考慮に入れることで、ネットワーク分析を用いた多くの研究で考慮される一般的なグラフを分析する際には利用できない手法で引用ネットワークを分析することができます。たとえば、推移的縮約は、さまざまなアプリケーションで見られる引用分布に関する新しい洞察を与え、さまざまなコンテキストで引用ネットワークを作成するメカニズムの明確な違いを強調します。^{[ 50 ]}もう1つの手法は、引用リンクをたどり、特定の引用グラフで最も重要な引用チェーンを提案するメインパス分析です。

プライスモデルは引用ネットワークの現実的なモデルとしては単純すぎるが、その特性のいくつかを解析的に解くには十分単純である。これらの多くは、プライスモデルの無向バージョンであるバラバシ・アルバートモデルから得られる結果を使用することで見つけることができる。しかし、プライスモデルは有向非巡回グラフを与えるため、有向非巡回グラフに固有の特性の解析的計算を探す際には有用なモデルとなる。例えば、ネットワークに追加されたn番目のノードからネットワークの最初のノードまでの最長パスの長さは、^{[ 51 ]のようにスケーリングする。} $\ln(n)$ 。

データ圧縮

有向非巡回グラフは、シーケンスの集合のコンパクトな表現としても使用できます。この種のアプリケーションでは、パスが与えられたシーケンスを形成するDAGを見つけます。多くのシーケンスが同じサブシーケンスを共有する場合、これらの共有サブシーケンスはDAGの共有部分で表現できるため、すべてのシーケンスを個別にリストする場合よりも少ないスペースで表現できます。たとえば、有向非巡回ワードグラフは、単一のソースを持ち、エッジが文字または記号でラベル付けされた有向非巡回グラフによって形成されるコンピュータサイエンスのデータ構造です。このグラフのソースからシンクへのパスは、英語の単語などの文字列の集合を表します。 ^{[ 52 ]}任意のシーケンスの集合は、シーケンスの各接頭辞に対してツリーの頂点を形成し、これらの頂点の1つの親が1つ少ない要素を持つシーケンスを表すようにすることで、ツリー内のパスとして表現できます。このようにして文字列の集合に対して形成されたツリーは、トライと呼ばれます。

同様に、二分探索木は、パスがキーのソートされた順序を表すルート付きDAGと見なすことができますが、より複雑なDAGに見られるパスマージ圧縮はありません。^{[ 53 ]}有向非巡回単語グラフは、パスが分岐して再結合することを可能にすることでトライ木よりもスペースを節約し、同じ接尾辞を持つ単語のセットを単一のツリー頂点で表すことができます。^{[ 54 ]}

パスのファミリーを表すために DAG を使用するという同じ考え方は、バイナリ関数を表すための DAG ベースのデータ構造であるバイナリ決定図 [ 55 ] [ 56 ] にも見られます。バイナリ^決定図で^は、各非シンク頂点にはバイナリ変数の名前がラベル付けされ、各シンクと各エッジには 0 または 1 がラベル付けされます。変数への任意の真偽割り当てに対する関数値は、単一のソース頂点から始まるパスをたどってシンクで見つかる値です。このパスは、各非シンク頂点で、その頂点の変数の値でラベル付けされた出力エッジをたどります。有向非巡回ワードグラフがトライの圧縮形式と見なせるのと同様に、バイナリ決定図は、残りのすべての決定の結果に一致するときにパスが再結合できるようにすることでスペースを節約する決定木の圧縮形式と見なすことができます。 ^{[ 57 ]}

参考文献

1 2 Thulasiraman, K.; Swamy, MNS (1992)、「5.7 非巡回有向グラフ」、Graphs: Theory and Algorithms、John Wiley and Son、p. 118、ISBN 978-0-471-51356-8。
1 2 3 Bang-Jensen, Jørgen (2008), "2.1 非巡回有向グラフ", Digraphs: Theory, Algorithms and Applications , Springer Monographs in Mathematics (第 2版), Springer-Verlag, pp. 32–34 , ISBN 978-1-84800-997-4。
↑ Christofides, Nicos (1975), Graph theory: an algorithmic approach , Academic Press, pp . 170–174 。
↑ Kozen, Dexter (1992), 『アルゴリズムの設計と分析』、コンピュータサイエンスのモノグラフ、Springer、p. 9、ISBN 978-0-387-97687-7。
↑ Banerjee, Utpal (1993), "演習2(c)", Loop Transformations for Restructuring Compilers: The Foundations , Springer, p. 19, Bibcode : 1993ltfr.book.....B , ISBN 978-0-7923-9318-4。
↑ Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", Digraphs: Theory, Algorithms and Applications , Springer Monographs in Mathematics, Springer, pp. 36–39 , ISBN 978-1-84800-998-1。
↑ Jungnickel, Dieter (2012), Graphs, Networks and Algorithms , Algorithms and Computation in Mathematics, vol. 5, Springer, pp. 92–93 , ISBN 978-3-642-32278-5。
↑ Sedgewick, Robert ; Wayne, Kevin (2011), "4,2,25 一意なトポロジカル順序付け", Algorithms (第 4版), Addison-Wesley, pp. 598–599 , ISBN 978-0-13-276256-4。
↑ Bender, Edward A.; Williamson, S. Gill (2005)、「例26（線形拡張 - トポロジカルソート）」、離散数学入門、Dover Books on Computer Science、Courier Dover Publications、p. 142、ISBN 978-0-486-43946-4。
1 2 Robinson, RW (1973), "ラベル付き非巡回有向グラフの計数", Harary , F. (編), New Directions in the Theory of Graphs , Academic Press, pp. 239–273 参照：Harary, Frank ; Palmer, Edgar M. (1973), Graphical Enumeration , Academic Press , p. 19, ISBN 978-0-12-324245-7。
↑ワイスタイン、エリック W.、「ワイスタインの予想」、MathWorld{{cite web}}: CS1 maint: 設定の上書き (リンク)
↑ McKay, BD ; Royle, GF ; Wanless, IM; Oggier, FE ; Sloane, NJA ; Wilf, H. (2004), "Acyclic digraphs and eigenvalues of (0,1)-matrices" , Journal of Integer Sequences , 7 : 33, arXiv : math/0310423 , Bibcode : 2004JIntS...7...33M 、第04.3.3条。
↑ Furnas, George W. ; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) , pp. 330– 336, doi : 10.1145/191666.191778 , ISBN 978-0897916509S2CID 18710118 。
↑ Rebane, George; Pearl, Judea (1987)、「統計データからの因果ポリツリーの復元」、第3回人工知能における不確実性に関する年次会議（UAI 1987）議事録、米国ワシントン州シアトル、1987年7月（PDF）、pp. 222–228 。
1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7{{cite book}}: CS1 maint: 上書きされた設定 (リンク) セクション 22.4、トポロジカルソート、pp. 549–552。
1 2 Jungnickel (2012)、pp. 50–51。
↑深さ優先探索に基づくトポロジカルソートアルゴリズムの場合、この妥当性チェックはトポロジカルソートアルゴリズム自体と交互に実行できます。例えば、 Skiena, Steven S. (2009), The Algorithm Design Manual , Springer, pp. 179–181 , ISBNを参照してください。 978-1-84800-070-4。
↑ Stanley, Richard P. (1973), "グラフの非巡回方向" (PDF) , Discrete Mathematics , 5 (2): 171– 178, doi : 10.1016/0012-365X(73)90108-8。
↑ゲイリー、マイケル R. ;ジョンソン、デイビッド S. (1979)、コンピュータと難解性: NP完全性理論への手引き、数学科学シリーズ (第 1版)、ニューヨーク: WH フリーマン・アンド・カンパニー、ISBN 9780716710455MR 0519066、OCLC 247570676 、問題GT7およびGT8、191 ～192ページ。
↑ハラリー、フランク；ノーマン、ロバート Z.；カートライト、ドーウィン (1965)、『構造モデル：有向グラフ理論入門』 、ジョン・ワイリー＆サンズ、 63ページ。
↑スキエナ (2009)、p. 495。
↑スキエナ (2009)、p. 496。
↑ Bang-Jensen & Gutin (2008)、p. 38.
↑ピカール、ジャン＝クロード (1976)、「グラフの最大閉包と組み合わせ問題への応用」、マネジメントサイエンス、22 (11): 1268–1272、doi : 10.1287/mnsc.22.11.1268、MR 0403596 。
↑ Cormen et al. 2001、セクション 24.2、有向非巡回グラフにおける単一始点最短経路、pp. 592–595。
↑ Cormen et al. 2001、セクション 24.1、ベルマン・フォードアルゴリズム、pp. 588–592、および 24.3、ダイクストラアルゴリズム、pp. 595–601。
↑コーメンら。 2001 年、p. 966.
↑スキエナ (2009)、p. 469。
↑ Al-Mutawa, HA; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "Javaプログラムにおける循環依存関係の形状について",第23回オーストラリアソフトウェアエンジニアリング会議、IEEE、pp. 48–57、doi : 10.1109/ASWEC.2014.15、ISBN 978-1-4799-3149-1S2CID 17570052 。
1 2 Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbook of Graph Theory (2nd ed.), CRC Press, p. 1181, ISBN 978-1-4398-8018-0。
↑ Srikant, YN; Shankar, Priti (2007), The Compiler Design Handbook: Optimizations and Machine Code Generation (2nd ed.), CRC Press, pp. 19–39 , ISBN 978-1-4200-4383-9。
↑ Wang, John X. (2002), What Every Engineer Should Know About Decision Making Under Uncertainty , CRC Press, p. 160, ISBN 978-0-8247-4373-4。
↑ Sapatnekar、Sachin (2004)、Timing、Springer、p. 133、ISBN 978-1-4020-7671-8。
↑ Dennis, Jack B. (1974), "データフロー手続き言語の最初のバージョン", Programming Symposium , Lecture Notes in Computer Science, vol. 19, pp. 362–376 , doi : 10.1007/3-540-06859-7_145 , hdl : 1721.1/148889 , ISBN 978-3-540-06859-4。
↑ Touati, Sid; de Dinechin, Benoit (2014), Advanced Backend Optimization , John Wiley & Sons, p. 123, ISBN 978-1-118-64894-0。
↑ガーランド、ジェフ、アンソニー、リチャード (2003)、『大規模ソフトウェアアーキテクチャ：UML を使用した実践ガイド』、ジョン・ワイリー＆サンズ、p. 215、ISBN 9780470856383。
↑ゴプニック、アリソン；シュルツ、ローラ（2007）『因果学習』オックスフォード大学出版局、4ページ、ISBN 978-0-19-803928-0。
↑ Shmulevich, Ilya; Dougherty, Edward R. (2010), Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks , Society for Industrial and Applied Mathematics, p. 58, ISBN 978-0-89871-692-4。
↑ロバート・G・コーウェル;フィリップ・デイヴィッド;ラウリッツェン、ステフェン L. ; Spiegelhalter、David J. (1999)、「3.2.1 Moralization」、Probabilistic Networks and Expert Systems、Springer、pp. 31–33、ISBN 978-0-387-98767-5。
↑ドーフ、リチャード C. (1998)、『テクノロジーマネジメントハンドブック』、 CRC Press、 9-7ページ、ISBN 978-0-8493-8577-3。
↑ボスロー、サラ（2008）、『疫学百科事典』第1巻、SAGE、255ページ、ISBN 978-1-4129-2816-8。
↑ Pearl, Judea (1995), "実証研究のための因果図" , Biometrika , 82 (4): 669–709 , doi : 10.1093/biomet/82.4.669。
↑ Kirkpatrick, Bonnie B. (2011年4月)、「家系図におけるハプロタイプと遺伝子型の比較」、Algorithms for Molecular Biology、6 (10) 10、doi : 10.1186/1748-7188-6-10、PMC 3102622、PMID 21504603 。
↑ McGuffin, MJ; Balakrishnan, R. (2005), "Interactive visualization of genealogical graphs" (PDF) , IEEE Symposium on Information Visualization (INFOVIS 2005) , pp. 16–23 , doi : 10.1109/INFVIS.2005.1532124 , ISBN 978-0-7803-9464-3S2CID 15449409 。
↑ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001)、「有向非巡回グラフにおける最小共通祖先の発見」、第12回ACM-SIAM離散アルゴリズムシンポジウム（SODA '01）議事録、米国ペンシルベニア州フィラデルフィア：産業応用数学会、pp. 845–854、ISBN 978-0-89871-490-6。
↑ Bartlang, Udo (2010), Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems , Springer, p. 59, Bibcode : 2010aamf.book.....B , ISBN 978-3-8348-9645-2。
↑ Pach, János ; Sharir, Micha (2008), Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical surveys and monographs, vol. 152, American Mathematical Society, pp. 93–94 , ISBN 978-0-8218-7533-9。
↑ Price, Derek J. de Solla (1965年7月30日)、「科学論文のネットワーク」(PDF)、Science、149 (3683): 510–515、Bibcode : 1965Sci...149..510D、doi : 10.1126/science.149.3683.510、PMID 14325149 。
↑ Price, Derek J. de Solla (1976)、「書誌計量およびその他の累積的優位性プロセスの一般理論」、Journal of the American Society for Information Science、27 (5): 292–306、doi : 10.1002/asi.4630270505、S2CID 8536863 。
↑ Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "引用ネットワークの推移的削減", Journal of Complex Networks , 3 (2): 189– 203, arXiv : 1310.8224 , doi : 10.1093/comnet/cnu039 , S2CID 10228152 。
↑ Evans, TS; Calmon, L.; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model", Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038/s41598-020-67421-8 , PMC 7324613 , PMID 32601403
↑ Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", Combinatorial Pattern Matching , Lecture Notes in Computer Science, vol. 1264, Springer, pp. 116–129 , CiteSeerX 10.1.1.53.6273 , doi : 10.1007/3-540-63220-4_55 , ISBN 978-3-540-63220-7S2CID 17045308 。
↑トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト、 Stein、Clifford (2009)、アルゴリズム入門(第 3版)、MIT Press、 286 ～ 307ページ、ISBN 978-0-262-03384-8。
↑ Lothaire, M. (2005), Applied Combinatorics on Words , Encyclopedia of Mathematics and its Applications, vol. 105, Cambridge University Press, p. 18, ISBN 9780521848022。
↑ Lee, CY (1959)、「バイナリ決定プログラムによるスイッチング回路の表現」、Bell System Technical Journal、38 (4): 985–999、Bibcode : 1959BSTJ...38..985L、doi : 10.1002/j.1538-7305.1959.tb01585.x 。
↑ Akers, Sheldon B. (1978), "Binary decision diagrams", IEEE Transactions on Computers , C-27 (6): 509–516 , Bibcode : 1978ITCmp.100..509A , doi : 10.1109/TC.1978.1675141 , S2CID 21028055 。
↑ Friedman, SJ; Supowit, KJ (1987)、「二分決定図の最適な変数順序の発見」、第24回ACM/IEEE設計自動化会議（DAC '87）議事録、ニューヨーク州ニューヨーク、米国：ACM、pp. 348–356、doi：10.1145/37888.37941、ISBN 978-0-8186-0781-3S2CID 14796451 。

外部リンク

ワイススタイン、エリック・W.、「非巡回有向グラフ」、MathWorld{{cite web}}: CS1 maint: 設定の上書き (リンク)
DAGitty – DAGを作成するためのオンラインツール

[thul-1] 1 2 Thulasiraman, K.; Swamy, MNS (1992)、「5.7 非巡回有向グラフ」、Graphs: Theory and Algorithms、John Wiley and Son、p. 118、ISBN 978-0-471-51356-8。

[bang-2] 1 2 3 Bang-Jensen, Jørgen (2008), "2.1 非巡回有向グラフ", Digraphs: Theory, Algorithms and Applications , Springer Monographs in Mathematics (第 2版), Springer-Verlag, pp. 32–34 , ISBN 978-1-84800-997-4。

[3] Christofides, Nicos (1975), Graph theory: an algorithmic approach , Academic Press, pp . 170–174 。

[4] Kozen, Dexter (1992), 『アルゴリズムの設計と分析』、コンピュータサイエンスのモノグラフ、Springer、p. 9、ISBN 978-0-387-97687-7。

[5] Banerjee, Utpal (1993), "演習2(c)", Loop Transformations for Restructuring Compilers: The Foundations , Springer, p. 19, Bibcode : 1993ltfr.book.....B , ISBN 978-0-7923-9318-4。

[6] Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", Digraphs: Theory, Algorithms and Applications , Springer Monographs in Mathematics, Springer, pp. 36–39 , ISBN 978-1-84800-998-1。

[7] Jungnickel, Dieter (2012), Graphs, Networks and Algorithms , Algorithms and Computation in Mathematics, vol. 5, Springer, pp. 92–93 , ISBN 978-3-642-32278-5。

[8] Sedgewick, Robert ; Wayne, Kevin (2011), "4,2,25 一意なトポロジカル順序付け", Algorithms (第 4版), Addison-Wesley, pp. 598–599 , ISBN 978-0-13-276256-4。

[9] Bender, Edward A.; Williamson, S. Gill (2005)、「例26（線形拡張 - トポロジカルソート）」、離散数学入門、Dover Books on Computer Science、Courier Dover Publications、p. 142、ISBN 978-0-486-43946-4。

[enum-10] 1 2 Robinson, RW (1973), "ラベル付き非巡回有向グラフの計数", Harary , F. (編), New Directions in the Theory of Graphs , Academic Press, pp. 239–273 参照：Harary, Frank ; Palmer, Edgar M. (1973), Graphical Enumeration , Academic Press , p. 19, ISBN 978-0-12-324245-7。

[11] ワイスタイン、エリック W.、「ワイスタインの予想」、MathWorld{{cite web}}: CS1 maint: 設定の上書き (リンク)

[12] McKay, BD ; Royle, GF ; Wanless, IM; Oggier, FE ; Sloane, NJA ; Wilf, H. (2004), "Acyclic digraphs and eigenvalues of (0,1)-matrices" , Journal of Integer Sequences , 7 : 33, arXiv : math/0310423 , Bibcode : 2004JIntS...7...33M 、第04.3.3条。

[13] Furnas, George W. ; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) , pp. 330– 336, doi : 10.1145/191666.191778 , ISBN 978-0897916509S2CID 18710118 。

[14] Rebane, George; Pearl, Judea (1987)、「統計データからの因果ポリツリーの復元」、第3回人工知能における不確実性に関する年次会議（UAI 1987）議事録、米国ワシントン州シアトル、1987年7月（PDF）、pp. 222–228 。

[clrs-15] 1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7{{cite book}}: CS1 maint: 上書きされた設定 (リンク) セクション 22.4、トポロジカルソート、pp. 549–552。

[j50-16] 1 2 Jungnickel (2012)、pp. 50–51。

[17] 深さ優先探索に基づくトポロジカルソートアルゴリズムの場合、この妥当性チェックはトポロジカルソートアルゴリズム自体と交互に実行できます。例えば、 Skiena, Steven S. (2009), The Algorithm Design Manual , Springer, pp. 179–181 , ISBNを参照してください。 978-1-84800-070-4。

[18] Stanley, Richard P. (1973), "グラフの非巡回方向" (PDF) , Discrete Mathematics , 5 (2): 171– 178, doi : 10.1016/0012-365X(73)90108-8。

[19] ゲイリー、マイケル R. ;ジョンソン、デイビッド S. (1979)、コンピュータと難解性: NP完全性理論への手引き、数学科学シリーズ (第 1版)、ニューヨーク: WH フリーマン・アンド・カンパニー、ISBN 9780716710455MR 0519066、OCLC 247570676 、問題GT7およびGT8、191 ～192ページ。

[20] ハラリー、フランク；ノーマン、ロバート Z.；カートライト、ドーウィン (1965)、『構造モデル：有向グラフ理論入門』 、ジョン・ワイリー＆サンズ、 63ページ。

[21] スキエナ (2009)、p. 495。

[22] スキエナ (2009)、p. 496。

[23] Bang-Jensen & Gutin (2008)、p. 38.

[24] ピカール、ジャン＝クロード (1976)、「グラフの最大閉包と組み合わせ問題への応用」、マネジメントサイエンス、22 (11): 1268–1272、doi : 10.1287/mnsc.22.11.1268、MR 0403596 。

[25] Cormen et al. 2001、セクション 24.2、有向非巡回グラフにおける単一始点最短経路、pp. 592–595。

[26] Cormen et al. 2001、セクション 24.1、ベルマン・フォードアルゴリズム、pp. 588–592、および 24.3、ダイクストラアルゴリズム、pp. 595–601。

[27] コーメンら。 2001 年、p. 966.

[28] スキエナ (2009)、p. 469。

[29] Al-Mutawa, HA; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "Javaプログラムにおける循環依存関係の形状について",第23回オーストラリアソフトウェアエンジニアリング会議、IEEE、pp. 48–57、doi : 10.1109/ASWEC.2014.15、ISBN 978-1-4799-3149-1S2CID 17570052 。

[hgt1181-30] 1 2 Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbook of Graph Theory (2nd ed.), CRC Press, p. 1181, ISBN 978-1-4398-8018-0。

[31] Srikant, YN; Shankar, Priti (2007), The Compiler Design Handbook: Optimizations and Machine Code Generation (2nd ed.), CRC Press, pp. 19–39 , ISBN 978-1-4200-4383-9。

[32] Wang, John X. (2002), What Every Engineer Should Know About Decision Making Under Uncertainty , CRC Press, p. 160, ISBN 978-0-8247-4373-4。

[33] Sapatnekar、Sachin (2004)、Timing、Springer、p. 133、ISBN 978-1-4020-7671-8。

[34] Dennis, Jack B. (1974), "データフロー手続き言語の最初のバージョン", Programming Symposium , Lecture Notes in Computer Science, vol. 19, pp. 362–376 , doi : 10.1007/3-540-06859-7_145 , hdl : 1721.1/148889 , ISBN 978-3-540-06859-4。

[35] Touati, Sid; de Dinechin, Benoit (2014), Advanced Backend Optimization , John Wiley & Sons, p. 123, ISBN 978-1-118-64894-0。

[36] ガーランド、ジェフ、アンソニー、リチャード (2003)、『大規模ソフトウェアアーキテクチャ：UML を使用した実践ガイド』、ジョン・ワイリー＆サンズ、p. 215、ISBN 9780470856383。

[37] ゴプニック、アリソン；シュルツ、ローラ（2007）『因果学習』オックスフォード大学出版局、4ページ、ISBN 978-0-19-803928-0。

[38] Shmulevich, Ilya; Dougherty, Edward R. (2010), Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks , Society for Industrial and Applied Mathematics, p. 58, ISBN 978-0-89871-692-4。

[39] ロバート・G・コーウェル;フィリップ・デイヴィッド;ラウリッツェン、ステフェン L. ; Spiegelhalter、David J. (1999)、「3.2.1 Moralization」、Probabilistic Networks and Expert Systems、Springer、pp. 31–33、ISBN 978-0-387-98767-5。

[40] ドーフ、リチャード C. (1998)、『テクノロジーマネジメントハンドブック』、 CRC Press、 9-7ページ、ISBN 978-0-8493-8577-3。

[41] ボスロー、サラ（2008）、『疫学百科事典』第1巻、SAGE、255ページ、ISBN 978-1-4129-2816-8。

[pearl:95-42] Pearl, Judea (1995), "実証研究のための因果図" , Biometrika , 82 (4): 669–709 , doi : 10.1093/biomet/82.4.669。

[43] Kirkpatrick, Bonnie B. (2011年4月)、「家系図におけるハプロタイプと遺伝子型の比較」、Algorithms for Molecular Biology、6 (10) 10、doi : 10.1186/1748-7188-6-10、PMC 3102622、PMID 21504603 。

[44] McGuffin, MJ; Balakrishnan, R. (2005), "Interactive visualization of genealogical graphs" (PDF) , IEEE Symposium on Information Visualization (INFOVIS 2005) , pp. 16–23 , doi : 10.1109/INFVIS.2005.1532124 , ISBN 978-0-7803-9464-3S2CID 15449409 。

[45] Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001)、「有向非巡回グラフにおける最小共通祖先の発見」、第12回ACM-SIAM離散アルゴリズムシンポジウム（SODA '01）議事録、米国ペンシルベニア州フィラデルフィア：産業応用数学会、pp. 845–854、ISBN 978-0-89871-490-6。

[46] Bartlang, Udo (2010), Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems , Springer, p. 59, Bibcode : 2010aamf.book.....B , ISBN 978-3-8348-9645-2。

[47] Pach, János ; Sharir, Micha (2008), Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical surveys and monographs, vol. 152, American Mathematical Society, pp. 93–94 , ISBN 978-0-8218-7533-9。

[48] Price, Derek J. de Solla (1965年7月30日)、「科学論文のネットワーク」(PDF)、Science、149 (3683): 510–515、Bibcode : 1965Sci...149..510D、doi : 10.1126/science.149.3683.510、PMID 14325149 。

[49] Price, Derek J. de Solla (1976)、「書誌計量およびその他の累積的優位性プロセスの一般理論」、Journal of the American Society for Information Science、27 (5): 292–306、doi : 10.1002/asi.4630270505、S2CID 8536863 。

[50] Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "引用ネットワークの推移的削減", Journal of Complex Networks , 3 (2): 189– 203, arXiv : 1310.8224 , doi : 10.1093/comnet/cnu039 , S2CID 10228152 。

[ECV-51] Evans, TS; Calmon, L.; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model", Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038/s41598-020-67421-8 , PMC 7324613 , PMID 32601403

[52] Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", Combinatorial Pattern Matching , Lecture Notes in Computer Science, vol. 1264, Springer, pp. 116–129 , CiteSeerX 10.1.1.53.6273 , doi : 10.1007/3-540-63220-4_55 , ISBN 978-3-540-63220-7S2CID 17045308 。

[53] トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト、 Stein、Clifford (2009)、アルゴリズム入門(第 3版)、MIT Press、 286 ～ 307ページ、ISBN 978-0-262-03384-8。

[54] Lothaire, M. (2005), Applied Combinatorics on Words , Encyclopedia of Mathematics and its Applications, vol. 105, Cambridge University Press, p. 18, ISBN 9780521848022。

[55] Lee, CY (1959)、「バイナリ決定プログラムによるスイッチング回路の表現」、Bell System Technical Journal、38 (4): 985–999、Bibcode : 1959BSTJ...38..985L、doi : 10.1002/j.1538-7305.1959.tb01585.x 。

[56] Akers, Sheldon B. (1978), "Binary decision diagrams", IEEE Transactions on Computers , C-27 (6): 509–516 , Bibcode : 1978ITCmp.100..509A , doi : 10.1109/TC.1978.1675141 , S2CID 21028055 。

[57] Friedman, SJ; Supowit, KJ (1987)、「二分決定図の最適な変数順序の発見」、第24回ACM/IEEE設計自動化会議（DAC '87）議事録、ニューヨーク州ニューヨーク、米国：ACM、pp. 348–356、doi：10.1145/37888.37941、ISBN 978-0-8186-0781-3S2CID 14796451 。

[ 1 ]

[

[ 3 ]

[

[

[

[

[ 8 ]

[ 9 ]

n個の

[ 11 ]

[

[ 13 ]

[

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[

[

[

[ 23 ]

[ 24 ]

[

[

[

[ 28 ]

[

[ 30 ]

[

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 43 ]

[ 44 ]

[ 45 ]

[

[

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]のようにスケーリングする。

[ 52 ]

[ 53 ]

[ 54 ]

決定図で

は、各

[ 57 ]