2-5 複雑系への組合せ論および計算論からのア
プローチ
●代表者

斎藤 明（情報システム解析学科・教授）●分担者

鈴木 理（情報システム解析学科・教授）
戸田誠之助（情報システム解析学科・教授）【研究の目的および概要】
複雑系は自然科学，社会科学に現れる現象やシステムを記述する理論的なモデルの 1 つである。得られるモデルは本質的に連続系であり，従来の研究では微分方程式として記述され，解析的な手法で調べられてきた。しかし系が複雑になると，得られる微分方程式も複雑になり解析的な取り扱いが難しくなる。そのような場合，離散化とよばれる手法がとられる。これはモデルから得られた微分方程式を，離散方程式で近似することである。離散化により得られた離散方程式については，解の挙動を計算機上でシミュレートすることができる。従って解析的な取り扱いができない場合でも，実験的に挙動を調べることができる。
しかしながら，離散化によって問題の本質的な難しさが解消されるわけではない。シミュレーションによる実験から，解の挙動に関する予想を立てることは可能である。しかしその予想を理論的に証明する際には，本来の連続系と同程度の困難さが伴うことが多い。また解析学の長い歴史に比べ，離散数学の歴史は浅く，そのため研究の道具となる理論の整備も解析学に比べて遅れている。このため離散化することにより，逆に解析学の豊富な手法を利用できなくなり，理論的な解析がむしろより困難になることもある。このように離散化は計算機の利用の面からの利点がある一方，理論的な扱いにはかえって不利となることもある。
また計算機実装には計算量的な困難が発生することもある。初めに得られる微分方程式が複雑であると，それを離散化して得られる離散方程式も複雑になる。離散化されているので，計算機上で実装することは可能だが，実行に莫大な資源（時間，メモリ）が必要となり，事実上実行不可能となることもある。
こうした背景を踏まえ，本研究は複雑系から得られる離散方程式の分析に必要な組合せ論，計算論の手法を進展させることを目的とした。
研究にあたり，組合せ論に関しては斎藤が，計算論に関しては戸田が手法の開発に努めた。鈴木は複雑系の専門家として，斎藤，戸田に必要となるモデルや微分方程式の提供を行った。6 月まで研究分野のレビューを行い，対象となる問題を具体的に見定め，7 月以降その解決を試みた。
上記研究で離散化され，コンピュータ上でシミュレートされる解の中には可視化できるものも多い。可視化された解は高校生の理系への興味を引き起こす材料となる可能性がある。そこでコンピュータ教育の専門家であるリトアニア，ヴィルニュス大学の Dagiene 教授が来日した際に講演を依頼し，研究情報の交換を行った。
【研究の結果】
離散化された問題は，いくつかの対象間の 2 項関係として表現されることが多い。2 項関係はグラフとして扱うことができるので，斎藤は得られる問題にグラフ理論からアプローチした。与えられた連結グラフ H に対して，Hと同形なグラフを誘導部分グラフに含まないようなグラフは H- フリーグラフ，あるいは H を禁止されたグラフとよばれる。また複数のグラフ H1,…,Hkの全ての Hi について Hi- フリーとなるグラフを {H1,…,Hk}- フリーグラフ，

あるいは {H1,…,Hk} を禁止されたグラフとよぶ。定式化される問題は，いくつかのグラフを禁止した状況で 2- 正則な全域部分グラフが存在するかどうかを問う問題に帰着された。今回の研究の結果，禁止することにより 2- 因子の存在が（有限個の例外を除いて）保証されるような禁止部分グラフのペアを決定した。
またこのような禁止部分グラフの研究では，帰結の有限個の例外を許すことが多い。それは，単に位数が小さいという理由により，禁止部分グラフの条件を満たすものがあり，これらは問題と本質的に関係しないためである。

