はじめに

今回から数回に渡って、離散数学の中心的な分野である「グラフ理論」について、個人的にまとめていこうと思う。

なお、当ブログでは競技プログラミングの話題が中心ということもあり、理論について詳しく扱うというよりはむしろ、プログラミングにおけるグラフ理論の扱い (各アルゴリズムの C++ による実装など) を中心に書いていこうと考えている。投稿ペースは不定期になると予想されるので悪しからず。

さて、初回となる今回は、「グラフ理論で扱う『グラフ』とは何か」「グラフ理論の基本用語」などを中心に扱う。この回はかなり辞書的な内容になると思うので、退屈に感じたらとりあえず先へ進んで必要に応じて戻ってくる、という流れでも構わない。

「グラフ」とは何か？

高校数学までは、「グラフ」といったら関数を座標平面(空間)上にプロットしたものだったり、たくさんのデータを棒状や円状にまとめたものだったりを指す用語であった。

しかし、グラフ理論における「グラフ」というのは「対象物の関係性を表すもの」である。通常、対象物は丸 (頂点) で表され、対象物間の関係は線あるいは矢印 (辺) で表される。

身近な例で言えば、 SNS 上のアカウントの相互関係や、鉄道路線図が分かりやすいだろう。

札幌市営地下鉄の路線図。駅を頂点、路線を辺と捉えれば、上のグラフと同じに見えないだろうか。

さて、このような丸と丸を線でつないだ関係について考えることには、どのような意味があるのだろうか。

先ほどの例で言えば、 SNS 上のアカウントの相互関係をグラフとしてモデル化して分析することで、どのようなコミュニティが存在するのかや情報がどのように拡散されていくのかといったことが分かる。

また、駅と駅がどのような路線で結ばれているのか、また各駅間の所要時間・運賃をモデル化することで、ある駅からある駅までの最短経路や最安経路を求めることもできるのだ。

このように、世の中の問題をグラフに関する問題として捉えることで、見通しよく考えることができるようになることがある。グラフ理論を学ぶ意義はこのようなところにあると私は思っている。

グラフの定義

それでは、改めて「グラフ」を数学的に定義してみる。

グラフ

頂点 (vertex) の集合を $V = \{v_1, v_2, v_3, \cdots, v_n\}$ 、辺 (edge) の集合を $E = \{e_1, e_2, e_3, \cdots, e_n\}$ とする。グラフ $G$ をこれらの組 (順序対) として定義し、 $G = (V, E)$ と表す。ここで、辺 $e \in E$ は2つの頂点 $v_i, v_j \in V$ の集合として定義され、 $e = \{v_i, v_j\}$ と表す。

また、頂点集合の要素数 (位数) を $|V|$ 、辺集合の要素数を $|E|$ と表す。

グラフ理論の基本用語

続いて、グラフ理論に登場する基本的な用語について紹介する。

頂点の接続

頂点 $v_i, v_j$ が辺 $e$ によって結ばれているとき、「辺 $e$ は頂点 $v_i$ と頂点 $v_j$ に接続している」という。また、このときの $v_i, v_j$ を $e$ の端点という。

頂点の接続には単純な接続の他にも「多重辺」「自己ループ」といったパターンがある。

また、多重辺や自己ループを持つグラフを「多重グラフ」、そうでないグラフを「単純グラフ」という。

辺の重み

各辺に実数値をとる「重み (weight) 」が付随したグラフを考えることもある。このようなグラフを「重み付きグラフ」という。逆にそうでないことを強調するときは「重みなしグラフ」という。

辺に重みを加えることで、最短経路や最小コストの経路を求めたいときに有効になる。

有向グラフと無向グラフ

各辺に「向き」があるグラフを考えることもある。向きがある辺 (有向辺) を1つ以上含むグラフを「有向グラフ」といい、有向辺については矢印で表す。逆にそうでないグラフを「無向グラフ」という。

有向辺は2つの頂点の順序対で表され、 $e = (v_i, v_j)$ のように書く。 $(v_i, v_j) \neq (v_j, v_i)$ であることに注意。

以降、単に「グラフ」と書くときは単純無向グラフを指す。

有向グラフは一方通行の経路を示すときに有効である。

