絡み目の不変量 絡み目の不変量

絡み目の不変量 絡み目の不変量

カウフマンブラケット多項式 カウフマンブラケット多項式

の効率的な実装 の効率的な実装

平成 13 年 2 月 7 日 ( 水 )

5497033

5497033 澤木　俊澤木　俊 明明

5497038 加藤　正

朗

概要 概要

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

? ?

これらの問題は結び目理論 の基本的なテーマである。

結び目が自明な結び目 か？

（ 絡まった輪をほどけるか

）

二つの結び目が同じである か？

（ 二つの絡まった輪の一方を もう一方と同じ形にできる

か ）

ある結び目理論に関連する問題を解くプログラム制 作

今回の成果 今回の成果

目次 目次

 結び目・絡み目の定義 結び目・絡み目の定義

 絡み目の不変量 絡み目の不変量

 カウフマンブラケット多項式 カウフマンブラケット多項式

 今回制作したプログラムについて 今回制作したプログラムについて

結び目の定義 結び目の定義

R³

結び目（ Knot ）

：

R 3 内の多辺形 （ 閉じた折れ 自明な結び目 ： 線 ）R 内の多辺形と 同型

なもの

2

全同位変形（ a

mbient isotopy ） R 内で自分自身を横切らないでひもを動かすような

こと

全同位変形

結び目 自明な結び目

位相同型を与える同相写像

二つの結び目が同じと は？

3

同じ結び目

一方から他方へ全同位変形可能

絡み目の定義 絡み目の定義

複数の結び目の輪が絡んでできたもの

R³

結び目は１成分の絡み目 注

絡み目の一つでホワイトヘッド絡 み目と呼ばれているものである。

これは二本の輪（２つの成分）か らできている。

絡み目 （ Lin

k ）

射影図 ： 結び目を平面に射影した図

正則射影 ： 多重点が横断的に交わっている二重点のみの射 影図

正則射影 ダイアグラ ム

R²

射影図 射影図

R³

絡み目

射影

ダイアグラム ： 正則射影に交叉の情報を与えたもの

であり L ~ で表す

〇×

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

二つのダイアグラムが同じ絡み目を表すか どうかを判定するための道具

ライデマイスター移動 （ Reidemeister m ove ）

ライデマイスター移動 にはⅠ、Ⅱ、Ⅲ の三つの移動がある

絡み目 A

絡み目 全同位変形 B

ダイアグラ ム A

射影 射

影

ダイアグラ ム B

?

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

ルールⅠ

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

ルールⅡ

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

ルールⅢ

ダイアグラ ム A

ダイアグラ ム B

ライデマイス ター移動

ライデマイス ター移動

二つダイアグラムが互いに移り合うことが可能で もその順序や回数を得るアルゴリズムは知られて いない。

二つのダイアグラムが 同じ絡み目を表す

両者間を移り合う ライデマイスター移動

の

有限列が存在

順序？回数？

A と B が同じ絡み 目のダイアグラムと すると

絡み目の不変量 絡み目の不変量

同じ絡み目に対して必ず同じ値を持つもの .

絡み目の不変量（ 以下、不変量 ） が異なれば 少なくとも同じ絡み目とはいえない 。

絡み目の不変量

（ invarinat ）

例えば、左の絡み目の閉曲線の本数 が ３ であるということは 不変量 である。

しかし、この二つは違う絡み目である。

このように、閉曲線の本数は絡み目を区別するのにはあまり適さな い。

右の絡み目の閉曲線の本数も ３ であ る。

多項式不変量 多項式不変量

有向絡み目 の 多項式不変量 のひと つ

ジョーンズ多項式

（ Jones polynomia l ）

( - A ) < L >

カウフマンブラケット多項式（ < L > ）

　 に乗算することによって

ジョーンズ多項式 を得る。

ジョーンズ多項式

~

ライズ（

writhe ） ^Jones 多項式 を求めるために 有向絡み目 の 交点のパラメータを計算したもので、 ω( L ) で表す。

~

この多項式自体は 不変量ではない が、 ω( L ) と組み合わせること に

よって Jones 多項式 が得られる。

カウフマンブラケット多項式（

kauffman bracket polynomial

） < L > : カウフマンブラッケト多

項式

~

~

目標 目標

我々は ジョーンズ多項式 という有向絡み目の不 変量を求めるために必要な カウフマンブラケット カウフマンブラケット 多項式 多項式 を計算するプログラムの制作を最終目標 とした。

ここからは カウフマンブラケット多項式 カウフマンブラケット多項式 を

求めるために必要な処理や手順を紹介して行

きたいと思います。

不変量（ジョーンズ多項 不変量（ジョーンズ多項

式）を求めるには 式）を求めるには

絡み目

ダイアグラム（射影図）

ダイアグラムのグラフ ダイアグラムのグラフ 立体から平面

へ

図をグラフ に置きかえ る

ω( L )

カウフマンブラ カウフマンブラ

ケット多項式 ケット多項式 ジョーンズ多項式

ステート ステート を使 いグラフを数 値化

有向にし、ライ ズを計算する

~

ダイアグラムのグラフ ダイアグラムのグラフ

射影図を二色に塗り分け、非有界な領域を含まない色の 各領域に一点ずつ点を取りグラフの頂点とします。それ らの点を交差する部分を通るように結びグラフの辺とし ます。

ダイアグラムの交差部分の上下の情報をグラフの辺に加 える。グラフの辺に注目したとき、辺を時計回りに回し

、上を通るダイアグラムに重なれば、＋。逆ならば、－

。

＋ －

－

－

－

＋

－ G

sgn = ｛＋１ , －１ , ＋１｝

