数理解析研究所講究録
第 1649 巻 2009 年 189-194189

グラフ同型問題から環同型問題への新たな帰着
早坂智行 (Tomoyuki Hayasaka)
東京工業大学理学部情報科学科
Dept. of Information Science, School of Science,
Tokyo Institute of Technology
概要

グラフ同型問題は環同型問題に帰着することができることが知られている. また, 帰着の際にグラフからどのような環を作るかについて 2 通りの構成法が既に知られている. 本論文では, 既知の 2 つの構成法よりも自然でシンプルな第 3 の構成法を考案し, この構成法においてもグラフの同型性と環の同型性が同値であることを示した. また, 既知の 2 つの構成法において, 環の同型写像はあるーつのグラフ同型写像を直接含んでいる. これに対し, 今回の新しい構成法における環の同型写像からも,多項式時間でグラフの同型写像を計算することができるだけでなく, 複数のグラフ同型写像の情報を含んでいる可能性があることも示した.

1

はじめに環とは, 加法

$(+)$

2
と乗法

$($

.

$)$

の二っの二項演算を備えた代数系のことであり, 数学の研究, 特に数論や代数学の研究において欠かせないものである.
また, 計算機科学の世界においても. 様々な問題が環の問題としてとらえることができることが知られている.
たとえば, [1] の決定的多項式時間の素数判定テストは,環$\mathbb{Z}_{n}[X]/\langle X^{r}-1\rangle$なる環の自己同型写像を調べていると見なすことができる [2]. 同様に素因数分癬問題も, ある環の同型写像の数を計算する, あるいは同型写像を一つ求める, といった環の同型写像の問題に帰着される [3].

またそれに類する結果として, グラフ同型問題を環同型問題へ多項式時間多対一還元を行うことができる,ということが知られている [3, 2]. 本論文では, これに対し別証を与える.

第 2 章ではグラフ同型問題を環同型問題へ帰着を行う
ための既知の構成法を紹介する. 第 3 章ではより自然でシンプルな新しい構成法を紹介し, それにより帰着を行うことができることを証明する. 第 4 章では新しい構成法における環の同型写像から, グラフの同型写像を計算する方法を与える. 第 5 章ではまとめと今後の課題について述べる.

既知の帰着法グラフ同型問題から環同型問題への帰着では, 与えられたグラフから 「グラフの構造を表現する環」 を構成すという事を行う.
[3] においては, 以下のような帰着法が紹介された.

る.

190

この構成法においては、変数しており,$A_{(1,2)},$$A_{(n-1,n)}$$\ldots,$と見ることができる.

る,, 瑞が各頂点を表が頂点のペアを表してい$v_{1},$$\ldots$は次のように書ける.

また, 辺がある点のペアにお$\phi(\lambda_{t}’)=\alpha_{i}+\sum_{1\leq j\leq n}\beta_{i,j}Y_{j}+\sum_{1\leq j<k\leq n}\gamma_{i,j,k}Y_{j}Y_{k}$

いてはその位数を $p$ に, 辺がない点のペアにおいてはその位数を$p^{2}$にすることで,グラフの辺の情報を表現して

いる.

ただし,
$Y_{1},$$R_{G}$$\cong$1

R 心 2 であるとき, 同型写像 $\phi:R_{G_{1}}arrow R_{G_{2}}$において, 各隣について$\phi(V_{l})$は次のように書ける.

$R_{G_{2}}$

における

おいて,

$\beta_{i,j}\neq 0$とにすると,$\pi(i)$となる.
は$G_{1}$

を区別のため$X_{1},\ldots,X_{n}$, 琉と表記している.

$\ldots$

このとき, ただ一っの

このような
から

$G_{2}$

$j$

$j$

に

を $\pi(i)$ と書くこへの同型写像を与えることが知られている.
$\phi(v_{i})=\alpha\iota+\sum_{1\leq j\leq n}\beta_{i_{t}j}V_{j}’n+\sum_{1\leq j<k\leq n}\gamma_{l.j,k}A_{(j,k)}’$

