囲碁から始めるグラフ理論

四角形の碁盤と円形の碁石を用いる囲碁は方円とも呼ばれる。
ところで、碁盤の形は四角形でなくてはいけないのだろうか。
囲碁の根幹をなすルールに「囲んだ石を提（と）る」があります。

呼吸点

では、「囲む」とはどういうことか。
図1(a)では中央白1子から4本の線が伸びている。
その線の先にある$\Box$をすべて黒石で埋めれば白石を提ることができる。
$\Box$のような点を呼吸点(liberty)と呼ぶ。
呼吸点をすべて埋められると呼吸ができず石が死んでしまうというイメージだ。
図1 (b)のように辺や隅では呼吸点の個数も少なくなる。
また複数の石がある場合の呼吸点は図1 (c)のようになる。
図1の$\times$は呼吸点ではない。
言い換えると、石に隣接する交点が呼吸点になり、隣接していない点は呼吸点にならない。
交点同士の隣接関係さえわかれば囲碁が打てることになる。

点の隣接関係に注目する数学モデルはグラフと呼ばれる。
そこで、グラフを碁盤として見ることで囲碁を数学的に表現してみよう。

以下、数A程度の集合の知識を前提とする。

碁盤

碁盤は$19\times 19=361$個の交点（以下、グラフ理論の言葉に合わせて頂点(vertex)と呼びます。）と縦19本横19本の直線から構成される。
しかし、「1本の直線上に19個の頂点がある」ではどの頂点が隣接するのかが不明である。
そこで1本の直線を図2に矢印で示した18の部分に分けて考え、それぞれを辺(edge)と呼ぶ。
つまり、碁盤は361個の頂点と684本の辺からなっていると捉えられる。

三路盤

数が大きくなるとわかりにくいので、ここからは三路盤で考えよう。
三路盤には9つの頂点$v_1$、$v_2$、$v_3$、$v_4$、$v_5$、$v_6$、$v_7$、$v_8$、$v_9$がある。
そして、辺は両端の2つの頂点を指定すれば、どの辺を指しているかわかる。
そのため、$\{v_1,v_2\}$のように２つの頂点からなる集合で表される。
辺$\{v_1,v_2\}$は$v_1$と$v_2$を結ぶ辺である。
通常$v_1v_2$のように中括弧とカンマを省略して書く。
グラフは頂点集合$V$と辺集合$\Edge{E}$との組$G=(V,\Edge{E})$で表される。
三路盤の場合、頂点集合が
$ V=\{v_1,\ v_2,\ v_3,\ v_4,\ v_5,\ v_6,\ v_7,\ v_8,\ v_9\} $、
辺集合が
$ \Edge{E} = \{ v_1v_2,v_2v_3,v_1v_4,v_2v_5,v_3v_6,v_4v_5,v_5v_6,v_4v_7,v_5v_8,v_6v_9,v_7v_8,v_8v_9 \} $
であるようなグラフである。

頂点$v$と辺$\edge{e}$に対して、$v\in \edge{e}$となるとき、$v$は$\edge{e}$に接続(incident)するといい、$v$は$\edge{e}$の端点(endvertex)といい、$\edge{e}$は$v$の接続辺(join)という。
2つの頂点$u$、$v$に対して辺$uv$が存在するとき,$u$と $v$とは隣接(adjacent)するといい、互いに他の隣接点(neighbour)であるという。
例えば、図3では頂点$v_1$は辺$v_1v_2$に接続し、辺$v_1v_2$は頂点$v_1$の接続辺である。
辺は2つの頂点からなる集合なので、$v_1\in v_1v_2=\{v_1,v_2\}$となる。

頂点の集合$X$、$Y$と辺$\edge{e}$に対して$\edge{e}$の端点のうち、一方が$X$に、もう一方が$Y$に属するとき、$\edge{e}$を$X-Y$辺と呼ぶ。
$X-Y$辺全体の集合を$\Edge{E}(X,Y)$と表す。
端点の一方が$X$に属するとき、$X$辺といい、$X$辺全体の集合を$\Edge{E}(X)$と表す。
$X$が一つの頂点$x$だけからなる集合であるとき、単に$E(x)$と書く。
$E(x)$の本数を次数(degre)という。
碁盤はほとんどの頂点の次数が4で、辺の頂点の次数が3、隅の頂点の次数が2になる。
いわゆる隅の魔力はこの次数によるところが大きくなる。

