（应用数学专业论文）群在图形上的应用及程序实现.pdf

摘 要 i 群在图形上的应用及程序实现群在图形上的应用及程序实现 作者简介：廖芳燕,女,1984 年 5 月生,师从成都理工大学魏贵民教授,2010 年 7 月毕业于成都理工大学应用数学专业,获得理学硕士学位. 摘摘 要要 本文首先对群作用和置换群作进行了进一步的研究,在这两个知识点的基础 之上讨论了位移群及刚体运动群并得到了一个很重要的结论： 凡旋转轴是通过空 间中一定点o的直线的有限阶旋转群只可能是五种型分别是n阶旋转循环群、 二 面体群、四面体群、正六面体群或正八面体群和正十二面体群或正二十面体群, 这与图论中 euler 多面体公式得到的空间中的五种正多面体：正四面体、正六面 体、正八面体、正十二面体和正二十面体的结论一致. 本文着重在正方体的对称变换、 刚体变换和对正方体的顶点和面不等价着色 的种类上面进行探讨和研究.正方体的对称变换共有 24 个,前人都有了很深入和 准确的研究.在对正方体的刚体变换进行研究时本文用了两种方法：正方体的 刚体变换的研究是在正方体的对称变换的基础之上进行的.正方体的对称变换是 由恒等旋转、绕三对对立面的中心旋转、绕对边中点的连线的旋转 180和绕对角 点的旋转组成.正方体的刚体变换的是在正方体的对称变换的基础之上增加了镜 面照映、反射成对径点、绕对角点的旋转与镜面照映乘积和绕对角点的旋转与反 射成对径点的乘积.从而得到了正方体的刚体变换的 48 种置换方式.这种方法具 体且形象的将正方体的刚体变换展现了出来.运用群作用的这一知识点,并结 合群的轨道个数、 稳定子群的个数和群的阶三者的数量关系最后得到了正方体的 刚体变换有 48 种.这种方式没有具体的得出正方体刚体变换， 只是通过抽象的数 量关系得到了最后的结果。 用形象和抽象的两种方式都得到了一致的结论即正方体的刚体变换的方式 共有 48 种。 接下来本文结合群论、数论和图论的部分知识点得到了burnside定理和 polya计数公式。然后运用这两个公式和相关知识点我们求得用红色和蓝色两种 颜色对正方体的顶点进行不等价着色共有 23 种方式；用红色和蓝色两种颜色对 正方体的面进行不等价着色共有 10 种方式。 成都理工大学 ii 最后本文用 matble 语言将正方体的对称变换与计算机程序结合起来,在计 算机上将正方体对称变换即恒等旋转、绕三对对立面的中心旋转、绕对边中点的 连线的旋转 180和绕对角点的旋转得以实现。 关键词关键词：群作用 置换群 程序实现 burnside定理polya计数公式 abstract iii group in the application of graph and the procedure realizes introduction of the author:liao fangyan, female, was born in may, 1984 whose tutor was professor wei guimin. she graduated from chengdu university of technology in applied mathematics major and was granted the master degree in june, 2010. abstract this article first did to the group action and the permutation group has conducted the further research, discussed the displacement group and the rigid body group of motions above a these two knowledge foundation and obtained a very important conclusion： every rotation axis is through the space in certain spot straight line limited step rotation group only possibly is five kinds respectively is the step revolving circulation group, the dihedral group, the tetrahedral group, the cube group either the octahedral group and the ten dihedral groups or the icosahedral group。this in spatial five kind of regular polyhedrons which the euler polyhedron formula obtains with the graph theory in: the regular tetrahedron, the cube, the octahedron, the dodecahedron and the two decahedrons conclusion is consistent. this article emphatically in the cube symmetry transformation, the rigid body transformation and are not equal to the cube apex dough making above the type which colors to carry on the discussion and the research。 the cube symmetry transformation altogether had 24, the predecessors had thorough and the accurate research。. when conducts the research to the cube rigid body transformation this article has used two methods: the cube rigid body transformations research is carries on above the cube symmetry transformation foundation. the cube symmetry transformation is by identically equal revolving, circles three pair of opposites central revolving, to circle the opposite side center point segment revolving and circles to vertex revolving is composed. what cube rigid body transformation was increases the mirror surface above the cube symmetry transformation foundation to cast light upon, to reflect the antipodal point, to circle to vertex revolving and the mirror surface casts light upon the product and circles to vertex revolving and reflects the antipodal point the product. thus obtained the cube rigid body transformation 48 replacement way. this method is concrete, and the image has unfolded the cube rigid body transformation. using the group functions this knowledge spot, the orbital integer which, stable subgroups integer and the group step three stoichiometric relation the parallel connection got on well with others obtains the cube rigid body transformation to have 48 kinds 成都理工大学 iv finally. this way concrete has not obtained the cube rigid body transformation, was only obtained the final result through the abstract stoichiometric relation. obtained the consistent conclusion with vivid and the abstract two ways is the cube rigid body transformation way altogether has 48 kinds. then this article unified the group theory, the theory of numbers and the graph theory partial knowledge spot obtained the theorem and the counting formula. then utilizes these two formulas and the related knowledge selects us to obtain carries on with red and the blue color two kind of colors to the cube apex is not equal colors altogether has 23 ways; carries on with red and the blue color two kind of colors to the cube surface is not equal colors altogether has 10 ways. finally this article the language unifies with matble the cube symmetry transformation and the computer program, in computer general cube symmetry transformation namely identically equal revolving, circles three pair of opposites central revolving, to circle the opposite side center point segment revolving and circles to vertex revolving can realize. keywords: group action permutation groups the procedure realizes burnsidetheorem polyacounting formula 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果.据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他 人已经发表或撰写过的研究成果,也不包含为获得 成都理工大学 或其他教育 机构的学位或证书而使用过的材料.与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意. 学位论文作者签名： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 成都理工大学 有关保留、使用学位论文的规定, 有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和 借阅.本人授权 成都理工大学 可以将学位论文的全部或部分内容编入有关数 据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文. （保密的学位论文在解密后适用本授权书） 学位论文作者签名： 学位论文作者导师签名： 年 月 日 第 1 章 引 言 1 第第 1 章章 引引 言言 1.1 选题依据及国内外研究现状（研究目的和意义）选题依据及国内外研究现状（研究目的和意义） 群论是法国传奇式人物伽罗瓦（ galois,18111832 年）的发明.他用该 理 论 , 具 体 来 说 是 伽 罗 瓦 群 , 解 决 了 五 次 方 程 问 题 . 在 此 之 后 柯 西 （ augustin-louis cauchy,17891857年 ), 阿 贝 尔 （ niels henrik abel,18021829 年）等人也对群论作出了发展. 最先产生的是n个文字的一些置换所构成的置换群,它是在研究当时代 数学的中心问题即五次以上的一元多项式方程是否可用根式求解的问题时, 经由 j.-l.拉格朗日、p.鲁菲尼、n.h.阿贝尔和 e.伽罗瓦引入和发展,并有成 效地用它彻底解决了这个中心问题.某个数域上一元n次多项式方程,它的 根之间的某些置换所构成的置换群被定义作该方程的伽罗瓦群,1832 年伽 罗瓦证明了： 一元n次多项式方程能用根式求解的一个充分必要条件是该方 程的伽罗瓦群为“可解群”（见有限群）.由于一般的一元n次方程的伽罗 瓦群是n个文字的对称群 n s.而当5n时 n s不是可解群,所以一般的五次以 上一元方程不能用根式求解.伽罗瓦还引入了置换群的同构、正规子群等重 要概念.应当指出,a.-l.柯西早在 1815 年就发表了有关置换群的第一篇论文, 并在 18441846 年间对置换群又做了很多工作.至于置换群的系统知识和 伽罗瓦用于方程理论的研究,由于伽罗瓦的原稿是他在决斗致死前夕赶写 成的,直到后来才在 c.若尔当的名著“置换和代数方程专论”中得到很好 的介绍和进一步的发展.置换群是最终产生和形成抽象群的第一个最主要 的来源. 在数论中,拉格朗日和 c.f.高斯研究过由具有同一判别式 d 的二次型类, 即 22 2cybxyaxf,其中cba,为整数,yx,取整数值.且acbd 2 为固定 值.对于两个型的复合乘法,构成一个交换群.j.w.r.戴德金于 1858 年和 l.克罗内克于 1870 年在其代数数论的研究中也引进了有限交换群以至有限 群.这些是导致抽象群论产生的第二个主要来源. 在若尔当的专著影响下,（c.）f.克莱因于 1872 年在其著名的埃尔朗根 纲领中指出,几何的分类可以通过无限连续变换群来进行.克莱因和（j.-） h.庞加莱在对 自守函数”的研究中曾用到其他类型的无限群（即离散群 或不连续群） .在 1870年前后, m.s.李开始研究连续变换群即解析变换李群, 成都理工大学硕士学位论文 2 用来阐明微分方程的解,并将它们分类.这无限变换群的理论成为导致抽象 群论产生的第三个主要来源. a.凯莱于 1849 年、 1854 年和 1878 年发表的论文中已然提到接近有 限抽象群的概念.f.g.弗罗贝尼乌斯于 1879 年和 e.内托于 1882 年以及 w.f.a.von 迪克于 18821883 年的工作也推进了这方面认识.19 世纪 80 年 代,综合上述三个主要来源,数学家们终于成功地概括出抽象群论的公理系 统,大约在 1890 年已得到公认.20 世纪初,e.v.亨廷顿,e.h.莫尔,l.e.迪克森 等都给出过抽象群的种种独立公理系统,这些公理系统和现代的定义一致. 在 18961911 年期间,w.伯恩赛德的“有限群论”先后两版,颇多增 益.g.弗罗贝尼乌斯、w.伯恩赛德、i.舒尔建立起有限群的矩阵表示论后, 有限群论已然形成.无限群论在 20 世纪初,也有专著,如 1916 年 .施米特 的著作.群论的发展导致 20 世纪 30 年代抽象代数学的兴起.尤其是近 30 年 来,有限群论取得了巨大的进展,1981 年初, 有限单群分类问题的完全解决 是一个突出的成果.与此同时,无限群论也有快速的进展. 时至今日,群的概念已经普遍地被认为是数学及其许多应用中最基本 的概念之一.它不但渗透到诸如几何学、代数拓扑学、函数论、泛函分析及 其他许多数学分支中而起着重要的作用,还形成了一些新学科如拓扑群、李 群、代数群、算术群等,它们还具有与群结构相联系的其他结构如拓扑、解 析流形、代数簇等,并在结晶学、理论物理、量子化学以至（代数）编码学、 自动机理论等方面,都有重要的应用.作为推广“群”的概念的产物：半群 和幺半群理论及其近年来对计算机科学和对算子理论的应用,也有很大的 发展.群论的计算机方法和程序的研究,已在迅速地发展. 今天,群论经常应用于物理领域.粗略地说,我们经常用群论来研究对 称性,这些对称性能够反映出在某种变化下的某些变化量的性质.它也跟物 理方程联系在一起.基础物理中常被提到的李群,就类似与伽罗瓦群被用来 解代数方程,与微分方程的解密切相关. 在物理上,置换群是很重要的一类群.置换群包括 3 s群,二维旋转群,三 维旋转群以及和反应四维时空相对应的洛仑兹群.洛仑兹群加上四维变换 就构成了 poincare 群. 另外, 晶体学中早期的关于晶体的各种结构的问题中,也是靠群论中 的费得洛夫群的研究给出了答案.群论指出,空间中互不相同的晶体结构只 有确定的 230 种. 第 1 章 引 言 3 在研究群时,使用表象而非群元是较方便的,因为群元一般来说都是抽 象的事物.表象可以看成矩阵,而矩阵具有和群元相同的性质.不可约表象 和单位表象是表象理论中的重要概念. 在许多研究群论的数学家眼中,也即指在抽象群论中,数学家关心的是 各元素间的运算关系,也即群的结构,而不管一个群的元素的具体含义是什 么.举一个具体的例子,群论研究表明,任何一个群都同构于由群的元素组 成的置换群.于是,特别是对研究有限群来说,研究置换群就是一个重要的 问题了. 因为每个抽象群都与一个置换群同构,所以从代数结构来看,这两类群 是没有什么区别的.然而对置换群有其独特的研究方法,有些关于置换群的 概念,例如通过群作用刻画的不动点和传递性等概念以及由此而得出的置 换群的一些特殊子群等,是置换群所特有的.而且我们还可以很方便的利用 置换群来构造一般的群.因此国内外对置换群通过群作用的方式进行了很 多的研究.在其他学科也有很好的应用. 今天,群论经常应用于物理领域.粗略地说,我们经常用群论来研究对 称性,这些对称性能够反映出在某种变化下的某些变化量的性质.它也跟物 理方程联系在一起.基础物理中常被提到的李群,就类似与伽罗瓦群被用来 解代数方程,与微分方程的解密切相关. 1.2 本文的研究思路及研究内容本文的研究思路及研究内容 在科学的各个领域以及科学应用的各个领域中,越来越多的各类构形应用于巨 型数据库中.这些构形可能非常复杂.在医学决策系统中,有医疗图像的大型数据 库.在分子生物研究中,有蛋白质结构的巨型数据库.在环境建模中,有环境特性的 巨大数据库.电信和信用卡公式有通信和消费模式的巨大数据库来帮助发现欺诈 行为.存储于这些巨型数据内的构形通常是复杂的几何对象,或带有各种维数或性 质的对象.这些巨型数据库使得搜索、恢复甚至组织等成为令人生畏的问题.有时 候,计数特定类型构形的数量以便帮助估测数据库中的搜索长度是很有用的.我们 遇到的问题之一是要确定两个构形是否相同.我们就要开发若干用于计数特定类 型的不同构形数量的技术.当然,这些技术的充分利用涉及精确地确定两个构形是 否相等的概念即群论中的图形的对称变换和刚体变换,还有图论中的图形同构问 题等. 我们有知道群常常是以作用的方式或者是自同构群的方式显示自己的 存在价值,不论是在理论上（甚至是数学自己的理论上）还是在应用上往往 都是这样.所以,为了解决上述问题我们必须掌握群论和图论中的相关知识 成都理工大学硕士学位论文 4 点.比如,群作用、置换群、群的共轭、burnside 轨道计数公式、cauchy 公 式、图的自同构、euler 多面体公式和 polya 计数定理等. 本文用群作用的思想证明了 burnside 轨道计数公式和 polya 计数定理.而群 论特别是置换群论也有自己的组合问题则由置换群我们又解决了对换图的问题. 然后我们综合以上的知识点解决了对图形着色的问题. 由以上的理论基础本文最后在 matlab软件上结合计算机程序对正方体的 对称变换予以实现。 第 2 章 预备知识 5 第第 2 章章 预备知识预备知识 2.1 符号说明符号说明 本文采用通用的一记号,为了叙述的方便和统一,特将文中所用的一些符号 作如下说明： g 表示一个有限群 g 表示g的阶 )(ao 表示元素a的阶 gexp 表示g的方次数 gn 表示n是g的子群 gn 表示n是g的真子群 gn 表示n是g的正规子群 gcharn 表示n是g的特征子群 kh 表示h和k的直积 ng 表示g关于正规子群n的商群 hg: 表示子群h在g中的指标 g 表示g的换位子群 )(gz 表示g的中心 )(hng 表示群g中h的正规化子 )(hcg 表示群g中h的中心化子 n s 表示n次对称群 n a 表示n次交代群 p z 表示p阶循环群 )(gsylp 表示g的sylowp子群集 成都理工大学硕士学位论文 6 )(gend 表示g的全体自同态组成的集合 )(gaut 表示g的自同构群 )(ginn 表示g的内自同构群 1 gg 表示g与 1 g同构 1 gg 表示g与 1 g同态 2.2 群论群论知识知识 引理 2-2-111 设x与y是两个基数相等的有限集合.则对于任意一双射, 映射yxf:. 1 ),()(: ffysymxsymf 是群同构并使得 xxxsymxffxf)(),()()( 引理 2-2-211 任意二个彼此无公共文字的循环置换相乘可交换. 引理 2-2-311 任一置换在不计乘积顺序的意义下可以唯一的写成彼此无公 共文字的循环置换之积使得每个文字恰出现一次,称为置换的循环分解. 把n次置换的循环分解 )()( 212222111211rkrrji aaaaaaaaa （21） 中的括号去掉,就是n, 2 , 1的一个排列. 引理 2-2-411 设)()( 212222111211rkrrji aaaaaaaaan次置换的 循环分解, n s,则 )()()()()()()()()( 212222111211 1 rkrrji aaaaaaaaa 证明 rkri aaaa, 1111 是n, 2 , 1的一个置换,所以, )(,),(,),(,),( 1111rkri aaaa也是n, 2 , 1的一个置换,因而上式右端是一 第 2 章 预备知识 7 个循环置换分解.那么只要证明 ),()(),()( 1312 1 1211 1 aaaa 即可；而这些式子时显然成立的. 定义 2-2-511 设 n次置换的循环分解中长度l的循环有)(l个,则 l 是 置换的非负整函数,称为置换的第l个型函数；在确定时,简记为 l .序列 ),( 21n 称为该n次置换的型；型有时也形式的记作 n n 212 1. 命题 2-2-611 对称群 n s中两置换与共轭当且仅当与的型相同,即 )()( ll ,nl, 2 , 1. 证明 必要性,若 1 ,由公式（2-1）以及定义 2-2-4,它们的型相同. 充分性,假设它们的型相同,那么可以把它们的循环分解按循环长度排列使得对 应的循环的长度相等 ),()( 212222111211rkrrji aaaaaaaaa ),()( 212222111211rkrrji bbbbbbbbb 那么 rkrri aaaaaa 2111211 与 rkrri bbbbbb 2111211 都是n, 2 , 1的排列,所 以 rkrrji rkrrji bbbbbbbbb aaaaaaaaa 212222111211 212222111211 是一个n次置换,由公式（2-1）就得 1 . 命题 2-2-711 cauchy 公式 型为),( 21n 的n次置换的个数是 12 12 ! ! 1 2 n n n n 证明 考虑填空模型 .(*)(*)(*)(*) 21 把n, 2 , 1填入各*位置处,共有! n种填法；这样就给出了全部型为),( 21n 的n次置换.但同一个n次置换在此过程中重复得出多次；前 1 个括号的任意排 成都理工大学硕士学位论文 8 列得出同一个置换,这种重复有! 1 次；类似的, 2 个*型括号给出! 2 次重复, 等等.又,同一个k循环可以有k种不同的写法 （循环中任一文字可以放在首位） , 而k循环有 k 个,就得到 k k 个重复；这里nk, 2 , 1.综合起来,同一个n次置 换在上述填空过程中重复得出的次数是 n n n 212 1! 21 . 定义 2-2-811 g是一个群,是一个非空集合.设,gx我们用 x 表 示中的一个元素.则有一个映射 x xg),( ;.我们就说群g作用在 集合上,如果满足： 1） g 1 =,. 2） xyyx )(,gyx,. 定义2-2-911 设群g在集合上的作用为.如果 ker=1,则称g忠实地 作用在上,这个时候可以把g看作上的变换群；如果ker=g,则称g平凡 的作用在上. 命 题2-2-1011 设 群g作 用 在 集 合上 , 则 对 每 个 , x gxg 是g的子群,叫做点的稳定子群.并且对任意的gy,有ygyg y 1 . 证明 设 gyx,则 yx ,. 于是 yxyx , 1 , 即 , 1 gxygx 所以,gg . 又,ygyxgyxygx yxyyxy x 11 1 )( . 于是ygyg y 1 . 定义 2-2-1111 设群g作用在集合上,称二元素，为等价的,记作 ,如果存在gx,使得 x .容易验证关系 “” 是上的等价关系.对 “” 的一个等价类叫做g在上的一个轨道.一个轨道所包含的元素个数叫做该 轨道的长. 对于,令gx xg ,则 g 是g的包含点的轨道. 第 2 章 预备知识 9 定义 2-2-1211 如果g在上只有一个轨道,即本身,则称g在上的作 用是传递的.这时也称g所对应的上的变换群是传递的. 定 理2-2-1311 设 有 限 群g作 用 在 有 限 集 合上 , 则 gg g : 特别地,轨道 g 的长是g的因子. 证明 对于任意的gg ,规定 g gf)(.则f是g到 g 上的满射.因为对任 意的ghg,有 gghhfgf ghhg 1 1 )()( hggg 于是轨道 g 中不同点的个数恰为 g在g中的右陪集个数,即 gg g :. 定义 2-2-141 设有限群g作用在有限集合上,. 对于子集中点在群g中的稳定子群表示为 , x gxg ）（ 对于子集在群g中的稳定子群表示为 x gxg 我 们 容 易 知 道 )( gg和都 是g的 子 群 并 且 有 gg ）（ . 注 意 到 ggg ）（ ,.一般说来对于有限集合 1k ， 我们通常用 k g , 1 代替 )( g 定义 2-2-151 设有限群g作用在有限集合x上.对gg ,令 xxgxxgfix)( |)( 称为g在集合x上的不动点集. 定理2-2-1611 （burnside轨道计数公式） 设有限群g作用在有限集合x上. 则x的g-轨道的个数t为 成都理工大学硕士学位论文 10 gg gfix g t)( 1 . （22） 证 明 取xx 1 , r xxrx xxx 21 , 21 ；取xxr 1 但 1 1xr x , 21 1 rrx xx r , n gggg, 21 . 建立映射： jji jji ij xxg xxg f 0 1 表表 2 2- -1 1 映射 ij f的取值 1 x 2 x r x 1r x 2r x 1 g 11 f 12 f r f1 1, 1 r f 2, 1 r f 2 g 21 f 22 f r f2 1, 2 r f 2, 2r f n g 1n f 2n f nr f 1, rn f 2, rn f 则：第一行有)( 1 gfix个 1； 第二行有)( 2 gfix个 1 第n行有)( n gfix个 1. 整个表格有 gg gfix)(个 1. 第一列有 1 x g个 1； 第二列有 2 x g个 1 第2r列有 2r x g个 1 整个表格有 r xxx ggg 21 个 1. 又由轨道长公式： 11 : xx gg 第 2 章 预备知识 11 得到 11 : xx gg而 r xxrx xxx 21 , 21 . 有 r xxx ggg 21 . 则gggrggg xxxxxx r 11121 . 整个表格的和为： g xx g xxx rrr ggggg 2121 . 那么有多少个轨道就有多少个g相加.所以有 gg gfixgt)(. 命题得证. 定理 2-2-1711 任意n次置换可以写成有限个对换的乘积,其对换因子的 个数为 )(mod2)t(个数 2.3 图论图论知识知识 定理 2-3-13 两个图 21,g g称为是同构的,如果存在一个从)( 1 gv到)( 2 gv 的一一对应使得：)( 111 gevu当且仅当)()()( 211 gevu.此时,称为是从 1 g到 2 g的一个同构.如果 1 g和 2 g是同构图,则称 1 g同构于 2 g,记为 21 gg .对 于非标号图 1 g和 2 g,如果对他们的顶点进行 （任意） 标号所得的标号图是同构的, 则称 1 g和 2 g是同构的.如果 1 g和 2 g不是同构的,则称他们为非同构图. 定义 2-3-211 设),(evx 是图. （1）vvv 21, 在x中称为连通的,如果 21 vv 或者 1 v到 2 v之间有一条道. （2）连通关系是v的等价关系,任一个等价类的导出子图称为图x的连通分 支. （3）如果x只有一个连通分支,则称x为连通图. （4）如果x的任意两地点之间都有一条边,则称x为完全图；n阶完全图常 记作 n k. 成都理工大学硕士学位论文 12 定义 2-3-311 n阶连通图的任意n阶子树称为该图的生成树.（75） 命题 2-3-411 图),(evx 中 （1）顶点 21,v v之间若有道则必有路. （2）顶点v到v若有闭路则必有含v的圈. 引理 2-3-53设),(evx 是一个连通图.则1 ve. 证明 对e进行归纳.当0e时,x只能是一个点的图或者是空图,命题显 然成立. 再设1 ne.任取euv )(.令),( evx 是从图x中去掉一条边)(uv后 得到的图,即)( uvee.对于任意vw,我们证明在图 x中或者与u连通或 者与v连通.若uw则w与u连通.再设uw .在图x中从w到u有一条开路 uvvvw l , 21 .若任意vvi,则边)(uv不在这条路中出现,所以w与u在图 x中也连通.否则,存在lj 0使得vvj；而且,因为路中无重复点,u不在路 vvvvw l , 21 中出现,故w与u在图 x中连通. 如果图 x是连通的,因ene1 ,由归纳法,得1 vee.如果 图 x不是连通的,由上段论证,图 x中u所在的连通分支),( uuu evx ,与v所在 的连通分支),( vvv evx ,满足vvv vu （即包含了x的所有顶点）和 eee vu ,那么可对连通图 u x和 v x分别使用归纳法,得 1 uu ve和1 vv ve； 所以 11) 1() 1(1 vvveee vuvu （23） 使得上述命题中的等号成立的图显然存在. 定理 2-3-611 设),(evx 是图.则以下三条件彼此等价： （1）x是一棵树； （2）x的任意两个不同点间恰好有一条路相连； 第 2 章 预备知识 13 （3）x连通而且1 ve. 证明 )2() 1 (.如果两点vvu之间有两条不同的路相连,则这两条路形 成闭路；由命题 2-2-4,x有圈. )3()2(.由（2）已知x连通,而且任意去掉一条边)(uv后得到的 x不再连 通（否则此二点在图x中有两条路相连） ；则 x恰有两个连通分支),( 1 1 1 evx 和),( 2 2 2 evx使得 2 1 vvv(不交并)且)( 2 1 uveee（不交并） ； 而且 图 1 x和 2 x显然都满足 （2） ； 可对图的阶v采用归纳法； 于是2 , 1, 1 ive ii ； 那么 11) 1() 1(1 2121 vvveee. ) 1 ()3(.由于x连通.若x有圈,可从x中去掉一条边使得所得图 ),( evx 仍然连通,但由 （3） ,得2 ve,按照公式 （2-3） ,这是不可能的. 所以x没有圈,即x是一座林.而x是连通的,故得到（1）. 定理 2-3-73（ euler 多面体公式） 设g是一个有e条边曲线的n阶平面图并假设g是连通的,那么g把平面分 割成的区域数r满足 2ner 证明 首先假设g是一棵树,因为有n个顶点的数有1n条边,则1 ne且 1r（唯一的区域是无穷区域,它的每条边曲线分解两次）则证明完毕. 再假设g不是一棵树,因为g是连通的,所以g有生成树t(包含g中所有顶 点 的 树 ),t的 顶 点 数 为nn , 边 数 为1 ne, 区 域 数 为1 r且 满 足 2 ner.我们可以设想,从t的一条边曲线开始,然后每次添加一条新的边 曲线,直到得到g.每次插入一条新的边曲线就把已经存在的区域分割成两个区域. 因此,每次插入另一条边曲线时, e增加 1, r增加 1, n不变总为n.所以,生成树t从 2 ner开始到添加所有余下的边曲线,该关系始终成立. 成都理工大学硕士学位论文 14 2.4 综合知识综合知识 引理 2-4-111 设nv, 2 , 1,e为集合v的一些对换的集合.则下述三条 件等价： （1） n se ,即e生成对称群 n s. （2）e生成的子群在上可迁； （3）图),(evx 连通. 证明 )2() 1 (.显然. )3()2(.反证之.若图),(evx 不连通,则x可分为子图),( 111 evx 和 ),( 222 evx使得 21 vvv(不交并)和 21 eee（不交并）,而它们二者不 连通.特别是, 1 e的任何对换不会把 1 v的点变成 2 v的点,也不会把 2 v的点变成 1 v 的点； 2 e的任何对换也是这样.对于任意e k 21 ,每个e i ,则也 不会把 1 v的点变成 2 v的点,等等.总之,e在v上不可迁；这与（2）矛盾. ) 1 () 3(.要证明（1）,由公式（2-2）,只要证明任意对换eij )(.但由（3）, 图),(evx 连通的,即有路 jiiii k , 21 使得每对换eii tt )( 1 .那么 eiiiiiiiiiiiiij kkkk )()()()( 21321213221 定理 2-4-211 至少要1n个对换才能生成n次对称群 n s.而1n个对换生 成对称群 n s当且仅当它们的图是一棵树（这里说的数是连通树）. 证明 由引理 2-3-1,m个n次对换生成 n s当且仅当它们的图连通；那么由引理 2-2-5,1nm.此即第一个结论.再由定理 2-2-6,1n个对换的图连通当且仅 当它是一棵树.这就是第二个结论. 定义 2-4-311 设g是群,运算写作乘法“”.在集合g上定义运算“”为 1221 gggg.则在运算“”之下g也是一个群称为原来的群),(g的反群.为 第 2 章 预备知识 15 了与原来群区别,记作 g. 命题 2-4-45 设群g作用在有限集合x上：gg 对应为x的可逆变换g ； 设c是集合. 则g在x上的作用诱导它的反群 0 g在集合),(cxhom上的作用： gg 对应为),(cxhom的可逆变换 * g使得),(, )( * cxhomgg. 问题 2-4-511 （1）设nv, 2 , 1,c是有限集,mc ；记:),(cvcvhom是所 有v到c的映射的集合.显然 n mcvhom),(. （2） 有限群g作用于集合v.在具体问题中这个群作用往往就是集合v上的 具体结构的自同构群,则由上个命题知,这个群作用诱导出g的反群 0 g在 ),(cvhom上 的 一 个 作 用 ： *0 ),(ggcvhomsymg, 其 中 ),(,)( * cvhomgg. （3）目的：求群 0 g在),(cvhom上的作用的轨道的个数. 定义 2-4-65 对于任意gg ,g作为v的一个置换,有循环分解,令其型为 )(,),(),( 21 ggg n .关于不定元 n xxx, 21 的多项式称为群g在集合v上的 循环指标多项式. gg g n gg n n xxx g xxxgp )()( 2 )( 121 21 1 ),;( 定理 2-4-711 0 g在),(cvhom上的轨道个数 gg ggg n mmm g mmmgp )()()( 21 1 ),;( 证明 由定理 2-1-15,所求轨道数为 gg gfix g )( 1 * 其中)( * gfix为 * g在),(cvhom上的不动点的集合.而)( * gfix当且仅当 vvvvg)()(,当且仅当vvivvg i , 0),()(；所以有以下结论. 成都理工大学硕士学位论文 16 结论 2-4-811 )( * gfix当且仅当在v的同一g-轨道上取同一值,即 是g-轨道函数.换言之,的函数轨道集合到的cgvgfix)( * . 长l的g-轨道有)(g l 个,取值c中的轨道函数在这)(g l 个轨道上可以取值的 方式有 )(g l m种.那么容易算出 )()()(* 21 )( ggg n mmmgfix 定义 2-4-97