有向非巡回グラフ

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

有向非巡回グラフは、非巡回有向グラフ^[1]または非巡回有向グラフ^[2]とも呼ばれます。

定義

グラフは頂点と、頂点のペアを接続する辺によって形成されます。頂点は、辺によってペアで接続されたあらゆる種類のオブジェクトです。有向グラフの場合、各辺には、1 つの頂点から別の頂点への方向があります。有向グラフのパスとは、一連の辺の終了頂点が、次の辺の開始頂点と同じであるという特性を持つ一連の辺です。パスの最初の辺の開始頂点が最後の辺の終了頂点と等しい場合、パスは循環を形成します。有向非巡回グラフは、循環のない有向グラフです。^[1]^[2]^[3]

有向グラフの頂点 $vは、$ $uから始まり$ $v$ で終わるパスが存在する場合、別の頂点 $uから$ 到達可能であると言われます。特別なケースとして、すべての頂点は、（ゼロのエッジを持つパスによって）自分自身から到達可能であると見なされます。頂点が非自明なパス（1つ以上のエッジを持つパス）を介して自分自身に到達できる場合、そのパスはサイクルであるため、有向非巡回グラフを定義する別の方法は、非自明なパスを介して自分自身に到達できないグラフであるということです。^[4]

数学的性質

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

DAG の到達可能性関係は、DAG の頂点上の半順序 $\leq$ として形式化できます。この半順序では、DAG で $uから$ $v$ への有向パスが存在する場合、つまり $uが$ $v$ に到達できる場合(または $vが$ $u$ から到達可能) 、2 つの頂点 $u$ と $vは$ $u \leq v$ と順序付けられます。 ^[5]ただし、異なる DAG が同じ到達可能性関係と同じ半順序を生じる場合があります。^[6]たとえば、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 に対して一意に定義されます。対照的に、非巡回でない有向グラフの場合、同じ到達可能性関係を持つ複数の極小サブグラフが存在する可能性があります。^[7]推移的簡約は、同じ順序を表す他のグラフよりも辺が少なく、したがってグラフの描画が単純になるため、それが表す半順序を視覚化するのに役立ちます。半順序のハッセ図は、推移的簡約の描画であり、すべての辺の方向は、辺の開始頂点を終了頂点よりも低い位置に配置することによって示されます。^[8]

位相的順序

有向グラフの位相的順序とは、すべての辺について、辺の開始頂点が辺の終了頂点よりも前に出現するように頂点を順序付けることです。位相的順序を持つグラフにはサイクルが存在できません。サイクルの最も早い頂点への辺は間違った方向に向いている必要があるためです。したがって、位相的順序を持つすべてのグラフは非巡回です。逆に、すべての有向非巡回グラフには少なくとも 1 つの位相的順序があります。したがって、位相的順序の存在は、有向非巡回グラフの同等の定義として使用できます。つまり、それらはまさに位相的順序を持つグラフです。^[2] 一般に、この順序は一意ではありません。DAG が一意の位相的順序を持つのは、すべての頂点を含む有向パスがある場合のみであり、その場合、順序はパスに頂点が出現する順序と同じです。^[9]

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

組み合わせ列挙

有向非巡回グラフを数えるグラフ列挙問題は、ロビンソン（1973）によって研究された。[ 11 ^] $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}.

^[11]

Eric W. Weisstein は^[12] 、McKay ら (2004)が証明したように、同じ数は、すべての固有値が正の実数である(0,1) 行列を数えます。証明は全単射です。行列 $A$ がDAG の隣接行列である場合、かつその場合に限り、 $A$ $+$ $I$ はすべての固有値が正である (0,1) 行列です。ここで、 $I は$ 単位行列を表します。DAG は自己ループを持つことができないため、その隣接行列はゼロの対角を持つ必要があり、したがって $I を$ 追加してもすべての行列係数が 0 または 1 であるという特性が保持されます。 ^[13]

計算上の問題

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

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

与えられた有向グラフがDAGであるかどうかを線形時間で確認することも可能です。これは、位相的順序付けを見つけようとし、各辺に対して結果の順序付けが有効かどうかをテストすることによって行われます^[18]。あるいは、一部の位相的ソートアルゴリズムでは、アルゴリズムがエラー条件を満たさずにすべての頂点を正常に順序付けていることを確認することによって行われます^{[17] 。}

巡回グラフからの構築

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

