14.8. モデル化とグラフ

コンピュータで扱う情報は、画像(文字を含む)音といった人の五感と対応するものだけでなく、抽象的な内容もあります。グラフも符号化できるので、電車の路線図、化学反応の行程、自律動作の規則などをグラフで表現すると、コンピュータで扱えるようになります。

グラフ #

グラフは、接続関係を表すモデルです。頂点 (ノード) と辺 (エッジ、アーク) の集合で定義されます。頂点は、図では丸や長方形で表記します。辺は頂点二つのペアで、向きを持つ場合は矢印で、持たない場合は線で頂点同士をつないで図示します。通常は、位置関係は無視して考えます。

たとえば、鉄道を (経営や路線を無視すると)、駅をノードで、隣接する駅を辺として、グラフで表現することができます。

グラフは、行列で表現することができます。下のグラフは、頂点に整数で番号をつけ、r行c列の行列について成分が1のとき rからcへの辺があるという規則で表現しました。これを隣接行列と言います。この例では行列の要素について、01で辺の有無を表現しましたが、辺の情報 (番号、コスト、遷移確率など) を表現することもできもあります。

stateDiagram-v2
    direction LR
    state "1" as s1
    state "2" as s2
    state "3" as s3
    state "4" as s4
	s1 --> s2
	s2 --> s3
	s3 --> s4
	s4 --> s2
	s4 --> s3

\( \begin{pmatrix}0& \underbrace{1}_{1\to 2} &0 &0 \\ 0& 0 &\underbrace{1}_{2\to 3} &0 \\ 0 &0 &0 &\underbrace{1}_{3\to 4} \\ 0 &\underbrace{1}_{4\to 2} &\underbrace{1}_{4\to 3} &0\end{pmatrix} \)

隣接行列の冪乗

隣接行列を2乗すると、その各要素は、非ゼロなら rからcにちょうど2歩で行けるという意味になります。n乗ならn歩です。

木 #

一つの頂点から、枝分かれしてゆくタイプのグラフを木と言います。厳密には、連結でサイクルを持たないグラフと定義します。特に辺が向きを持つ木で、すべての出発点を根 (root)、辺で接続する頂点ペアについて、根に近い方を親、遠い方を子、子を持たない頂点を葉 (leaf) と言います。

ファイルシステムの階層構造や2進符号が木に対応することを、これまで紹介してきました。通常根を上に書くことが多いですが、回転させても意味は同じです。

stateDiagram-v2
    state "?" as s0
    state "?" as s1
    state "出席" as s00
    state "欠席" as s01
    state "遅刻" as s10
    state "早退" as s11
	[*] --> s0 : 0
	[*] --> s1 : 1
	s0 --> s00 : 0
	s0 --> s01 : 1
	s1 --> s10 : 0
	s1 --> s11 : 1

stateDiagram-v2
    direction LR
    state "?" as s0
    state "?" as s1
    state "出席" as s00
    state "欠席" as s01
    state "遅刻" as s10
    state "早退" as s11
	[*] --> s0 : 0
	[*] --> s1 : 1
	s0 --> s00 : 0
	s0 --> s01 : 1
	s1 --> s10 : 0
	s1 --> s11 : 1

森

木の集まりを森といいます。

オートマトン #

自立的な動作の表現に、グラフを用いることもできます。

右図は `a` または `b` で構成される文字列を読み、開始から今までに `aba` の並びがあったかどうかを判定するオートマトンの設計をグラフで示したものです。`Start` のノードで開始し、`a` または `b` の文字を読むたびに、対応するラベルを持つ矢印に従って次のノードに移動します。 `aba` を読むと `OK` のノードに移動していて、その後は何を読んでも、そのノードに留まります。これにより、1度でも `aba` を読んだか、を現在のノードにより判定することができます。(先頭ではなく途中で `aba` をよんだとしても `OK` のノードに到達していることを確認しましょう)

stateDiagram-v2
    state "start" as s0
    state "?" as sa
    state "?" as sab
    state "OK" as saba
	s0 --> sa : a
	s0 --> s0 : b
	sa --> sa : a
	sa --> sab : b
	sab --> saba : a
	sab --> s0 : b
	saba --> saba : a, b

「情報」の授業では、オートマトンについての演習も用意されています。

オートマトンシミュレータによる計算モデルの理解