頂点の隣接と次数

頂点 $v_1, v_2$ が辺 $e_1 = \{v_1, v_2\}$ によって接続されているとき、「頂点 $v_1, v_2$ は隣接している」という。また、別の辺 $e_2 = \{v_2, v_3\}$ が存在するとき (2つの辺が1つの端点を共有しているとき) 、「辺 $e_1$ は隣接している」という。

ある頂点について、その頂点に接続している辺の数 (隣接している頂点の数) をその頂点の次数 (degree) といい、グラフ $G$ の頂点 $v$ の次数を $\deg_G(v)$ と書く。

また、多重辺の場合は辺の数だけ次数もカウントされ、自己ループの場合は次数を2回カウントする。

上のグラフ $G$ では、

$\deg_G(a) = 3, \: \deg_G(b) = 3, \: \deg_G(c) = 0, \: \deg_G(d) = 2$

となる。

なお有向グラフでは、ある頂点に向かってくる辺の数を入次数、ある頂点から出ていく辺の数を出次数といい、それぞれ $\deg_G^-(v), \deg_G^+(v)$ と書くことがある。

上のグラフ $G'$ では、例えば

$\deg_{G'}^-(a) = 1, \: \deg_{G'}^+(a) = 2, \: \deg_{G'}^-(b) = 2, \: \deg_{G'}^+(b) = 1$

となる。

部分グラフ・誘導部分グラフ

あるグラフの頂点や辺の一部を取り出してきたグラフを部分グラフという。数学的に定義すると次のようになる。

部分グラフ

グラフ $G = (V, E)$ に対して、 $V' \subset V, E' \subset E$ が作るグラフ $G' = (V', E')$ を $G$ の部分グラフという。

また、あるグラフの頂点の一部を取り出し、それらの頂点に接続する辺は元のグラフと同じであるグラフを誘導部分グラフという。数学的な定義は次の通り。

誘導部分グラフ

グラフ $G = (V, E)$ の部分グラフ $G' = (V', E')$ のうち、任意の頂点 $u, v \in V'$ を端点とする全ての辺 $e = \{u, v\} \in E$ について、 $e \in E'$ となるようなグラフを $G$ の誘導部分グラフという。

ウォーク・トレイル・サーキット・パス

あるグラフ $G = (V, E)$ の部分グラフの一種として他に重要なものには、以下が挙げられる。

ウォーク (walk) : $G$ 上の任意の頂点 $s, t$ について、 $s$ から $t$ へ隣接する頂点をたどりながら到達することができるとき、その経路を「 $s-t$ ウォーク」や「 $s$ から $t$ への歩道」などといい、このときの $s$ を始点、 $t$ を終点という。同じ頂点や辺を通ることも許容される。
トレイル (trail) : ウォーク $P$ に同じ辺が含まれていないとき、その経路をトレイル (小道) という。同じ頂点を通ることは許容される。
サーキット (circuit) : トレイル $P'$ の始点と終点が同じであるとき、その経路をサーキット (回路) という。つまり、同じ辺を2回以上通らずに初めの頂点に戻ってくるような頂点の辿り方のことである。
パス (path) : ウォーク $P$ に同じ頂点が含まれていないとき、その経路をパス (道) という。始点と終点が同じものを特に閉路 (cycle) という。つまり、同じ頂点を2回以上通らずに初めの頂点に戻ってくるような頂点の辿り方のことである。

ただし、これらの語の定義については参考書間で微妙に異なっていることがあるので注意してほしい。このブログでは上の定義に従って書くことにする。

下のグラフを例にとると、

ウォーク :

$a \to b \to e \to h \\ e \to b \to a \to c \to e \to b \to d \to g$

トレイル :

$c \to a \to b \to e \to c \to f$

サイクル :

$a \to c \to b \to e \to a \\ h \to g \to d \to b \to e \to h \to f \to i \to h$

パス :

$a \to b \to e \to h \\ h \to g \to d \to b \to e \to h$

※ここでは分かりやすいよう矢印で繋いでいるが、実際に表記するときはカンマで列挙することが多い。

また、有向グラフ上でもこれらの語は同様に定義され、有向であることを強調するために「有向○○」ということがある。