任意の有向グラフは、フィードバック頂点集合またはフィードバックアーク集合（それぞれ、すべてのサイクルに接する頂点または辺の集合）を削除することによってDAGにすることができます。しかし、そのような最小の集合を見つけることはNP困難です。^[20]任意の有向グラフは、その強く連結された各コンポーネントを単一のスーパー頂点に縮小することによって、その凝縮と呼ばれるDAGに変換することもできます。 ^[21]グラフがすでに非巡回である場合、その最小のフィードバック頂点集合とフィードバックアーク集合は空であり、その凝縮はグラフそのものです。

推移閉包と推移還元

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

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

閉鎖問題

閉包問題は、頂点重み付き有向非巡回グラフを入力として、閉包の最小（または最大）重み（頂点Cの集合で、 C から辺が離れない）を求める問題である。この問題は、非巡回性を仮定せずに有向グラフに対して定式化することもできるが、その場合、グラフの凝縮に関する同じ問題と同等であるため、一般性はそれほど高くない。最大フロー問題への還元を使用して、多項式時間で解くことができる。^[25]

パスアルゴリズム

位相的順序付けの原理に基づき、一般的なグラフではなくDAGで使用すると、いくつかのアルゴリズムはより単純になります。たとえば、DAG内の特定の開始頂点からの最短経路と最長経路を線形時間で見つけるには、頂点を位相的順序で処理し、各頂点の経路長をその入ってくる辺のいずれかを介して得られる最小または最大の長さになるように計算します。^[26]対照的に、任意のグラフの場合、最短経路にはダイクストラのアルゴリズムやベルマン・フォードのアルゴリズムなどのより遅いアルゴリズムが必要になる場合があります。 ^[27]また、任意のグラフで最長経路を見つけることはNP困難です。^[28]

アプリケーション

スケジュール

部分順序の有向非巡回グラフ表現は、順序制約のあるタスクのシステムのスケジューリングに多くの応用があります。 ^[29] このタイプの問題の重要なクラスは、更新する必要があるオブジェクトのコレクションに関するものです。たとえば、スプレッドシートのセルの 1 つが変更された後や、ソースコードが変更された後のコンピュータソフトウェアのオブジェクトファイルなどです。このコンテキストでは、依存関係グラフは、更新される各オブジェクトの頂点と、2 つのオブジェクトのうちの 1 つをもう 1 つよりも早く更新する必要がある場合にそれらを接続するエッジを持つグラフです。このグラフのサイクルは循環依存関係と呼ばれ、サイクルに含まれるタスクを一貫してスケジュールする方法がないため、通常は許可されません。循環依存関係のない依存関係グラフは DAG を形成します。^[30]

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

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

データ処理ネットワーク

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

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

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

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

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

因果構造

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

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

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

系譜とバージョン履歴

家系図は、各家族メンバーを頂点とし、各親子関係を辺とする有向非巡回グラフとみなすことができます。^[44]名前にもかかわらず、これらのグラフは必ずしも木ではありません。親族間の結婚（つまり、子供は母方と父方の両方に共通の祖先を持つ）により家系崩壊が発生する可能性があるためです。^[45]母系（母娘関係）と父系（父息子関係）のグラフは、このグラフ内の木です。誰も自分の祖先になることはできないため、家系図は非巡回です。^[46]

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

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

引用グラフ

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

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

データ圧縮

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

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

参考文献

