大学代数知识在互联网络中的应用

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