数学のグラフ理論の分野において、有向グラフ の推移簡約（すいいかんやく、）とは、同じ頂点集合を持ち、できるだけ辺の数が少ない別の有向グラフであって、頂点の任意の組 、 について、 内に から への（有向）道が存在することと、簡約後のグラフにそのような道が存在することが同値であるようなものをいう。推移簡約は によって導入され、彼らはその構成の計算複雑性について厳密な限界を与えた。
より技術的に言えば、この簡約は と同じ到達可能性関係を持つ有向グラフである。同値な言い方をすれば、 とその推移簡約は互いに同じ推移閉包を持たなければならず、また の推移簡約は、その性質を満たすすべてのグラフの中で辺の数ができるだけ少ないものでなければならない。
有限の有向非巡回グラフ（有向の閉路を持たない有向グラフ）の推移簡約は一意に定まり、元のグラフの部分グラフになる。しかし、（有向の）閉路を持つグラフでは一意性は成り立たず、無限グラフに対しては存在すら保証されない。
これと近い関係にある概念として最小同値グラフがある。これは と同じ到達可能性関係を持ち、辺の数ができるだけ少ない の部分グラフである。違いは、推移簡約は の部分グラフである必要がなく、元の には無い辺を含みうるという点である。有限の有向非巡回グラフについては、最小同値グラフは推移簡約と一致する。しかし、閉路を含みうるグラフについては、最小同値グラフの構成はNP困難である一方、推移簡約は多項式時間で構成できる。
推移簡約は、集合上の抽象的な二項関係に対しても、その関係の各組を有向グラフの弧とみなすことで定義できる。
グラフの分類 有向非巡回グラフにおいて 有限の有向グラフ G の推移簡約とは、元のグラフと同じ到達可能性関係を持つ、辺の数ができるだけ少ないグラフである。すなわち、グラフ G の中で頂点 x から頂点 y への道が存在するならば、G の推移簡約の中にも x から y への道が存在しなければならず、その逆もまた成り立つ。具体的には、x から y への道と、y から z への別の道が存在する場合、推移簡約には x から z への直接の辺が存在しないことがある。x、y、z についての推移性とは、x < y かつ y < z ならば x < z であることを意味する。y から z への任意の道に対して x から y への道が存在するならば、x から z への道が存在する。しかし、x から y への道と x から z への道が存在するからといって y から z への道が存在するとは限らない。したがって、頂点 x と z の間の辺は、それが推移的でない歩道を表すものである限り、推移簡約からは除外される。次の画像は、非推移的な二項関係に対応するグラフ（左側）と、その推移簡約（右側）の図を示している。
有限の有向非巡回グラフ G の推移簡約は一意に定まり、両端点の間の唯一の道を成す G の辺から構成される。特に、これは常に与えられたグラフの全域部分グラフである。このため、この場合には推移簡約は最小同値グラフと一致する。
二項関係の数学理論において、集合 X 上の任意の関係 R は、X を頂点集合とし、R において関係を持つ元の任意の順序対に対して弧 xy を持つ有向グラフとみなすことができる。特にこの方法により、半順序集合を有向非巡回グラフとして再解釈することができ、この場合、半順序の与えられた元の組の間に順序関係 x < y が存在するときは常に、グラフ中に弧 xy が存在する。このようにして構成された有向非巡回グラフに対して推移簡約の操作を適用すると、その半順序の被覆関係が得られ、これはしばしばハッセ図によって視覚的に表現される。
推移簡約は、有向非巡回グラフとして表現できるネットワーク（例えば引用グラフや引用ネットワーク）に対して、ネットワーク間の構造的な違いを明らかにするために用いられてきた。
閉路を持つグラフにおいて 閉路を持つ有限グラフでは、推移簡約は一意とは限らない。すなわち、同じ頂点集合上に、辺の数が最小であり、かつ与えられたグラフと同じ到達可能性関係を持つグラフが複数存在することがある。さらに、これらの最小グラフのいずれもが与えられたグラフの部分グラフにならない場合もある。
とはいえ、与えられたグラフ G と同じ到達可能性関係を持つ最小のグラフを特徴づけることは容易である。G を任意の有向グラフとし、H を G と同じ到達可能性関係を持つ、可能な限り辺の数が少ないグラフとすると、H は次のもので構成される。 G の各強連結成分に対する、その成分内の頂点をつなぐ有向閉路 G の凝縮の推移簡約における各辺 XY に対応する辺 xy。ここで X と Y は凝縮においてある辺で結ばれた G の2つの強連結成分であり、x は成分 X 内の任意の頂点、y は成分 Y 内の任意の頂点である。G の凝縮とは、G の各強連結成分に対する頂点を持ち、G 内である辺で結ばれた任意の2成分に対する辺を持つ有向非巡回グラフである。特にこれは非巡回であるため、その推移簡約は前節と同様に定義できる。 このような推移簡約の辺の総数は、凝縮の推移簡約における辺の数に、自明でない強連結成分（頂点を2つ以上持つ成分）内の頂点の数を加えたものに等しい。
凝縮の辺に対応する推移簡約の辺は、常に与えられたグラフ G の部分グラフとなるように選ぶことができる。しかし、各強連結成分内の閉路については、その成分がハミルトン閉路を持つ場合に限って G の部分グラフとなるように選ぶことができ、これは常に成り立つとは限らず、確認も難しい。この難しさのため、与えられたグラフ G と同じ到達可能性を持つ最小の部分グラフ（その最小同値グラフ）を見つけることはNP困難である。
無限グラフにおいて Aho らは、においては、有限グラフの推移簡約をきれいに拡張するような最小性の条件を定義することが難しいことを示す、次のような反例を挙げている。これはグラフが非巡回である場合でも同様に難しい。「真部分集合がいずれも推移簡約にならない」ことを最小性の定義として選ぶと、彼らは次のような反例を挙げている。
各実数に対して頂点を持ち、実数として であるときは常に辺 を持つグラフを構成する。このグラフは無限かつ非巡回であり、推移閉包が取られた状態にある。しかし、同じ推移閉包を持つ任意の部分グラフにおいて、残っている各辺 は、推移閉包を変えることなく取り除くことができる。なぜなら、それらの間にある任意の頂点を経由して x から y への道が依然として存在するはずだからである。したがって、同じ推移閉包を持つ部分グラフの中には（真部分集合による定義の下では）最小のものは一つも存在しない。すなわち、推移簡約は存在しない。
計算複雑性 Aho らが示すように、グラフアルゴリズムの時間計算量を、辺の数の関数としてではなく、グラフの頂点数 n のみの関数として測る場合、有向非巡回グラフの推移閉包と推移簡約は同じ計算複雑性を持つ。すでに、大きさ n × n のブール行列の推移閉包と乗算が互いに同じ計算複雑性を持つことが示されていたため、 credit this result to an unpublished 1971 manuscript of Ian Munro, and to a Russian-language paper by M. E. Furman, .この結果によって推移簡約も同じ複雑性クラスに属することになった。2023年時点での行列乗算の最良の厳密アルゴリズムは、時間 O(n2.371552) で動作し、これを整数上の行列に適用し、その結果の非零成分を調べることで、密なグラフに対する推移簡約の、既知の最良の最悪時間計算量が得られる。
閉包を用いた簡約の計算 推移簡約が推移閉包と同程度に容易であることを示すため、Aho らはすでに知られているブール行列乗算との同値性を利用する。彼らは A を与えられた有向非巡回グラフの隣接行列とし、B をその推移閉包の隣接行列（何らかの標準的な推移閉包アルゴリズムで計算する）とする。このとき、辺 uv が推移簡約に属するのは、行列 A の行 u 列 v に非零の成分があり、かつ行列積 AB の同じ位置に零の成分がある場合、かつその場合に限る。この構成において、行列 AB の非零要素は、長さ2以上の道で結ばれた頂点の組を表す。
簡約を用いた閉包の計算 推移簡約が推移閉包と同程度に難しいことを示すため、Aho らは与えられた有向非巡回グラフ G から別のグラフ H を構成する。ここで G の各頂点は3つの頂点からなる道に置き換えられ、G の各辺は、それぞれの道の対応する中央の頂点をつなぐ H 内の辺に対応する。さらに Aho らは、グラフ H において、すべての道の始点からすべての道の終点への辺を追加する。H の推移簡約において、u の道の始点から v の道の終点への辺が存在するのは、辺 uv が G の推移閉包に属さない場合、かつその場合に限る。したがって、H の推移簡約を効率的に計算できれば、そこから直接 G の推移閉包を読み取ることができる。
疎グラフにおける簡約の計算 有向非巡回グラフの頂点数 n と辺数 m の両方で計測した場合、推移簡約は時間 O(nm) でも求めることができ、この限界はに対しては行列乗算による方法よりも高速になりうる。そのためには、与えられた有向非巡回グラフに対して、開始頂点の取りうるすべての選択について線形時間のを適用する。計算された最長路の中から、長さ1（単一の辺）のものだけを残す。つまり、u から v への他の道が存在しないような辺 (u、v) だけを残す。この O(nm) という時間限界は、深さ優先探索あるいは幅優先探索を用いて、開始頂点の各選択から到達可能な頂点を求めることで推移閉包を構成する場合の計算複雑性と一致しており、したがってこの仮定の下でも、推移閉包と推移簡約は同じ時間で求めることができる。
出力依存アルゴリズム n 個の頂点、m 本の辺を持ち、推移簡約に r 本の辺を持つグラフに対しては、m の代わりに r に依存する時間で推移簡約を求めるが存在する。このアルゴリズムは次の通りである。 入力グラフのトポロジカル順序の逆順で、各頂点 v について: v から到達可能な頂点の集合を、初期状態では単集合 {v} として初期化する。 w によるトポロジカル順序で、各辺 vw について、w が v の到達可能集合に含まれるかどうかを調べ、含まれていない場合: 辺 vw を推移簡約の一部として出力する。 v から到達可能な頂点の集合を、w の到達可能集合との和集合で置き換える。 内側のループにおける辺の順序は、辺をその終点のトポロジカル番号で、次にその始点で並べ替えるために、計数ソートや他の安定なソートアルゴリズムを2回適用することで得られる。集合をビット配列として表現すれば、それぞれの集合の和集合演算は時間 O(n) で、あるいはビット演算を用いればさらに高速に実行できる。これらの集合演算の回数は出力される辺の数に比例するため、全体の時間限界は O(nr) となる。このアルゴリズムの実行中に得られる到達可能集合は、入力の推移閉包を表している。
グラフがその頂点の k 本の鎖（互いに到達可能な部分集合）への分割とともに与えられている場合、各到達可能集合を鎖の接尾部分の和集合として簡潔に表現することで、この時間をさらに O(kr) に短縮できる。
脚注
参考文献 . .
. . . .
外部リンク