^ ab Thulasiraman, K.; Swamy, MNS (1992)、「5.7 非巡回有向グラフ」、グラフ: 理論とアルゴリズム、John Wiley and Son、p. 118、ISBN 978-0-471-51356-8。
^ abc Bang-Jensen, Jørgen (2008)、「2.1 非巡回有向グラフ」、有向グラフ：理論、アルゴリズム、アプリケーション、Springer Monographs in Mathematics（第2版）、Springer-Verlag、pp. 32–34、ISBN 978-1-84800-997-4。
^ クリストフィード、ニコス（1975）、グラフ理論：アルゴリズム的アプローチ、アカデミックプレス、pp. 170-174。
^ ミトラニ、I. (1982)、「離散事象システムのシミュレーション技術」、ケンブリッジコンピュータサイエンステキスト、第14巻、ケンブリッジ大学出版局、p. 27、ISBN 9780521282826。
^ Kozen, Dexter (1992)、アルゴリズムの設計と分析、Monographs in Computer Science、Springer、p. 9、ISBN 978-0-387-97687-7。
^ Banerjee, Utpal (1993)、「演習 2(c)」、ループ変換による再構築コンパイラ: 基礎、Springer、p. 19、Bibcode :1993ltfr.book.....B、ISBN 978-0-7923-9318-4。
^ Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008)、「2.3 推移的有向グラフ、推移的閉包および縮約」、有向グラフ: 理論、アルゴリズムおよびアプリケーション、Springer Monographs in Mathematics、Springer、pp. 36–39、ISBN 978-1-84800-998-1。
^ ユングニッケル、ディーター（2012）、グラフ、ネットワーク、アルゴリズム、数学におけるアルゴリズムと計算、第5巻、シュプリンガー、pp.92-93、ISBN 978-3-642-32278-5。
^ セジウィック、ロバート、ウェイン、ケビン (2011)、「4、2、25 ユニークな位相的順序付け」、アルゴリズム (第 4 版)、アディソン・ウェズリー、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。
^ ab Robinson, RW (1973)、「ラベル付き非巡回有向グラフのカウント」、Harary, F. (編)、『グラフ理論の新しい方向性』、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 メンテナンス: 上書きされた設定 (リンク)
^ McKay, BD ; Royle, GF ; Wanless, IM; Oggier, FE ; Sloane, NJA ; Wilf, H. (2004)、「(0,1)行列の非巡回有向グラフと固有値」、Journal of Integer Sequences、7 :33、arXiv : math/0310423、Bibcode :2004JIntS...7...33M、第04.3.3条。
^ ファーナス、ジョージ W. ; ザックス、ジェフ (1994)、「マルチツリー: 階層構造の強化と再利用」、SIGCHI ヒューマンファクターズインコンピューティングシステムカンファレンス (CHI '94) 論文集、pp. 330–336、doi : 10.1145/191666.191778、ISBN 978-0897916509、S2CID 18710118。
^ Rebane, George; Pearl, Judea (1987)、「統計データからの因果多木構造の復元」、人工知能における不確実性に関する第 3 回年次会議 (UAI 1987)、シアトル、ワシントン州、米国、1987 年 7 月(PDF)、pp. 222–228。
^ ab コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001) [1990]、アルゴリズム入門(第 2 版)、MIT Press および McGraw-Hill、ISBN 0-262-03293-7{{cite book}}: CS1 メンテナンス: 上書きされた設定 (リンク) セクション22.4、トポロジカルソート、pp. 549–552。
^ ab Jungnickel (2012)、50-51ページ。
^ 深さ優先探索に基づくトポロジカルソートアルゴリズムの場合、この妥当性チェックはトポロジカルソートアルゴリズム自体とインターリーブすることができます。たとえば、Skiena、Steven S. (2009)、The Algorithm Design Manual、Springer、pp. 179–181、ISBNを参照してください。 978-1-84800-070-4。
^ スタンレー、リチャード P. (1973)、「グラフの非巡回方向」(PDF)、離散数学、5 (2): 171–178、doi :10.1016/0012-365X(73)90108-8。
^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論ガイド」、数学科学シリーズ（第1版）、ニューヨーク：WHフリーマンアンドカンパニー、ISBN 9780716710455、MR 0519066、OCLC 247570676、問題GT7およびGT8、pp.191-192。
^ フランク・ハラリー、ロバート・Z・ノーマン、ドーウィン・カートライト（1965年）『構造モデル：有向グラフ理論入門』、ジョン・ワイリー・アンド・サンズ、63ページ。
^ スキエナ（2009）、495頁。
^ スキエナ（2009）、496頁。
^ バン＝ジェンセンとグーティン (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年966頁。
^ スキエナ（2009）、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-1、S2CID 17570052。
^ ab Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013)、グラフ理論ハンドブック（第2版）、CRC Press、p. 1181、ISBN 978-1-4398-8018-0。
^ Srikant, YN; Shankar, Priti (2007)、『コンパイラ設計ハンドブック: 最適化とマシンコード生成 (第 2 版)』、CRC Press、pp. 19–39、ISBN 978-1-4200-4383-9。
^ ワン、ジョン・X. (2002)、不確実性の下での意思決定についてエンジニアが知っておくべきこと、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)、「データフロー手続き言語の最初のバージョン」、プログラミングシンポジウム、コンピュータサイエンスの講義ノート、第19巻、pp. 362–376、doi :10.1007/3-540-06859-7_145、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）、Causal Learning、オックスフォード大学出版局、p. 4、ISBN 978-0-19-803928-0。
^ Shmulevich, Ilya; Dougherty, Edward R. (2010)、確率的ブールネットワーク：遺伝子制御ネットワークのモデリングと制御、産業応用数学協会、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。
^ Dorf, Richard C. (1998)、テクノロジーマネジメントハンドブック、CRC Press、p. 9-7、ISBN 978-0-8493-8577-3。
^ ボスラフ、サラ（2008）、疫学百科事典、第1巻、SAGE、p.255、ISBN 978-1-4129-2816-8。
^ パール、ジュデア（1995）、「実証研究のための因果図」、バイオメトリカ、82（4）：669–709、doi：10.1093/biomet/82.4.669。
^ カークパトリック、ボニー B. (2011 年 4 月)、「家系図におけるハプロタイプと遺伝子型」、分子生物学アルゴリズム、6 (10): 10、doi : 10.1186/1748-7188-6-10、PMC 3102622、PMID 21504603 。
^ McGuffin, MJ; Balakrishnan, R. (2005)、「系図グラフのインタラクティブな視覚化」(PDF)、IEEE 情報視覚化シンポジウム (INFOVIS 2005)、pp. 16–23、doi :10.1109/INFVIS.2005.1532124、ISBN 978-0-7803-9464-3、S2CID 15449409。
^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001)、「有向非巡回グラフにおける最小共通祖先の検出」、第 12 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA '01) の議事録、フィラデルフィア、ペンシルバニア州、米国: Society for Industrial and Applied Mathematics、pp. 845–854、ISBN 978-0-89871-490-6。
^ Bartlang, Udo (2010)、ピアツーピアシステムにおける柔軟なコンテンツ管理のアーキテクチャと方法、Springer、p. 59、Bibcode :2010aamf.book.....B、ISBN 978-3-8348-9645-2。
^ パック、ヤノシュ、シャリル、ミカ、組合せ幾何学とそのアルゴリズム的応用：アルカラ講義、数学的概説とモノグラフ、第152巻、アメリカ数学会、pp. 93-94、ISBN 978-0-8218-7533-9。
^ Price, Derek J. de Solla (1965 年 7 月 30 日)、「Networks of Scientific Papers」(PDF)、Science、149 (3683): 510–515、Bibcode :1965Sci...149..510D、doi :10.1126/science.149.3683.510、PMID 14325149。
^ プライス、デレク・J・デ・ソラ（1976）、「計量書誌学およびその他の累積的優位性プロセスの一般理論」、アメリカ情報科学協会誌、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。
^ エヴァンス、TS; カルモン、L.; ヴァシリアウスカイテ、V. (2020)、「価格モデルにおける最長経路」、サイエンティフィック・レポート、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)、「コンパクトな有向非巡回ワードグラフの直接構築」、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-7、S2CID 17045308。
^ ロテール、M. (2005)、「単語の応用組合せ論」、数学とその応用百科事典、第105巻、ケンブリッジ大学出版局、p. 18、ISBN 9780521848022。
^ Lee, CY (1959)、「バイナリ決定プログラムによるスイッチング回路の表現」、ベルシステム技術ジャーナル、38 (4): 985–999、doi :10.1002/j.1538-7305.1959.tb01585.x。
^ Akers, Sheldon B. (1978)、「二分決定図」、IEEE Transactions on Computers、C-27 (6): 509–516、doi :10.1109/TC.1978.1675141、S2CID 21028055。
^ Friedman, SJ; Supowit, KJ (1987)、「バイナリ決定図の最適な変数順序の検出」、Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)、ニューヨーク、ニューヨーク、米国: ACM、pp. 348–356、doi :10.1145/37888.37941、ISBN 978-0-8186-0781-3、S2CID 14796451。

