（基础数学专业论文）两种区分平面投影图平面合痕类的算法.pdf

大连理工大学硕士学位论文 摘要 拓扑学是近代发展起来的一个研究连续性现象的数学分支，也是十分重要的、基础 性的数学分支数学上的纽结理论是拓扑学的一个引人入胜的领域，而纽结理论的中心 问题就是纽结分类问题，目前，已经有了能够判断纽结的等价性的算法理论上可以造 出一台机器，输入任意两个纽结的投影图，它都能判定它们是否等价然而这只解决了 理论上的可判定性，还不切实可行在实际计算方面，数学家们已发明了一些新的多项 式不变量，它们比亚历山大多项式包含更多的信息本文是已有文献的结论的扩展和创 新，主要介绍了两种区分平面投影图平面合痕类的算法本文的结构如下： 由于我们讨论的分类问题是基于纽结理论的，从而首先我们在第一章简单的介绍 了拓扑学、纽结理论的发展历史及现状，及其在各个领域中的应用 在第二章，我们介绍了纽结理论中的基本概念，包括投影图、同胚、纽结的d t 码 的定义，以及详细介绍已知d t 码如何得到与它对应的纽结的方法，在最后一节我们对 某些特殊的纽结的d t 码的个数进行了略微的讨论 第三章是本文的中心部分，重点介绍了两种区分两个纽结图是否等价的方法，即 给出了两种区分平面投影图平面合痕类的算法，其中第一种方法是对文献 4 6 的扩展， 另一种方法是找到一个从一个纽结到另一个纽结的满足某种关系的映射，如果找到了， 就可以说明这两个纽结是合痕的，实例表明这两种方法是可行的 关键词：纽结；投影图；d t 码；序列的实现；等价 两种区分平面投影图平面合痕类的算法 t w o a l g o r i t h m sd i s t i n g u i s h i n gd i s t i n c tl i n kd i a g r a m su pt op l a n a r i s o t o p y a b s t r a c t t o p o l o g y ，w h i c h i sd e v e l o p e di nm o d e m t i m e s ，i sa l li m p o r t a n ta n db a s i cb r a n c ho f m a t h e m a t i c s ，f o c u s i n go nt h ep h e n o m e n o no fc o n t i n u i t y k n o tt h e o r yi sa l la t t r a c t i v ef i e l do f t o p o l o g y ，a n di t sc e n t r a lt o p i ci st h ec l a s s i f i c a t i o no fk n o t s i np r e s e n t ，m a t h e m a t i c i a n sh a v e b e e na b l et od e t e r m i n ew h e t h e rt w ok n o t sa r ee q u i v a l e n t i nt h e o r y ，w ec a l lc r e a t eam a c h i n e ， w h i c hc a nd e t e r m i n ew h e t h e rt w oi n p u to f k n o t p r o j e c t i o n sa r ee q u i v a l e n t t h i sc a l lb e d e t e r m i n e dt h e o r e t i c a l l y ，b u tn o tp r a c t i c a l l y i na c t u a lc a l c u l a t i o n , m a t h e m a t i c i a n sh a v e i n v e n t e dan u m b e ro fp o l y n o m i a li n v a r i a n t s ，a n dt h o s ei n v a r i a n t si n c l u d em o r ei n f o r m a t i o n t h a nj u s tt h ea l e x a n d e rp o l y n o m i a l t h i sa r t i c l em a k e st h ef o l l o w i n ge x p a n s i o na n d i n n o v a t i o n , i ti n t r o d u c e st w oa l g o r i t h m sd i s t i n g u i s h i n gd i s t i n c tl i n kd i a g r a m su pt op l a n a r i s o t o p y t h i sa r t i c l ei ss t r u c t u r e da sf o l l o w s ： f o rt h ep r o b l e m so fc l a s s i f i c a t i o nw ed i s c u s s e di sa b o u tk n o tt h e o r y ，s o ，f i s to fa l l ，w e i n t r o d u c et o p o l o g y ，k n o tt h e o r ya n dt h e i rh i s t o r yo fd e v e l o p m e n t , a n di t sa p p l i c a t i o ni n v a r i o u sf i e l d si nt h ef i r s tc h a p t e r i nt h es e c o n dc h a p t e r ，w ei n t r o d u c et h eb a s i cc o n c e p t so fk n o tt h e o r y ，i n c l u d i n gr e g u l a r p r o j e c t i o n ，d tc o d e ，a sw e l la st h ed e t a i l so nh o w t og e tad tc o d ef r o mak n o tp r o j e c t i o n f i n a l l y ，w eh a v ea l i t t l ed i s c u s s i o no nt h en u m b e ro fd tc o d e si ns o m es p e c i a lk n o t s p r o j e c t i o n s c h a p t e rh ii sac e n n aip a r to ft h i sa r t i c l e f o c u s i n go nt w om e t h o d st od i s t i n g u i s hd i s t i n c t l i n kd i a g r a m su pt op l a n a ri s o t o p y o n em e t h o di s 觚e x p a n s i o no ft h el i t e r a t u r e 【4 6 ，t h e o t h e ri sf i n d i n gam a pf r o mak n o td i a g r a mt oa n o t h e rd i a g r a mw h i c hs a t i s f i e ss o m e r e s t r i c t i o n s i fw ec o u l df i n di t ，w ec a l ls a yt h a tt h e ya r ep l a n a ri s o t o p i c e x a m p l e ss h o wt h a t b o t ho ft h e s em e t h o d sa r ef e a s i b l e a tl a s t , w ec o m p a r et h et w om e t h o d s k e yw o r d s ：k n o t ；r e g u l a rp r o j e c t i o n ；d tc o d e ；t h er e a l i z a t i o no fs e q u e n c e ；e q u i v a l e n t i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目：亟丕邃金銎亟熊因翌鱼全盔鍪垄垡垄 作者签名：乒啦一怵导馑月丝日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文 学位论文题目：鱼猫匡堡叠盘丝塑璺至鱼全壅垄幽堡 作者签名： 差垄聋日期：主啦吐月坐日 导师签名： 彳丕堑吞日期：丝啦“月三臣日 大连理工大学硕士学位论文 1 绪论 1 1 拓扑学概述 1 1 1 拓扑学定义 拓扑学f l - 3 】是近代发展起来的一个研究连续性现象的数学分支中文名称起源于希 腊语t o n o l o y 缸的音译t o p o l o g y 原意为地貌，于1 9 世纪中期由科学家引入，当时主要 研究的是出于数学分析的需要而产生的一些几何问题发展至今，拓扑学主要研究拓扑 空间在拓扑变换下的不变性质和不变量【4 “】举例来说，在通常的平面几何里，把平面 上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形但是， 在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化在拓扑学里没 有不能弯曲的元素，每一个图形的大小、形状都可以改变，这些就是拓扑学思考问题的 出发点简单地说，拓扑就是研究有形的物体在连续变换下，怎样还能保持性质不变 1 1 2 拓扑学的发展简史 拓扑学起初叫形势分析学，这是g w 莱布尼茨1 6 7 9 年提出的名词( 中文译成形势， 形指一个图形本身的性质，势指一个图形与其子图形相对的性质，经过2 0 世纪3 0 年代 中期起布尔巴基学派的补充( 一致性空间、仿紧性等) 和整理，纽结和嵌入问题就是势的 问题) 随后波兰学派和苏联学派对拓扑空间的基本性质( 分离性、紧性、连通性等) 做了 系统的研究l 欧拉1 7 3 6 年解决了七桥问题，1 7 5 0 年发表了多面体公式；c f 高斯1 8 3 3 年在电动力学中用线积分定义了空间中两条封闭曲线的环绕数拓扑学这个词( 中文是 音译) 是j b 利斯廷提出的( 1 8 4 7 ) ，源自希腊文( 位置、形势) 与( 学问) 这是萌芽阶段 1 8 5 1 年起，b 黎曼在复函数的研究中提出了黎曼面的几何概念，并且强调，为了研 究函数、研究积分，就必须研究形势分析学在几何学的研究中黎曼明确提出n 维流形 的概念( 1 8 5 4 ) 得出许多拓扑概念在数学上，关于哥尼斯堡七桥问题、多面体的欧拉定 理、四色问题【7 - 9 等都是拓扑学发展史的重要问题 组合拓扑学的奠基人是h 庞加莱他是在分析学和力学的工作中，特别是关于复函 数的单值化和关于微分方程决定的曲线的研究中，引向拓扑学问题的，但他的方法有时 不够严密，他的主要兴趣在r l 维流形他留下的丰富思想影响深远，但他的方法有时不 够严密，过多地依赖几何直观 一般拓扑学，最早研究抽象空间的是m 一r 弗雷歇，在1 9 0 6 年引进了度量空间的概 念f 豪斯多夫在集论大纲( 1 9 1 4 ) 中用开邻域定义了比较一般的拓扑空间，标志着用 两种区分平面投影图平面合痕类的算法 公理化方法研究连续性的一般拓扑学的产生l 欧拉1 7 3 6 年解决了七桥问题，随后波兰 学派和苏联学派对拓扑空间的基本性质( 分离性、紧性、连通性等) 做了系统的研究经 过2 0 世纪3 0 年代中期起布尔巴基学派的补充( 一致性空间、仿紧性f l o 】等) 和整理，一般 拓扑学趋于成熟，成为第二次世界大战后数学研究的共同基础从其方法和结果对于数 学的影响看，紧拓扑空间和完备度量空间【1 1 1 的理论是最重要的紧化问题和度量化问题 也得到了深入的研究 代数拓扑学l e j 布劳威尔在1 9 1 0 - - - , 1 9 1 2 年间提出了用单纯映射逼近连续映射的 方法，许多重要的几何现象，用以证明了不同维的欧氏空间不同胚，它们就不同胚引 进了同维流形之间的映射的度以研究同伦分类，并开创了不动点理论他使组合拓扑学 在概念精确、论证严密方面达到了应有的标准j w 亚历山大1 9 1 5 年证明了贝蒂数与 挠系数的拓扑不变性如连通性、紧性 1 1 3 拓扑学在数学领域中的作用 因为大量自然现象具有连续性，所以拓扑学具有广泛联系各种实际事物的可能性 通过拓扑学的研究，可以阐明空间的集合结构，从而掌握空间之间的函数关系本世纪 三十年代以后，数学家对拓扑学的研究更加深入，提出了许多全新的概念比如，一致 性结构概念、抽象距概念和近似空间概念等等。有一门数学分支叫做微分几何，是用微 分工具来研究曲线、曲面等在一点附近的弯曲情况，而拓扑学是研究曲面的全局联系的 情况，因此，这两门学科应该存在某种本质的联系1 9 4 5 年，美籍中国数学家陈省身建 立了代数拓扑和微分几何的联系，并推进了整体几何学的发展拓扑学在泛函分析、李 群论、微分几何、微分方程和其他许多数学分支中都有广泛的应用 除了通过各数学分支的间接的影响外，拓扑学的概念和方法对物理学( 如液晶结构 缺陷的分类) 、化学( 如分子的拓扑构形) 、生物学【1 1 1 ( 如d n a 的环绕、拓扑异构酶) 都有 直接的应用 拓扑学与各数学领域、各科学领域之间的边缘性研究方兴未艾 1 2 纽结理论的介绍 纽结理论 1 2 - 1 7 1 是本世纪以来作为拓扑学的一个重要部分而发展起来的拓扑学是 研究几何图形的连续变形的学科，纽结理论研究绳圈( 或多个绳圈) 在连续变形下保持不 变的特性由于纽结与链环既直观又奥妙，纽结理论成了拓扑学中引入入胜的一支，它 在数学中的重要性也日渐上升数学学科代数拓扑的一个分支，按照数学上的术语来说， 是研究如何把若干个圆环嵌入到三维实欧氏空间中去的数学分支纽结理论的特别之处 大连理工大学硕士学位论文 是它研究的对象必须是三维空间中的曲线在两维空间中，由于没有足够的维数，我们 不可能把让一根曲线自己和自己缠绕在一起打成结；而在四维或以上的空间中，由于维 数太多，无论怎么样的纽结都能够很方便地被解开成没有结的曲线 1 2 1 纽结与链环的定义 绳结是人人熟悉的，史前时期就有结绳记事人类自从会用绳子，就会打绳结， 我们的祖先在事前时代用绳结来记事，周易中就由“上古结绳之治 f j 8 j 的记载博 物馆里保存着“基普印加人用来进行统计和记事的系着各种结的彩色绳子，却没 有人说的清这些结眼来代表的意思，印加帝国的历史就成了一连串的谜这是结绳记 事的最突出的例子打结也曾是一种重要的使用技能，因此早就由专门著作来研究 外国的绳结大全之类的书，主要是总结海员们的经验，在什么场合下该用什么结、 不该用什么结也有的书总结魔术师的经验在我国，货运工人、卡车司机、马车把式 对绳结都有丰富的实践经验 撇开纽结的用途、手法、绳子的材料、长短、粗细等因素，各种结在几何形状上有 没有本质的差异呢? 为识别不同的结，必须先把封起来，把打好结的绳子的两端捻合 在一起，成为没有端点的圈 _ 之广分u 净 或 。 或 一术 ) ( 1 f 图2 1 瑞德迈斯特变换 f i 薛1 r e i d e m e i s t e rm o v e s 这三种变换是在投影图的局部进行的，在变换的那个部分除所画的线以外不能由别 的线介入例如： 两种区分平面投影图平面合痕类的算法 图2 2 不合法的墨变换 f i 9 2 2 i l l e g a lt r a n s f o r m a t i o no f 置 不是一个合法的冠变换 上面这三种初等变换很明显都可以用挪动绳子来实现瑞德迈思特说，反过来，如 果空间中的一个链环可以经过绳圈的移动变形变成另一个链环，那么第一个链环的投影 图一定可以通过一连串的初等变换( 以及平面变形) 变成第二个链环的投影图 纽结与链环可以用投影图来确定然而等价的链环可以有不同的投影图例如图2 3 为 八字结的两个投影图， 图2 3 八字结 f i 醇3 t h ef i g u r e e i g h tk n o t 由此可见，要利用投影图来研究纽结理论，先决条件是必须弄清楚，绳圈在空间中 的移位变形怎么在投影图上反映出来不言而喻地，我们当然应该允许投影图的平面变 形1 ，即把平面看成橡皮薄膜时，画在上面的图形可以产生的变形例如 q q 图2 4 平面变形 f i 醇4 p l a n a ri s o t o p y 定义2 3 1 1如果：彳专】，是一一对应，并且厂及其逆f 。：y - - 4 , x 都是连续的，则称厂 是一个同胚映射，或称拓扑变换，简称同胚当存在x 到i ，的同胚映射时，就称x 与】， 同胚，记作x 兰y 例如，开区间( 作为e 1 的子空间) 同胚于 大连理工大学硕士学位论文 定义2 4 i 1 】如果f ：x 叶y 是单的连续映射，并且：x 一( z ) 是周胚映射，就称 厂：x y 是嵌入映射 2 1 2 镜像 纽结理论中的一个重要问题是镜像问题，或者称为手征问题 定义2 5 f 1 8 设三是一个纽结或链环三的镜像顾名思义就是三在镜子中的像它仍是 个纽结或链环，通常用r 表示 当镜子在移动时三在镜子中的像也是移动的，可以不管镜子放在什么位置，镜子中 的像总是互相同痕的所以当我们说到三的镜像时，不必指名竞在的位置；要画三的镜 像r 时，可以把镜子放在最方便的位置如果给定了三的投影图，设想把镜面放在话投 影图的纸面，纳闷立刻就能画出f 的投影图：只须把三的投影图改一改，把每个交叉点 处的上线改作下线，下线改作上线就行了 如下图2 5 t 1 8 】的两个链环是互为镜像的 反正 图2 5 正反怀特海德链环 f i 9 2 5 p o s i t i v ea n dn e g a t i v ew h i t e h e a dl i n k s 定义2 6 t 1 8 1有手征的：如果一个纽结或链环z 不与其镜像同痕，我们说工是有 手征的，例如：三叶结、正反怀特海德链环 定义2 7 无手征的：一个纽结或链环三与其镜像同痕，例如：八字结 2 1 3纽结( 或链环的) 可逆性 定义2 8 一个链环( 或其投影图) ，如果给它规定某一种走向后它与它的逆同痕，我 们就说这个链环是可逆的，否则说不可逆的 三叶结与八字结都是可逆的，只要在它们上面画上箭头再翻转一下就可看出许 多简单的纽结都是可逆的，不可逆的纽结的第一个例子直到1 9 6 4 年才得到证明 可逆性问题试问：任给一个纽结或链环，怎么判断它们是否可逆? 在实际应用中 ( 例如研究生物化学中像d n a 之类的长链状分子时) ，纽结或链环上往往带有自然的标 号( 如特定的碱基序列或氨基酸序列) ，可以看成有向链环因而可逆性问题一是一个 重要问题研究的经验告诉我们，可逆性问题往往比手征问题棘手，因为还没有找到 很有效的不变量 两种区分平面投影图平面合痕类的算法 2 1 3 连通和 设一个纽结可以移动到某个位置使得空间中某个平面与它只有两个交点，把该平 面两侧的部分各用贴近平面的直线段封闭起来，分别得到两个纽结，我们就说原来的 纽结分解为这两个新纽结之和，例如，懒散结是两个右手三叶结之和，而方结则是一 个右手三叶结和一个左手三叶结之和 反过来说，先给两个纽结，怎样构作它们的和呢? 首先在这两个纽结上各取一个 走向，成为有向纽结，设为毛，毛，把它们放在一个平面的两侧，分别把它们的一小 段( 随便那一段都可以) 拉向分隔平面，然后把它们在那平面处连通，使得走向互相协 调，所得的这个纽结为原来两个有向纽结的和，又称连通和，记作毛# 如，如下图： 一 毛恕与# 吃 图2 6 纽结岛与岛的连通和墨# 屯 r i 9 2 6 t h ec o m p o s i t i o nk 1 # 如o f t w ok n o t s 毛a n d 如 定义2 。9 r 3 6 - 3 7 非平凡的纽结，它不能在分解成两个非平凡纽结的连通和了，称之为素纽结 例如：三叶结、八字结，环面纽结，双桥纽结都是素纽结 定义2 1 0 将一个纽结取定一个方向，称为有向纽结，否则称为无向纽结 值得注意的是，即使对于无向纽结，定义它们的连通和时也应先赋予走向，否则就 有不同的接通方法，得到的结果可能互不同痕当然，如果毛，岛都是可逆的纽结， 那就无所谓了 就像每个正整数在乘法运算下有唯一的因子分解一样，每一个非平凡的纽结都可 以分解成素纽结的连通和，而且这样的分解式是唯一的并且任意这样的分解是唯一 的 结论2 1 任意两个有向纽结只能做出唯一的连通和 结论2 2 如果一个纽结的d t 码能被分成两个可分离的子序列( 例如 4 。6 。2 ll l o 1 2 鬈 ) ， 则由该d t 码所确定的纽结一定是两个纽结图的和如下图2 7 ： 大连理工大学硕士学位论文 2 2d t 码 图2 7 两个纽结图的和 f i 鲒7 ac o m p o s i t ek n o t 2 2 1d t 码的定义 纽结的d t 码1 3 s - 4 1 1 是描述一个纽结投影图的一种简单方法，它的优势在于给定一个 纽结的d t 码，你会能够很快的画出该纽结的投影图：反之，任意给定一个纽结，我们 可以按如下方法得到它所对应的纽结 首先，给出纽结的d t 码的定义对于交错纽结( 或交错链环) 4 2 - 4 4 1 而言，先任取一 个方向，再任取纽结图中一交叉点作为起始点( 有上下之分) ，标记为1 ，然后沿着已选 定的方向走，标记下一个交叉点为2 ，继续下去，标记下一个为3 ，直至该纽结图中每 一个点处都有两个标号( 都在1 于2 n 之间) ，并且可以肯定的是，每一点处的两个标号 一个为奇数，另一个为偶数然后，写出奇数序列l ，3 ，2 胛在一行，再将与每一个 奇数有相同交叉点的偶数对应地写在下一行，从而得到一个偶数序列，我们称这两个 奇偶序列为该交错纽结的d t 码，而这个偶数序列唯一决定着这个d t 码 如下图2 8 3 5 j 是一个交错纽结图 图2 8 每一个交点处标记两个数字 f i 9 2 8l a b e l i n ge a c hc r o s s i n go f t h ek n o tw i t ht w on u m b e r s 由d t 码定义，我们得到序列1 41 2 1 021 81 6864 是下面的缩写 13579l l1 31 51 7。 1 41 21 021 81 6 86 4 为上述纽结图的d t 码 两种区分平面投影图平面合痕类的算法 如果我们以不同的点为起始点，例如以原来的3 为起始点取并取原来的方向，得到 的d t 码为1 08 1 81 61 46421 2 ，如果仍以原来的1 为起始点，但是取相 反的方向，得到的d t 码为6 1 61 41 2421 81 08 ，从而得出如下的结论： 结论2 3 一个纽结的d t 码是不唯一，即如果选取不同的点为起始点或选取不同的方向 为选定的方向，则得到的d t 码与原来的不一定相同 其次，对于非交错纽结而言，也采取同样的方法，不同的是非交错纽结的d t 码中 会有正负数之分，我们只标记偶数部分，如果偶数部分在下，则标号前加一个负号， 否则默认为在上 如图2 9 t 3 5 1 。 图2 。9 非交错纽结 f i 9 2 9 an o n a l t c m a t i n gk n o t 它的d t 码为：序列6 - 1 41 6 - 1 22 - 4 - 81 0 是下面的缩写 l35791 l1 31 5 6 - 1 41 6 1 22 - 4 81 0 因此对于交错纽结的d t 码，如果我们选取的起始点在下，则得到的偶数序列一定 都为正数，与前面定义的交错纽结的d t 码不矛盾反之，如果起始点在上，得到的偶 数序列一定都为负数，又由结论2 3 知，d t 码虽然不同，但是有可能是同一个纽结，仍 不矛盾从而知交错纽结的任意一个d t 码的偶数序列都是同号的 再考虑链环的d t 码的定义与定义纽结的类似，先取该链环的其中任意一个分支 中的任意一点作为起始点，标号为l ，沿着某个方向走，下一个交点标号为2 ，继续下去， 直到回到起始点，设最后一个标号为，z l ；然后再取另一个分支，以任意一点作为起始点， 标号为+ 1 ，继续下去，直到该链环的每一个交叉点处都有两个标号为止 注意：链环的“d t 码”不能保证每一个交点处的两个标号一个为奇数，一个为偶数， 但是与纽结类似的，它的“d t 码就也是一个序列 大连理工大学硕士学位论文 2 。2 2d t 码得到对应纽结的方法 已知一个纽结的d t 码 135791 11 3 81 0 1 22 1 464 用如下方法可得到它的纽结图： 首先画出第一个交叉点，标上1 和8 ，并由正负号确定二者之间的上下位置关系， 然后，延伸这个标有l 号的边，标记下一个结点为2 和7 ，在由正负确定2 和7 的上下 位置关系，继续下去，直到下一个结点的标号f 已经存在为止，再将f 与i + 1 连接起来， 因为我们知道，纽结是一个经过每一个结点两次的闭合回路，所以直到将所有的标号 都经过为止如下图2 1 0e 3 5 】即为由d t 码8 1 01 221 46 4 所确定的纽结 图2 1 0d t 码是81 01 221 464 的某个纽结 f i 醇1 0 t h e k n o t t h a t c a 3 m c $ 知m81 01 2 21 46 4 但是值得注意的是，用上述方法得到的纽结或链环不一定唯一因为在用上述方法 得到对应纽结的过程中，当第二次经过该交点时会有两种选择，可以从两个方向经过 该点，从而导致所得到的纽结也有可能不同我们以图2 11 和图2 1 2 为例 如图2 1 1 ，它们是由d t 码462 1 01 28 得到的，但是它们不是合痕的可 以看出，它们的共同特点是都是连通和 图2 1 1 有相同d t 码的两个纽结 f i 驴11 t w ok n o t sw i t ht h es a m ed o w k e rn o t a t i o n 如图2 1 2 3 5 1 ，它们的d t 码都为8 61 0 2 4 ，但是这两个纽结也不是等价的， 共同点是它们是互为镜像的 两种区分平面投影图平面合痕类的算法 图2 1 2 互为镜像的两个纽结 f i 醇12 ak n o ta n di t sm i r r o ri m a g e 我们有这样的结论： 结论2 4 e 3 5 1 已知一个纽结图的d t 码，如果它所确定的纽结图不是连通和的，且不互 为镜像的( 不是有手征的) ，则它一定是唯一的 值得注意的是，如果任意给定一个序列，然而我们不能保证它一定能投影到平面 上，即当投影到平面上时有可能有自交点，这样用上面介绍的画纽结的方法是不能够 画出来的，但是如果前提是己知的序列是由纽结得出的，则显然是可以画出来的 类似地，对于链环，我们也可以运用例3 的方法，得到链环与对应序列的关系 2 2 3 纽结的d t 码的个数讨论 由结论2 3 知，一个纽结的d t 码的个数不是唯一的，对于一般的纽结，它的所有 d t 码的个数等于它的交叉点数n 的四倍( 因为可以以任意一个交叉点处的上或下作为起 始点，而且在不同的起始点处可以选取两个不同的方向) 但是这4 玎个d t 码中可能有 一部分是相同的，从而严格来说它的个数是小于等于 结论2 5 对于一些具有某种对称性的纽结，设它的交叉点数是珂，则它的所有的d t 码 的个数也是刀，且它们之间的关系为： ( 1 ) f + = 町；表示以i 点为起始点取正向得到的d t 码与以q 点为起始点取负向得到 的d t 码相同： ( 2 ) f + = ( f + ) + ；表示以f 点为起始点取正向得到的d t 码与以f + ，2 点为起始点取正 向得到的d t 码相同 ( 规定：与原来的纽结走向相同的方向规定为正向，相反的方向为负向) 以对称纽结5 ，结为例，如图： 大连理工大学硕士学位论文 图2 1 3 5 2 结 f i 醇1 3 t h e5 2k n o t 按上图所选定的方向与起始点，可以得到以下的特殊关系： 6821 04 对应于1 + ，6 + ，6 一，1 一的d t 码 481 026 对应于2 + ，7 + ，5 - , 1 0 一的d t 码 61 082 4 对应于3 + ，8 + ，8 一，3 一的d t 码 681 04 2 对应于4 + ，9 + ，9 一，4 一的d t 码 861 024 对应于5 + ，1 0 + ，2 一，7 的d t 码 可以看出5 ，结满足结论2 1 5 ，经过验证4 ，结也满足可以看出它们都具有某种对称 性反过来，如果已知一个纽结的d t 码，如果这些d t 码之间有一种对称性对应着由 它们所确定的纽结也有某种对称性 2 3 本章小节 本章主要是介绍一些纽结相关的基本知识，其中介绍了纽结的同胚、合痕的概念， 和纽结连通和、镜像、可逆的定义重点是介绍纽结或链环的d t 码的相关知识，包括 d t 码的定义，给出了已知d t 码得到对应的纽结，以及己知纽结得到它的d t 码的方法 同时对d t 码的个数进行了略微的讨论 大连理工大学硕士学位论文 3 两种区分平面投影图平面合痕类的算法 在上一章我们介绍了已知一个纽结如何得到它的d t 码，一个纽结我们选取不同的 起始点或不同的方向，可以得到也许不同的纽结，从而，一个纽结的d t 码个数至多是 4 n ，其中是纽结交叉点的个数所以，已知两个纽结，它们有相同的交叉点数， 我们就可以知道它们是否有相同的d t ，只要将它们的d t 码一一比较，我们就知道它们 的d t 码是否相同，这样的比较次数至多有( 4 ) 2 次，我们可以用计算机来实现显然， 对于交叉点数不同的两个纽结，它们一定不是合痕的，本章讨论的纽结分类问题【4 5 】前 提是已知交叉点数相同且d t 码相同的两个纽结，我们来判断它们是否是合痕的 3 1 一种区分两个纽结图是否合痕的方法( 一) 3 1 1 序列的实现 设【f ，刀是 f ，f + 1 ，j m o d 2 n 的一个整数区间，已矢i ：i k 是一个纽结到r 2 的投影 定义3 1 【4 6 1 函数a 是一个将序列 1 , 2 ，2 n ) 应到它自身的映射，且满足口( 口( f ) ) = i ，称 口为对合函数，其中口( f ) 是纽结图k 中另一个与i 有相同的投影的交点，我们常常记 口( f ) 为q 如果序列 1 , 2 ，2 n 及它的对合映射是由纽结得到的，则对合映射一定是奇偶倒向 的映射，即如果f 是奇数，则q 一定是偶数，相反也成立我们记序列q ，口2 a 2 。为s ， 从而子序列q ，a 3 ，a 2 川决定了a 和s 定义3 2 f 4 6 1 令f o ，2 n 1 是r 中的闭区间序列s 的一个实现是一个分段线性映射 p ： 0 , 2 n 】一r 2 ，使得 ( 1 ) p ( 0 ) = p ( 2 n ) ： ( 2 ) p ( f ) = p ( a ，) 其中汪1 ，2 ，2 n ： ( 3 ) p 将 o , 2 n 】 0 ，l ，2 n 的周胚映到足2 上； ( 4 ) 弧j d ( 【f 一万t ，f + 扣) 与弧p ( 口，一了1 ，q + 吾】) 交于点p ( f ) ，其中 f 一三，f + 三1 ，q 一三1 ，q + 三1 都是m 。d 2 玎的 对于每一个这样的实现，都存在一个被 o ，2 刀】参数化的交错纽结k ，使得p 是k 到 r 2 的投影如果存在序列s 的一个实现，我就称s 是可实现的 两种区分平面投影图平面合痕类的算法 定义3 3 t 删令s 2 是一个二维球面包含r 2 和一个无穷远点令g 是一个有限图，两个分 段线性嵌入q ，：g r 2 称为等价的，如果存在一个同胚映射h ：s 2 s 2 使得i i z 。q = f 2 。 因此，我们说序列s 的两个实现p l ，p ，：g 寸r 2 是等价的，如果存在一个同胚映射 h ：j 2 一s 2 使得h oa = p 2 如果k 是被 0 ，2 n 】参数化的纽结，使得n 将它投影到r 2 上，如果仍与岛是等价的， 则一定存在同样被参数化的纽结，见将它投影到r 2 上，且这两个纽结有相同的类型 由上面的分析可知，对于交错纽结k 而言，它的序列与d t 码是等同的，而对于非 交错的纽结，序列与d t 码不同的是d t 码有正负之分，如果去掉符号，d t 码与序列仍然 相同在文献【4 6 】中，给出了关于两个交错纽结( 或链环) 有相同的d t 码它们是否等价，在 下一节我们进行介绍 3 1 2 交错纽结且非纽结图的和的讨论 定义3 4 有限图g 保持无定向循环序，是指在图g 分段线性嵌入到r 2 上，使得每一 点处边保持与原来的顺序相同或相反的顺序，而不能打乱原来的顺序 以四度图3 1 、图3 2 为例来理解无定向循环序的定义， 1 l 4 3 1 l 2 3 k| 4 ( 1 ) ( 2 ) 图3 1 该点处保持边的无定向循环序( 其中图中卜4 代表四条边) f i 9 3 1p r e s e r v et h eu n o f i e n t e dc y c l i co r d e r a tt h ev e r t e x 1 | 4 3 1 | 4 2 图3 2 不保持边的无定向循环序 f i 够2n o tp r e s e r v et h eu n o r i e n t e dc y c l i co r d e r 从上面的例子我们可以看出，某点处保持无定向循环序是指，保持该点处四条边两 两对应的顺序，即如果将图3 1 中的( 1 ) 应到r 2 上，一定是要保证边1 和3 是对应的，边 2 和4 是对应的 3 大连理工大学硕士学位论文 法则3 1 删 设序列q ，a 2 ，口2 。即s 满足： ( 1 ) 刀3 ； ( 2 ) 没有序列 1 ，2 ，2 n ) 的真子区间【f ，f + 1 ，j m o d 2 n 由对合映射a ：k _ 吼将其 映到自身 从现在开始，我们只考虑满足法则3 1 的序列 因为 1 ，2 ，2 玎 有2 n ( 2 n 1 ) 个 1 ，2 ，2 n ) m o d 2 n 的真子区间，每一个区间有偶数 个元素，并且一个是另一个的补集每一个真子区间都是一一映射到自身的，所以如果 想检验一个给定的序列s 是否满足法则3 1 ，只要检验n ( n 一1 ) 个m o d 2 n 的区间就足够了， 每一个由至多丹个元素，或者检验 1 ，2 n 】 n ( n - 1 ) 个真子区间，不包含2 珂 因为每一个序列s 的实现都对应一个被f o ，2 n 参数化的纽结k 到r 2 的投影，所以 我们有下面的结论： 结论3 1 如果序列s 满足法则3 1 ，则与这个序列对应的纽结一定是两个纽结和的图； 反之也成立 例如： 已知序列s 如下： f q 1 23 4567891 0 1 1 1 2 1 01 167 83451 2129 我们知道，对于交错纽结而言，一个纽结足的序列与它的d t 码是等价的，所以我们可 以利用第二章介绍的，已知一个d t 如何得到与其对应的纽结的方法，得到与序列s 对 应的纽结k ，如图3 3 ： 图3 3 序列s 对应的纽结k f 炉3 t h e l m o tkc o m e s 觎嘲s 显然，该纽结图k 是一个纽结和的图，但是并不是两个纽结图的和其中序列s 中划线的部分是它的一个真子区间，且将自身映到自身，从而符合结论3 1 的结论 结论3 2 令图g 是个四度图，且是由【0 ，2 n 】得到的，其中将0 和2 n 、f 和口j 合并起来 ( f = 1 ，2 ，2 n ) ，如果它满足法则3 1 就会满足如下的三条 ( 1 ) g 的每一条边都连接两个相同的顶点： 两种区分平面投影图平面合痕类的算法 ( 2 ) g 中任意去除两条边，g 都保持连通： ( 3 ) g 中去掉任意一个顶点，g 都保持连通 引理3 1 【4 7 螂】已知g 是一个有限图，满足： ( 1 ) g 的每一条边都连接两个相同的顶点： ( 2 ) g 中任意去除两条边，g 都保持连通： ( 3 ) g 中去掉任意一个顶点，g 都保持连通 且给定图g 的每一点处边的无定向循环序，如果存在图g 到r 2 的一个分段线性嵌入且 保持每一点处的无定向循环序，则任意两个这样的嵌入都是等价的 综合以上结论，我们可以得出下面的定理： 定理3 1 4 6 1 如果序列s 是可实现的，则它的任意两个实现都是等价的 证明：因为每一个序列s 的实现都对应一个被【0 ，2 ，? 】参数化的纽结k 到r 2 的投影，又因 为纽结的投影图是一个四度图g ，且满足法则3 1 ，从而满足结论3 1 对于序列s 的任 意一个实现，都可被认为是一个图g 到足2 的分段线性嵌入，并且保持相在每一点处 i - 1 ，f 】，【a i - 1 ，q 】， f ，i + 1 】，【a i ，q + 1 】的无定向的循环顺序，更简单地来说，序列s 的 实现是一个分段线性嵌入f ：g 寸r 2 ，它保持在每一点处保持边的无定向循环序，从而 满足引理3 1 ，证毕 结论3 3 对于有相同序列( 或d t 码) 的交错纽结，且不是纽结和的图，则它们到r 2 的 投影是等价的 但是对于有相同序列( 或d t 码) 的非交错的，且不是纽结和的图的两个纽结，它们到 r 2 的投影是否等价，在后两节我们进行了详细的讨论 3 1 3 非纽结图的和的讨论 由引理3 1 知，已知d t 码或序列相同的两个纽结或链环，如果不是两个纽结图( 或 链环) 的和，如果不考虑手征问题，则它们一定是等价的但是在文献 4 6 】中没有给出怎 样区分一个纽结是否是有手征的，本文给出了一种判断方法以三叶结图3 4 为例： o - 图3 4 三叶结 f i 9 3 4t h et r e f o i lk n o t s 大连理工大学硕士学位论文 ( 1 ) 分别以图中给定的起始点和方向，我们得到它们有相同的d t 码为- 4 6 - 2 ( 2 ) 在左手三叶结中任取一交叉点，记为q ，在该点处有两个标号，然后在右手三 叶结中找到与这两个标号相同的交叉点，记为乃 ( 3 ) 我们规定： 十一 ( 4 ) 按上面规定的正负，如果q 与6 ，符号不同，则这两个纽结图是互为镜像的，否 则它们是合痕的只要判断一个交叉点就可以因为如果两个纽结中有一个点标号相同 且正负相同，其他标号相同的点正负不同，则这两个纽结的d t 码一定是不相同的 用这种方法可以得出左、右手三叶结是不等价的纽结，与三叶结有手征的正好吻合 相反的，对于无手征的，例如八字结，任何与它d t 码相同的纽结，按上面的规定，在每 一个对应点处的符号一定是相同的，所以它们是等价的由结论2 4 知，对于两个非纽结 图的和的纽结，我们只要按上面的四条判断，就可知道它们是否等价了 3 1 4 纽结图的和的纽结的讨论 己知两个纽结五，k ，它们有相同的d t 码记为s ，如果d t 码是可分离的，则原来 的两个纽结一定是纽结图的和 ( 1 ) 记s 的可分离的子序列为s ，剩下的部分记为最 ( 2 ) 在纽结图墨，局中分别将子序列s 所在的所有交叉点单独分离开来，然后将 两个端点接起来，得到两个子纽结，它们有相同的d t 码 ( 3 ) 如果两个子纽结是纽结图的和，则重复操作，否则判断它们是否是合痕( 只要判 断它是否是互为镜像的) ，如果不是，则原来的两个纽结一定是不合痕的，结束整个过 程 ( 4 ) 将s 换为最，重复上面的过程 如果纽结墨，憨的所有子纽结对应部分都合痕，则原来的纽结一定是合痕的我 们以第二章图3 5 为例 两种区分平面投影图平面合痕类的算法 图3 5d t 码相同的两个纽结图 f i 9 3 5t w o k n o td i a g r a m sw i t ht h es f l n l ed o w k c rn o t a t i o n 它们的d t 码是4621 0 1 28 ，显然是纽结图的和，则可以分成两个可分离 的子序列4 6 2 记为s ，和序列1 0 1 2 8 记为是其中与s 对应的那两个子纽结 我们按原来的顺序从新标号，用上一节的方法判断它们是等价的，结论是肯定的而与 &