解説 7月5日A

今日の学習項目です。


グラフ

教科書59ページから61ページまで読んでおいてください。

これまで「木」を学んできました。実は「木」は「グラフ」の一種でした。 今回はグラフとその表現方法を学びます。

グラフ(graph) G は、頂点(vertex)の集合Vと辺(edge)の集合Eのペアとして定義されます。そして、これを G = (V, E)のように表します。

ここで、頂点の集合V={v1, v2, …, vn}は有限集合で、 辺の集合Eは、Vの2つの要素からなる集合(つまり、大きさ2のVの部分集合)の集合です。例えば { {v1, v2}, {v2, v3} } は辺の集合を表しています。

この方法によれば、教科書図6.1のグラフは(どちらも)、 V = {v1, v2, v3, v4}, E = {{v1,v2}, {v2,v3}, {v1, v3}, {v3,v4}} によって表されます。 [要素の順番が気になる人に]

今、V = {v1, v2, v3, v4}のように(Eも同じ)特定の順番で要素を書きました。 そこでV = {v4, v3, v2, v1}と書いた場合と違いが気になる人がいるかもしれません。。。実際には、この二つは同じものです。これは「集合」を表しています。 そして集合の場合は、要素の順番(や要素の重複でさえも)は無視されます。 ですからどのような順番で要素を書いたとしても、それは同じ集合とみなされるのでした。

この方式によってグラフを表現できなくはないですが、もう一つの表現方法をここで紹介します。それは「隣接頂点関数T」を用いる方法です。 隣接頂点関数Tは頂点を引数にとります(仮にその頂点をvとします)。そして、その頂点に隣接している頂点の集合を返すものです。 ここで「隣接している」頂点とは、教科書p.60の2行目からの説明にあるように、枝によって頂点vと結ばれている頂点(すべて)のことです。たとえば、図6.1のグラフでは T(v1)={v2, v3}となります。

課題1-1

図6.1のグラフにおいて、T(v2), T(v3), T(v4)の値をそれぞれ書きなさい。

課題1-2

以下に挙げるEと隣接頂点関数Tによって定まるグラフはどのようなものか、図示しなさい。
E = {v1, v2, v3, v4, v5}, T(v1) ={v2, v3}, T(v2) ={v1, v4}, T(v3) ={v1, v5}, T(v4) ={v2}, T(v5)={v3}

グラフの探索

教科書の6.2節を読んでおいてください。 これについては次回扱います。

「アルゴリズムとデータ構造」のホームに戻る