外部リンク

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

[thul-1] Thulasiraman, K.; Swamy, MNS (1992)、「5.7 非巡回有向グラフ」、グラフ: 理論とアルゴリズム、John Wiley and Son、p. 118、ISBN 978-0-471-51356-8。

[bang-2] Bang-Jensen, Jørgen (2008)、「2.1 非巡回有向グラフ」、有向グラフ：理論、アルゴリズム、アプリケーション、Springer Monographs in Mathematics（第2版）、Springer-Verlag、pp. 32–34、ISBN 978-1-84800-997-4。

[3] クリストフィード、ニコス（1975）、グラフ理論：アルゴリズム的アプローチ、アカデミックプレス、pp. 170-174。

[4] ミトラニ、I. (1982)、「離散事象システムのシミュレーション技術」、ケンブリッジコンピュータサイエンステキスト、第14巻、ケンブリッジ大学出版局、p. 27、ISBN 9780521282826。

[5] Kozen, Dexter (1992)、アルゴリズムの設計と分析、Monographs in Computer Science、Springer、p. 9、ISBN 978-0-387-97687-7。

[6] Banerjee, Utpal (1993)、「演習 2(c)」、ループ変換による再構築コンパイラ: 基礎、Springer、p. 19、Bibcode :1993ltfr.book.....B、ISBN 978-0-7923-9318-4。