ただし,$R_{G_{2}}$における $V_{1},\ldots,$ $V_{n},A_{(1,2)},$ $\ldots,A_{(n-1,n)}$を区別のためにしている.

$V_{1}’,$$\ldots$,$V_{n}’,A_{(1,2)}’,$

このとき, ただ一つの$j$$A_{(n-1,n)}’$$\ldots,$において,$\beta_{i,j}$と表記が$\mathbb{Z}_{p^{3}}$において逆元を持つ. このような を $\pi(i)$ と書くことにすると, $\pi(i)$ はからへの同型写像を与えること$j$$G_{1}$$G_{2}$

が知られている.

[2] においては, 以下のような帰着法が紹介された.
こで,$\langle S\rangle$

こは集合 $s$ から生成されるイデアルを表すもの

とする.

3

新しい帰着法
一つ目の帰着法は, 比較的複雑な構造をしている. ま

た,

$=$

つ目の帰着法は,シンプルではあるが, 条件付きであることと,「辺のあるところを足すと$0$になる」という構造となっていることが若干不自然である.
そこで, 次のようなよりシンプルにグラフの構造を表現している環も, グラフ同型性問題から環同型性問題への帰着に利用できないか, と考えるのはごく自然なことである.

をすべて足すと
このとき, グラフ

$G_{1},$$G_{2}$

が, 孤立点を除くと完全グラフになるようなグラフでないとき,$G_{1}$.

$G_{2}$

が同型のとき, かつその時に限り, 構成法 2 により作られた環$R_{G_{2}}$$R_{G_{1}}$,が同型となる.

この構成法においては, 一次の項 $x_{1},\ldots,x_{n}$ が各頂点を表しており, 二次の項 $X_{1}X_{2},$ $\ldots,X_{n-1}X_{n}$ が頂点のペアを表している,とみることができる.

また,

辺が

ある点のペアを全て足すとになる, という条件を環が満たすようにすることで, グラフの辺の情報を保存して$0$になる」という部分を変更し, 「辺は$0$である」としたものである. この構成は構成法 1 より簡潔であり, かっ構成法 2 よりも辺の情報の埋め込みかたが自然である.
しかし,

この構成法 3 において, グラフが同型である

ことと構成された環が同型であることが同値であるかど
うかは明らかではない. なぜなら, 環の同型写像は直接的にはグラフの同型写像を表さない場合があるからである.
実際, ある環の同型写像 $\phi:R_{G_{1}}arrow R_{G_{2}}$ が与えられ,$\phi(X_{i})=\phi(X_{i})=\alpha_{i}+\sum_{1\leq j\leq n}\beta_{i_{l}j}Y_{j}+\sum_{(j,k)\not\in E_{2}}\gamma_{i,j,k}Y_{j}Y_{k}$いる.

2 の場合, 同型写像 $\phi:R_{G_{1}}arrow R_{G_{2}}$ において,$0$$\phi(X_{i})$と書いたとき,となるようなは複数ある場合は有限体の要素であるから逆元を必ず持つ. そのため, 構成法 1 や構成法 2 の際とがあり,$\beta_{i_{7}j}\neq 0$

またそのような$\beta_{i,j}$

$j$

191
同様の方法ではグラフの同型写像を得られない. したがっ環が同型のときグラフも同型であるかどうかは自明

て,

ではない.

しかしながら,この構成法について次の結果を得た.

定理 $.1. グラフ
が同型のとき, かつその時に限り, 構成法 3 により作られた環 $Rc_{1},$が同型である.
$G_{1},$

また,$\phi$(X,Xj) ただし$(i,j)$$($

であり,$\phi(X_{i}X_{j})=\phi(X_{i})\phi(X_{j})$について,$E_{1})$$\not\in$が定数項$\phi(X_{i}),\phi(X_{j})$を持たず-次以上の項しか持たないことから,
は二次の項しか持たない. したがって,ように書ける.

$\phi(X_{i}X_{j})$$\phi(X_{i}X_{j})$は次の$G_{2}$$R_{G_{2}}$

証明.

以下.

