本論文は5章からなり、第1章は問題の概要、第2章は定義および既存の方法についての説明、第3章はネットワーク信頼性への応用、第4章は結び目理論への適用、第5章はフロー多項式について述べられている。 Tutte多項式とはグラフ理論における基本的な不変量を表わす多項式であり、様々な分野に応用することができる。例えば、頂点を彩色する方法が何通りあるかを表わす彩色多項式と関係があるほか、与えられたグラフの全域木の数や森の数を表わすことが知られている。さらに結び目理論で有名なJones多項式やネットワーク信頼性、統計物理学のモデルなどとも関連している。 しかしながら、一般にTutte多項式を計算する問題は#p-困難に属する問題で、単純に定義式から計算したのでは、ごく小さいグラフに対してしか実際に計算することができない。この論文では、Tutte多項式をはじめとする幾つかの不変量を表わす多項式の計算方法について模索し、それらが中規模のグラフ等に対しても正確に計算できることを示す。 第2章ではまず最初に定義および再帰公式から単純に計算する既存の方法では、その計算量が全域木の数に比例してしまうことを示す。次にTutte多項式の重複計算を省くアルゴリズムについて考察をおこない、より大きなグラフのTutte多項式も計算できるようなアルゴリズムを提示する。具体的には以下の通りである。まず、Tutte多項式は辺の削除・縮約を再帰的に繰り返すことによって計算することができる。その際、同型なグラフが数多く生じるが、それらについて別々に再帰的計算を繰り返すのは冗長であるので、まとめて計算をおこなうことにする。このときグラフの同型判定をおこなう効率のよいアルゴリズムは知られていないため、ここでは与えられたグラフの辺に順序を付け、辺の順序も含めて同型なグラフを判定する効率のよい方法を示し、これを用いる。この方法をもとに辺の順序も含めて同型なグラフをすべて統一し、重複する計算を省くというのがアルゴリズムの概略である。さらにこの方法が、与えられたグラフのすべての全域木を表わす二分決定グラフと関連があることを示す。また、このアルゴリズムを用いた場合と既存の方法により計算した場合の計算量の比較をおこなう。 第3章ではこのアルゴリズムのネットワーク信頼性への応用について考察する。最近、ネットワーク信頼性については、ランダム化を用いた近似解法を用いる例が多くみられる。ここではTutte多項式を計算するアルゴリズムを応用することによって、各枝の消滅確率が異なる一般の場合の全端子間および2端子間ネットワーク信頼性の計算が、近似ではなく正確に(exactly)できることを示す。次に、完全グラフの信頼性について考察する。一般の単純グラフは頂点数の同じ完全グラフから辺を削除したものと考えることができるため、完全グラフの信頼性の値は一般の単純グラフの信頼性の値の上限値を示している。ところが上記のアルゴリズムによる計算においては、辺の数が多いため一般の単純グラフよりも計算が複雑となる。そこで完全グラフの信頼性を正確に計算する効率のよい方法が存在すること、およびその計算結果を示す。 第4章ではこのアルゴリズムの結び目理論への応用について考察する。交代絡み目のJones多項式の値とTutte多項式の値とが関係していることはすでに知られているが、ここでは一般の絡み目のJones多項式の計算に上記のTutte多項式を計算するアルゴリズムが応用できることを示す。Jones多項式の計算は平面グラフのTutte多項式の計算に対応しているため、このアルゴリズムを用いての計算が特に有効となる。ここでは、交点数140以上の絡み目のJones多項式の計算が可能となる例を示す。 第5章では再帰公式を用いた計算アルゴリズムからはやや離れて、フロー多項式の分解について述べる。フロー多項式は2変数多項式であるTutte多項式を1変数に制限したものであり、彩色多項式とも密接な関係をもつ。具体的には、2辺および3辺切断、2頂点および3頂点切断に関してフロー多項式の分解が成り立つことを示す。また、これらの分解を用いて未解決問題であるTutteの予想について考察する。さらに同型ではないどのようなグラフが同一のフロー多項式をもつかということについても考察する。 なお、第2章は今井浩、谷誠一郎との、第5章はC.Q.Zhangとの共同研究であるが、論文提出者が主体となって展開しまとめたものであり、論文提出者の寄与が十分であると判断する。 よって、博士(理学)の学位を授与できると認める。 |