G = ( V , E , sgn )

＋

ダイアグラムの

｛＋ , －｝パラメータ の集合

sgn :

グラフの詳細 グラフの詳細

E : 辺の集合 V : 頂点の集合

｜ V ( G ) ｜ : G の頂点の 数｜ E ( G ) ｜ : G の辺の数

ステート ステート

｛＋１ , ＋１ ,

＋１｝

｛＋１ , ＋１ ,

－１｝

｛＋１ , －１ ,

＋１｝

｛＋１ , －１ ,

－１｝

｛－１ , ＋１ ,

＋１｝

｛－１ , ＋１ ,

－１｝

｛－１ , －１ ,

＋１｝

｛－１ , －１ ,

－１｝

グラフの辺に任意に｛＋１ ,

S

－１｝情報を与えたもの

辺が３本の場合

＋ ＋

－ G

2

ステート（ st

ate ）　ステートを s 、

　ステートの集合を S で 表す。

注

sG sG の作り方 の作り方

sGG

＋ ＋

－

＋ － －

グラフ（ G ） のパラメータ と ステート を対応させて｛＋ , －｝

情報が一致する辺を有効にしたグラ フ

s = ｛＋１ , －１ ,

－１｝

sG = ( V , Es )

ステートグラフ

（ sG ）

sgn = ｛＋１ , －１ , ＋１｝

s = sgn sG の

E ( Es )

< L > = ∑ T(s)

s S∈

T(s) = A (

－ A

－

A )

μ(s) : ステートの 和

s = ｛＋１、－１、＋１｝ μ(s) = １－１

＋１ = １ 例

カウフマンブラケット多項式

カウフマンブラケット多項式

β β （ｓ） （ｓ）

a : sG の閉路をなくすために取らなくては

ならない辺の最小本数

b : sG のコンポーネント数

a = 2

sG

b = 2 β(s) = a + b

β(s) = 2 + 2 = 4

｜ E ( sG ) ｜ － 全域森の辺の数

= sG が閉路を持たないようにするために

取り除かなければならない最小辺数 = a

全域森 の辺の数 = ｜ V ( sG ) ｜ – コンポーネント数

｜ V ( sG ) ｜ – 全域森の辺の数 = コンポーネント数 = b

β(s) = a + b

全域森の辺の数 = sG 4

｜ V ( sG ) ｜ = 6

｜ E ( sG ) ｜ = 6

a = 6 － 4 = 2 b = 6 － 4 = 2

全域森

カウフマンブラケット多項式 カウフマンブラケット多項式 の例 の例

G = ( V , E , sgn ) =

－

－

ステートは辺に対応してできる以下では簡単の ため s ( ＋１ , ＋１ , －１ ) などを

s = ( ＋＋－ ) ^－

＋

＋ と表す

S 　＝

s = ( ＋＋＋ )

＋

＋ ＋

s = ( ＋－＋ )

－

＋ ＋

s = ( －＋＋ )

＋

－ ＋

s = ( ＋－－ )

－

＋ －

s = ( ＋＋－ )

＋

＋ －

s = ( －＋－ )

＋

－ －

s = ( －－＋ )

－

－ ＋

s = ( －－－ )

－

－ －

s = ( －－－ )

－

－ －

－

－

－

－

－

－

μ （ s ） = －３ β （ s ） = １＋

１＝２

＋

＋ ＋

s = ( ＋＋＋ ) μ （ s ） = ３ β （ s ） = ３

＋０ T(s) = A ( ^３ － A ² － A )^{－2 3 －１}

= 　 A + 2A + A^{－１ 3 7}

= A + A

T(s) = A ( ^{－ ３} － A ^２ － ^－２A )^{２ － １}

－ １ － ５

－

－

－

－

－

－

－

－

－

s = ( ＋－＋ )

＋ ＋

s = ( －＋＋ )

＋

s = ( ＋＋－ )

＋

μ （ s ） = １ β （ s ） = ２＋０

－

＋

－

－

＋

T(s) = A ( ^１ － A ^２ － ^－２A )^{２ －１}

= 　－ A ^３ － ^－１A

T(s)×3 = － 3A ^３－ 3A ^－１

－

－

－

－

－

－

－

－

－

s = ( －＋－ )

s = ( －－＋ )

s = ( ＋－－ ) μ （ s ） = －１ β （ s ） = １＋０

T(s)×3 = 3A －１

T(s) = A ( ^－１ － A ^２ － A )^{－2 １－１}

= 　 A ^－１ 　

＋ －

－

－

－

＋

＋

－

－

∑ T(s)

s S∈

= A ＋

2A

－ A

＋

A

G = ( V , E , sgn )

－

－

－

のカウフマンブラケット多 項式

= A ＋

2A

－ A

＋

A

プログラム プログラム

テキストを読み込む ダイアグラムのグラフ G を構築

（ 隣接リスト ）

全ての s に対して以下を実行

カウフマンブラッケト多項式 カウフマンブラッケト多項式 ダイアグラムのグラムをテキストファイルに

変換

S に対し G より sG を構築・格納 sG に対して深さ優先探索 T ( s ) を求める

< L > = < L > + T ( s )~ ~

PowerPoint 製作 : 加藤正朗 Resume 製作 : 澤木俊明

Program 製作 : 澤木俊明、加藤正朗

Knot グループ

澤木俊明、加藤正 朗

終わり

発表者 : 澤木俊明

Specal Thanks : スポーツ グループ

質問タイム

有向絡み目のダイアグラム

+

+ + -

- -

+

+ 1 + 1 + 1 - 1 - 1 = 1 w( L ) = 1

L~