グラフ理論におけるグラフとは、関数やデータを表現する際に用いるグラフのことではなく、点とそれらをつなぐ線で構成される数学的な構造のことを指します。 Lesson 11 ではグラフに関する基本的な用語やグラフの種類をいくつか説明していきます。

グラフの例

その前に、このグラフがどのような分野で用いられるのかについて説明します。 グラフ理論は、数学や計算機科学、物理学、経済学、社会科学、通信工学など、多岐にわたる分野で応用されています。

例えば、ネットワークの構造と特性の解析の際に使われています。 これにはソーシャルネットワークの分析、航空路線ネットワークの設計、インターネットのルーティングなどが含まれ、 ニューラルネットワークもよくグラフの言葉を用いて説明されます。

またグラフ理論は、最適化問題を解決するためにも利用されています。 巡回セールスマン問題、最小全域木問題、最短経路問題などが具体例です。

グラフ理論にはこの他多くの応用例があります。 よってグラフについての基礎的な知識を身に着けておくことは、深層学習だけでなくこれからさまざまなことを学ぶのに非常に役立つでしょう。

ここではグラフに関する用語をいくつか説明します。

グラフにおける点は、頂点やノードと呼ばれることが多いです。 また線は辺やエッジなどと呼ばれます。 グラフには、いくつかの頂点$v$と辺$e$が存在して、すべての辺は両端に頂点を持ちます。 グラフは頂点の集合$V$と辺の集合$E$で定義されるものということができます。 Chapter1のグラフの例では、頂点は9個、辺は10本あるので、$|V|=9$、$|E|=10$となります。 グラフの見た目が違ったとしても、頂点集合$V$と辺集合$E$が一致していれば同じグラフとみなされます。

これらは見た目上異なるが、同一のグラフである

頂点につながっている辺は何本あっても構いません（0本でもよい）。ある頂点につながっている辺の数をその頂点の次数といって、 頂点$v$の次数を$d(v)$と書きます。 例えばChapter1のグラフの例の図においては、頂点1の次数は1、頂点4の次数は3、などとなり、$d(1)=1$、$d(4)=3$と書きます。

これ以降いくつかのグラフの種類を紹介していきますが、頂点や辺、次数といった用語は頻繁に出てくるので、 これらの用語の意味をしっかり理解しておきましょう。

グラフ中のある2つの頂点について、それらを結ぶ辺が複数ある時、それらを多重辺といいます。 また、ある1つの辺が結ぶ2つの頂点が同一のものであるとき、その辺をループあるいは自己閉路といいます。

多重辺の例 ループの例

グラフに多重辺またはループが1つ以上含まれていないグラフを多重グラフと呼びます。 そうでないグラフ、つまり多重辺もループも一切含まれていないようなグラフを単純グラフといいます。 Chapter1のグラフの例は、多重辺やループが含まれていないので単純グラフということになります。

完全グラフとは、任意の2頂点間に辺があるような単純グラフ（Chapter3）のことです。 $|V|=n$となるような完全グラフのことをよく$K_n$と書きます。 以下は$K_n$をいくつか並べたものになります。

左から順に、$K_2$、$K_3$、$K_5$

完全グラフ$K_n$の辺の数$|E|$を求めてみましょう。 完全グラフではどの頂点の間にも1本の辺があることから、$n$個の頂点からちょうど2個の頂点を選ぶ場合の数を考えればよく、 \[ |E| = {}_nC_2 = \dfrac{1}{2}n(n-1) \] となります。よってオーダー（Lesson 12 参照）としては$O(n^2)$になります。 完全グラフは頂点の数を固定した単純グラフの中では辺の数が最大になるので、単純グラフの辺の数は多くても$O(n^2)$で見積もれることがわかります。

各辺に重み（コスト）が定義されているようなグラフを重み付きグラフといいます。 重みは一般には実数値をとります（負の値をとっても構いません）。 以下は重み付きグラフの例です。

重み付きグラフの例

この重みの意味は、どんな分野でグラフを使うかによりますが、例えば各頂点を町、各辺をそれらを結ぶ道としてみなしたグラフでは、 辺のコストはその道を使うときの所要時間として考えることができます。

またパーセプトロンおよび（全結合型）ニューラルネットワークは重み付きグラフとして表現することができ、 それぞれの重みは各パラメータに対する係数を表すことになります。

有向グラフとは、各辺に向きがあるようなグラフのことです。 向き付きの辺のことを有向グラフといいます。 以下は有向グラフの例です。

有向グラフの例

有向グラフにおける次数は、その頂点に入ってくる辺の本数とその頂点から出ていく辺の本数を区別してそれぞれ入次数、出次数ということがあります。 上の例では、例えば頂点4の入次数は2、出次数は1になります。

有向グラフは、経路の問題でいえば一方通行の道路を表すのに使うことがあります。 両方向の通行が可能なときはそれぞれの方向の矢印を書くのが一般的です（上の図の頂点2・3、および頂点7・8参照）。 また重み付きの有向グラフを考えることもあり、このときは両方向の矢印それぞれに重みが付きます。これらの重みは異なっても構いません。

ここまでグラフ理論に関する基礎的な知識を学んできました。機械学習や深層学習を学ぶ上ではこの程度の知識で問題ありませんが、 グラフ理論はそれ単体で非常に奥深いものなので、興味があればもっと調べてみると良いでしょう。