（未完）グラフ同型を解くLuksアルゴリズムを実装したい

#数学  #Python 

グラフ同型問題は計算量クラスとして絶妙な位置（N よりは難しいが、 NP 完全ほどではない）にあるとしてよく話題に上がるが、いまいちこの問題を解くアルゴリズムを理解しているケースは少ないようにみえる。実際、 Babai により擬多項式時間でグラフ同型問題を解くアルゴリズムが与えられている [L. Babai, 2015] が、検索してもブログレベルで解説されていることはない。

そこで、本稿では、 Babai のアルゴリズムを理解するために重要な Luks のアルゴリズムを Python で実装することを目的とする。 Luks のアルゴリズムは既に日本語文献で解説されているが、（自分の能力では）読んでもぱっとはわからなかったので、その文献をもとに少しずつ進んでいきたい。

なお、今回最終的に得られるのは 3-正則グラフのグラフ同型問題を解く Luks のアルゴリズムである。3-正則グラフとは、すべての頂点の次数（他の頂点と結ぶ辺の本数）が 3 であるグラフのことであり、例えば 6 頂点グラフなら以下のようなものがある：

このうち、中央と右は同型であり、左のものとは異なっている。確かに左のグラフのように三角形の形に辺を辿ることはできないので納得できるだろう（このグラフの参考）。

群

わかっている人にとっては「ここから？！」と思われそうだけれど、基本に立ち返って、念のため。

ある集合 \(\tilde{G}\) とある演算 \(\cdot\) が与えられたとき

1. あらゆる \(a,b,c\in\tilde{G}\) について \((a\cdot b)\cdot c=a\cdot(b\cdot c)\)（結合則）
2. あらゆる \(a\in\tilde{G}\) について \(e\cdot a=a\cdot e=a\) を満たすある \(e\in\tilde{G}\) が存在する（単位元の存在）
3. あらゆる \(a\in\tilde{G}\) について \(a^{-1}\cdot a=a\cdot a^{-1}=e\) を満たす \(a^{-1}\in\tilde{G}\) が存在する（逆元の存在）

この 1.-3. を満たす \((\tilde{G},\cdot)\) の組を群という。

このような群を \(G\) として、集合 \(\tilde{G}\) の要素（元） \(a\) をわざわざ \(a\in\tilde{G}\) と書かずに \(a\in G\) と書いてしまうことが多い。

（参考：群の定義といろいろな具体例、3.1節 群論からの準備）

対称群

対称群とは、ある集合 \(X(\neq\emptyset)\) から \(X\) 自身への全単射を集合としてもち、それらの写像の合成を演算としてもつ群。 \(\mathrm{Sym}(X)\) と表されることが多い。

例えば、 \(X=\{0,1,2,3\}\) であるとき、その対称群のある元 \(f\in\mathrm{Sym}(X)\) により \(f(0)=2\), \(f(1)=0\), \(f(2)=3\), \(f(3)=1\) のように順番が交換されることとなる。これは

$$ f=\begin{pmatrix} 0 & 1 & 2 & 3 \\ 2 & 0 & 3 & 1 \end{pmatrix} $$

のように表される。写像の合成が演算となるとは、例えば、 \(f,g\in\mathrm{Sym}(X)\) について \(f(0)=2\), \(g(2)=1\) であれば \((f\circ g)(0)=1\) と合成されることになる。この合成関数はやはり \(\mathrm{Sym}(X)\) に含まれるので、確かに群となっている。

なお、 2 つの値の順番だけを交換する写像は互換と呼ばれる。

（参考：1.6 対称群と置換群）

自己同型群

対称群は集合 \(X\) を対象としていたが、自己同型群は群 \(G\) を対象とする。自己同型群 \(\mathrm{Aut}(G)\) は、ある群 \(G\) から \(G\) 自身への同型写像（次で説明する）の集合をもち、その同型写像はやはり合成されてその集合に含まれるので、群となる。

同型写像

群に対する写像を考えることができる。これは群のもつ演算とは別である。ここで、群 \(G\) から群 \(G'\) への写像 \(f:G\to G'\) について、あらゆる \(a,b\in G\) について

$$f(ab)=f(a)f(b)$$

が成り立つとき、そのような写像 \(f\) を準同型写像という。つまり掛けてから写像しても、写像してから掛けても同じというものである。

そのうえで、この \(f\) が全単射（すべての要素が 1 対 1 対応）であるとき、同型写像という。

（参考：3.1節 群論からの準備）

部分群

ある群 \(H\) が群 \(G\) の部分群（\(H\subseteq G\)）であるとは、 \(H\) の集合が \(G\) の演算について閉じているということ。つまり、 \(H\) の任意の要素について \(G\) の演算を掛けても \(H\) の集合に含まれていれば良い。