無向グラフ$G=(\Vtx{V},\Edge{E})$と$H=(\Vtx{U},\Edge{F})$に対して、$\Vtx{U}\subseteq \Vtx{V}$かつ$\Edge{F}\subseteq \Edge{E}$となるとき、$H$は$G$の部分グラフであるといい, $H\subseteq G$と書く。
$H\subseteq G$であり、任意の$x,y\in \Vtx{U}$に対して$xy\in \Edge{E}$ならば$xy\in \Edge{F}$となるとき、$H$は$G$の誘導部分グラフという。
このとき、$U$は$G$において$H$を誘導するといい、$H=G[U]$と書く。

頂点$\vtx{v}$の隣接点全体の集合を$\Nei(\vtx{v})$と書く。
頂点の集合$\Vtx{U}\subseteq \Vtx{V}$に対して、$\Vtx{U}$に属する頂点の$\Vtx{V}\setminus\Vtx{U}$内にある隣接点全体の集合を$\Vtx{U}$の近傍(neighbourhood)といい、$\Nei(\Vtx{U})$と書きます。
例えば、図1の$\Box$が白石の近傍になります。

「つまり、呼吸点とは近傍のことである」と簡単に言えれば万々歳だが、実際には頂点の集合$\Vtx{U}$として図1 (b)の白石二つからなる集合をとることもできる。
要するに、$\Vtx{U}$はつながっていなくてもよい。
つながっていない石同士では呼吸点は共有されない。
近傍という概念だけでは呼吸点を述べることはできないことになる。

石がつながっているとはどう表されるだろうか。
頂点と辺の交互列$\vtx{v}_0\edge{e}_1\vtx{v}_1\dots\vtx{v}_{n-1}\edge{e}_n\vtx{v}_n$を歩道(walk)という。
歩道のうち、同じ辺を二度と通らないものを小径(trail)といい、同じ頂点を二度と通らないものを道(path)という。
道の最初の頂点と最後の頂点とを辺で結んだものを閉路(cycle)という。
グラフ理論は一筆書きの研究で生まれた。
閉路は一筆書きのことになる。
図4の太い線が道の例、二重線が閉路の例である。

閉路と道

頂点の集合$X,Y\subset V$と道$\Path=v_0\dots v_n$に対して、$V(\Path)\cap X=\{v_0\}$、$V(\Path)\cap Y=\{v_n\}$となるとき、$\Path$を$X\mathrm{-}Y$道という。
$X\mathrm{-}Y$道全体の集合を$\PATH(X,Y)$と表す。
$\PATH(\{x\},Y)$や$\PATH(X,\{y\})$は単に$\PATH(x,Y)$や$\PATH(X,y)$と書く。
$\PATH(v,v)$は長さ0の道$v$のみからなる集合である。

無向グラフ$G=(\Vtx{V},\Edge{E})$の任意の2頂点が道で結ばれるとき、$G$は連結(connected)であるという。
頂点の集合$U\subset V$に対して、$G[U]$が連結であるとき、$U$は連結であるという。
無向グラフ$H$が無向グラフ$G$の連結成分(component)であるとは、$H$が$G$の連結な部分グラフであって、任意の$H\subsetneq H'\subseteq G$となるグラフ$H'$が連結でないことをいう。
頂点の集合$U\subset V$に対して、$G[U]$が$G$の連結成分であるとき、$U$は$G$の連結成分であるという。

連結成分

石がつながっているとは二つの石を結ぶ道が存在すること、石のかたまりとは連結成分のようなものだと捉えることができる。
より正確に言えば、黒石だけの誘導部分グラフを考えたとき、その連結成分が石のかたまりになる。
例えば、図5の右が黒石の誘導部分グラフになり、7子、3子、2子のかたまりが1つづつ、1子で孤立している石が3子あることがわかる。

ここまで定めることで、呼吸点とは連結成分の近傍である、と言うことができる。

マジメなグラフ理論の記事は こちら