グラフによる碁の表現

グラフ理論

グラフ理論の基本

形式的に書けば$[S]^n=\{X\subset S\mid|X|=n\}$となる。
グラフとは図1のように「頂点」と「辺」からなる図形である。グラフを考えるうえでは頂点の位置や辺の長さや形は考えず、頂点と辺の接続関係に着目する。具体的な例としては路線図などを考えるとよいだろう。路線図は駅のつながりに注目した図であり、駅がどの路線でつながっているかは正確に表すが、線は現実の線路の形通りではないし駅の位置も現実通りではない。

頂点は辺によってほかの頂点とつながっている。辺は二つないし一つの頂点に接続している。二頂点間に複数の辺があるとき、これを多重辺という。ある辺の両端点が等しいとき、これをループという。図1の$e_5$、$e_6$が多重辺であり、$e_2$がループである。多重辺もループもないグラフを単純グラフといい、多重辺やループを含むグラフを多重グラフという。

グラフの例

形式的には、グラフは以下のように定義される。

例えば図1で考えると、$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*}
となっている。このとき、辺$e\in E$に対して$\psi(e)=\{u,v\}$の元を$e$の端点と呼び、辺$e$は頂点$u,v$に接続する、頂点$u,v$は$e$によって結ばれる、頂点$u,v$は互いに隣接している、などという。$\psi(e)=\{u,v\}$であるとき、$e=uv$と書く。

単純グラフ$G=(V,E,\psi)$に関して、接続写像$\psi$は単射であり、値域は$[V]^2$となる。よって$E\subset[V]^2$としてしまっても構わない。ここで、$e=\{u,v\}\in E$は頂点$u$、$v$を結ぶとする。このとき接続写像は辺集合$E$から自然に定まるので、単純グラフは頂点集合と辺集合の組$G=(V,E)$で表す。

グラフ$G$の頂点集合を$V(G)$、辺集合を$E(G)$、接続写像を$\psi_G$で表す。グラフと頂点集合や辺集合を厳密に区別しない場合も多くある。すなわち、$v\in V(G)$と書くべきところを$v\in G$と書いたりする。

図2の二つのグラフは頂点と辺のつながり方が一緒である。このようなグラフを同型なグラフという。

同型なグラフ

$A$-$B$辺全体の集合を$E(A,B)$と表す。$E(\{u\},B)$や$E(A,\{v\})$を単に$E(u,B)$、$E(A,v)$と書き、$u$-$B$辺などという。頂点$v$に接続する辺全体の集合を$E(v)$で表す。

頂点$v\in V$の隣接点全体の集合を$\mathrm{Nei}(v)$と書く。さらに、$U\in V$に対して、$U$内の頂点の隣接点で$V\setminus U$に属するもの全体の集合を$\mathrm{Nei}(U)$と書く。

グラフの辺に向きを考えたものを有向グラフという。これに対し、向きのないグラフを無向グラフという。有向グラフでは辺が集合ではなく組で表される。例えば、$e_1=(v_2,v_1)$である。有向グラフもまた$(V,E,\psi)$という組で表されるが、接続写像は$\psi:E\to V^2$となる。

有向グラフの例

道

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

道の例

道はその頂点の集合$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$というように表す。

$A$-$B$道全体の集合を$\mathrm{Path}(A,B)$で表す。以前と同様に波括弧を省略し$\mathrm{Path}(v_0,B)$などと書いたりする。

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

極大な連結部分グラフを連結成分という。

縮約

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

図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$の分岐集合という。

グラフ碁とは

いよいよグラフを用いて碁について考える。終局がわかりやすい純碁を基に考える。純碁について詳しくはこちら https://note.com/kurosen0000/n/nb2db700f9b95

まず、碁盤について考えてみよう。碁盤は交点を頂点とみなせばグラフととらえられる。碁盤が多重辺やループを持っていたとしても、碁を打つうえでは特に意味を持たない。これは、石の存在にはどの交点が隣接しているのかさえわかればよいからである。例えば、図6は九路盤に三本の辺を加えているが、それが在ろうとなかろうと黒石は取られている。したがって碁盤は単純グラフとしてしまってよい。

多重辺と石の存在

さらに、碁盤は連結グラフとしてしまってよい。というのも、ある連結成分に打たれた
石がほかの連結成分に在る石の存在にかかわることはないので、それぞれの連結成分の中だけで考えれば十分だからである。

以下、特に断らない限り$G=(V,E)$は碁グラフであるとする。

碁盤を用意したので、次は石について考えよう。交点は「黒が置かれている」「白が置かれている」「空点である」の三つのうちいづれかの状態にある。よって、例えば黒を-1、白を1、空点を0とすれば、写像$f:V\to\{-1,0,1\}$と盤面が同一視できることとなる。つまり$f(v)=-1$のとき交点$v$には黒石が置かれていると考えるのである。

