このチュートリアルでは、ラベル付き有向グラフの描き方と、より早くグラフを作成する方法について説明します。
目次
ラベル付き有向グラフを作る
このチュートリアルでは以下のようなグラフを作ります。
このグラフはチュートリアル(1)のグラフとはいくつかの点で異なっています。具体的にその違いを挙げると、以下のようになります。
- 辺に矢印が付いている
- 辺に文字が付いている
- 初期状態とよばれる頂点がある
- 受理状態とよばれる頂点がある
- 始まりと終わりが同じ頂点になっている辺がある
1,2の特徴を持ったグラフを「ラベル付き有向グラフ」と言います。また、3,4は有限オートマトンと呼ばれるものを表す際に使われます。チュートリアルではこれらの数学的な意味には触れず、どのようにグラフを描くかについてだけ説明します。
作成モードと操作モード
具体的な作り方に入る前にSimpleGraphが持つ2つのモードについて説明します。SimpleGraphにはグラフを作成するためのモード（作成モード）と、それを操作するためのモード（操作モード）があります。チュートリアル(1)では後者のモードでグラフを作成しました。どちらのモードであってもグラフを作れますが、慣れれば前者の方がより早くグラフを作成できます。
2つのモードの切り替えは簡単で、グラフエリアのdrawingというチェックボックスをオンにすれば作成モードになり、オフにすれば操作モードになります。SimpleGraphを起動した状態では操作モードになっています。
それではdrawingのチェックボックスをオンにして作成モードに切り替えてみましょう。操作モードでは頂点を作成するのに右クリックでメニューを表示させて、add vertexを選ぶ必要がありましたが、作成モードではグラフエリア上でクリックした場所に頂点が作られます。グリッドをオンにして、下のように5カ所をクリックし、5つの頂点を作成してみてください。
作成モードでは頂点を（左）クリックするとメニューが表示されるので、label…を選んで頂点ラベルも設定してください。（※操作モードでは右クリックでメニューが現れます）
慣れないうちは余計な場所をクリックして無駄な頂点を増やしてしまうでしょう。頂点を削除するには、単に頂点の上でクリックして現れたメニューでdeleteを選んでください。
向きのある辺（弧）を作る
次に向きのある辺を作ります。一般的に向きのある辺のことを「弧」と呼びますので、これ以降は「弧」と表現します。弧を作るには2通りの方法があります。向きのない辺に対して後から向きを設定する方法と、最初から弧を作る方法です。
前者の場合、作成モードの場合は辺をクリックして（操作モードの場合は右クリック）メニューを表示させ、toggle arrowを選びます。そうすると、クリックした場所に近い方の端に矢印がつきます。
例題のように最初から有向グラフを作るとわかっている場合には、後者の方法を使う方が便利です。グラフエリアのdirectedチェックボックスをオンにすると、弧を作れるようになります。directedチェックボックスをオンにしましょう。
弧を作るには、矢印の根元にあたる頂点でCtrl（あるいはControl）キーを押しながらマウスを押したままに（つまりドラッグ）すると弧が現れます。そのまま矢印の先にあたる頂点でマウスボタンを離すとその頂点までの弧ができます。このやり方は弧（もちろん辺も）を作成する時間を大幅に短縮できますので、ぜひマスターしてください。
では、以下のように弧を作成してみてください。
ループを作る
ループとは始まりと終わりが同一の頂点であるような辺や弧のことです。
辺や弧を作る際、最初にクリックした頂点でマウスボタンを離せばループが作られます。なお、頂点のどの位置にループが作られるかは、マウスを離したときのハンドルの位置によって決まります。
以下を参考にして4つのループを作成してください。
辺を直線から曲線に変える
例題のグラフではq3からq1の頂点へ延びる弧がありますが、今までの方法で弧を作ると以下のように新しく作った弧が他の弧や頂点と重なってしまいます。
そこで、新しく作った弧が重ならないように曲線にします。曲線にするためには、弧の中央にある黄色いハンドルを掴んで動かします。ハンドルを中央から遠ざけるほど曲線の曲がり方が増します。下の図を見て適切な位置まで調整してください。
辺にラベルを設定する
チュートリアル(1)では頂点に文字を設定しました。頂点や辺に付けられた文字や数値のことを「ラベル」と言います。頂点にラベルを設定するのと同様に、辺や弧にもラベルを設定することができます。違いは2種類のラベルを表示させることができる点です。
上のグラフの弧には、aとxの2つのラベルが設定されていますが、xは枠で囲まれて弧の中央にあり、aに枠はなく頂点寄りにあります。SimpleGraphではxをラベル（label）、aを入力ラベル（input label）と呼んで区別しています。
今のところ、見た目上の違いしかありませんが、このグラフを有限オートマトンや有限状態機械として用いる際には大きな役割を果たします。例題を見ると入力ラベルとして設定されているので、そのようにしましょう。
それでは、弧をクリック（操作モードなら右クリック）してメニューを表示させ、input label…を選んで入力ラベルを設定してください。
初期状態と受理状態を設定する
例題の頂点のうち、q0とq4は他と若干異なる外観をしています。q0には左側に短い矢印が付いており、q4は二重の円で囲まれています。前者はq0がこのグラフの初期状態であることを、後者はq4が受理状態であることを示しています。初期状態も受理状態も有限オートマトンや有限状態機械に関係するものですが、ここでは詳細な意味には触れずに、その特徴だけを述べます。
初期状態はグラフの頂点のうち１つだけに設定することができます。つまりある頂点が初期状態であれば、その他の頂点は初期状態ではないということです。他方、受理状態はどの頂点にも設定することができます。
SimpleGraphでは、どちらも頂点をクリック（操作モードなら右クリック）して現れるメニューで設定できます。初期状態はset as initialで設定し、他の頂点が初期状態になれば自動的に解除されます。頂点の初期状態を解除するときは再度set as initialを設定します。受理状態はtoggle acceptableで設定と解除を行うことができます。初期状態と違ってある頂点を受理状態に設定しても、他の頂点が受理状態を解除されるということはありません。
それではq0を初期状態に、またq4を受理状態に設定し、例題のグラフを完成させてください。
以上でこのチュートリアルは終わりです。