2005年11月16日 作成 有向 グラフ （入次数、出次数、次数） >> 目次 （作成日順）
2010年 1月 1日 補遺 　


　
　e ＝ (u, v) が辺であるとき、

　（1） 頂点 u は、頂点 v へ 隣接 しているという （あるいは、v は u から隣接 しているという）。

　（2） 辺 e は、頂点 v へ 接続 しているという （あるいは、e は u から接続 しているという）。

　
　頂点 u の入次数とは、u へ接続している辺の個数をいい、in-deg (u) として記述する。
　頂点 u の出次数とは、u から接続している辺の個数をいい、out-deg (u) として記述する。
　次数とは、in-deg (u) ＋ out-deg (u) のことをいい、deg (u) として記述する。

　　　　　　　　　　　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.

　たとえば、G では、in-deg (v3) ＝ 2、out-deg (v3) ＝ 1、deg (v3) ＝ 3 である。

　
[ 参考 ]

　頂点 u から 頂点 v への道が存在するとき--上述の例 G では、頂点 v0 から頂点 v3 への道が存在するので--、到達可能 である、という。 G の どの 2点をとっても、少なくとも、どちらか から もういっぽうへ到達可能であるならば、G は 片方向連結 である、という。そして、G の どの 2頂点をとっても、たがいに、いっぽうから、もういっぽうへ到達可能ならば、G は 強連結 である、という。当然ながら、道 （順路） は、強連結である。

　（1） 片方向連結

　　　　　　　　　　　　　┌─────────┐
　　　　　　　　　　　　　｜　　　　　　　　　　　　　↓
　　　　　　　　　　　　　a ○ ──→ ○ b ──→ ○ c

　（2） 強連結

　　　　　　　　　　　　　┌─────────┐
　　　　　　　　　　　　　↓　　　　　　　　　　　　　｜
　　　　　　　　　　　　　a ○ ──→ ○ b ──→ ○ c



[ 補遺 ] （2010年 1月 1日）

　本 エッセー に対して、取り立てて補遺はいらないでしょう。

　有向 グラフ の基本的概念を丁寧に読んで習得してください。ただ、本 エッセー で説明した概念は、離散数学を学習するときに習得しておけばいいと思われる概念であって、データベース 設計には直接に役立つ概念ではないかもしれない。そして、本 エッセー を読み返してみて、私は、由々しい遺漏に気づきました。というのは、本 エッセー に続いて （次回に） ハッセ 図を説明しているのですが、有効 グラフ の応用 （特殊形） である 「『木』 構造」 を全然説明していない。申し訳ない。
　以下に 「『木』 構造」 の説明を （本 ホームページ の） 「『赤本』 を読む」 から再録しておきます。

　「木 （tree）」 は、離散数学の 「グラフ （graph）」 の領域で説明されます。数学では、基本閉路をふくんでいない グラフ を 「森 （forest）」 とか 「林」 といい、連結な無閉路 グラフ を 「木」 と云います。特に、コンピュータ・サイエンス では、「木」 には 1つの 「根 （root）」 があることを前提にするので、「木」 と謂えば、ふつう、「根付き木 （rooted tree）」 のことを云います。「木」 は有向 グラフ の特殊形であって、「根付き木」 が indexing で使われています。

　以下の単純な 「木」 を例にして、「検索法」 を説明します。 


　　　　　　　　　　　　　　r ○
　　　　　　　　　　　　　　／　＼
　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　 y1 ○　　　　　○ y2
　　　　　　　　　　　／　＼
　　　　　　　　　　／　　　＼
　　　　　　　 x1 ○　　　　　○ x2
　「根付き木」 では、ルート r から頂点 x1, x2, y2 への道があり、y1 は この道のうえの頂点であるとき、y1 を x1, x2 の 「祖先」 であると云い、x1, x2 は y1 の 「子孫」 であると云います。そして、特に、y1, x1 （および、y1, x2） が 「辺」 であれば、y1 を x1 （および、x2） の 「親」 と云い、x1 （および x2） を 「子」 と云います。

　「子」 を持たない頂点を 「葉 （leaf）」 と云います──この例では、x1, x2 および y2 が 「葉」 です。

　「木」 では、「子」 のあいだには、「関係」 が定められていないのですが、「子」 のあいだに 「並び」 が定められている 「木」 を 「順序木 （ordered tree）」 と云います。「木」 と云えば、ふつう──特に断りがなければ──「根付き順序木」 を指します （下図参照）。


　　　　　　　　　　　　　　r ○
　　　　　　　　　　　　　　／　＼
　　　　　　　　　　　　　／　　　＼
　　　　　　　　　　 y1 ○─────○ y2
　　　　　　　　　　　／　＼
　　　　　　　　　　／　　　＼
　　　　　　　 x1 ○─────○ x2
　さて、「根付き順序木」 において、検索の基本法には、以下の 2つが考えられます。

　（1） DFS （Depth First Search）
　（2） BFS （Breadth First Search）

　DFS は、「階」 関係の道を辿る やりかた で──たとえば、(r, y1) (y1, x1) (y1, x2) (r, y2) ──、BFS は 「次数」 の道を辿る やりかた です──たとえば、(y1, y2) (x1, x2)。




　 << もどる HOME すすむ >>
　 ▼ ベーシックス