グラフ理論の基本

この記事は、ほかの記事でグラフ理論を使うときの説明用の記事です。ほかの記事で必要な内容が出るたびに更新する予定です。

記号について

集合や写像についての基礎的な知識は前提とし用語や記号は断りなく使います。

集合$S$に対して、$[S]^n$で$S$の$n$元からなる部分集合全体を表します。形式的に書けば$[S]^n=\{X\subset S\mid|X|=n\}$となります。

無向グラフ

グラフとは

単純グラフ

グラフとは図1のように頂点と辺からなる図形です。グラフを考える際には、頂点の位置や辺の長さ・形は意味を持たず、頂点と辺の接続関係だけに注目します。身近な例としては、路線図を考えるとわかりやすいでしょう。路線図はどの駅にどの路線が通っているかが重要で、その形が実際の線路の形そっくりになっている必要はありません。駅の位置関係も、実際とは異なっていても構いません。

グラフの例

グラフの形式的な定義は以下のようになります。

図1のグラフは頂点集合$V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8\}$、辺集合$E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_1\},\{v_4,v_5\},\{v_4,v_6\},\{v_4,v_7\}\}$のグラフ$G=(V,E)$です。

ハイパーグラフ

先に路線図の例を挙げました。駅を頂点、路線を辺とすると一つの辺に3つ以上の頂点が接続していることになります。このように、辺の要素数の制限をなくしたものをハイパーグラフといいます。

単純グラフはハイパーグラフの特別な場合と言えます。

多重グラフ

図2のような図形もまたグラフと呼ばれます。$e_2$のような両端点ともひとつの頂点であるような辺をループといい、$e_5$と$e_6$のように両端点ともを共有する辺を多重辺といいます。多重辺やループを持つグラフを多重グラフといいます。逆に単純グラフとは多重辺やループを持たないグラフです。

多重グラフの例

多重グラフの形式定義は以下の通りです。

図2では、$V=\{v_1,v_2,v_3,v_4,v_5\}$、$E=\{e_1,e_2,e_3,e_4,e_5,e_6,e_7,e_8\}$であり、接続関数$\psi$は\begin{align*} \psi(e_1)&=\{v_1,v_2\}\\ \psi(e_2)&=\{v_2\}\\ \psi(e_3)&=\{v_2,v_3\}\\ \psi(e_4)&=\{v_2,v_4\}\\ \psi(e_5)&=\{v_3,v_4\}\\ \psi(e_6)&=\{v_3,v_4\}\\ \psi(e_7)&=\{v_3,v_5\}\\ \psi(e_8)&=\{v_4,v_5\}\\ \end{align*}
となっています。

単純グラフはループや多重辺を持たない多重グラフだと考えることができます。単純グラフで考えるより多重グラフで考えたほうが自然で、証明などもしやすくなるような場合もあります。

（ところでハイパーグラフで多重グラフなグラフって聞かない気がします。定義すること自体は簡単ですが、何かそういうグラフが使われている例とかってあるんでしょうか。ご存じの方がいらっしゃいましたらコメントなどで教えてください。）

基本的な用語

グラフ$G$の頂点集合を$V(G)$、辺集合を$E(G)$、接続関数を$\psi(G)$と書きます。例えばグラフ$H=(W,F)$に対して$V(H)=W$、$E(H)=F$です。$W(H)$とは書きません。グラフと頂点集合・辺集合を厳密に区別せず、例えば$v_1\in G$、$\{v_2,v_4\}\notin G$のように書いたりもします。

グラフ$G$の頂点数を位数といい、$|G|$で表します。辺数は$||G||$と書きます。位数が有限なグラフを有限グラフ、位数が無限のグラフを無限グラフといいます。

グラフ$\{\varnothing,\varnothing\}$を空グラフと呼びます。

接続・隣接

頂点$v$と辺$e$に対して、$v\in e$（多重グラフなら$v\in \psi(e)$）となるとき、$v$は$e$に接続するといい、$e$を$v$の接続辺といいます。1つの辺に接続する2つの頂点はぞの辺の端点と呼び、辺はその端点を結ぶといいます。

辺$\{x,y\}$を単純に$xy$（または$yx$）と書きます。多重グラフのときも$x$、$y$が$e$の端点であることを表すために$e=xy$と書きますが、もはや$e$を一意に定めることはできません。この書き方は$\psi(e)=\{x,y\}$を省略したものとみることもできます。

グラフ$G$に辺$xy$が在るとき、$x$と$y$は隣接するといい、互いにほかの隣接点であると呼びます。また、2つの辺$e\ne f$が共通の端点を持つとき隣接するといいます。

グラフ$G=(V,E)$において、頂点$v$の$G$における隣接点全体の集合を$N_G(v)$または単に$N(v)$と表します。一般に、頂点からなる集合$U\subseteq V$に対して、$U$に属する頂点の$V\setminus U$の中にある隣接点全体の集合を$U$の近傍といい、$N_G(U)$または$N(U)$と表します。このように、誤解の恐れがないときは添え字の$G$を省略することがあります。

$X$と$Y$を頂点からなる集合とします。$x\in X$、$y\in Y$となるような辺$e=xy$を$X$-$Y$辺と呼びます。$X$-$Y$辺全体の集合を$E(X,Y)$と表します。$E(\{x\},Y)$や$E(X,\{y\})$を単に$E(x,Y)$や$E(X,y)$と書きます。このように単元集合のとき、波括弧$\{\}$を省略することがあります。頂点$v$に接続する辺全体の集合を$E(v)$と書きます。

次数

