大学代数知识在互联网络中的应用-1.docx

大学代数知识在互联网络中的应用 大学代数知识在互联网络中的应用周进鑫（北京交通大学数学系，北京100044）摘要：代数方面的知识是数学工作者的必备基础。本文通过讨论大学代数知识在互联网络对称性研究中的应用，提出大学数学专业学生检验自己对已学代数知识的掌握程度的一种新思路，即思考一些比较前沿的数学问题。关键词：代数；对称；自同构基金项目：本文得到国家自然科学基金的资助（编号：11271012）作者简介：周进鑫（1979-），男（汉族），山西大同人，北京交通大学数学系副教授，硕士生导师，博士，研究方向：图的对称性、网络的容错性及可靠性。一、引言与基本概念高等代数（advanced algebra）和近世代数（abstractalgebra）是大学数学专业有关代数方面的两门重要课程。前者是大学数学各个专业最重要的主干基础课程之一，后者既是对前者的继续和深入，也是代数方面研究生课程的重要先修课程之一。这两门课程概念众多，内容高度抽象，是数学专业学生公认的难学课程。甚至，很多学生修完高等代数之后，就放弃了继续学习近世代数。即使对于那些坚持认真学完这两门课程的学生来讲，也未必能做到“不仅知其然，还知其所以然”，而要做到“知其所以然，还要知其不得不然”就更是难上加难了。众所周知，学习数学，不仅逻辑上要搞懂，还要做到真正掌握，学以致用，也就是“学到手”。当然，做课后习题和考试是检验是否学会的一个重要手段。然而，利用所学知识独立地去解决一些比较前沿的数学问题，也是检验我们对于知识理解和掌握程度的一个重要方法。这样做，不仅有助于巩固和加深对所学知识的理解，也有助于培养学生的创新意识和自学能力。笔者结合自己所从事的教学和科研工作，在这方面做了一些尝试。互连网络的拓扑结构可以用图来表示。为了提高网络性能，考虑到高对称性图具有许多优良的性质，数学与计算机科学工作者通常建议使用具有高对称性的图来做互联网络的模型。事实上，许多著名的网络，如：超立方体网络、折叠立方体网络、交错群图网络等都具有很强的对称性。而且这些网络的构造都是基于一个重要的代数结构即“群”。它们的对称性也是通过其自同构群在其各个对象（如：顶点集合、边集合等）上作用的传递性来描述的。下面介绍一些相关的概念。一个图G是一个二元组（V，E），其中V是一个有限集合，E为由V的若干二元子集组成的集合。称V为G的顶点集合，E为G的边集合。E中的每个二元子集u，v称为是图G的连接顶点u与v的一条边。图G的一个自同构f是G的顶点集合V上的一个一一映射（即置换），使得u，v为G的边当且仅当uf，vf也为G的边。图G的全体自同构依映射的合成构成一个群，称为G的全自同构群，记作Aut（G）。图G称为是顶点对称的，如对于G的任意两个顶点u与v，存在G的自同构f使得uf=v。图G称为是边对称的，如对于G的任意两条边u，v和x，y，存在G的自同构f使得uf，vf=x，y。设n为正整数，令Z2n为有限域Z2=0，1上的n维线性空间。由近世代数知识可知，Z2n的加法群是一个初等交换2群。在Z2n中取出如下n个单位向量：e1=（1，0，0），e2=（0，1，0，0），en=（0，0，1）。n维超立方体网络（记作Qn）是一个以Z2n为顶点集合的图，对于Qn的任意两个顶点u和v，u，v是Qn的一条边当且仅当v-u=ei，其中1in。n维折叠立方体网络（记作FQn）是一个以Z2n为顶点集合的图，对于Qn的任意两个顶点u和v，u，v是Qn的一条边当且仅当v-u=ei（1in）或者v-u=e1+en。n维交错群图网络（记作AGn）是一个以n级交错群An为顶点集合的图，对于AGn的任意两个顶点u和v，u，v是AGn的一条边当且仅当vu-1=ai或ai-1，这里3in，ai=（1，2，i）为一个3轮换。一个自然的问题是：这三类网络是否是顶点对称的？是否边对称的？但值得我们注意的是，这些问题都可以利用大学所学的代数知识得到完全解决。二、三类网络的对称性先来看n维超立方体网络的对称性。定理一：n维超立方体网络Qn是顶点和边对称的。证明：对于Z2n中的任一向量x=（x1，xn），如下定义V（Qn）=Z2n上面的一个映射：f（x）：uu+x，u取遍V（Qn）中所有元素。容易验证f（x）是一个1-1映射。（注：这个映射在高等代数中已学过，即所谓的平移映射。）而u，v是Qn的一条边，当且仅当v-u=ei（1in），当且仅当vf（x）-uf（x）=ei（1in），当且仅当v（f x），u（f x）是Qn的一条边。所以，f（x）也是Qn的一个自同构。这样，任取V（Qn）中两个顶点u和v，则uf（v-u）=v。从而说明Qn是顶点对称的。下面证明Qn是边对称的。只需证明：对于Qn的任一条边u，v，都存在Qn的自同构g使得ug，vg=0，e1，其中0为Z2n中的零向量。事实上，uf（-u），vf（-u）=0，v-u，其中v-u=ei （1in）。显然，e1，ei-1，ei，ei+1，en和ei，ei-1，e1，ei+1，en是Z2n的两组基向量。由高等代数知识可知存在Z2n上的可逆线性变换t使得t对换e1和ei而不动其余向量。此时易见，若a，b是Qn的一条边，则a-b=ej （1jn）。若j=1，则at-bt=ei；若j=i，则at-bt=e1；若j1，i，则at-bt=ej；所以at，bt也是Qn的一条边。由定义可知，t是Qn的一个自同构。进一步，0t，（v-u）t=0，e1，即uf（-u）t，vf（-u）t=0，e1。结论得证。利用和定理一相似的办法，我们进一步可以得到如下定理。定理二：n维折叠立方体网络FQn是顶点和边对称的。最后，来决定n维交错群图网络的对称性。定理三：n维交错群图网络AGn是顶点和边对称的。证明：首先，来证明AGn是顶点对称的。给定An中的一个元素g，如下定义一个映射：R（g）：xxg，其中x取遍An中所有元素。容易验证R（g）为AGn顶点集合上上的一个1-1映射。（注：这个映射在有限群论中是一个十分重要的映射，即所谓的右乘变换。）设u，v是AGn的一条边，则vu-1=ai或ai-1，这里1in。易见，（vg）（ug）-1=vu-1。所以，vR（g），uR（g）是AGn的一条边。因此，R（g）是AGn的一个自同构。这样，对于AGn的任意两个顶点u和v，有uR（g）=v，这里g=u-1v。这说明AGn是顶点对称的。下面来证明AGn是边对称的。只需证明对于AGn的任一条边u，v，都存在AGn的自同构g使得ug，vg=e，a3，其中e为An中的单位元。给定对称群Sn中的一个元素g，如下定义一个映射：C（g）：xg-1xg，其中x取遍An中所有元素。由近世代数知识可知，交错群An是对称群Sn的正规子群。容易验证C（g）是AGn的顶点集合上的一个1-1映射。（注：这个映射其实就是把An中任一元素x变为它在g下的共轭。这也是有限群论中一个十分常用的映射。）令x=（1，2），y（j）=（3，j），j=3，n。下面证明C（x）和C（y（j）都是AGn的自通构。取u，v为AGn的任一条边，则vu-1=ai或ai-1。从而，vC（x） （u-1） C（x）=（x-1vx）（x -1u-1x）=x-（1 vu-1）x=ai-1或ai。因此，uC（x），vC（x）也是AGn的一条边。从而说明C（x）是AGn的自通构。同理，若j=i，有vC（y（j）（u-1）C（y（j）=a3-1或a3；若ji，则有vC（y（j）（u-1）C（y（j）=ai-1或ai。这说明uC（y（j），vC（y（j）也是AGn的一条边，从而C（y（j）是AGn的自通构。现在，对于AGn的任一条边u，v，令g=u-1，则uR（g），vR（g）=e，vu-1=e，ai或e，ai-1。若i=3，则e，a3-1C（x）=e，a3。而若i 3，则e，aiC（y（j）=e，a3而e，ai-1C（y（j）=e，a3-1。由此可见，总存在AGn的自同构g使得ug，vg=e，a3，结论得证。至此，完全决定了这三类网络的对称性。不难看出，除了必要的图论概念外，我们的证明主要利用了高等代数和近世代数的知识。做为上述问题的继续和深入，有兴趣的同学还可以考虑以下问题：1.这些网络是否具有更强的对称性？比如：弧对称性？距离对称性？2.完全决定这些网络的全自同构群。实际上，利用与上面证明相同的思路，结合对图的局部结构的分析，利用一些组合技巧，这些问题也可以得到解决。三、小结大学所学代数知识在数学领域中的许多学科、乃至其他领域都有重要的应用。笔者认为任课教师可以根据自己所熟悉的科研领域，选取一些与大学代数知识有紧密联系的前沿数学问题，引导一些学有余力的学生开展相关研究，甚至可以吸引一些本科生加入自己的课题组。当然，教师要给予必要的指导，比如讲解相关背景知识、必要的概念和方法等。指导学生从相对简单的问题入手，循序渐进，由易到难，逐步加深对代数学知识的系统理解，积累一些经验，为考虑进一步的问题奠定基础。本文所提到的利用高等代数和近世代数的知识来研究网络的对称性就是笔者在教学工作中曾做过的一些尝试。在该方面，笔者指导完成了由三名大三学生参加的国家级大学生创新实验项目一项。这样以来，学生在学习经典数学知识的同时，也可以思考一些比较前沿的数学问题；学生在巩固已学知识的同时，也可以激发其学习兴趣，训练学生的逻辑思维，培养学生的创新思维，以及独立发现问题和解决问题的能力。