21ところがいくつかのグラフ H1,…,Hk を禁止すると，{H1,…,Hk}- フリーグラフ全体の成す集合が有限集合となることがある。このような場合，それら全てを「有限個の例外」とすることにより，全ての性質が満たされてしまう。これでは特定の性質に知見が得られたとは言えない。そこで，このように {H1,…,Hk}- フリーグラフが有限集合となる場合を研究し，多くの必要条件，十分条件を得た。また連結度が 6 以下の場合に，3 個以下のグラフを禁止して有限集合を得る場合を完全に特定した。
一方，いくつかの問題はスター因子の存在問題に帰着した。スター因子とは各成分がスター（一方の部集合の位数が 1 であるような完全 2 部グラフ）である全域部分グラフである。与えられた正整数 k について最大次数が k 以下のスター因子が存在するための必要十分条件は，k=1 ついては Tutte が 1954 年に，k ≧ 2 については Amahashi-Kanoが 1980 年に与えた。しかし今回帰着された問題は位数の小さい成分の存在を認めない形になっており，従来の結果は適用できなかった。そこで小さい位数の成分を許さないような形で帰納法をかける道を探り，2 ≦ m < n なる
2 つの整数 m, n について，各成分の位数が m 以上 n 以下となるようなスター因子の存在を保証する十分条件を得た。
残念ながらこれは必要十分条件ではないが，定理の中に現れるいくつかの値について，その最良性を示すこともできた。
一方戸田は計算理論の成立過程を文献調査を通して分析し，1971 年の Cook の論文を境として，その前後で研究主題，学問的方法論ともに分断されていることを明らかにした。これは，本研究に寄与する計算論的研究は 1971年以降のものに限定して良いことを示唆している。
【研究の考察・反省】
本研究により，複雑系から得られるいくつかの離散的な問題の中で，主にグラフ理論に帰着するものについて，いくつかの知見が得られた。特に禁止部分グラフに関しては，禁止する部分グラフの個数が少ない場合について，2- 因子の存在が保証される場合，得られる集合が有限集合となる場合を完全に決定することができた。計算論的な側面については，利用できる研究の年代を特定することができた。とはいえ，1 年間の研究では解決できなかった部分も多い。例えば，禁止部分グラフについては，禁止するグラフの個数が増えていくと，状況は急速に不明瞭になる。特に 4 個以上のグラフを禁止した場合のグラフの振る舞いについては，2- 因子，有限性ともほとんど不明である。また離散化される問題の中にはグラフ理論に帰着しないものも数多い。それらについては，今回の研究では手が回らなかった。また計算論的なアプローチについては，使うことのできる研究の年代を特定することはできたが，具体的な問題の解決には至らなかった。
本研究の教育への活用も課題として残る。リトアニア，ヴィルニュス大学の Dagiene 教授との意見交換により，本研究も高校教育における良い題材となり得る感触を得た。しかし時間的な制約から実証実験を行うことができず，結果としてまとめることはできなかった。今後は個人研究，科研費研究などに研究の場を移して，研究を進めていきたい。
【研究発表】（1）O. Suzuki, “Binary and ternary Clifford analysis on Nonion algebra and su（3）” , The 9th. International ISSAC
Congress, 2012 年 8 月 6 日 , Pedagogical Univeristy in Krakow, Krakow, Poland.
（2）鈴木理，“オートマトンを用いたべき則揺らぎの生成可能性について”，研究集会「サリスエントロピーの最近の発展」，2012 年 11 月 12 日，京都大学数理解析研究所（3）鈴木理，“絶滅の生態系（Haldane をめぐって）”，数理生物学研究集会，2012 年 12 月 11 日，京都大学数理解析研究所

22

（4）鈴木理，“安定同位体比に基づく国産米の産地特定”，応用数学合同研究集会，2012 年 12 月 17 日，龍谷大学（5）Akira Saito, “Forbidden subgraphs generating a finite set”（招待講演），The 5th. International Workshop on Optimal
Networks Topologies, 2012 年 7 月 27 日 , Bandung Institute of Technology, Bandung, Indonesia.
（6）斎藤明，“Star-factors with large components”，日本数学会秋季総合分科会，2012 年 9 月 19 日 , 九州大学

（7）斎藤明，“The local Chvatal-Erdos condition and 2-factors in graphs”，日本数学会年会，2013 年 3 月 20 日，京都大学【研究成果物】（1）B.Kerner and O.Suzuki, Internal symmetric groups of cubic albebra, to appear in International Journal of Modern
Method in Mathematics Physics.
（2）J.Lawrynowics, K.Nouno and O.Suzuki, A method of non-commutative Galois theory for Nonion algebras and its
application to the construction of quark models, Proceedings of The theory of Micro and Macro Duality in Statistical
Mechanics, 2012.
（3）J.Lawrynowicz, K.Nouno and O.Suzuki, A method of non-commutative Galois theory for binary and ternally Cliffors
analysis, to appear inProceedings of 9th. Confegress of ICNAPP, 2012（4）H.Bruhn and A.Saito, “Clique or hole in claw-free graphs”, Journal of Combinatorial Theory, Series B, 102（2012）
1-13.
（5）M.Kano, Y.Egawa, A.Kyaw, H.Matsuda, K.Ozeki, A.Saito and T.Yamashita, “Spanning trees with a bounded number ofleaves in a claw-free graph”, Ars Combinatoria 103（2012）137-154.
（6）G.Chen, Y.Egawa, R.J.Gould and A.Saito, “Forbidden pairs for k-connected hamiltonian graphs, Discrete Mathematics
312（2012）938-942.
（7）G.Chen, K.Ota, A.Saito and Y.Zhao, “Hamiltonian cycles with all small even chords” , Discrete Mathematics 312（2012）1226-1240.
（8）J.Fujisawa and A.Saito, “A pair of forbidden subgraphs and 2-factors”, Combinatorics, Probability and Computing 21（2012）149-158.
（9）M.Kano and A.Saito, “Star-factors with large components”, Discrete Mathematics 312（2012）2005̶2008.
（10）J.Harant, A.Kemnitz, A.Saito and I.Schiermeyer, “Closures, cycles and paths”, Journal of Graph Theory 69（2012）314-323.

23