$\phi(X_{i}X_{j})=\sum_{(k_{1}l)\not\in E_{2}}\delta_{i,j,k,l}Y_{k}Y_{l}$以上により主張は示された.

$c_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ から構成法

3 により作られた環を,R2 と書く.
グラフとが同型であるとき, グラフの同型写像が自然に導く環の同型写像によりと R2 が同型となるのは明らかである.
$G_{1}$$R_{1}$$G_{2}$

系$\theta.4$$R_{1}$

逆に,から R2 への同型写像が存在すると仮定
このとき,とが同型であることを示す.
まず, 一般性を失わずにとの頂点数は等しいとして良い. なぜなら,との頂点数が等しくない場
合は,と R2 が同型にはならないことが簡単に分かる$R_{1}$

する.

$G_{1}$$G_{1}$と$G_{2}$$\phi^{-1}(Y_{i})=\sum_{1\leq j\leq n}\beta_{i,j}’X_{j}+\sum\gamma_{*j,k}’\prime X_{j}X_{k}(j,k)\not\in E_{1}^{\cdot}(1\leq i\leq n)$$G_{2}$の頂点数を $n$ とおく. R2 におけ

注 3.2. 同型写像の定義より,$\phi$$Y_{1}$, ...,$Y_{n}$と表記する.

主張 35. 任意の $(i,j)\not\in E_{2}$ について,$\{\phi(X_{k}X_{l})|(k,l)\not\in E_{1}\}$ の線形結合で書ける.
証明.

$Y_{i}Y_{j}$は系 3.4 より,は次の条件を満たすことに注意する.

$\phi^{-1}(Y_{i}Y_{j})=\sum_{(k,l)\not\in E_{1}}\delta_{i,j,k_{J}l}’X_{k}X_{l}$$\{\phi(1),\{\phi(X_{i})\}_{1\leq i\leq n},\{\phi(X_{i}X_{j})\}_{(i,j)\not\in E_{1}}\}$

が$R_{2}$において基底をなしている. したがって, これらは線形独立である.

.

$((i,j)\not\in E_{2})$$\phi^{-1}(Y_{i}Y_{j})=\sum_{(k_{t}l)\not\in E_{1}}\delta_{i,j,k,l}’X_{k}X_{l}$$G_{2}$

る変数 $X_{1},\ldots,X_{n}$ を区別のため.

$\phi^{-1}(1)=1$$\phi$$R_{1}$$G_{1}$

は以下のような形をしている.

$\phi^{-1}$$G_{2}$$G_{1}$

からである.

.

口と書けるから,$\phi$を両辺に作用させると,$Y_{i}Y_{j}= \sum_{(k,l)\not\in E_{1}}\delta_{i,j,k,l}’\phi(X_{k}X_{l})$$\phi(X_{t})\phi(X_{j})=\phi(X_{i}X_{j})$が成立している.

主張 3.3. 同型写像 $\phi:R_{1}arrow R_{2}$ は以下のような形をし

口

ている.

