大连理工大学硕士学位论文两种区分平面投影图平面合痕类的算法姓名：卢婷申请学位级别：硕士专业：基础数学指导教师：杨志青20090624大连理工大学硕士学位论文摘要拓扑学是近代发展起来的一个研究连续性现象的数学分支，也是十分重要的、基础性的数学分支．数学上的纽结理论是拓扑学的一个引人入胜的领域，而纽结理论的中心问题就是纽结分类问题，目前，已经有了能够判断纽结的等价性的算法．理论上可以造出一台机器，输入任意两个纽结的投影图，它都能判定它们是否等价．然而这只解决了理论上的可判定性，还不切实可行．在实际计算方面，数学家们已发明了一些新的多项式不变量，它们比亚历山大多项式包含更多的信息．本文是已有文献的结论的扩展和创新，主要介绍了两种区分平面投影图平面合痕类的算法．本文的结构如下：由于我们讨论的分类问题是基于纽结理论的，从而首先我们在第一章简单的介绍了拓扑学、纽结理论的发展历史及现状，及其在各个领域中的应用．在第二章，我们介绍了纽结理论中的基本概念，包括投影图、同胚、纽结的ＤＴ码的定义，以及详细介绍已知ＤＴ码如何得到与它对应的纽结的方法，在最后一节我们对某些特殊的纽结的ＤＴ码的个数进行了略微的讨论．第三章是本文的中心部分，重点介绍了两种区分两个纽结图是否等价的方法，即给出了两种区分平面投影图平面合痕类的算法，其中第一种方法是对文献［４６］的扩展，另一种方法是找到一个从一个纽结到另一个纽结的满足某种关系的映射，如果找到了，就可以说明这两个纽结是合痕的，实例表明这两种方法是可行的．关键词：纽结；投影图；ＤＴ码；序列的实现；等价两种区分平面投影图平面合痕类的算法ＴｗｏＡｌｇｏｒｉｔｈｍｓＤｉｓｔｉｎｇｕｉｓｈｉｎｇＤｉｓｔｉｎｃｔＬｉｎｋＤｉａｇｒａｍｓｕｐｔｏＰｌａｎａｒＩｓｏｔｏｐｙＡｂｓｔｒａｃｔＴｏｐｏｌｏｇｙ，ｗｈｉｃｈｉｓｄｅｖｅｌｏｐｅｄｉｎｍｏｄｅｍｔｉｍｅｓ，ｉｓａｌｌｉｍｐｏｒｔａｎｔａｎｄｂａｓｉｃｂｒａｎｃｈｏｆｍａｔｈｅｍａｔｉｃｓ，ｆｏｃｕｓｉｎｇｏｎｔｈｅｐｈｅｎｏｍｅｎｏｎｏｆｃｏｎｔｉｎｕｉｔｙ．Ｋｎｏｔｔｈｅｏｒｙｉｓａｌｌａｔｔｒａｃｔｉｖｅｆｉｅｌｄｏｆｔｏｐｏｌｏｇｙ，ａｎｄｉｔｓｃｅｎｔｒａｌｔｏｐｉｃｉｓｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｋｎｏｔｓ．Ｉｎｐｒｅｓｅｎｔ，ｍａｔｈｅｍａｔｉｃｉａｎｓｈａｖｅｂｅｅｎａｂｌｅｔｏｄｅｔｅｒｍｉｎｅｗｈｅｔｈｅｒｔｗｏｋｎｏｔｓａｒｅｅｑｕｉｖａｌｅｎｔ．Ｉｎｔｈｅｏｒｙ，ｗｅｃａｌｌｃｒｅａｔｅａｍａｃｈｉｎｅ，ｗｈｉｃｈｃａｎｄｅｔｅｒｍｉｎｅｗｈｅｔｈｅｒｔｗｏｉｎｐｕｔｏｆｋｎｏｔｐｒｏｊｅｃｔｉｏｎｓａｒｅｅｑｕｉｖａｌｅｎｔ．ＴｈｉｓＣａｌｌｂｅｄｅｔｅｒｍｉｎｅｄｔｈｅｏｒｅｔｉｃａｌｌｙ，ｂｕｔｎｏｔｐｒａｃｔｉｃａｌｌｙ．Ｉｎａｃｔｕａｌｃａｌｃｕｌａｔｉｏｎ，ｍａｔｈｅｍａｔｉｃｉａｎｓｈａｖｅｉｎｖｅｎｔｅｄａｎｕｍｂｅｒｏｆＰｏｌｙｎｏｍｉａｌＩｎｖａｒｉａｎｔｓ，ａｎｄｔｈｏｓｅｉｎｖａｒｉａｎｔｓｉｎｃｌｕｄｅｍｏｒｅｉｎｆｏｒｍａｔｉｏｎｔｈａｎｊｕｓｔｔｈｅＡｌｅｘａｎｄｅｒＰｏｌｙｎｏｍｉａｌ．Ｔｈｉｓａｒｔｉｃｌｅｍａｋｅｓｔｈｅｆｏｌｌｏｗｉｎｇｅｘｐａｎｓｉｏｎａｎｄｉｎｎｏｖａｔｉｏｎ，ｉｔｉｎｔｒｏｄｕｃｅｓｔｗｏａｌｇｏｒｉｔｈｍｓｄｉｓｔｉｎｇｕｉｓｈｉｎｇｄｉｓｔｉｎｃｔｌｉｎｋｄｉａｇｒａｍｓｕｐｔｏｐｌａｎａｒｉｓｏｔｏｐｙ．Ｔｈｉｓａｒｔｉｃｌｅｉｓｓｔｒｕｃｔｕｒｅｄａｓｆｏｌｌｏｗｓ：Ｆｏｒｔｈｅｐｒｏｂｌｅｍｓｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎｗｅｄｉｓｃｕｓｓｅｄｉｓａｂｏｕｔｋｎｏｔｔｈｅｏｒｙ，ＳＯ，ｆｉｓｔｏｆａｌｌ，ｗｅｉｎｔｒｏｄｕｃｅｔｏｐｏｌｏｇｙ，ｋｎｏｔｔｈｅｏｒｙａｎｄｔｈｅｉｒｈｉｓｔｏｒｙｏｆｄｅｖｅｌｏｐｍｅｎｔ，ａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎｉｎｖａｒｉｏｕｓｆｉｅｌｄｓｉｎｔｈｅｆｉｒｓｔｃｈａｐｔｅｒ．Ｉｎｔｈｅｓｅｃｏｎｄｃｈａｐｔｅｒ，ｗｅｉｎｔｒｏｄｕｃｅｔｈｅｂａｓｉｃｃｏｎｃｅｐｔｓｏｆｋｎｏｔｔｈｅｏｒｙ，ｉｎｃｌｕｄｉｎｇｒｅｇｕｌａｒｐｒｏｊｅｃｔｉｏｎ，ＤＴｃｏｄｅ，ａｓｗｅｌｌａｓｔｈｅｄｅｔａｉｌｓｏｎｈｏｗｔｏｇｅｔａＤＴｃｏｄｅｆｒｏｍａｋｎｏｔｐｒｏｊｅｃｔｉｏｎ．Ｆｉｎａｌｌｙ，ｗｅｈａｖｅａｌｉｔｔｌｅｄｉｓ悖酰螅螅椋铮?ｏｎｔｈｅｎｕｍｂｅｒｏｆＤＴｃｏｄｅｓｉｎｓｏｍｅｓｐｅｃｉａｌｋｎｏｔｓｐｒｏｊｅｃｔｉｏｎｓ．ＣｈａｐｔｅｒＨＩｉｓａｃｅｎｎ．ａＩｐａｒｔｏｆｔｈｉｓａｒｔｉｃｌｅ．ｆｏｃｕｓｉｎｇｏｎｔｗｏｍｅｔｈｏｄｓｔｏｄｉｓｔｉｎｇｕｉｓｈｄｉｓｔｉｎｃｔＬｉｎｋｄｉａｇｒａｍｓｕｐｔｏＰｌａｎａｒＩｓｏｔ