グラフ理論の基礎 — 頂点・辺・基本概念

グラフ理論は、頂点と辺からなる構造であるグラフを研究する分野です。頂点は対象を表し、辺は2つの対象の関係を表します。

グラフ理論の基礎を知りたいなら、まずこの考え方から始めましょう。グラフは、つながりをすっきり表現する方法です。SNS上の人間関係、道路で結ばれた都市、相互にリンクされたWebページは、どれもグラフで表せます。

数学でグラフとは何を意味するか

無向グラフでは、辺は2つの頂点がつながっていることを表し、そのつながりに向きはありません。$A$ が $B$ と結ばれていれば、$B$ も $A$ と結ばれています。

有向グラフでは、辺には向きがあります。そのため、$A \to B$ と $B \to A$ は別の意味になります。初学者向けの例では、単純無向グラフを使うことが多く、これはループがなく、同じ2頂点の間に重複する辺もないことを意味します。

この条件は重要です。というのも、多くの定義はまず単純無向グラフで導入されるからです。グラフの種類が変わると、用語の意味も変わることがあります。

最初に知っておきたいグラフ理論の基本用語

頂点と辺

頂点は、追跡したい対象そのものです。辺は、追跡したい対象どうしのつながりです。

都市と道路を表すグラフなら、都市が頂点で、道路が辺です。

次数

無向グラフでは、頂点の次数とは、その頂点に接している辺の本数です。

ある都市がほかの3つの都市と道路でつながっていれば、その次数は $3$ です。

道

道とは、隣り合う頂点の各組が辺で結ばれているような頂点の列です。

ある頂点から別の頂点への道があれば、辺をたどって一方から他方へ移動できます。

閉路

閉路とは、同じ頂点から始まり同じ頂点で終わる道です。基本的な定義では、それ以外の頂点は繰り返しません。

閉路があるということは、グラフの中に閉じたループがあるということです。

連結グラフと連結成分

無向グラフが連結であるとは、どの頂点からどの頂点へも、何らかの道で到達できることをいいます。

それが成り立たないとき、グラフはいくつかの連結成分に分かれます。各成分は、グラフの中で連結になっている部分です。

例題：小さなグラフを1つ見てみよう

頂点 $A$, $B$, $C$, $D$, $E$ をもち、辺が

$$AB,\ AC,\ BC,\ CD$$

であるグラフを考えます。

これは $A$, $B$, $C$ の間に三角形があり、さらに $C$ から $D$ への辺が1本あり、$E$ は孤立頂点になっていることを意味します。

この例を見ると、主要な考え方がすぐに確認できます。

各頂点の次数は

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

です。

$A$ から $D$ への道があります：

$$A-C-D$$

閉路もあります：

$$A-B-C-A$$

このグラフは連結ではありません。なぜなら、$E$ にはほかの頂点から到達できないからです。したがって、このグラフには2つの連結成分があります。1つは $A,B,C,D$ を含む成分、もう1つは $E$ だけを含む成分です。

この1つの例だけで、次数、道、閉路、孤立頂点、連結成分がどのように関係しているかがわかります。

すばやく確認：次数の総和

任意の有限無向グラフについて、

$$\sum \deg(v) = 2|E|$$

が成り立ちます。

これは、どの辺もちょうど2つの端点に接しているため、各辺が2つの次数にそれぞれ $1$ ずつ加えるからです。

上の例では、次数の総和は

$$2+2+3+1+0=8$$

です。

辺の本数は $4$ 本なので、

$$2|E| = 2 \cdot 4 = 8$$

となります。

これは、手で次数を数えるときの便利な確認方法です。数が一致しなければ、どこかで数え間違いがあります。

グラフ理論でよくある間違い

頂点と辺を取り違える

頂点は対象です。辺は対象どうしの関係です。

どの種類のグラフかを忘れる

単純無向グラフで正しいことでも、有向グラフやループを許すグラフでは修正が必要な場合があります。

道と閉路を同じように扱う

道は、出発点に戻る必要はありません。閉路は戻ります。

孤立頂点を無視する

次数が $0$ の頂点も、グラフの一部です。それによってグラフが連結かどうかが変わることがあります。

グラフ理論の基礎はどこで使われるか

これらの考え方は、コンピュータネットワーク、経路計画、スケジューリング、推薦システム、SNSなどに現れます。文脈は変わっても、問われることはよく似ています。何がつながっているのか、どこまで到達できるのか、どこにループがあるのか、という点です。

そのため、グラフ理論は離散数学でも計算機科学でも早い段階で登場します。

似たグラフで試してみよう

4つの頂点 $P$, $Q$, $R$, $S$ を描いてください。辺 $PQ$, $QR$, $RS$, $SP$ を加えます。

そして次の3つの問いに答えてみましょう。各頂点の次数はいくつか、グラフは連結か、そして閉路を含むか。