を若干変更して次のような写像$\phi$$\phi(1)=1$$\phi(X_{i})=\sum_{1\leq j\leq n}\beta_{i,j}Y_{j}+\sum_{(j,k)\not\in E_{2}}\gamma_{i,j,k}Y_{j}Y_{k}$$(1\leq i\leq n)$$((i,j)\not\in E_{1})$$\phi(X_{1}X_{j})=\sum_{(k,l)\not\in E_{2}}\delta_{i_{\{}j,k_{i}l}Y_{k}Y_{l}$$\phi’(X_{i}X_{j})=\sum_{(k,l)\not\in E_{2}}\delta_{*,j,k,l}Y_{k}Y_{l}$

任意の$X_{i}$について,$\phi(X_{i})$$X_{1}$という形で書けるはずである.
とを利用すると,$=\phi$(X?)$=\phi$(Xi)2$R_{1}$$=\alpha$

上で $X_{i}^{2}=0$ であるこの写像先のみ,$\phi(X_{i})$$+$(一次以上の項)$\phi$

から二次の項主張 3.6.
証明.

i2$((i,j)\not\in E_{1})$は,$\phi(X_{l})=\alpha_{i}+\sum_{1\leq j\leq n}\beta_{i_{t}j}Y_{j}+\sum_{(j,k)\not\in E_{2}}\gamma_{i,j,k}Y_{j}Y_{k}$0: $R_{1}arrow R_{2}$ を作$\phi’(1)=1$$(1\leq i\leq n)$$\phi’(X_{i})=\sum_{1\leq j\leq n}\beta_{i,j}Y_{j}$証明.

$\phi’$

ることができる.

$\phi’$

も$R_{1}$と$\phi’$$Y_{k}Y_{l}$は異なっており,$\phi’(X_{i})$は,が省かれている.

から R2 への同型写像である.

について, 注 3.2 の各性質が満たされているかどうかをチェックすれば良い.
まず, 線形独立性について確かめる. $\phi’(X_{i})$ は,から $Y$ の二次の項臨を除いたものであるが, 主張 3.5
よりは $\{\phi(X_{i}X_{j})\}$ の線形結合で書けるから,は (X のから $\{\phi(X_{k}X_{l})\}$ の線形結合を除いたものであ$\phi’$$\phi(X_{i})$より $\alpha_{i}=0$ である.

したがって,$\phi(X_{i})$は次のように書ける.

$Y_{l}$$Y_{k}Y_{l}$$\phi’(X_{i})$$\phi$$\phi(X_{i})=\sum_{1\leq j\leq n}\beta_{i,j}Y_{j}+\sum_{(j_{Z}k)\not\in E_{2}}\gamma_{i,j,k}Y_{j}Y_{k}$るといえる.

したがって線形独立性は保たれる.

192
また. $\phi’(X_{i})\phi’(X_{j})=\phi’(X_{i}X_{j})$ が満たされることは,主張 3.9.

と $S’\subset$ 巧について,$s\subset v_{1}$$\phi’(x_{i}x_{j})=\phi(x_{i}x_{j})=\phi(x_{i})\phi(X_{j})=\phi’(x_{i})\phi’(x_{j})$となることより確かめられる.
も以上によりから R2 への同型写像である.
$\phi’$

注 3.7.

$\phi^{\prime-1}$$|S|\leq|j_{\phi}(S)|$$|S’|\leq|f_{\phi^{-1}}(S’)|$口$R_{1}$

は以下のようになることが容易に分かる.

が成立する.

証明.

前者のみ示す.

$\{Y_{j}|j\in\phi(S)\}$

したがって,$\phi^{-1}(1)=1$

主張 3. $10$$\phi^{-1}(Y_{i})=\sum_{1\leq j\leq n}\beta_{j}’X_{j}$$|S|\leq|\phi(S)|$.

$S\subset V_{1}$でなければならない.

口と $S’\subset V_{2}$ について,$f_{\phi-1}(f_{\phi}(S)))\supseteq S$$((i,j)\not\in F_{2}\lrcorner)$$\phi^{-1}(Y_{i}Y_{j})=\sum_{(k_{l}l)\not\in E_{1}}\delta_{i,j,k,l}’X_{k}X_{l}$$\{\phi(X_{i})|i\in S\}$ はそれぞれがの線形結合でかけ, かつ線形独立である.

$f_{\phi}(f_{\phi-1}(S’)))\supseteq S’$

以降は, 議論を簡単にするため,$\phi’$をあらためて$\phi$

と

置く.

を用いた,

$\phi$$f_{\phi}:2^{V_{I}}arrow 2^{V_{2}}$の点集合からの点集合への写像を以下のように定義する.
$G_{1}$$G_{2}$

が成立する.

証明.

前者のみ示す.

$i\in S$について,$\phi(X_{i})=\sum_{k\in f_{\phi}(S)}\beta_{i,k}Y_{k}$$f\phi(S)=\{j|i\in S, \beta:_{1}j\neq 0\}$

と書ける.
これは,

$G_{1}$の点集合 $s$ から, $rs$ に含まれるを$x_{i}$$\phi$

