Interval (graph theory) とは

グラフ理論では、有向グラフの区間I(h)は、hが唯一のI(h)であり、I(h)のすべての閉路がhを含む最大の単一エントリ部分グラフである。間隔は、F.E.AllenおよびJ.Cockeによって1970年に記載されている。区間グラフは、コンパイラで使用されるいくつかのアルゴリズム、特にデータフロー分析に不可欠です。
次のアルゴリズムは、頂点Nとエントリ頂点n0からなるグラフ内のすべての区間を求め、与えられたノードnの先行ノードと後続ノードのリストをそれぞれ返す関数pred(n)とsucc(n)で求める。
 H = {n0} // Hが空ではない間に作業リストを初期化するHから次のhを削除するI(h)+ = {h}∃n∈{succ(I(h)) – I (h)}、次のヘッダ∃m∈pred(n)を見つけるような∃n∈Nの間、pred(n)⊆I(h) m∈I(h)H + = n
アルゴリズムは事実上、グラフをその区間に分割する。
各区間は、1つのノードで置き換えることができます。一方、元のグラフの異なる区間にあるノード間のすべてのエッジは、新しいグラフの対応するノード間のエッジになります。この新しいグラフを区間派生グラフと呼びます。導出されたグラフを作成するプロセスは、結果のグラフをさらに減らすことができなくなるまで繰り返すことができます。最終的なグラフが単一のノードからなる場合、元のグラフは縮小可能であると言われる。