前回から引き続き、有向 グラフ について述べる。有向 グラフ に関して綴っている理由は──有向 グラフ そのものは、本 ホームページ の 「数学基礎論 （現代集合論）」 のように、「グラフ 理論」 として独立した単元を作って扱えば良いのかもしれないが──、以下の 2点を、データ 設計のなかで検討したいからである。

　　（1） ハッセ 図や 「ラベル 付き グラフ」 を、TM の構造図 （構文図） として使うことはできないか。
　　（2） 同値類の 「分割・細分」 （同値類上の関係） と 「グラフ 上の巡回」 （親子関係） を検討する。

　
　有限列 P ＝ (v₀, v₁,..., v_n) を G の頂点として、(v_i−1, v_i) ∈ E とする。なお、1 ≦ i ≦ n とする。
　(v₀, v_n) を道あるいは路という （通路とか順路ともいう）。v₀ を P の始点といい、v_n を P の終点といい、n を道の長さという。なお、(v₀) は、長さ 0 の道とみなす。

　同じ辺を ２度以上 通らない道を単純道という。
　同じ頂点を ２度以上 通らない道を基本道という。
　そして、始点と終点が一致する道を閉道という （閉路とか回路ともいう）。

　長さが 1 以上で、同じ辺を 2度以上 通らない閉道を単純閉道という。
　長さが 1 以上で、同じ頂点を 2度以上 通らない閉道を基本閉道という。

　　　　　　　　　　　G：
　　　　　　　　　　　　　　　　　　┌─┐
　　　　　　　　　　　　　　　　　　│　│
　　　　　　　　　　　　v0 ○ ──→ ○　│v1
　　　　　　　　　　　　　↑│　　│↑　│
　　　　　　　　　　　　　││　　│└─┘
　　　　　　　　　　　　　│↓　　↓
　　　　　　　　　　　　v3 ○ ←── ○ v2