2005年11月16日 作成 有向 グラフ (単純道、基本道、閉道) >> 目次 (テーマごと)
2009年12月16日 補遺  


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

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

 
 有限列 P = (v0, v1,..., vn) を G の頂点として、(vi−1, vi) ∈ E とする。なお、1 ≦ i ≦ n とする。
 (v0, vn) をあるいはという (通路とか順路ともいう)。v0 を P の始点といい、vn を P の終点といい、n を道の長さという。なお、(v0) は、長さ 0 の道とみなす。

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

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

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

  道     : v0, v3, v0, v1, v1, v2, v3.
  単純道  : v0, v1, v1, v2, v3.
  基本道  : v0, v1, v2, v3.
  閉道   : v0, v1, v2, v3, v0.



[ 補遺 ] (2009年12月16日)

 本 エッセー に対して、取り立てて補遺はいらないでしょう。
 有向 グラフ の基本的概念を丁寧に読んで習得してください。

 TMD (TM Diagram) は、有向 グラフ を 「線と箱」 で記述した図です──したがって、TMD は、チェン ERD とは、全然、ちがう系統の技術です。TM の前身である T字形 ER手法は、ER 手法という呼称を付けたので、世間では、チェン ER と同じ流派として括られたようなので、その謬見を今後抱かれないように、T字形 ER手法を TM と改称した次第です。ちなみに、私は、チェン ER を モデル とは思っていない [ 記法にすぎない、と思っています ]。TM を 「T字形 メソッド」 の略として邪推されることもあるようですが、TM という呼称は、「Turing Machine」 を もじって付けました。というのは、「情報」 を 「解析」 するときにも、アルゴリズム (あるいは、文法としての構成) があることを示したかったので。

 なお、TMD が有向 グラフ を図にした物であるということは、「箱 (entity) ではなくて、線 (relation) を観よ」 ということを意味しています。すなわち、「関数」 としての 「構成」 を注視しなさい、ということ。なぜなら、「箱」 の意味は、文脈 (構成) のなかで定立するから。

 本 エッセー で言及した 「ハッセ 図」 を、後日、「ベーシックス」 の テーマ にしているのですが [ 本 ホームページ、464 ページ参照 ]、その ページ では 「ハッセ 図」 を TMD として使うことができないと述べています。





  << もどる ベーシックス すすむ >>
  データベースの基礎知識