した先に現れる巧」の点集合へ写像するものである.
れと同様に$f_{\phi^{-1}}$:$2^{V_{2}}arrow 2^{V_{1}}$

これより,

で写
こ

$X_{i}= \sum_{k\in f_{\phi}(s)}\beta_{i,k}\phi^{-1}(Y_{k})$を以下のように定義する.
となる. したがって, ある $k\in f_{\phi}(S)$ においてである (つまり $\phi^{-1}(Y_{k})$ の値にが現れる). したがっ$\beta_{k,i}’\neq 0$$f_{\phi^{-1}}(S’)=\{J|i\in S’,\beta_{i,j}’\neq 0\}$

主張 3.8.

$C\subset V_{1}$が$G_{1}$

上クリークであるとき,は G2 上クリークである.

リークであるとき,

$i$

同様に,

$f_{\phi-1}(C’)$

は$C’\subset V_{2}$$G_{1}$がて,$i\in f_{\phi-1}(f_{\phi}(S))$,j$\in\phi$$G_{2}$

上ク

上クリークである.

(C) ただし $i\neq j)$ について,$($

系 3.11.

$(i,j)\in E_{2}$$G_{1}$

上の極大クリーク $c$ と$\beta_{k,i}\neq 0$

かつ $\beta_{k,j}\neq 0$ となる$f_{\phi-1}(f_{\phi}(C)))=C$

1 の場合,

上の極大クリーク $c$ について, $f\phi(C)$ は上の極大クリークであり, $|C|=|f_{\phi}(C)|$ が成立する.
同様に,上の極大クリーク $C’$ について, $f_{\phi^{--1}}(C’)$ は$\phi(X_{k}^{2})$であり,$G_{1}$の値は次のように書ける.

$G_{1}$($Y_{i}Y_{j}$$2\beta_{k,i}\beta_{k,j}\neq 0$を含まない項)であるから,

証明.

$Y_{i}Y_{j}=0$

ら.

$\beta_{k,i}\neq 0,$$\beta_{l.j}\neq 0$となる $k,\downarrow\in c$ を取っての値は以下のようになる.

$\phi(X_{k}X_{l})=\beta_{k_{2}i}\beta_{i.j}Y_{1}Y_{j}+$($Y_{i}Y_{j}$が成立

前者のみ示す.

$f_{\phi^{-1}}(f\phi(C)))=c$$c$は極大クリークであるかが成立する.

$G_{2}$$C^{*}$$c\cdot\supseteq f_{\phi}(C)$な$f_{\phi^{-1}}(C^{*})\supseteq$$|C|\leq|f_{\phi}(C)|\leq|C^{*}|\leq|f_{\phi-1}(C^{*})|=|C|$を含まない項)がクリークであるから $\phi(X_{k}X_{l})=0$ であり,であるから, $Y_{1}Y_{j}=0$ である$|C’|=|f_{\phi-1}(C’)|$上の任意のクリークについて,$f_{\phi^{-1}}(f_{\phi}(C))=C$ であり, $c$ が極大であることにより$f_{\phi-1}(C^{*})=C$ である.
ここで主張 39 を用いると,る$\phi(X_{k}X_{l})$上の極大クリークであり.

する.

である.

$0$

主張 3.12.

$G_{2}$$\phi(X_{k}^{2})=2\beta_{k,i}\beta_{k_{1}j}Y_{i}Y_{j}+$$c$$f_{\phi}(f_{\phi^{-1}}(C’)))=C’$$G_{2}$

2. そうでない場合

2 の場合,

上の極大クリーが成立する.

場合

くると,$G_{2}$であの 2 つの場合に分けて考える.

$\phi(X_{k}^{2})=0$

口ク $C’$ について,ること, すなわち $Y_{i}Y_{j}=0$ であることを示せばよい. 次

1. ある $k\in C$ においてである

$f_{\phi}(C)$

前者のみ示す. 後者も同様にして示される. 任意