（参考：部分群の定義と判定方法～例4つと性質～）

置換群

対称群の部分群のこと。

生成系

群 \(G\) について、その集合のある部分集合 \(S\subset G\) を考える。任意の \(s_1\dots s_n\in S\) と任意の \(a_1,\dots,a_n\in\mathbb{Z}\)（\(\mathbb{Z}\) は整数）に対し、

$$s_1^{\pm a_1}\cdot s_2^{\pm a_2} \cdots s_n^{\pm a_n}$$

と表される元の集合は、 \(G\) の演算のもとで \(G\) の部分群となる。この部分群のことを \(S\) で生成される部分群といい \(\langle S \rangle\) と表す。また、 \(S\) を生成系、 \(S\) の元を生成元という。

例として、対称群のシンプルなものを考える。生成元として

$$ \sigma=\begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \end{pmatrix} $$

のみを持つ生成系 \(S=\{\sigma\}\) を考える。すると、 \(\langle S\rangle\) は

$$ \langle S\rangle=\left\{ \begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 & 2 \\ 2 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 2 \end{pmatrix} \right\} $$

となる。これは例えば \(\sigma(\sigma(\sigma(0)))=0\) となることからわかるだろう。

（参考：群の生成とは～定義と具体例～）

剰余類

群 \(G\) について、部分群 \(H\subseteq G\) を考える。このときある \(g\in G\) について

$$gH=\{g\cdot h\mid h\in H\}\subseteq G$$

を \(G\) における \(H\) の左剰余類といい、

$$Hg=\{h\cdot g\mid h\in H\}\subseteq G$$

を \(G\) における \(H\) の右剰余類という。

（参考：剰余類と部分群の指数～定義と具体例～）

正規部分群

群 \(G\) について、部分群 \(H\subseteq G\) を考える。任意の \(g\in G\) について

$$gHg^{-1}\subseteq H$$

が成り立つとき、 \(H\) は正規部分群であるという。なお、 \(gHg^{-1}=H\) と同値である（びっくり）。共役変換しても不変な部分群ということらしい。

（参考：正規部分群の定義と基本的な判定方法・具体例、正規部分群の例題【判定と証明】）

商群

群 \(G\) について、正規部分群 \(H\subseteq G\) を考える。このとき剰余類の集合（剰余類自体を集めているので、つまり集合の集合になっている） \(G/H=\{gH\mid g\in G\}\) は、その任意の元 \(g_1 H,g_2 H\in G/H\) について

$$(g_1 H)(g_2 H)=g_1 g_2 H\in G/H$$

という演算によって群をなす。この \(G/H\) を商群（もしくは剰余群）という。

（参考：剰余群(商群)とは～定義・具体例・性質の証明～）

完全代表系

ある集合 \(X\) について、その元 \(a,b\in X\) の中である同値関係が存在するとき（\(a\sim b\)）、その同値関係が成り立つ元を集めた部分集合で \(X\) を分ける

$$X=X_1 + X_2 + \cdots + X_n\qquad (X_i\cap X_j=\emptyset\quad(i\neq j))$$

ことを類別という。

この類別は群についても考えることができ、ある群 \(G\) と部分群 \(H\subseteq G\) について、その元 \(a\in G\) で得られる剰余類 \(aH\) に対して、 \(a,b\in aH\) として \(a\sim b\) の同値関係を考えられる。そして、その同値関係が成り立つ元を集めた剰余類で \(G\) を分ける

$$G=H+a_1 H+a_2 H+\cdots + a_n H\qquad (a_i\nsim a_j\quad(i\neq j))$$

類別を考えられる。これを部分群による類別と呼ぶこともある。

このとき、各剰余類から 1 つずつ元をとってきて作る集合を完全代表系という。

（参考：類別、剰余類、完全代表系と商集合）

\(p\) 群

群 \(G\) の要素の数を位数といい、 \(|G|\) で表す。この \(|G|\) が有限であるとき、 \(G\) は有限群であるという。そして、ある素数 \(p\) について、 \(|G|\) が \(p\) のべき乗で表されるとき、 \(G\) は \(p\) 群であるという。

（参考：「p群とは？」シローの定理と関連する重要な概念【代数学の基礎シリーズ】群論編 その24）

軌道

集合 \(X\) の対称群 \(\mathrm{Sym}(X)\) について、任意の部分群 \(G\subseteq\mathrm{Sym}(X)\)（つまり置換群）をとると、任意の \(x\in X\) に対して

$$G(x)=\{g(x)\mid g\in G\}$$

