絡み目の不変量 カウフマンブラケット多項式 の効率的な実装

Presentation on theme: "絡み目の不変量 カウフマンブラケット多項式 の効率的な実装"— Presentation transcript:

1 絡み目の不変量 カウフマンブラケット多項式 の効率的な実装
平成13年2月7日(水) 澤木　俊明 加藤　正朗

2 概要 結び目とはゴムのように伸び縮みする輪のようなもので、結び目理論とは絡まった輪を切らずにほどくことができるかどうか？というようなことを考える学問です。 ?

3 これらの問題は結び目理論の基本的なテーマである。
二つの結び目が同じであるか？ （ 二つの絡まった輪の一方を もう一方と同じ形にできるか ） 結び目が自明な結び目か？ （ 絡まった輪をほどけるか ） これらの問題は結び目理論の基本的なテーマである。 今回の成果 ある結び目理論に関連する問題を解くプログラム制作

4 目次 結び目・絡み目の定義 絡み目の不変量 カウフマンブラケット多項式 今回制作したプログラムについて

5 結び目の定義 R 結び目（ Knot ） ： R 内の多辺形 （ 閉じた折れ線 ） 自明な結び目 ： R 内の多辺形と 同型 なもの
3 結び目（ Knot ） ： R 内の多辺形 （ 閉じた折れ線 ） 自明な結び目 ： R 内の多辺形と 同型 なもの 2 位相同型を与える同相写像 全同位変形（ ambient isotopy ） 3 R 内で自分自身を横切らないでひもを動かすようなこと 二つの結び目が同じとは？ 一方から他方へ全同位変形可能 全同位変形 自明な結び目 R 3 結び目 同じ結び目

6 絡み目の定義 絡み目（ Link ） 複数の結び目の輪が絡んでできたもの 結び目は１成分の絡み目 R
絡み目の一つでホワイトヘッド絡み目と呼ばれているものである。これは二本の輪（２つの成分）からできている。 結び目は１成分の絡み目 注 R 3

7 射影図 L で表す 正則射影 ダイアグラム 絡み目 射影 〇 × R R 射影図 ： 結び目を平面に射影した図
射影図 ： 結び目を平面に射影した図 正則射影 ： 多重点が横断的に交わっている二重点のみの射影図 ダイアグラム ： 正則射影に交叉の情報を与えたものであり L で表す ~ 正則射影 ダイアグラム 絡み目 射影 〇 × R 3 R 2

8 ライデマイスター移動 （ Reidemeister move ）
絡み目A 全同位変形 絡み目B ダイアグラムA 射影 ダイアグラムB ? 二つのダイアグラムが同じ絡み目を表すかどうかを判定するための道具 ライデマイスター移動 （ Reidemeister move ） ライデマイスター移動 にはⅠ、Ⅱ、Ⅲ の三つの移動がある

9 ライデマイスター移動Ⅰ ルールⅠ

10 ライデマイスター移動Ⅱ ルールⅡ

11 ライデマイスター移動Ⅲ ルールⅢ

12 両者間を移り合う ライデマイスター移動の 有限列が存在 二つのダイアグラムが 同じ絡み目を表す ダイアグラム A ダイアグラム B
順序？回数？ 二つダイアグラムが互いに移り合うことが可能でもその順序や回数を得るアルゴリズムは知られていない。

13 絡み目の不変量 絡み目の不変量 （ invarinat ） 同じ絡み目に対して必ず同じ値を持つもの.
絡み目の不変量（ 以下、不変量 ） が異なれば 少なくとも同じ絡み目とはいえない 。 例えば、左の絡み目の閉曲線の本数が ３ であるということは 不変量 である。 ある二つの対象を区別するために定義された不変の値 。 右の絡み目の閉曲線の本数も ３ である。 しかし、この二つは違う絡み目である。 このように、閉曲線の本数は絡み目を区別するのにはあまり適さない。

14 カウフマンブラケット多項式（ kauffman bracket polynomial ）
~ 多項式不変量 ジョーンズ多項式（ Jones polynomial ） 有向絡み目 の 多項式不変量 のひとつ ( -A ) < L > -3ω( L ) ~ カウフマンブラケット多項式（ < L > ） 　 に乗算することによって ジョーンズ多項式 を得る。 ジョーンズ多項式 この多項式自体は 不変量ではない が、ω( L ) と組み合わせること によって Jones多項式 が得られる。 カウフマンブラケット多項式（ kauffman bracket polynomial ） < L > : カウフマンブラッケト多項式 ~ ライズ（ writhe ） Jones多項式 を求めるために 有向絡み目 の交点のパラメータを計算したもので、ω( L ) で表す。 ~

15 目標 我々は ジョーンズ多項式 という有向絡み目の不変量を求めるために必要な カウフマンブラケット多項式 を計算するプログラムの制作を最終目標とした。 ここからは カウフマンブラケット多項式 を求めるために必要な処理や手順を紹介して行きたいと思います。

16 不変量（ジョーンズ多項式）を求めるには 絡み目 立体から平面へ ダイアグラム（射影図） 図をグラフに置きかえる 有向にし、ライズを計算する
ダイアグラムのグラフ ~ ω( L ) カウフマンブラケット多項式 ステート を使いグラフを数値化 ジョーンズ多項式