証明.
の$x_{i}$$\beta_{k,i}\beta_{k,j}\neq$$\square$となるので, 上式中の不等号は実際には全て等号である
ことが分かる. したがって $|f\phi(C)|=|C^{*}|$ より $f_{\phi}(C)$ は極大クリークであり,$|C|=|f_{\phi}(C)|$が成立する$\square$193
系 313.

上の極大クリーク $c$ と$G_{1}$$G_{2}$

上の極大クリーク $C’$ について.
$f\phi(C)=C’\Leftrightarrow f_{\phi^{-1}}(C’)=C$

像を多項式時間で計算できることが示される.

が成立する.

定理 4.1. グラフ $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ が同型

これより,
と

$f_{\phi}(C)=C’$という$G_{1}$

上の極大クリーク上の極大クリーク $C’$ の関係は, 一対一の対応関係であることが簡単に分かる. この対応関係から,$c$$G_{2}$$G_{1}$の極大クリークの総数と$G_{2}$

極大クリークの総数は等し

いことになる.

以下,
グラフ$G_{1}$

今回の構成法 3 における環の同型写像は直接的に対し,にはグラフの同型写像を表していない. しかし, 構成法
3 から得られた環の同型写像からでも, グラフの同型写と$G_{2}$の極大クリークの総数を とする. また,$l$の極大クリークを $c_{1},c_{2},c_{3},$とし,の極大クリークをとし, $f_{\phi}(C_{i})=C_{i}’$が各 で成立しているとする.
$G_{1}$$\ldots,c_{l}$$c_{1}^{J},c_{2}’,c_{3}’,$$G_{2}$$1\leq m\leq n$ なる任意の $m$ で,と$R_{G_{1}}$$R_{G_{2}}$の任意の同型写像 $\phi;R_{G_{1}}arrow Rc_{2}$ が与えられたとき, 多項式時間でグラフの同型写像 $\pi:V_{1}arrow V_{2}$ を計算できる.
証明.

定理 3.1 の証明中と同様にををR2 と略記し?
$C_{i}(1\leq i\leq l)$ といった記号も,$R_{1},$$R_{G_{1}}$$R_{G_{2}}$$f\phi,$$\beta_{t,j},$

先と同様のものを指すものとする.

証明の準備として新たな記号の定義を行う.

$\ldots,c_{\text{\’{i}}}$$i$

主張 3.14.