[7] Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008)、「2.3 推移的有向グラフ、推移的閉包および縮約」、有向グラフ: 理論、アルゴリズムおよびアプリケーション、Springer Monographs in Mathematics、Springer、pp. 36–39、ISBN 978-1-84800-998-1。

[8] ユングニッケル、ディーター（2012）、グラフ、ネットワーク、アルゴリズム、数学におけるアルゴリズムと計算、第5巻、シュプリンガー、pp.92-93、ISBN 978-3-642-32278-5。

[9] セジウィック、ロバート、ウェイン、ケビン (2011)、「4、2、25 ユニークな位相的順序付け」、アルゴリズム (第 4 版)、アディソン・ウェズリー、pp. 598–599、ISBN 978-0-13-276256-4。

[10] 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-11] Robinson, RW (1973)、「ラベル付き非巡回有向グラフのカウント」、Harary, F. (編)、『グラフ理論の新しい方向性』、Academic Press、pp. 239–273参照：Harary, Frank ; Palmer, Edgar M. (1973)、Graphical Enumeration、Academic Press、p. 19、ISBN 978-0-12-324245-7。

[12] ワイスタイン、エリック W.、「ワイスタインの予想」、MathWorld{{cite web}}: CS1 メンテナンス: 上書きされた設定 (リンク)

[13] McKay, BD ; Royle, GF ; Wanless, IM; Oggier, FE ; Sloane, NJA ; Wilf, H. (2004)、「(0,1)行列の非巡回有向グラフと固有値」、Journal of Integer Sequences、7 :33、arXiv : math/0310423、Bibcode :2004JIntS...7...33M、第04.3.3条。

[14] ファーナス、ジョージ W. ; ザックス、ジェフ (1994)、「マルチツリー: 階層構造の強化と再利用」、SIGCHI ヒューマンファクターズインコンピューティングシステムカンファレンス (CHI '94) 論文集、pp. 330–336、doi : 10.1145/191666.191778、ISBN 978-0897916509、S2CID 18710118。

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

[clrs-16] コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001) [1990]、アルゴリズム入門(第 2 版)、MIT Press および McGraw-Hill、ISBN 0-262-03293-7{{cite book}}: CS1 メンテナンス: 上書きされた設定 (リンク) セクション22.4、トポロジカルソート、pp. 549–552。

[j50-17] Jungnickel (2012)、50-51ページ。

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

[19] スタンレー、リチャード P. (1973)、「グラフの非巡回方向」(PDF)、離散数学、5 (2): 171–178、doi :10.1016/0012-365X(73)90108-8。

[20] ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論ガイド」、数学科学シリーズ（第1版）、ニューヨーク：WHフリーマンアンドカンパニー、ISBN 9780716710455、MR 0519066、OCLC 247570676、問題GT7およびGT8、pp.191-192。

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

[22] スキエナ（2009）、495頁。

[23] スキエナ（2009）、496頁。

[24] バン＝ジェンセンとグーティン (2008)、p. 38.

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

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

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

[28] コーメン他2001年966頁。

[29] スキエナ（2009）、469頁。

[30] 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-1、S2CID 17570052。

[hgt1181-31] Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013)、グラフ理論ハンドブック（第2版）、CRC Press、p. 1181、ISBN 978-1-4398-8018-0。

[32] Srikant, YN; Shankar, Priti (2007)、『コンパイラ設計ハンドブック: 最適化とマシンコード生成 (第 2 版)』、CRC Press、pp. 19–39、ISBN 978-1-4200-4383-9。

[33] ワン、ジョン・X. (2002)、不確実性の下での意思決定についてエンジニアが知っておくべきこと、CRC Press、p. 160、ISBN 978-0-8247-4373-4。

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

[35] Dennis, Jack B. (1974)、「データフロー手続き言語の最初のバージョン」、プログラミングシンポジウム、コンピュータサイエンスの講義ノート、第19巻、pp. 362–376、doi :10.1007/3-540-06859-7_145、ISBN 978-3-540-06859-4。

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

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