17 ダイアグラムのグラフ ダイアグラムの交差部分の上下の情報をグラフの辺に加える。グラフの辺に注目したとき、辺を時計回りに回し、上を通るダイアグラムに重なれば、＋。逆ならば、－。 射影図を二色に塗り分け、非有界な領域を含まない色の各領域に一点ずつ点を取りグラフの頂点とします。それらの点を交差する部分を通るように結びグラフの辺とします。 － － ＋ － －

18 グラフの詳細 G = ( V , E , sgn ) V : 頂点の集合 E : 辺の集合 ダイアグラムの sgn :
｛＋ , －｝パラメータの集合 sgn : ＋ ＋ sgn = ｛＋１ , －１ , ＋１｝ － ｜V ( G )｜ : G の頂点の数 G ｜E ( G )｜ : G の辺の数

19 ステート S 2 ステート（ state ） ｛＋１ , ＋１ , ＋１｝ ｛＋１ , ＋１ , －１｝ ｛＋１ , －１ , ＋１｝
グラフの辺に任意に｛＋１ , －１｝情報を与えたもの S ｛＋１ , ＋１ , ＋１｝ ｛＋１ , ＋１ , －１｝ ｛＋１ , －１ , ＋１｝ ｛＋１ , －１ , －１｝ ｛－１ , ＋１ , ＋１｝ ｛－１ , ＋１ , －１｝ ｛－１ , －１ , ＋１｝ ｛－１ , －１ , －１｝ 　ステートを s 、 　ステートの集合を S で表す。 注 辺が３本の場合 ＋ ＋ 2 ( 辺の本数 ) － G

20 sG の作り方 グラフ（ G ） のパラメータ と ステート を対応させて｛＋ , －｝情報が一致する辺を有効にしたグラフ ステートグラフ （ sG ） sG の E ( Es ) s sgn = sgn = ｛＋１ , －１ , ＋１｝ ＋ ＋ ＋ － － s = ｛＋１ , －１ , －１｝ － sG = ( V , Es ) G sG

21 カウフマンブラケット多項式 < L > = ∑ T(s) ～ s ∈ S T(s) = A ( － A － A ) μ(s) 2
－2 β(s) － 1 μ(s) : ステートの和 例 s = ｛＋１、－１、＋１｝ μ(s) = １－１＋１ = １

22 β（ｓ） β(s) = a + b a : sG の閉路をなくすために取らなくては ならない辺の最小本数 b : sG のコンポーネント数

23 全域森 の辺の数 = ｜V ( sG )｜ – コンポーネント数
｜V ( sG )｜ – 全域森の辺の数 = コンポーネント数 = b ｜E ( sG )｜ － 全域森の辺の数 = sG が閉路を持たないようにするために 取り除かなければならない最小辺数 = a 全域森 β(s) = a + b ｜V ( sG )｜ = 6 ｜E ( sG )｜ = 6 全域森の辺の数 = 4 sG a = 6 － 4 = 2 b = 6 － 4 = 2

24 カウフマンブラケット多項式の例 G = ( V , E , sgn ) = －
＋ と表す s = (＋＋－)

25 s = (＋＋＋) s = (＋－－) s = (＋＋－) s = (－＋－) S ＝ s = (－－＋) s = (＋－＋)

26 s = (－－－) μ（s）= －３ β（s）= １＋１＝２ = A + A T(s) = A ( － A － A ) s = (＋＋＋)
－ ３ ２ － １ －２ ２ － １ － ５ － ＋ ＋ s = (＋＋＋) μ（s）= ３ β（s）= ３＋０ ＋ T(s) = A ( － A － A ) ３ 3 －１ －2 2 = 　A A + A －１ 3 7

27 s = (＋＋－) μ（s）= １ β（s）= ２＋０ T(s) = A ( － A － A ) = － A － A s = (＋－＋)
２ －１ １ －２ = 　－ A － A ３ －１ ＋ ＋ s = (＋－＋) － － T(s)×3 = －3A －3A ３ －１ － ＋ s = (－＋＋) ＋

28 s = (＋－－) μ（s）= －１ β（s）= １＋０ T(s) = A ( － A － A ) = A s = (－＋－)
２ １－１ －１ －2 = 　A 　 － － s = (－＋－) ＋ － －１ T(s)×3 = 3A － ＋ s = (－－＋) －

29 = A ＋ 2A － A ＋ A = A ＋ 2A － A ＋ A のカウフマンブラケット多項式 G = ( V , E , sgn ) ～
∑ T(s) s ∈ S － ５ －１ ３ ７ = A ＋ 2A － A ＋ A G = ( V , E , sgn ) － のカウフマンブラケット多項式 － ５ －１ ３ ７ = A ＋ 2A － A ＋ A

30 < L > = < L > + T ( s )
プログラム ダイアグラムのグラムをテキストファイルに変換 ダイアグラムのグラフ G を構築 （ 隣接リスト ） テキストを読み込む 全ての s に対して以下を実行 S に対し G より sG を構築・格納 sG に対して深さ優先探索 < L > = < L > + T ( s ) ~ T ( s ) を求める カウフマンブラッケト多項式

31 Specal Thanks : スポーツ グループ
発表者 : 澤木俊明 PowerPoint製作 : 加藤正朗 Resume製作 : 澤木俊明 Program製作 : 澤木俊明、加藤正朗 Knot グループ 澤木俊明、加藤正朗 Specal Thanks : スポーツ グループ 終わり

32 質問タイム ~ 有向絡み目のダイアグラム L + + - - = 1 w( L ) = 1