グラフ理論を用いた囲碁 数式一覧 (2)

群接点

交点 $i$ に群接する点と $i$ 自身を示す行列です。盤上の群を表しています。群とは隣接またはナナメに接する(リンクする)同じ色の石の集合です。$_i Q _j$ は $i$ が $j$ と等しいか、$i$ と $j$ が同じ群に含まれる群関係を表します。空点は各点が独立して群関係を満たします。下記の定義において $(G)_{ij}=1$ のとき $j$ は $i$ に群接するといいます。このとき、$i$ が着点ならば、$j$ は $i$ の群に含まれる石かその群に隣接する点で、$i$ が空点ならば、$j$ は $i$ に隣接する点です。この行列は郡ができるごとに変化していきます。盤面に2子以上の群が1つもない場合、$G = F_0$ となります。$F_0$ が対称行列であるのに対し、$G$ は対称行列であるとは限りません。 $$(G)_{ij} = \begin{cases} 1 & ^\exists k; (_i Q _k \; \text{and} \; _k N _j) \\ 0 & \text{otherwise} \end{cases} \tag{15} $$

端 (edge)

盤の端をベクトルで表しました。$F_0 \boldsymbol{e}_i$ は交点 $i$ の隣接点ですが、$i$ 自身も含むので盤の端（辺または隅）でなければ5点あります。5未満の場合は盤の端になります。 $$(\boldsymbol{\varepsilon})_i = \begin{cases} 1 & \left|F_0 \boldsymbol{e}_i \right| \lt 5 \\ 0 & \text{otherwise} \end{cases} \tag{16-1} $$ この端 $\boldsymbol{\varepsilon}$ を4つに分けて、上端 $\boldsymbol{\varepsilon}_u,$ 下端 $\boldsymbol{\varepsilon}_d,$ 左端 $\boldsymbol{\varepsilon}_l,$ 右端 $\boldsymbol{\varepsilon}_r$ とすると、それぞれは、 $$(\boldsymbol{\varepsilon}_u)_i = \begin{cases} 1 & J_u \boldsymbol{e}_i = \boldsymbol{0} \\ 0 & \text{otherwise} \end{cases} \tag{16-2} $$ $$(\boldsymbol{\varepsilon}_d)_i = \begin{cases} 1 & J_d \boldsymbol{e}_i = \boldsymbol{0} \\ 0 & \text{otherwise} \end{cases} \tag{16-3} $$ $$(\boldsymbol{\varepsilon}_l)_i = \begin{cases} 1 & J_l \boldsymbol{e}_i = \boldsymbol{0} \\ 0 & \text{otherwise} \end{cases} \tag{16-4} $$ $$(\boldsymbol{\varepsilon}_r)_i = \begin{cases} 1 & J_r \boldsymbol{e}_i = \boldsymbol{0} \\ 0 & \text{otherwise} \end{cases} \tag{16-5} $$ と表せます。ここで、$J_u, J_d, J_l, J_r$ はそれぞれ上下左右の隣接を表しており、3路盤の場合、 $$ J_u = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} \\ J_d = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \\ J_l = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \\ J_r = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$ となります。隅が重複しますが、$\boldsymbol{\varepsilon} = \boldsymbol{\varepsilon}_u \vee \boldsymbol{\varepsilon}_d \vee \boldsymbol{\varepsilon}_l \vee \boldsymbol{\varepsilon}_r$が成り立ちます。

拡大 (thicken)

一方の石のみ（黒石のみまたは白石のみ）の集合 $\boldsymbol{s}_o$ 全体の隣接点を表しています。黒石の場合、 $\boldsymbol{s}_o$ は $\boldsymbol{b}_o = \boldsymbol{b} - \boldsymbol{l} = \overline{\boldsymbol{w}}$ となります。 $$thicken(\boldsymbol{s}_o) = F_0 \boldsymbol{s}_o \tag{17} $$

外縁 (exterior)

一方の石のみの集合 $\boldsymbol{s}_o$ 自身を除いた隣接点を表しています。この式は $\boldsymbol{s}_o$ に対してのみでなく、領域 $\boldsymbol{r}$ に対しても成り立ちます。領域とは盤上の縦横につながる任意の交点のことを言います。 $$exterior(\boldsymbol{s}_o) = thicken(\boldsymbol{s}_o) - \boldsymbol{s}_o \tag{18} $$

呼吸点 (liberty)

一方の石のみの集合 $\boldsymbol{s}_o$ の呼吸点を表しています。 $$liberty(\boldsymbol{s}_o) = exterior(\boldsymbol{s}_o) \wedge \boldsymbol{l} \tag{19} $$

隣接関係の数

一方の石のみの集合 $\boldsymbol{s}_o$ の内部の隣接関係の数を表しています。 $$\# adjacent(\boldsymbol{s}_o) = \left| \boldsymbol{s}_o \wedge J_r \boldsymbol{s}_o \right| + \left| \boldsymbol{s}_o \wedge J_d \boldsymbol{s}_o \right| \tag{20} $$

1点についての最大隣接数

一方の石のみの集合 $\boldsymbol{s}_o$ のそれぞれの石の隣接数の最大値を表しています。$n$ はベクトルの次数を表します。3路盤なら $n = 9$ です。$J_1$ は式(14-1)にもある隣接関係を表す行列です。 $$\# max\_neighbor(\boldsymbol{s}_o) = \max_{1 \le i \le n} \left| J_1 \boldsymbol{e}_i \wedge \boldsymbol{s}_o \right| \tag{21} $$