$B$、$W$、$N$が$c$により定められることを強調したいときは$B_c$、$W_c$、$N_c$などと書いたりする。

例えば図7では$B=\{v_2,v_4,v_6\},\ W=\{v_5,v_8\},\ N=\{v_1,v_3,v_7,v_8\}$となる。

配置の例

$V=B\sqcup W\sqcup N$であるから、$B$、$W$が定まればおのずと$N$も定まる。そのため、$C=(B,W)$と略すことがある。

碁盤上で「つながっている」石のかたまりを連という。碁盤と配置の同一視の方法から、ある二つの石が碁盤上でつながっていることと、その二つの頂点が分割集合の同じ連結成分に属していることが同じ意味になる。

$c(v)$は$v$の石の色を表す。なので$c^{-1}(\{c(v)\})$は$v$と同じ色の分割集合となる。たとえば$v\in B$のときは$c^{-1}(\{c(v)\})=c^{-1}(\{-1\})=B$となる。さらに$v-w$道$P$の頂点$V(P)$が黒の部分集合であるから、当然$w\in B$であり$v,w$が黒石だけからなる道で結べることを表している。この同値関係による同値類（のうち黒か白に含まれるもの）が連となる。

$G/\sim_c$は$G$の縮約となっている。さらに隣接する頂点は違う色からなる交点の集合になっていて、その作り方から$G/\sim_c$は三部グラフになっている。

さて、配置は碁盤に石を置いただけであり、碁の局面としては適しないものも含まれている。具体的に言えば、取られた状態にある石が存在してはいけない。石が存在するための条件はその石のかたまりが空点に隣接していることで、例えば日本囲碁規約の第四条がそれにあたる。

まずは、いわゆる呼吸点を定義する。

式中の$u$は$[v]_c$内の点なので、$v$と同じ色の石だけでつながっている（もちろん$u=v$でもよい）。その$u$が空点$w$と隣接しているので$v$は盤上に存在できる。$l(v)=\varnothing$のときはそのような空点がないので$v$は存在できない。

定義より明らかに$l(v)\subset\mathrm{Nei}([v]_c)$である。

配置$c$における呼吸点集合であることを強調するときは$l_c$などと書く。

例えば、図8は盤面でない配置の例である。白□は呼吸点集合が空になっている。

盤面でない例

$c-v$は配置$c$において$v$に黒石を打った場合、$c+v$は配置$c$において$v$に白石を打った場合に対応している。

$l^{-1}_{c}(\{v\})\cap W_c$は$W_c$の頂点のうち, $v$のみを呼吸点に持つものの集合である. $v$を呼吸点に持つ頂点の集合ではない. つまり、$l^{-1}_{c}(\{v\})\cap W_c$は黒が$v$に打ったときに取りあげられる白石全体の集合である。

図9において$v\in l^{-1}(\{u\})$であるが、$v'\notin l^{-1}(\{u_1\})$である。これは$l(v')=\{u_1,u_2,u_3,u_4\}\ne\{u_1\}$であるからだ。

呼吸点集合

定義18では$c$、$c-v$、$c+v$は配置ではあるものの盤面とは限らない。正規の着手では、着手前も着手後も盤面となっている必要がある。

石を打つ直前の盤面と直後の盤面の組により着手を定義している. $M^-$が黒による着手全体の集合, $M^+$が白による着手全体の集合である. $(C^\ast,M)$は有向グラフになっている。

$c-v$（$c+v$）は黒石（白石）を一つ打ち、取れるなら白石（黒石）を取り上げる、という操作である。もしこの結果が盤面にならないとするなら、$c$において黒（白）は$v$に打つことができない。

少しもったいぶった言い方になっているが、「普通に」着手を並べれば着手列となる。

ただし、この定義では黒と白の着手が交互に並んでいる必要はない点に注意されたい。もし黒の着手が連続している場合、その間白はパスをしているものと考える。

これは同一局面の反復を禁ずるもので、いわゆる超劫ルールに相当する。

$(C^\ast,M)$をグラフとしてみたとき、着手列は歩道に、正規着手列は道にあたる。着手列はその盤面だけ、あるいは着手だけを取り出して並べても一意に定まる。

これに限らず、着手列$r$をその最終盤面そのものであるかのように記号を濫用する。

着手列$r$の最終盤面において、$v\in V$が黒石のとき$r(v)=-1$であるから$\sum_{v\in B}r(v)=-|B|$となる。同様に考えて$\sum_{v\in W}r(v)=|W|$であり、$\sum_{v\in N}r(v)=0$である。したがって$s(r)=\sum_{v\in V}r(v)=|W|-|B|$であり、黒石と白石の個数の差を考えていることがわかる。

$h$はコミといい, 事前に定められる数である. 日本では-6.5になっている.

以上により、（純碁を基にした）囲碁の数学的なルールが完成した。

次回

次回は グラフ碁の死活 です。