を \(x\) の \(G\) による軌道という。ここで、 \(G(x)=X\) であるなら群 \(G\) は \(X\) 上で推移的であるという（つまり、軌道が再びもとの集合となるということ）。

\(G\)-安定

上の軌道で導入した \(X\), \(G\) について、任意の部分集合 \(Y\subseteq X\) に対して

$$\{g(y)\mid g\in G,y\in Y\}$$

が成り立つとき、 \(Y\) は \(G\)-安定であるという。

\(G\)-block

\(G\) を \(X\) 上で推移的な群であるとする。このとき、空でない部分集合 \(Y\subset X\) が任意の \(\sigma,\tau\in G\) に対して \(\sigma(Y)=\tau(Y)\) または \(\sigma(Y)\cap\tau(Y)=\emptyset\) なら、 \(Y\) は \(G\)-block であるという（つまり、 \(G\) の元である写像 \(\sigma\), \(\tau\) によりまったく同じ集合が得られる場合、もしくは完全に異なる集合が得られる場合）。

また、 \(Y\) が \(G\)-block であるとき、集合族（基本的には集合の集合のこと） \(\{\sigma(Y)\mid\sigma\in G\}\) を \(Y\) についての \(G\)-block system という。

グラフ同型

与えられた 2 つのグラフ \(Q_1\), \(Q_2\) について考える。 \(V\), \(E\) を与えられたグラフの頂点集合、辺集合を返す関数とする。このとき、任意の 2 頂点 \(v,w\in V(Q_1)\) について、

$$(v,w)\in E(Q_1)\Leftrightarrow (f(v),f(w))\in E(Q_2)$$

となるような全単射写像 \(f:V(Q_1)\to V(Q_2)\) が存在するとき、 \(Q_1\) と \(Q_2\) は同型であるという。

（参考：グラフ理論入門：グラフとは、グラフの同型、うさぎでもわかる離散数学（グラフ理論）　第9羽　グラフの基礎3）

グラフの自己同型群

自己同型群は群を対象とするので、グラフの自己同型群というからにはグラフは群として表されるべきだろう。しかし、どうやら群ではなく、辺を持つか否かという関係（二項関係）をもつ集合としてグラフを捉えているようである。

つまり、頂点集合に対して順番を入れ替える写像が、その適用前後で辺の有無が変わらず、そして全単射である。そのような写像の集合（そして、そのような写像は合成できるので、その集合は群となる）をグラフの自己同型群と呼んでいる。（ということだろう）

結局のところ、対称群と呼んで差し支えないだろう。

（参考：グラフの準同型って何？）

集合のバックスラッシュ \(\setminus\)

2 つの集合 \(X\), \(Y\) について、 \(X\setminus Y\) は差集合を表し、 \(X\) から \(Y\) の要素を除いたものである。

Luks のアルゴリズムの定理

さて、本題である。まずは Luks のアルゴリズムを支える重要な定理から理解していく。

定理 3.1. 3 正則グラフの同型性判定問題は 3 正則な連結グラフの自己同型群の生成系を求 める問題に多項式時間で還元可能である．

この証明に沿っていく。 2 つの与えられた頂点数の等しい \(n\) 頂点の 3 正則グラフ \(Q_1\), \(Q_2\) について考える。

Q1 の適当な辺を e1 として固定する．このとき Q2 の各辺 e2 に対して次のような操作を 行い Q1 と Q2 を連結する．

1. e1, e2 のそれぞれの中間点に新しい頂点 v1v2 を導入する．
2. v1 と v2 を新たな辺でつなぎ，その辺の中間点に新たな頂点 s を導入する． このようにして連結したグラフを X とする．

この操作を図示すると、以下のようになる：

\(X\) の自己同型群 \(\mathrm{Sym}(X)\) の部分群である、頂点 \(s\) を固定して他の頂点の順番を入れ替える \(\mathrm{Sym}_s(X)\) を考える。ここで、 \(e_1\) を \(e_2\) へ写像し、そのときにのみ \(v_1\) を \(v_2\) に写像する \(\mathrm{Aut}_s(X)\) の元が存在するとき、そのうちの 1 つは \(\mathrm{Aut}_s(X)\) の生成元である。よって、 \(\mathrm{Aut}_s(X)\) の生成系を求めて、そこにそのような写像が存在すれば \(Q_1\) と \(Q_2\) は同型、存在しなければ同型でないということになる。

確かに \(e_1\) を \(e_2\) に写像するということはその両端の頂点が写像されているわけなので、そうなると、それらの頂点に隣接する頂点たちも次々と写像されなくてはならないので、それが完遂されるということは同型である条件を満たしていることになる。