であるとする. 構成法 3 により作られた環$\{1,$$\ldots$

弓に対して$P_{S}$$1\leq j_{1}<$$P_{S},Q_{S}$$s\subseteq$

を次のように定義する.

$=$$\{\bigcap_{:\in s}c_{:1\cap\{\bigcap_{i\not\in S}\overline{C_{1}}\}}$$...<j_{m}\leq n$ において,$Q_{S}$$=$$\bigcap_{:\in S}C_{1}$$| \bigcup_{i=1}^{m}C_{j_{i}}|=|\bigcup_{=1}^{m}C_{j}’:|$

も同様に定義する. 例えば,

$P_{S}’,Q_{S}’$が成立する.

$P_{\{1,4\}}=C_{1}\cap\overline{C_{2}}\cap\overline{C_{3}}\cap C_{4}$証明.

$m=1$ の場合は, 主張 3.12 において既に示されている. $m=2$ の場合を考える. $\{\phi(X_{i})|i\in c_{j_{1}}\cup c_{j_{2}}\}$

が線形独立になるためには,であり,$l=4$ のとき,
$Q_{\{1_{2}4\}}=C_{1}\cap C_{4}$

である.
今,

$G_{1}\cong G_{2}$であるから, 任意の $S\subseteq\{1, \ldots,l\}$ において次が成立する.
$|P_{S}|$$=$$|P_{S}’|$$|Q_{S}|$$=$$|Q_{s}’|$$|C_{j_{1}}\cup C_{j_{2}}|\leq|C_{j_{1}}’\cup C_{j_{2}}’|$

でなければならない. 同様な議論を逆方向から行えば,また, 定義より $Ps$ と $Q_{S}$ の関係として次の式が成立する.
$|C_{j_{1}}\cup C_{j_{2}}|\geq|C_{j_{1}}’\cup C_{j_{2}}’|$

でなくてはならないことが分かる. すなわち,$Q_{S}= \bigcup_{\tau\supseteq s}P_{S}$$|C_{j_{1}}\cup C_{j_{2}}|=|C_{j_{1}}’\cup C_{j_{2}}’|$$P_{S}^{t}$である. $m>2$ の場合も同様にして示される.
これは,$G_{1}$の極大クリークの構造と,$G_{2}$

ロの極大クリークの構造が完全に一致していることを示している.
したがって,$G_{1}\cong G_{2}$である$\square$と$Q_{\acute{S}}$の間でも同様の関係が成り立つ.

主張 42. 全単射写像 $\pi:V_{1}arrow V_{2}$ について,らば$\pi(i)\in P_{\acute{S}}$となっているとき,$\pi$$i\in Ps$ なはグラフの同型写

像である.

証明.

$i\in P_{S}$と $j\in P_{T}$ に対し,$(i,j)\in E_{1}$のとき, またそのときに限り $(\pi(i),\pi(j))\in E_{2}$ であることを示せばよい.

4環の同型写像からのグラフの同型写像の構成ここで,構成法 3 によりグラフから作られた環の同型

写像が与えられたとき, そこからグラフの同型写像を構成できるか, ということを考える.
前述の通り, 以前の構成法 1 と構成法 2 において, 環の同型写像はグラフの同型写像を直接的に表しているの$(i,j)\in E_{1}$ であるとき,$S\cap T$

は空集合でない. なぜなら $(i,j)$ という辺を含んだ極大クリークが少なくともーっ

存在するからである. 今, $\pi(i)\in$ 塔かつ
り,

$\pi$

(D

$\in$

P 暢であ

さらに $S\cap T$ が空でないのだから $(\pi(i),\pi(j))\in E_{2}$

である.

同様に,
$i)$

で
る
である

$P_{S}’$$(i,j)\not\in E_{1}$であるとき,$S\cap T$

は空集合であり.

かつ $\pi(j)\in P_{T}’$ であるから,$\hslash$$(\pi(i),\pi(j))\not\in E_{2,\square }$194
主張 4.3. 任意の $i\in V_{1}$ について,ば,である.

$i\in P_{S}$証明.

となる任意の$k\in S$$k$

同型写像 $\phi:R_{1}arrow R_{2}$ は複数のグラフの同型写像の情報を含んでいる可能性がある. なぜなら,について,$\{i\}\subseteq C_{k}$ることより $f_{\phi}(\{i\})\subseteq\phi(C_{k})=C_{k}’$ となる.
$f\phi(\{t\})\subseteq Q_{\acute{s}}$

に,

であるなら

$f_{\phi}(\{i\})\subseteq Q_{S}’$であしたがって,

である$V_{1}$

から$V_{2}$

へのマッチングの解は複数個ある可能性があり, それらは全てグラフの同型写像となっているからである.

$\square$主張 44. 任意の同型写像 $\phi:R_{1}arrow R_{2}$ が与えられた
とき, 任意の で $\beta_{:,\pi(i)}\neq 0$ である (すなわち $\pi(i)\in$

5

まとめと今後の課題$i$$f_{\phi}(\{i\})$である)

ような全単射写像:$\pi$$V_{1}arrow$

脇は,グ

ラフの同型写像となっている.
において, $i\in P_{S}$ ならば (i)P\’{s}という事象を $(*)$ と略記することにする. 主張
42 より, 任意の $S\subseteq\{1, \ldots l\}$ で $(*)$ が成立することを示せば良い. 仮定より, $i\in P_{S}$ について $\pi(i)\in f\phi(\{i\})$ であり, 主張 4.3 よりであるから, $\pi(i)\in Q_{S}’$が成立している事に注意し. 帰納法により証明する.
$s=\{1, \ldots,l\}$ とする. このとき,
であるか

証明.

$s\subseteq\{1, \ldots,l\}$

$\pi$

$\in$

である,

$f_{\phi}(\{i\})\subset Q_{\acute{S}}$$Q_{\acute{S}}=P_{S}’$ら,$i\in P_{S}$について $\pi(i)\in Q_{S}’=P_{s}’$ となり $(*)$ が成立する.
$s\subseteq\{1, \ldots,l\}$について,の $Y\supseteq\{1, \ldots,l\}$ で $(*)$$i\in Ps$

$T\supsetarrow s$となるような任意が成立していたと仮定する.

について,巧の各点について,

$\pi$

なる

$P_{T}’$に含まれるによる防の点との対応付けが既に決まっているから, 結局い.

$\tau\supsetneq s$$\pi(i)\in P_{\acute{S}}$でなければならな

したがって $(*)$ が成立する

任意の$\pi:V_{1}arrow$

で $\pi(i)\in f_{\phi}(\{i\})$ となるような全単射写像
砺を計算する問題は, 2 部グラフ完全マッチン$i$$i\in V_{1}$と $j\in$ 巧が $j\in f_{\phi}(\{i\})$ のときに限り辺で繋がれているような,を頂点集合とする 2 部グラフ上で, 完全マッチングを行うのと同値である. ここで, 主張 44 はそ$V_{1}\cup V_{2}$の完全マッチングはグラフの同型写像を導くことを示し
また, 任意の $S\subset V_{1}$ について,$|S|\leq|f_{\phi}(S)|$Haii の定理 [4] より,
少なくとも一つ完全マッチングが存在することが保証さであったから (主張 3.9 による),れる. また, 2 部グラフの完全マッチングは, 多項式時間で計算することが出来る [5].
以上より, 環の同型写像 $\phi:R_{1}arrow R_{2}$ からグラフの同型写像 $\pi:V_{1}arrow V_{2}$ を多項式時間で計算することが出来ることが示されたては, 環の同型写像から多項式時間でグラフの同型写像を計算することができるだけでなく, 複数のグラフ同型
写像の情報を含んでいる可能性があることも示した.
今後の課題としては, 環同型問題とグラフ同型問題の難しさの関係を解明する上で, 環同型問題からグラフ同型問題への逆向きの帰着は可能なのか, ということが未解決の問題として残されている.

た上で環同型性判定を効率的に解くことができるような量子アルゴリズムが存在するならば, グラフ同型問題も量子計算機上で効率よく解けることになる.

$\square$グの問題であるとみなすことが出来る. すなわち,ている.

の同型性が同値であることを示した. また, 既知の構成法において, 環の同型写像はあるーつのグラフ同型写像
を直接含んでいるのに対し, 今回の新しい構成法においまた, 量子計算機上において, 環同型問題を効率的に解くことができるのか. という問題も未解決である. また, 一般の環では難しくとも, 帰着で利用される環に限っ$\pi(i)\in Q_{S}’=\bigcup_{T\supset S}P_{T}’$であるが, 帰納法の仮定より

本論文では. グラフ同型問題から環同型問題への帰着
グラフから環の構成方法について, 既知の 2つの構成法 [3, 2] よりも自然でシンプルな第 3 の構成法を考案し, その構成法においても, グラフの同型性と環
における,

口

注 4.8. 構成法 1, 構成法 2 における環の同型写像は唯一つのグラフ同型写像の情報を含んでいた. しかし, 今
回の構成法 3 の場合, 定理 41 の証明から明らかなよう

参考文献[1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in P. Annals of Mathematics, Vol.
160, No. 2, pp. 781-793, 2004.
$[$

2] Manindra Agrawal and Nitin Saxena. Automorphisms of finite rings and applications to complexity of problems. STACS 05, Springer LNCS 3404,

pp. 1-17. Springer Verlag, 2005.
[3] Neeraj Kayal and Nitin Saxena. Complexity of ringmorphism problems. Comput. Complex., Vol. 15,
No. 4, pp. 342-390, 2006.
[4] Reinhard Diestel. Graph Theory, Vol. 173 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, 3rd edition, 2005.
[5] Thomas Cormen, Charles Leiserson, and Ronald
Rivest. Introduction to Algorithms. The MIT
Press, Cambridge, MA, 1989.