部分ノードセットからノードまでの距離と高さ

有向無循環グラフGで考える。循環があるとうまくない。A⊆Node(G) とする。ノードxに対して、集合Aとxの非対称距離を次のように定義する。

• {d(a, x) | a∈A } の最小値

d(a, x)は、aからxに至るパスの長さの最小値とする。dは対称ではないので距離ではない。集合とのノードの距離は、片一方（パスの出発点）のノードを集合内で動かしての、最短となるパスの長さ。

同様な設定で、ノードxの集合Aからの高さを、

• {d(a, x) | a∈A } の最大値

と定める。非循環グラフなら、高さは有限な値となる。そして、高さに関する直和分解ができる。

R = {x∈Node(G) | xは親がない} として、Rからの高さが1, 2, ... の集合が直和分解を与えて、グラフが有限なら直和成分も有限個となる。

[追記]一般的には、「高さ」って用語は適切じゃないな。なんか考えないと。[/追記]