Kauffman bracket 多項式 を 計算するアルゴリズムとその実装 谷 研究室 村上 雅彦 Masahiko MURAKAMI 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 2 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 3 結び目 結び目とはゴムのように伸び縮みする1本の輪 のようなもの 2003年2月13日 平成14年度卒業研究発表会 4 結び目理論の概要 結び目が絡まった輪を切らずにほどくことがで きるかどうか？というようなことなどを考える ? 2003年2月13日 平成14年度卒業研究発表会 5 絡み目，結び目 (n成分の)絡み目⇒ R3内に埋め込まれた互いに素なn個の単純閉 折線 結び目⇒1成分の絡み目 注 意！ 曲線ではなく 折線 (2成分の)絡み目 2003年2月13日 3 R 平成14年度卒業研究発表会 結び目 6 正則射影，ダイアグラム 正則射影⇒ 絡み目を平面に射影した図で、多重点が横 断的に交わっている2重点のみのもの ダイアグラム⇒ 正則射影の各2重点にもとの絡み目におけ る交差の上下の情報を加えたもの 正則射影 2003年2月13日 平成14年度卒業研究発表会 ダイアグラム 7 絡み目の同型 結び目 同じ結び目 R3 2003年2月13日 平成14年度卒業研究発表会 8 自明な結び目 自明な結び目⇒ 2次元ユークリッド空間内に埋め込まれた1本 の単純閉曲線と同型な結び目 2003年2月13日 平成14年度卒業研究発表会 9 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 10 結び目理論の基本問題 2つの結び目が同型であるかを判定する問題 コンピュータを使って解けないか？ 2003年2月13日 平成14年度卒業研究発表会 11 絡み目の表現 ３次元座標のリスト (2成分の)絡み目 2003年2月13日 R3 座標は整数 平成14年度卒業研究発表会 12 2つの絡み目は同型か？ 2つの絡み目が与えられたときそれらが同型で あるかの判定はとても難しい 不変量を導入 2003年2月13日 平成14年度卒業研究発表会 13 不変量とは 絡み目から対応付けられる数学的な量 （数や多項式など） 同型な絡み目からは同じ量が対応付け可能 多項式不変量を 絡み目の同型性の指標 2003年2月13日 平成14年度卒業研究発表会 14 多項式不変量 Kauffman bracket多項式 この多項式自体は 不変量ではない が，ω( L ) と組み ~ 合わせること によって Jones多項式 が得られる Jones多項式 有向絡み目 の 多項式不変量 のひとつ 2003年2月13日 平成14年度卒業研究発表会 15 Jones多項式の計算 Kauffmanの計算法では2c (L~)個の多項式の和 の計算が必要 絡み目を限定すると計算の手間が減る 2003年2月13日 平成14年度卒業研究発表会 16 既存の結果 符号付きグラフが格子グラフとなるような絡み目に おいて264交点までJones多項式を計算 関根,今井,今井[1996] プレッツェル絡み目において10000交点までJones 多項式を計算 内海,今井[2002] 2003年2月13日 平成14年度卒業研究発表会 17 特定の絡み目のJones多項式の計算 2-bridge絡み目の標準的なダイアグラムの Kauffman bracket多項式はO(c(L))回の多項式 の演算で計算できる 原, 谷, 山本[2002] closed 3-braidダイアグラムのKauffman bracket多 項式はO(c(L)3)回の多項式の演算で計算できる 古藤[2002] 2003年2月13日 平成14年度卒業研究発表会 18 今回の結果 2-bridge絡み目の標準的なダイアグラムの Kauffman bracket多項式はO(c(L))回の多項式 の演算で計算できる 原, 谷, 山本[2002] アルゴリズムを再構築，実装 closed 3-braidダイアグラムのKauffman bracket多 項式はO(c(L)3)回の多項式の演算で計算できる 古藤[2002] 再構築，O(c(L))回の多項式の演算，実装 XXX交点まで計算 2003年2月13日 平成14年度卒業研究発表会 19 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 20 Kauffman bracket多項式 ルール1 ＜○＞＝１ 自明な結び目 2003年2月13日 平成14年度卒業研究発表会 21 Kauffman bracket多項式 ルール2 ＜L∪○＞＝(－A２－A－２)＜L＞ ＝A 2003年2月13日 ＋A－１ 平成14年度卒業研究発表会 22 Kauffman bracket多項式 ルール3 ＜ ＞＝A( )＋A－１( ＝A 2003年2月13日 ) ＋A－１ 平成14年度卒業研究発表会 23 Taitグラフ 2003年2月13日 平成14年度卒業研究発表会 24 Taitグラフ • 絡み目のダイアグ ラムの領域に対し て1つおきに陰をつ けていく 2003年2月13日 平成14年度卒業研究発表会 25 Taitグラフ • 陰をつけた各領域 に頂点をおく 2003年2月13日 平成14年度卒業研究発表会 26 Taitグラフ • 交点を共有するよ うな領域の2個の 頂点を辺で結ぶ 2003年2月13日 平成14年度卒業研究発表会 27 Taitグラフ • 各交点の符号を決 める ＋の交点 2003年2月13日 ーの交点 平成14年度卒業研究発表会 28 Taitグラフ • 交点が正か負かに よって対応する各 辺に＋または−の 符号を付ける ＋の交点 ーの交点 ー ー ＋ 2003年2月13日 平成14年度卒業研究発表会 29 Taitグラフ • こうしてTaitグラフ が得られる ー ー ＋ 2003年2月13日 平成14年度卒業研究発表会 30 タングル(tangle) • タングル⇒ 絡み目の一部分で，ちょうど4点で交わるような円で 囲まれた領域（絡み目が円と交わる4点はNW, NE, SW, SEにあるとする） 2003年2月13日 平成14年度卒業研究発表会 31 タングル(tangle) 0−タングル⇒ NWとSWを、NEとSEを結んだタングル 0−タングル 2003年2月13日 3−タングル 平成14年度卒業研究発表会 (-2)−タングル 32 タングル(tangle) n−タングル⇒ 0−タングルをn 回捻ってできるタングル 0−タングル 2003年2月13日 3−タングル 平成14年度卒業研究発表会 (-2)−タングル 33 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 34 今回の結果 2-bridge絡み目の標準的なダイアグラムのTait グラフから整数列表現を求める 整数列表現からKauffman bracket多項式を計 算する closed 3-braid絡みの標準的なダイアグラムの 整数列表現を求める 2003年2月13日 平成14年度卒業研究発表会 35 2-bridge絡み目の 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia1 Ia2 Ia2 〜 〜 Ia3 〜 〜 〜 〜 〜 〜 Ian-1 〜 〜 2003年2月13日 〜 〜 Ian 平成14年度卒業研究発表会 Ian-1 Ian n が 偶 数 の と き 36 2-bridge絡み目の 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia2 Ia3 〜 〜 〜 〜 Ian-1 〜 〜 2003年2月13日 Ian 2-bridge絡み目の 標準的なダイアグラム L~(a1 , … , an)⇒ 整数タングルIak (k = 1, … , n)を左のよう に結んだダイアグラム 平成14年度卒業研究発表会 37 2-bridge絡み目の 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia2 Ia3 〜 〜 〜 〜 Ian-1 〜 〜 2003年2月13日 Ian 2-bridge絡み目の標準 的なダイアグラムの整 数列表現⇒ 2-bridge絡み目の標準 的なダイアグラムL~(a1 , … , an)に対して(a1 , … , an) 平成14年度卒業研究発表会 38 アルゴリズム1 • 2-bridge絡み目の標準的なダイアグラムの Taitグラフから整数列表現を求めるアルゴリ ズム 2003年2月13日 平成14年度卒業研究発表会 39 アルゴリズム1 L~( -2 , 2 , 1 , -1, -2） + のTaitグラフ + + 2003年2月13日 平成14年度卒業研究発表会 + + + 40 アルゴリズム1 一番次数の大きい 頂点v を探す + + v + 2003年2月13日 平成14年度卒業研究発表会 + + + 41 アルゴリズム1 頂点v を取り除いたグラフ + + 2003年2月13日 平成14年度卒業研究発表会 42 アルゴリズム1 出力：-2 + 端点とv の間の辺数に それらの辺の符号と (-1)を掛けて出力 + v + 2003年2月13日 平成14年度卒業研究発表会 + + + 43 アルゴリズム1 出力：-2, 2 + 次数が3以上になるまで 隣の頂点に移動して それまで通った辺の v 値の和を出力 + + 2003年2月13日 平成14年度卒業研究発表会 + + + 44 アルゴリズム1 出力：-2, 2, 1 + v の間の辺数に それらの辺の符号と (-1)を掛けて出力 + v + 2003年2月13日 平成14年度卒業研究発表会 + + + 45 アルゴリズム1 出力：-2, 2, 1, -1 + 次数が3以上になるまで 隣の頂点に移動して それまで通った辺の v 値の和を出力 + + 2003年2月13日 平成14年度卒業研究発表会 + + + 46 アルゴリズム1 出力：-2, 2, 1, -1, -2 + v の間の辺数に それらの辺の符号と (-1)を掛けて出力 + v + 2003年2月13日 平成14年度卒業研究発表会 + + + 47 アルゴリズム1 計算時間を減らす工夫 + 先にすべての辺を走査 + 頂点の次数 vとの間の辺の符号 隣接する頂点 v O(c(L)) 2003年2月13日 平成14年度卒業研究発表会 + + + + 48 アルゴリズム2 整数列表現からKauffman bracket多項式を計 算する 2003年2月13日 平成14年度卒業研究発表会 49 原・谷・山本 〈L~(a1,…,an)〉 ＝ 1 －A２－A－２ × ( fan-1〈L~(a1,…,an-2)〉 ＋fan(A)〈L~(a1,…,an-1)〉) 2003年2月13日 平成14年度卒業研究発表会 50 アルゴリズム2 n=1〈L~(a1)〉＝(−A)−3a1−2sgn(a1) ×Σk=1|a1|(−A4sgn(a1))k ＋Aa1(−A−2−A2) n=2〈L~(a1,a2)〉＝ (−A)−3a2−2sgn(a2) 〈L~(a1)〉 ＋Σk=1|a2|(−A4sgn(a2))k ＋Aa2(−A)−3a1 n≧3 〈L~(a1,…,an)〉＝ (−A)−3an−2sgn(an) ×〈L~(a1,…,an-1)〉 ＋Σk=1|an|(−A4sgn(an))k ＋Aan(−A)−3an-1 〈L~(a1,…,an-2)〉 2003年2月13日 平成14年度卒業研究発表会 51 アルゴリズム2 n=1〈L~(a1)〉＝(−A)−3a1−2sgn(a1) ×Σk=1|a1|(−A4sgn(a1))k ＋Aa1(−A−2−A2) n=2〈L~(a1,a2)〉＝ (−A)−3a2−2sgn(a2) 〈L~(a1)〉 ＋Σk=1|a2|(−A4sgn(a2))k ＋Aa2(−A)−3a1 n≧3 〈L~(a1,…,an)〉＝ (−A)−3an−2sgn(an) ×〈L~(a1,…,an-1)〉 ＋Σk=1|an|(−A4sgn(an))k O(c(L))回の an(−A)−3an-1 〈L~(a ,…,a )〉 ＋ A 1 n-2 多項式演算 2003年2月13日 平成14年度卒業研究発表会 52 3-braid • 3-braid⇒ 両端が2つの平行な 平面に接続している 3本の紐で、それぞ れの紐が2つの平面 の間にあるすべての 平行な平面とちょう ど1回ずつ交わって いるもの 2003年2月13日 平成14年度卒業研究発表会 53 closed 3-braidダイアグラム • closed 3-braid ダイアグラム⇒ 3-braidを正則射影し 射影平面上で紐の 両端を自分自身とも 他の紐とも交わらな いように結んだもの 2003年2月13日 平成14年度卒業研究発表会 54 closed 3-braidの 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia1 Ia2 Ia2 〜 〜 Ia3 2003年2月13日 〜 〜 〜 〜 Ian-1 〜 〜 Ian 〜 〜 〜 〜 平成14年度卒業研究発表会 Ian-1 Ian n が 偶 数 の と き 55 closed 3-braidの 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia2 Ia3 〜 〜 Ian-1 〜 〜 2003年2月13日 〜 〜 Ian closed 3-braidの 標準的なダイアグラム w~(a1 , … , an)⇒ 整数タングルIak (k = 1, … , n)を左の ように結んだ ダイアグラム 平成14年度卒業研究発表会 56 closed 3-braidの 標準的なダイアグラム Ia1 n が 奇 数 の と き Ia2 Ia3 〜 〜 Ian-1 〜 〜 2003年2月13日 〜 〜 Ian closed 3-braidの標準 的なダイアグラムの整 数列表現⇒ closed 3-braidの標準 的なダイアグラム w~(a1 , … , an)に対し て(a1 , … , an) 平成14年度卒業研究発表会 57 アルゴリズム3 n=1〈w~(a1)〉＝ (−A−2−A2) 〈L~(a1)〉 n偶数〈w~(a1, …,an)〉＝Aan〈w~(a1,…,an-1)〉 ＋(−A)−3an−2sgn(an) ×〈L~(a1,…,an-1)〉 ×Σk=1|an|(−A4sgn(an))k n奇数〈w~(a1, …,an)〉＝Aan〈w~(a1,…,an-1)〉 ＋(−A)−3(a1＋an)−2sgn(an) ×〈L~(a2,…,an-1)〉 ×Σk=1|an|(−A4sgn(an))k 2003年2月13日 平成14年度卒業研究発表会 58 アルゴリズム3 n=1〈w~(a1)〉＝ (−A−2−A2) 〈L~(a1)〉 n偶数〈w~(a1, …,an)〉＝Aan〈w~(a1,…,an-1)〉 ＋(−A)−3an−2sgn(an) ×〈L~(a1,…,an-1)〉 ×Σk=1|an|(−A4sgn(an))k n奇数〈w~(a1, …,an)〉＝Aan〈w~(a1,…,an-1)〉 ＋(−A)−3(a1＋an)−2sgn(an) O(c(L))回の ×〈L~(a2,…,an-1)〉 多項式演算 ×Σk=1|an|(−A4sgn(an))k 2003年2月13日 平成14年度卒業研究発表会 59 アルゴリズムの実装 500交点の2-bridge絡み目の標準的なダイア グラムやclosed 3-braidの標準的なダイア グラムのKauffman bracket多項式を計算 2003年2月13日 平成14年度卒業研究発表会 60 作成したプログラム一覧 make_tait make_progression comp_bracket comp_bracket_3 2003年2月13日 平成14年度卒業研究発表会 61 目次 1. 絡み目とその表現 2. 結び目理論における計算 3. Kauffman brackte多項式， Taitグラフ，タングルの紹介 4. アルゴリズム（今回の結果） 5. 今後の課題 2003年2月13日 平成14年度卒業研究発表会 62 今後の課題 • Arborescent絡み目やプレッツェル絡み目 へ拡張できないか？ • BDDを用いたアルゴリズムとの比較 2003年2月13日 平成14年度卒業研究発表会 63
© Copyright 2024 ExpyDoc