さらに、これらの語の「長さ」といったときには、重みなしグラフでは単にその経路上の辺の本数を、重みありグラフでは経路上の重みの総和を表す。

グラフの連結性

無向グラフ $G = (V, E)$ の任意の2頂点 $s, t \in V$ に対して $s-t$ パスが存在するとき、 $G$ は連結 (連結グラフ) であるという。連結グラフでないグラフは非連結グラフといい、これはいくつかの連結部分グラフに分割することができる。これらを連結成分という。

上のグラフは非連結グラフだが、各連結部分グラフ (3つの頂点集合 $\{a, b, c, e\}, \{d, g\}, \{f, h, i\}$ からなる3つの部分グラフ) は元のグラフの連結成分に当たる。

有向グラフについても連結性を定義できるが、辺の向きが存在することに注意する必要がある。

任意の2頂点 $s, t \in V$ に対して $s-t$ パスと $t-s$ パスがともに存在するとき強連結であるといい、有向グラフを無向グラフとして捉えたときに連結となるとき弱連結であるという。

上の図で、左のグラフでは $f \to a$ は到達可能だが $a \to f$ は到達不可能である。したがってこのグラフは強連結ではない (弱連結ではある) 。

一方、右の2つのグラフは左のグラフの部分グラフである。これらのグラフはそれぞれ任意の2頂点間を互いに行き来できるので強連結である。このような部分グラフを、元のグラフの強連結成分という。

握手補題

すべてのグラフにおいて、辺の本数と次数との間にはとある関係が成り立つことが知られている。これを握手補題という。

握手補題

任意のグラフ $G = (V, E)$ において、以下の関係が成り立つ。

$\displaystyle \sum_{v \in V} \deg_G(v) = 2|E|$

端的に言ってしまえば、「グラフ上の各頂点の次数の総和は、辺の本数の2倍に等しい」ということである。これは、グラフ上の次数の総和は偶数であるということも示している。

証明は意外と簡単で、数学的帰納法による。

【証明】

グラフ $G = (V, E)$ について、 $n = |E|$ とする。

$(\mathrm{i}) \: n = 1$ のとき

頂点の次数の総和は $2$ であり、 $2 \cdot |E| = 2$ であるから成立。

$(\mathrm{ii}) \: n = k$ のとき

握手補題の成立を仮定すると、 $n = k+1$ のとき (辺を1本追加したとき) 、追加した辺の両端点の次数が1ずつ増加するので、次数の総和は $2 + \displaystyle \sum_{v \in V} \deg_G(v) = 2 + 2|E|$ 。一方、辺の本数は $2 \cdot (|E| + 1) = 2 + 2|E|$ 。したがって、このときも成立。

$(\mathrm{i}), (\mathrm{ii})$ より、数学的帰納法により握手補題が成り立つことが示された。 (証明終)

この補題はグラフ理論における基本定理であり、詳しくは書かないがこれを利用することで他のグラフに関する定理の証明をすることもできる。

グラフを表すデータ構造

さて、ここまで様々なグラフについて見てきたが、これをコンピュータ上で表現するにはどうすればよいのだろう。

コンピュータ上でグラフを表す際に用いられるデータ構造として代表的なのは、隣接行列と隣接リストである。それぞれ簡単に解説する。

隣接行列

※この項では行列の知識を少し必要とする。

隣接行列は隣接している頂点同士の関係を表した行列であり、型は $|V| \times |V|$ の正方行列となる。各成分の定義は次の通り。

隣接行列

無向グラフ $G = (V, E)$ の隣接行列を $A_{G}$ とすると、その $i, j$ 成分 $a_{ij}$ は、

$a_{ij} = \left\{\begin{array}{} 1 & \{v_i, v_j\} \in E \\ 0 & \mathrm{else} \end{array}\right.$

有向グラフ $G' = (V', E')$ の隣接行列を $A_{G'}$ とすると、その $i, j$ 成分 $a'_{ij}$ は、

$a'_{ij} = \left\{\begin{array}{} 1 & (v_i, v_j) \in E \\ 0 & \mathrm{else} \end{array}\right.$

※頂点の集合か順序対かの違い。

上の2つのグラフを隣接行列で表現すると、以下のようになる。

