有向グラフとして解釈可能／表現可能なデータ構造はいろいろあります。有向グラフ構造を扱うとき、有向サイクル（矢印をたどって同じ所に戻る道）があるとマズイことは多いと思います。しかし、有向サイクルの検出は大変です。有向サイクルを作らないように注意しながら有効グラフを変形するほうがいいでしょう。つまり、「サイクルがない」という制約（不変条件）を守り続けるわけ。（以下、サイクル＝有向サイクル）
とはいえ、具体的にどうするのか？ 万能ではありませんが、比較的簡単な方法があります。Gを有向グラフとして、ノード（頂点）の集合をNode(G)とします。Node(G) 上で定義された整数値関数fで*1次の性質を持つものを考えます。
- a, b∈Node(G)、aからbへ向かう有向辺があるなら f(a) ＜ f(b)
不等号の向きは逆でもいいですが、とにかくどちらかに決めます。この性質を持つようなNode(G)上の関数を仮にGのレベル関数（水準関数）と呼んでおきます。
グラフGにサイクルがあると、レベル関数は存在できません。まず、aからa自分に戻る辺（ループ）が出ているとします。このとき、「aからaへ向かう有向辺があるが、f(a) ＜ f(a) ではない」ので、レベル関数となるf(a)が定義できません。同じように、a→a1→a2→ ... →an = a のようなサイクルがあると、f(a)の値をレベル関数になるようには定義できません。
待遇対偶を取ると：
- グラフG上にレベル関数が存在するなら、Gにサイクルは存在しない。
G上にレベル関数fが存在するとき、GをG'に変形すると同時にfをf'に修正して、f'がG'のレベル関数になるようなアルゴリズムが作れるならば、サイクルの非存在は保証できます。
これでもけっこうな手間になったりしますが、大域的にサイクルを検出するよりはマシなことが多いと思います。
図形の話（幾何学）だと、図形の上の関数や微分形式の存在／非存在が、その図形の位相的な不変量を反映していることがよくありますが、有向サイクルとレベル関数は、その極端に簡単な実例と言えるかもしれません。
*1:値の領域は、全順序集合なら何でもかまいません。
