グラフ理論入門

Mona

2021.06.07

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、ドイツのモナでございます〜

いろんなサイエンスにおいてグラフ理論がとても重要な用具となっていますが、グラフ理論ってそもそも何なのかご存知ない方も少なくもないですね。

ということで、今日は簡単にグラフ理論の基本や用語など紹介したいと思います！なお、入門のため誰にでも分かるように数学的な定義は避けるようにします。

また、グラフ理論の応用は別の話ですので今回は応用の話しません〜

なぜグラフが面白いのか

具体的な応用の話はしませんが、たくさんの分野においてグラフ理論が重要となっています。

ネットワーク（例：トポロジー、ルーティングアルゴリズム）
AI（例：ニューラルネットワーク）
コンピューターサイエンス（例：ファイルシステム）
社会科学（例：ソーシャルネットワーク分析）
皆さんの生活の中（例：カーナビの最短ルートの計算）

グラフ理論とは？

ここで議論するグラフというのは、よく思い浮かぶような以下みたいなグラフのことではありません！

Wikipediaより

グラフ理論のグラフとは、ノードとエッジからできている構成です。はじめに、これらについて説明します。

ノードとエッジ

グラフ理論におけるノードとは、ドットや丸で表すものです。ノード間の接続はエッジと呼ばれる線の役割です。一つのエッジに必ず両側にノードが存在しないとなりません。つまり、正しいグラフの実例は以下です。

その一方、定義外となるグラフは例えば以下のようなものです。

エッジに必ず元と先が必要なのですが、これらが同一のノードであっても問題ありません。その場合のエッジは、ループと呼ばれます。

有向グラフと無向グラフ

なお、上記に矢印のような形しているエッジと単純な線のような形しているエッジがありますが、それは有向グラフ(directed graph)と無向グラフ(undirected graph)の２種類があります（ミックスも可能ですが今回は無視します）。有向グラフに全てのエッジに向きがあり、元と先がはっきりとなっています。イメージ的に一方通行だと考えればいいでしょう。無向グラフには、向きがなく、一つのエッジと繋がっているノードが両方元にも先にもなっています。

ループは有向グラフにも無向グラフにも対応されますが、無向グラフに使われないことが多いです。定義によって対応されないこともあります。

とあるノードに接合しているエッジの数を次数(degree)といいます。なお、有向グラフの場合はとあるノード「入る」エッジの数は入次数(indegree)といい、「出る」エッジを出次数(outdegree)といいます。下記にまず有向グラフの実例があります。各ノードに「入次数、出次数」と書いてあります。

ここで気になるノードありますね！入次数も出次数も０となっていて、他のノードから少し離れているように見えるノードのことです。下記にもう少し詳しく載せますが、こういったグラフは非連結グラフ(disconnected graph)といいます。つまり、二つの別々になっているグラフではなく、非連結でもまだ一つだけのグラフです。

なお、上記の有向グラフを無向グラフに変形すると、以下のグラフになります。見比べするとまた面白いこと二つありますね。まず、入次数と出次数の区別がなくなり、単純な次数に変わります。また、赤いエッジのところが一つだけのエッジになっていますね。それは、定義によって異なったりしますが、有向グラフ→無向グラフの変換で元と先が同一のエッジを統括することが多いです（私感）。逆に、無向グラフ→有向グラフに変換する場合は、格エッジを二つの有向エッジに変えます。（例；(A)--(B)が(A)->(B)、(B->(A)になります）

多重グラフと単純グラフ

ここまで見てきたグラフは全て単純グラフ(simple graph)の定義に入ります。単純グラフとは、二つのノード間にエッジがあるとすれば一つだけとのことです（有向グラフの場合は方向毎に一つだけ）。でも実は、ノード間に複数のエッジが存在することができます。そのようなグラフは多重グラフ(multigraph)といいます。シンプルな例は以下にあります。

単純グラフも多重グラフもそれぞれユースケースがありますが、今回は定義だけに絞っておきます。

連結性

上記の次数が入っているグラフを見ると、もっとも左側にあるノードから全くエッジがないですね。つまり、他のノードから連結がないと言えますね。実はグラフ理論においては、グラフの連結性(connectivity)がかなり大事な概念です。

ここでまず経路の話をしたいと思います！

とあるグラフの任意のノードから、エッジ沿いに他のノードに着くことができれば、その二つのノード間に経路(path)があります。有向グラフの場合は、(A) -> (B)への経路があるとしても、(B) -> (A)への経路がないかもしれません。つまり、有向グラフの場合は、とあるノード間に一方的な経路しかない可能性があります。さて、例を見てみましょう。

ノード「２」から、「４」経由で「７」まで有向エッジがあるため「２」と「７」の間に経路があります。その一方で、「７」から頑張っても有向エッジを沿って「２」に着くことができないので「７」と「２」の間に経路がないということです。

無向グラフの場合は、(A)--(B)の経路があれば、(B)--(A)の経路も必ず存在します。

ここご覧の通り、「２」から「７」までの経路があるだけなく、「７」から「２」までの経路もあります。

なお、連結性に戻ると、とある（無向）グラフにおいて全てのノード間に少なくとも一つの経路があれば、そのグラフは連結グラフ(connected graph)といいます。有向グラフの場合は、そのグラフの無向バージョンが連結グラフであれば、元の有向バージョンも連結グラフとなります。例えば上記の例で言うと、「１」のノードから他のノードまでの経路が一つもないので、非連結グラフ(disconnected graph)です。他の言い方で言うと、連結グラフは一つだけの連結成分(component)からできている一方で、非連結グラフは複数の連結成分の構成になっています。

特別なグラフ

グラフ理論においてとある特徴が揃っている様々な特別なグラフが存在します。ただし、入門の範囲には入らないと思いますので、興味のある方は以下のキーワードで調べていただければいろいろ出てくるはずです。

ツリー (Tree)
有向非巡回グラフ (Directed acyclic graph)
閉路グラフ (Cycle graph)
２部グラフ (Bipartite)
平面グラフ (Planar graph)
完全グラフ (Complete graph)
etc.

なお、特別グラフの1種類だけ紹介したいと思います（簡単ですので！）。

完全グラフ

とあるグラフの全てのノード間にエッジがあるグラフを完全グラフ(complete graph)といいます。完全グラフの特徴の一つとして、ノードの数がnだとすると、各ノードの次数（上述のノードから出ているエッジの数）がn - 1です。例えば、４つのノードのある完全グラフの各ノードの次数は３です。なぜなら、各ノードが自分を除いて他の全てのノードにエッジがあるからです、つまりノードの数マイナス１。nが５までの完全グラフが以下にあります。