リンク数

群 $\boldsymbol{g}$ の石同士のリンク数（縦横ナナメの接続数）を表しています。 $$\# link(\boldsymbol{g}) = \# adjacent(\boldsymbol{g}) + \left|\boldsymbol{g} \wedge ((J_r J_d \boldsymbol{g} - (J_r \boldsymbol{g} \vee J_d \boldsymbol{g})) \vee (J_l J_d \boldsymbol{g} - (J_l \boldsymbol{g} \vee J_d \boldsymbol{g}))) \right| \tag{22} $$

閉ループ数

群 $\boldsymbol{g}$ の閉ループ（広さを持たないループ）の個数を表しています。 $$\# closed\_loop(\boldsymbol{g}) = \left|\boldsymbol{g} \wedge J_r \boldsymbol{g} \wedge J_d \boldsymbol{g} \wedge J_r J_d \boldsymbol{g} \right| \tag{23} $$

開ループ数

群 $\boldsymbol{g}$ の開ループ（広さを持つループ）の個数を表しています。この式の計算はオイラーの公式に基づいています。$\# link(\boldsymbol{g})$ が辺の数、$\left|\boldsymbol{g} \right|$ が頂点の数、計算結果が面（領域）の数を表しています。 $$\# open\_loop(\boldsymbol{g}) = \# link(\boldsymbol{g}) - \left|\boldsymbol{g} \right| - \# closed\_loop(\boldsymbol{g}) + 1 \tag{24} $$

仮想リンク数

群 $\boldsymbol{g}$ の盤の端にある石同士のリンク（繋がり）の個数を表しています。盤の端にある石の数から盤の端にある隣り合った石の数を引いて求めることができます。 $$\boldsymbol{g}_\varepsilon = \boldsymbol{g} \wedge \boldsymbol{\varepsilon} \tag{25-1} $$ $$ \# virtual\_link(\boldsymbol{g}_\varepsilon) = \left|\boldsymbol{g}_\varepsilon \right| - \#adjacent(\boldsymbol{g}_\varepsilon) \tag{25-2} $$

領域 (region)

交点の集合 $\boldsymbol{r}$ が領域である条件は $\boldsymbol{r}$ の任意の交点 $i$ から出発して、$\boldsymbol{r}$ 内の隣の交点をたどっていったとき、$\boldsymbol{r}$ 全体に到達できることです。これを式で表すと、 $$ \boldsymbol{r} = \boldsymbol{r}_t, r_0 = e_i, r_{t+1} = F_0 \boldsymbol{r}_t \wedge \boldsymbol{r}, \boldsymbol{r}_{t+1} = \boldsymbol{r}_t \tag{26} $$ となります。

内部 (interior)

全ての隣接点が、領域 $\boldsymbol{r}$ に含まれる交点の集合を表しています。 $$\begin{align} interior(\boldsymbol{r}) = & (J_u \vee (E \wedge (\boldsymbol{\varepsilon}_d \; ^t \boldsymbol{1}))) \boldsymbol{r} \wedge (J_d \vee (E \wedge (\boldsymbol{\varepsilon}_u \; ^t \boldsymbol{1}))) \boldsymbol{r} \wedge \\ & (J_l \vee (E \wedge (\boldsymbol{\varepsilon}_r \; ^t \boldsymbol{1}))) \boldsymbol{r} \wedge (J_r \vee (E \wedge (\boldsymbol{\varepsilon}_l \; ^t \boldsymbol{1}))) \boldsymbol{r} \end{align} \tag{27} $$ 盤の中央では、この式の右辺の括弧（かっこ）の中、例えば、$(J_u \vee (E \wedge (\boldsymbol{\varepsilon}_d \; ^t \boldsymbol{1})))$ は $J_u$ で置き換えても構いません。長くなっているのは盤の端で成り立たなくなることを避けるためです。

黒石の閉領域 (closed region)

領域 $\boldsymbol{r}$ が黒石の閉領域である条件は(1) $\boldsymbol{r}$ に黒石がない、(2) $\boldsymbol{r}$ の外縁は黒石のみ、(3) $\boldsymbol{r}$ の内部は白石のみ、の3つです。これを式で表すと、 $$ \boldsymbol{r} \wedge \boldsymbol{b}_o = \boldsymbol{0} \tag{28-1} $$ $$ exterior(\boldsymbol{r}) \subseteq \boldsymbol{b}_o \tag{28-2} $$ $$ interior(\boldsymbol{r}) \subseteq \boldsymbol{w}_o \tag{28-3} $$ となります。

白石の閉領域 (closed region)

領域 $\boldsymbol{r}$ が白石の閉領域である条件は(1) $\boldsymbol{r}$ に白石がない、(2) $\boldsymbol{r}$ の外縁は白石のみ、(3) $\boldsymbol{r}$ の内部は黒石のみ、の3つです。これを式で表すと、 $$ \boldsymbol{r} \wedge \boldsymbol{w}_o = \boldsymbol{0} \tag{28-4} $$ $$ exterior(\boldsymbol{r}) \subseteq \boldsymbol{w}_o \tag{28-5} $$ $$ interior(\boldsymbol{r}) \subseteq \boldsymbol{b}_o \tag{28-6} $$ となります。