第 6 回アルゴリズムに関する数学

本日の内容

6-1. グラフ
6-2. グラフの表現
6-3. 計算量
6-4. java のおまけ

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

6-1. グラフ

プログラムで扱うデータ構造としてグラフを取り上げます。グラフとは頂点とそれを結ぶ辺からなるものです。

頂点は vertex、節、 node などの呼び方があります、辺は edge、枝、 branch とも言います。辺に向きがないグラフを無向グラフ、辺に向きがあるグラフを有向グラフと言います。

互いに接続している頂点の列を道(path)と言います。無向グラフにおいて、全ての頂点の組合せについて道がある場合、そのグラフは連結であると言います。

頂点に接続している辺の数をその頂点の次数、degree 、arityと言います。有向グラフにおいては出る辺の数を出次数、out degree、入る辺の数を入次数、in degreeと言います。

グラフには様々な形があり、それについて名前が付けられています。無向辺において、木とは、ループのない連結グラフのことを言います。次数が 1 の頂点を葉、leafと言います。

根付有向木とは、次の条件を満たす有向グラフのことです。

根と呼ばれる頂点が一つだけ存在し、有向辺は入りません。
他の頂点は必ず一本の有向辺が入ります。
全ての頂点に、根からただ一つの道が存在します。

根付有向木で接続している二つの頂点に対して、辺が出る頂点を親、辺が入る頂点を子と言います。出次数が 0 (入次数が 1)の頂点を葉と言います。根付有向木において、出る辺の数が高々 2 本の木を二分木、二進木、binary tree と言います。

演習6-1

頂点が 4 つの二分木は何種類あるか? 実際に作図して求めなさい。

二分木において、葉にだけ値を割り当てたものを考えます。中間の頂点を . とし丸括弧でくくると次のような式で表すことができます。これをS 式と呼びます。

((a . b) . (c . d))

S 式を表す二分木において、さらに右側の枝に接続する葉に nil が割り当てられたものをリストと呼びます。 nil とはなにもないことを示す値のことなので、 $nil$ を $()$ と書くことがあります。このリストはプログラムで処理する時に番兵として使用します。一方、 $(X . (Y))$ を省略して $(X, Y)$ と表現します。

以下に例を示します。