$(左のグラフ) = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \quad (右のグラフ) = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}$

見てわかる通り、無向グラフの隣接行列は常に対称行列となる。

このデータ構造は、 C++ では二次元配列を用いて実現することができる。

無向グラフ $G = (V, E)$ について、 $N = |V|, M = |E|$ と各 $e_i = \{u_i, v_i\} \: (i = 1, 2, \cdots, M)$ が標準入力によって次のように与えられたとする。

N M
u_1 v_1
u_2 v_2
...
u_M v_M

このとき、 $G$ の隣接行列の各成分を標準出力するコードは次のようになる。

※本来は固定長の配列でも良いが、説明の都合上可変長配列vectorを使っている。

#include <iostream>
#include <vector>

int main()
{
    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int>> graph(N, std::vector<int>(N, 0)); // 隣接行列

    for (int i = 0; i < M; i++)
    {
        // 入力は 1-indexed
        int u, v;
        std::cin >> u >> v;

        graph[u - 1][v - 1] = 1;
        graph[v - 1][u - 1] = 1; // 有向グラフの場合は不要
    }

    for (auto &&row : graph)
    {
        for (auto &&x : row)
        {
            std::cout << x << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

例えば上図の左のグラフを表す入力 :

を与えると、出力は

0 1 1 
1 0 1 
1 1 0

となり、先ほどの数式による表現と一致した。

隣接行列は辺の追加・削除や存在確認が高速に行える一方、 $O(N^2)$ のメモリを消費してしまうので、グラフに対する辺の数が比較的多いグラフ (密グラフ) の場合に有効となるデータ構造である。なお、辺の重みを格納できないため有向グラフに対しては使えない。

隣接リスト

隣接リストは、グラフ $G = (V, E)$ の各頂点 $v \in V$ に対して辺 $e = (v, v') \in E$ が存在するような頂点 $v'$ を列挙する表現方法である。つまり、隣接行列の各行に対して $a_{ij} = 1$ となるような $j$ を取り出してきたものだ。

先ほどの2つのグラフ (下図に再掲) を隣接リストで表現すると、以下のようになる。

$(左のグラフ) = \{ \{2, 3\}, \{1, 3\}, \{1, 2\} \} \\ (右のグラフ) = \{ \{2, 3\}, \{3\}, \{\} \}$

C++ では、可変長配列vectorの2次元配列を用いれば実現できる。上述の標準入力から隣接リストを構築し、その内容を出力するコードは以下のようになる。

#include <iostream>
#include <vector>

int main()
{
    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int>> graph(N); // 隣接リスト

    for (int i = 0; i < M; i++)
    {
        // 入力は 1-indexed
        int u, v;
        std::cin >> u >> v;

        graph[u - 1].push_back(v - 1);
        graph[v - 1].push_back(u - 1); // 有向グラフの場合は不要
    }

    for (auto &&v : graph)
    {
        for (auto &&x : v)
        {
            std::cout << x + 1 << " "; // 出力は 1-indexed
        }
        std::cout << std::endl;
    }

    return 0;
}

入力に対する出力は

2 3 
1 3 
2 1

となる。

隣接リストはメモリ消費が $O(N)$ であるため広く用いられるデータ構造である。グラフに対する辺の数が比較的少ないグラフ (疎グラフ) の場合に特に有効である。

おわりに

いかがだっただろうか。今回は、離散数学の中心となる分野であるグラフ理論について、そもそも「グラフ」とは何かや、グラフ理論に登場する基本用語を紹介した。

一口にグラフと言っても様々な切り口から見たグラフの分類が存在するので、特徴を押さえながら理解していこう。

次回はグラフの特殊な形である「木」についてまとめていこうと思う。

Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【グラフ理論とアルゴリズム】①グラフ理論の基礎～基本用語と定義の確認～

はじめに

「グラフ」とは何か？

グラフの定義

グラフ理論の基本用語

頂点の接続

辺の重み

有向グラフと無向グラフ

頂点の隣接と次数

部分グラフ・誘導部分グラフ

ウォーク・トレイル・サーキット・パス

グラフの連結性

握手補題

グラフを表すデータ構造

隣接行列

隣接リスト

おわりに