頂点$v$の次数$d_G(v)$とは$v$に接続する辺の本数$|E(v)|$です。単純グラフなら、$v$の隣接点の個数に等しくなります。次数0に頂点を孤立点といいます。次数の最小値$\delta(G):=\min\{d(v)\mid v\in V\}$を最小次数、最大値$\Delta(G):=\max\{d(v)\mid v\in V\}$を最大次数と呼びます。

同型なグラフ

2つの単純グラフ$G=(V,E)$、$G'=(V',E')$について、一対一対応$f:V\to V'$が存在して、全ての$x,y\in V$に対して$xy\in E\Leftrightarrow f(x)f(y)in E'$を満たすとき、$G$と$G'$は同型であるといい、$G\simeq G'$と書き、この写像$f$を同型写像と呼びます。多重グラフのときは、同型写像が$f:V\to V'$と$g:E\to E'$の組$(f,g)$となり、条件が、全ての$x,y\in V$、$e\in E$に対して$\psi(e)=\{x,y\}\Leftrightarrow \psi'(g(e))=\{f(x),f(y)\}$が成り立つことになります。

同型なグラフ

部分グラフ

グラフ$G=(V,E)$、$G'=(V',E')$について、$V'\subset V$、$E'\subset E$であり、頂点と辺の接続関係が保存されるとき、$G'$を$G$の部分グラフと呼び、$G'\subset G$と書きます。

$G'\subset G$であり、$G$が$x,y\in V'$となるような辺$xy\in E$をすべて含むとき、$G'$は$G$の誘導部分グラフであるといいます。このとき、$V'$は$G$において$G'$を生成するといい、$G'=G[V']$と書きます。

道

歩道（小径、道）の辺の本数をその長さと言います。始点と終点は本質的には違いがありませんが、これを決めておくことで歩道内の要素に順番が与えられるので便利なことがあります。小径は頂点の重複を許す道、歩道は辺の重複を許す道、というとらえ方もできます。

道の例

道はその頂点の集合$V(P)$と辺の集合$E(P)$からなる単純グラフ$P=(V(P),E(P))$ととらえることもできます。道を表すために、その頂点だけを並べることも多いです。そのようなときは$P=v_0\cdots v_k$と書きます。

$0\le i\le j\le k$とします。道$P=v_0\cdots v_k$の一部を切り取ったものを以下のように表します。

\begin{align*} v_iP&=v_i\cdots v_k\\ Pv_j&=v_0\cdots v_j\\ v_iPv_j&=v_i\cdots v_j\\ \mathring{P}&=v_1\cdots v_{k-1}\\ \mathring{v_i}P&=v_{i+1}\cdots v_k\\ P\mathring{v_j}&=v_0\cdots v_{j-1} \end{align*}

$P$が長さ1の道であるとき、$\mathring{P}$は空グラフになります。これはもはや道ではありません。

さらに、いくつかの道をつないで新たな道を作るとき、たとえば三本の道の和$Px\cup xQy\cup yR$が道になるならば、これを単に$PxQyR$というように表します。

道$P=v_0\cdots v_k$と頂点の集合$A$、$B$について$V(P)\cap A=\{v_0\}$かつ$V(P)\cap B=\{v_k\}$となるとき、$P$を$A-B$道と言います。$A$-$B$道全体の集合を$\Path(A,B)$で表します。以前と同様に波括弧を省略し$\Path(v_0,B)$などと書いたりします。

連結

グラフ$G=(V,E,\psi)$について、任意の$u,v\in V$に対し$\Path(u,v)\ne\varnothing$となるとき、$G$は連結であると言います。

直観的に言えばすべてつながっているグラフが連結なグラフです。

極大な連結部分グラフを連結成分と呼びます。

縮約

グラフのある辺を縮めて一つの頂点にすることを考えましょう。

図5のようにグラフ$G=(V,E)$の辺$e=xy\in E$を選びます。この辺を新しい頂点$v_{e}$に置き換えます。このとき、$x$または$y$と隣接していた頂点は$v_e$と隣接するようにし、どちらとも隣接していない頂点は$v_e$とも隣接しないようにします。

縮約

こうして得られたグラフを、$G$から、その辺$e=xy$を1つの頂点$v_e$に縮約して得られたグラフといい、$G/e$で表します。$G/e$の頂点集合と辺集合は、形式的には以下のように表されます。
\begin{align*} V(G/e)&=(V\setminus\{x,y\})\cup\{v_e\}\\ E(G/e)&=\{vw\in E\mid\{v,w\}\cap\{x,y\}=\varnothing\}\cup\{v_ew\mid xw\in E\setminus\{e\}\mbox{または}yw\in E\setminus\{e\}\} \end{align*}

この縮約の操作を何度か繰り返し、$G$から新たにグラフ$X$を作ることを考えるます。各$x\in V(X)$に対し、$x$に縮約された$G$の頂点全体の集合を$V_x$とすると、各$V_x$は連結であり、任意の$x,y\in V(X)$に対し、$G$に$V_x-V_y$辺があることと、$xy\in E(X)$となることが同値です。集合$V_x$を$G$の分岐集合と言います。

多重グラフの場合はもう少し単純です。両端点が共通な辺が許されるため、頂点集合、辺集合は以下のようになります。
\begin{align*} V(G/e)&=(V\setminus\{x,y\})\cup\{v_e\}\\ E(G/e)&=E(G)\setminus\{e\} \end{align*}
そして、$e$以外の$e'\in E\setminus\{e\}$に対して、$\psi_{G/e}(e')$を新しい頂点集合に合わせて修正します。

多重グラフの縮約

有向グラフ

定義

辺に向きを考えたものが有向グラフです。組は順序も考えるので、$(u,v)$と$(v,u)$は異なります。

有向グラフの例

道

有向グラフの場合、辺の向きも重要になります。