$\begin{matrix} (a . nil) & \to & (a . ()) \\ \to & (a) \end{matrix}$
$\begin{matrix} (a . (b . nil)) & \to & (a . (b . ())) \\ \to & (a . (b)) \\ \to & (a, b) \end{matrix}$
$\begin{matrix} ((a . nil) . (b . nil)) & \to & ((a) . (b)) \\ \to & ((a), b) \end{matrix}$
$\begin{matrix} ((a . nil) . ((b . nil) . nil) & \to & ((a) . ((b) . ())) \\ \to & ((a) . ((b))) \\ \to & ((a), (b)) \end{matrix}$

ここでさらに左側の枝には必ず葉が接続するリストに限定して考えると次のような構造になります。これを線形リストと呼びます。

なお、プログラミング言語 LISP, Prolog, Logo はリスト構造を扱え、演算が可能です。 v

演習6-2

次のリストを木で図示しなさい。

$(+, 1, 2)$
$(+, 1, (*, 2, 3))$
$(+, (*, 1, 2), (*, 3, 4))$

リスト構造は式を表せるだけでなく、構造体なども表せます。例えば、次の構造体の場合 (point (x double) (y double)) のように表せます。


struct point {
  double x;
  double y;
};

参考

すべての頂点の次数が 2 の連結グラフはリングになります。

また、すべての頂点間に辺がある無向グラフを完全グラフと言います。

演習6-3

頂点数が n の完全グラフの辺の数を求めなさい。

頂点が二つのグループに分割でき、同じグループ同士には辺がないグラフを二部グラフと言います。特に、異なるグループのすべての頂点の組み合わせに辺がある無向二部グラフを完全二部グラフと言います。

演習6-4

頂点数が n, m の完全二部グラフの辺の数を求めなさい。

6-2. グラフの表現

コンピュータで情報処理をする際、情報をグラフの形で抽象化して処理することがしばしばあります。そこで、コンピュータでグラフを表現するしかたを考えます。

文字列

プログラムへの入出力のために、単純に文字列としてのやりとりを考えます。そのため数学的に基本的な記述を考えます。

まず、集合の演算である直積を導入します。集合 A の要素と集合 B の要素のすべての組にしたものを新たな要素とした集合を A と B の直積と言い、 A × B と書きます。数学の記号で書くと次のようになります。

A ⨯ B = {(a, b) | a \in A, b \in B}

さて、まず、グラフの頂点にはすべて名前が付けられているとします。頂点の名前の集合を V とします。すると、辺は二つの頂点の組み合わせで表せますので、辺の集合を E とすると、頂点の集合と頂点の集合の直積の部分集合になります。 $E \subseteq V ⨯ V$ なお、有向グラフでは辺は (出発点,終着点) で表すことにします。

グラフは頂点と辺からなりますので、頂点の集合の要素と辺の集合の要素をそれぞれ列挙すればグラフを表現できることになります。下のグラフを要素の列挙で表現すると次のようになります。

V = {a, b, c, d}, E = {(a, c), (b, a), (b, c), (c, b), (d, c)}

演習6-5

頂点数が n の有向グラフでは最大でいくつの要素を列挙する必要があるか求めなさい。

行列

頂点の数が n 個の時、n × n の正方行列を考えます。もし、 i 番目の頂点から j 番目の頂点へ辺がある場合 (i,j) 成分を 1 に、なければ (i,j) 成分を 0 にしたものはグラフの構造を表すことができます。このような行列を隣接行列と言います。なお、無向グラフで i と j に辺がある場合、 (i,j) 成分と (j,i) 成分をともに 1 にします。

演習6-6

次のグラフの隣接行列を求めなさい。

ポインタ

頂点を構造体とし、辺をポインタで表す方法でもグラフを表現できます。構造体の中には、頂点の名前と、接続する頂点へのポインタの列を含めます。もし、各頂点の出次数が制限されていれば構造体の中はポインタの配列になります。例えば出次数が 2 であれば次のような定義になります。


struct vertex {
  char *name;
  struct vertex *edge[2];
};

しかし、出次数に制限がなければ辺を表す頂点へのポインタを値として持つ線形リストへのポインタになります。


struct edgelist {
  struct vertex * edge;
  struct edgelist *next;
};
struct vertex {
  char *name;
  struct edgelist *edges;
};

6-3. 計算量

プログラムの実行時間を評価することを考えます。コンピュータの性能は個々に違い、また入力によってもプログラムの動きは変わるので、特定の条件での実時間の計測にはあまり意味はありません。計算量理論では、プログラムの実行時間の評価をするため、次のようなアプローチをしています。

コンピュータの実行時間を考えるため、まず、数学的に確立したコンピュータのモデルとして Turing 機械を考えます。これは、外部記憶装置として、マス目のついた無限長のテープを考え、そのテープにひとマス書き込み、隣のマスをアクセスする時間を一単位時間と計測します。

この Turing 機械は通常の計算機と比較して、計算が可能かどうかの能力差はなく、実行時間のステップ数も二乗程度で収まることが知られています。この Turing 機械は数学的なモデルなので、定理の証明に使うことができます。そして、プログラムの実行時間に関わるいくつかの定理が知られています。

定理

一つの関数を計算するプログラムは無限に存在する

定理(線形加速定理)

実行時間が t のプログラムが存在する時、それを c 倍速く計算する別のプログラムが存在する。

また、特定の入力に対してはあらかじめ答を覚えておき、プログラムの実行時に入力が特定の値かどうか調べて、もしそうならその答を出すような改造をすることができます。以上のことにより、プログラムの計算時間は単純な数値や関数では表せないことが分かります。

そこで計算時間は通常オーダーという尺度で計られます。オーダーとは関数の増え方を大雑把に捉える方法です。端的に言えば、実行時間を入力の長さの関数として表した時、最大次数の項について係数を無視したものを尺度として使うと言うものです。例えば、実行時間が入力の長さ n に対して、 $35 n^{3} + 4 n^{2} + 104 n + 2305$ だった場合、最大次数は 3 でその係数を無視して $O (n^{3})$ で表します。このようにすると、定数倍速いプログラムや、一部の入力について速いプログラムも同じオーダーになりますので、プログラムの速さを適切に表現できたことになります。因みにオーダーの数学的な定義は次のようになります。

オーダーの定義

関数 $T_{1} (n)$ 、 $T_{2} (n)$ が $T_{1} (n) = O (T_{2} (n))$ であるとは次を満たすことを言う。ある定数 $N_{0}$ が存在し、すべての $N > N_{0}$ に対して $T_{1} (N) < c T_{2} (N)$ が成り立つような定数 c を見つけられることである。

演習6-7

次のプログラムの実行時間を評価しなさい。但し、数値の代入、計算などは、取り扱っている数値の最大の値を n とすると $O (log n)$ だと評価しなさい。

```
int double(int x){
  return x*x;
}
```


int factor(int x){
  int i,f;
  f=1;
  for(i=2; i<=x; i++){
    f*=i;
  }
  return f;
}

6-4. java のおまけ

Java の SDK(Software Development Kit) に、グラフを表示するデモアプレットがあります。次のようにすると表示されます。


cd (Java SDK のインストールしているディレクトリ)demo/applets/GraphLayout
appletviewer example1.html

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 6 回 アルゴリズムに関する数学