[38] ゴプニック、アリソン、シュルツ、ローラ（2007）、Causal Learning、オックスフォード大学出版局、p. 4、ISBN 978-0-19-803928-0。

[39] Shmulevich, Ilya; Dougherty, Edward R. (2010)、確率的ブールネットワーク：遺伝子制御ネットワークのモデリングと制御、産業応用数学協会、p. 58、ISBN 978-0-89871-692-4。

[40] ロバート・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。

[41] Dorf, Richard C. (1998)、テクノロジーマネジメントハンドブック、CRC Press、p. 9-7、ISBN 978-0-8493-8577-3。

[42] ボスラフ、サラ（2008）、疫学百科事典、第1巻、SAGE、p.255、ISBN 978-1-4129-2816-8。

[pearl:95-43] パール、ジュデア（1995）、「実証研究のための因果図」、バイオメトリカ、82（4）：669–709、doi：10.1093/biomet/82.4.669。

[44] カークパトリック、ボニー B. (2011 年 4 月)、「家系図におけるハプロタイプと遺伝子型」、分子生物学アルゴリズム、6 (10): 10、doi : 10.1186/1748-7188-6-10、PMC 3102622、PMID 21504603 。

[45] McGuffin, MJ; Balakrishnan, R. (2005)、「系図グラフのインタラクティブな視覚化」(PDF)、IEEE 情報視覚化シンポジウム (INFOVIS 2005)、pp. 16–23、doi :10.1109/INFVIS.2005.1532124、ISBN 978-0-7803-9464-3、S2CID 15449409。

[46] Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001)、「有向非巡回グラフにおける最小共通祖先の検出」、第 12 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA '01) の議事録、フィラデルフィア、ペンシルバニア州、米国: Society for Industrial and Applied Mathematics、pp. 845–854、ISBN 978-0-89871-490-6。

[47] Bartlang, Udo (2010)、ピアツーピアシステムにおける柔軟なコンテンツ管理のアーキテクチャと方法、Springer、p. 59、Bibcode :2010aamf.book.....B、ISBN 978-3-8348-9645-2。

[48] パック、ヤノシュ、シャリル、ミカ、組合せ幾何学とそのアルゴリズム的応用：アルカラ講義、数学的概説とモノグラフ、第152巻、アメリカ数学会、pp. 93-94、ISBN 978-0-8218-7533-9。

[49] Price, Derek J. de Solla (1965 年 7 月 30 日)、「Networks of Scientific Papers」(PDF)、Science、149 (3683): 510–515、Bibcode :1965Sci...149..510D、doi :10.1126/science.149.3683.510、PMID 14325149。

[50] プライス、デレク・J・デ・ソラ（1976）、「計量書誌学およびその他の累積的優位性プロセスの一般理論」、アメリカ情報科学協会誌、27（5）：292-306、doi：10.1002/asi.4630270505、S2CID 8536863。

[51] 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-52] エヴァンス、TS; カルモン、L.; ヴァシリアウスカイテ、V. (2020)、「価格モデルにおける最長経路」、サイエンティフィック・レポート、10 (1): 10503、arXiv : 1903.03667、Bibcode :2020NatSR..1010503E、doi :10.1038/s41598-020-67421-8、PMC 7324613、PMID 32601403

[53] Crochemore, Maxime; Vérin, Renaud (1997)、「コンパクトな有向非巡回ワードグラフの直接構築」、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-7、S2CID 17045308。

[54] ロテール、M. (2005)、「単語の応用組合せ論」、数学とその応用百科事典、第105巻、ケンブリッジ大学出版局、p. 18、ISBN 9780521848022。

[55] Lee, CY (1959)、「バイナリ決定プログラムによるスイッチング回路の表現」、ベルシステム技術ジャーナル、38 (4): 985–999、doi :10.1002/j.1538-7305.1959.tb01585.x。

[56] Akers, Sheldon B. (1978)、「二分決定図」、IEEE Transactions on Computers、C-27 (6): 509–516、doi :10.1109/TC.1978.1675141、S2CID 21028055。

[57] Friedman, SJ; Supowit, KJ (1987)、「バイナリ決定図の最適な変数順序の検出」、Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)、ニューヨーク、ニューヨーク、米国: ACM、pp. 348–356、doi :10.1145/37888.37941、ISBN 978-0-8186-0781-3、S2CID 14796451。