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

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

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