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

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
平面三角分割グラフを列挙す るアルゴリズムの改良 中野 眞一 ( 群馬大学 ) 宇野 毅明 ( 情報学研究 所 ) 2002 年 6 月 24 日 コンピューテーション研究会.
PRML読書会第11回 8.4 グラフィカルモデルによる推論 SUHARA YOSHIHIKO (id:sleepy_yoshi)
2015 年度 有限幾何学 期末試験 次の各問に答えよ.( (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい) (1) 有向閉路が存在しない位数 4 のトーナメントを描け. (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ. (3) グラフ.
フロンティア法 - 組合せ問題の解を列挙索引化するZDD構築アルゴリズム
MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
絵画的迷路の作り方 岡本 吉央 東工大 上原 隆平 JAIST.
    有限幾何学        第8回.
On the Enumeration of Colored Trees
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
An Algorithm for Enumerating Maximal Matchings of a Graph
Permutationグラフと Distance-Hereditaryグラフの 再構築アルゴリズム
計算の理論 II NP完全 月曜4校時 大月美佳.
    有限幾何学        第5回.
    有限幾何学        第12回.
線形代数学 4.行列式 吉村 裕一.
Probabilistic Method 6-3,4
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
透視投影(中心射影)とは  ○ 3次元空間上の点を2次元平面へ投影する方法の一つ  ○ 投影方法   1.投影中心を定義する   2.投影平面を定義する
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
OpenGLによる結び目の 近傍抜き出しソフトウェア 情報システム解析学科 谷研究室  澄川 知弘.
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
A First Course in Combinatorial Optimization Chapter 3(前半)
7.時間限定チューリングマシンと   クラスP.
二分探索木によるサーチ.
アルゴリズムとデータ構造 2011年7月4日
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
Hough変換 投票と多数決原理に基づく図形の検出
計算の理論 I -Myhill-Nerodeの定理 と最小化-
オートマトンとチューリング機械.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
A Simple Algorithm for Generating Unordered Rooted Trees
離散数学 07. 木 五島.
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
計算の理論 II 前期の復習 -有限オートマトン-
第4章 識別部の設計 4-5 識別部の最適化 発表日:2003年5月16日 発表者:時田 陽一
    有限幾何学        第5回.
直並列グラフの連続多重彩色 西関研究室 吉田進太郎.
離散数学 06. グラフ 序論 五島.
Max Cut and the Smallest Eigenvalue 論文紹介
地理情報システム論(総)/ 国民経済計算論(商)
地理情報システム論 第4回 コンピュータシステムおける データ表現(2)
アルゴリズムとデータ構造 2013年7月8日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ~アルゴリズムの改良の考察と そのプログラム作成~
離散数学 11. その他のアルゴリズム 五島.
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
割り当て問題(assignment problem)
13.近似アルゴリズム.
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
アルゴリズムとデータ構造 2012年7月9日
計算の理論 I 最小化 月曜3校時 大月 美佳 平成15年6月23日 佐賀大学知能情報システム学科.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
ペンシルパズル「一本線」のヒント数の扱いに関する解析
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

グラフの詳細 G = ( V , E , sgn ) V : 頂点の集合 E : 辺の集合 ダイアグラムの sgn : {+ , -}パラメータの集合 sgn : + + sgn = {+1 , -1 , +1} - |V ( G )| : G の頂点の数 G |E ( G )| : G の辺の数

ステート S 2 ステート( state ) {+1 , +1 , +1} {+1 , +1 , -1} {+1 , -1 , +1} グラフの辺に任意に{+1 , -1}情報を与えたもの S {+1 , +1 , +1} {+1 , +1 , -1} {+1 , -1 , +1} {+1 , -1 , -1} {-1 , +1 , +1} {-1 , +1 , -1} {-1 , -1 , +1} {-1 , -1 , -1}  ステートを s 、  ステートの集合を S で表す。 注 辺が3本の場合 + + 2 ( 辺の本数 ) - G

sG の作り方 グラフ( G ) のパラメータ と ステート を対応させて{+ , -}情報が一致する辺を有効にしたグラフ ステートグラフ ( sG ) sG の E ( Es ) s sgn = sgn = {+1 , -1 , +1} + + + - - s = {+1 , -1 , -1} - sG = ( V , Es ) G sG

カウフマンブラケット多項式 < L > = ∑ T(s) ~ s ∈ S T(s) = A ( - A - A ) μ(s) 2 -2 β(s) - 1 μ(s) : ステートの和 例 s = {+1、-1、+1} μ(s) = 1-1+1 = 1

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

全域森 の辺の数 = |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

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

s = (+++) s = (+--) s = (++-) s = (-+-) S = s = (--+) s = (+-+)

s = (---) μ(s)= -3 β(s)= 1+1=2 = A + A T(s) = A ( - A - A ) s = (+++) - 3 2 - 1 -2 2 - 1 - 5 - + + s = (+++) μ(s)= 3 β(s)= 3+0 + T(s) = A ( - A - A ) 3 3 -1 -2 2 =  A + 2A + A -1 3 7

s = (++-) μ(s)= 1 β(s)= 2+0 T(s) = A ( - A - A ) = - A - A s = (+-+) 2 -1 1 -2 =  - A - A 3 -1 + + s = (+-+) - - T(s)×3 = -3A -3A 3 -1 - + s = (-++) +

s = (+--) μ(s)= -1 β(s)= 1+0 T(s) = A ( - A - A ) = A s = (-+-) 2 1-1 -1 -2 =  A   - - s = (-+-) + - -1 T(s)×3 = 3A - + s = (--+) -

= A + 2A - A + A = A + 2A - A + A のカウフマンブラケット多項式 G = ( V , E , sgn ) ~ ∑ T(s) s ∈ S - 5 -1 3 7 = A + 2A - A + A G = ( V , E , sgn ) - のカウフマンブラケット多項式 - 5 -1 3 7 = A + 2A - A + A

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

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

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