有限群凯莱图的新求法

I·格罗斯曼和W·迈格努斯给出了群的几何图象———群的图象表示 ,即群的凯莱图 .主要是通过正多边形和正多面体的重合运动来求群的凯莱图的 .给出了由群的定义关系直接求群的凯莱图的基图法 ,并给出了 16阶群的凯莱图 .     

关于n元生成群的凯莱图(1)

关于n(n =2 ,3,4)元生成群的凯莱图的一般规律已被讨论 .但是 ,4元生成群凯莱图的具体实例在文献中尚未见到 .该文解决了这一问题 ,并给出了 2 4阶群的凯莱图 ,进而对 4元生成群的凯莱图进行了探讨 .     

凯莱图的单特征值

图的特征值通常指的是其邻接矩阵的特征值,而图的单特征值(重数为1的特征值)在刻画图的特性方面尤其重要.点传递图的单特征值已经有了明确的范围,但是,对于一个给定的点传递图,尚未找到一个好的方法确定其单特征值.凯莱图是一类重要的点传递图,本文将计算两类凯莱图(循环群和二面体群的凯莱图)的单特征值.给出了这两类凯莱图的特征值是单特征值所需要满足的必要条件,同时讨论了这些条件中哪些是充分条件,并给出例子来说明充分条件的复杂性.     

初等交换群凯莱图的完备码与完全图的正则覆盖

LEE证明了超立方体图Q_n存在完备码当且仅当n=2~m-1(m≥2是自然数),当且仅当它是完全图K_(n+1)的正则覆盖.本文中,给出了这个结论的一个简单证明,并把这个结论推广到了初等交换群的凯莱图中.证明了初等交换p-群Z_p~n(这里p是奇素数)的凯莱图有完备码当且仅当n=(p~m-1)/2 (这里m是自然数且n≥2),当且仅当它是完全图K_(2n+1)的正则覆盖.     

简单图的子图及其性质研究

给出图论中关于子图的定义,并得到子图的一些性质。通过定理阐述子图与其导出子图的同构性、子图与哈密尔顿图的关系,并证明和举例。     

度为2的阿贝尔群上Cayley有向图的最优设计

G是一个有两个生成元的集合M上的一个有限阿贝尔群.我们考虑有向凯莱图D(G,M),它的结点对应于集合M的元素,并且结点x和y相邻当且仅当y-x∈M.一个值得关注的问题是:对一个给定的正整数N,所有这样的N个结点的有限阿贝尔群上2度有向凯莱图的直径的最小值是多少?在本文,我们给出了一个比较快的算法来计算这个最小值.因此,对一个给定的正整数,用我们的算法可以找到一个直径最小的阿贝尔群上2度有向凯莱图.     

无爪图中子图的度和与Hamilton圈

定义了子图的度的概念,证明了如下结果：设图G是n阶2-连通无爪图,如果G中任意两个同构于心的不相邻子图日,也的度和d（H1）＋d（H2）≥n-2,则G有Hamilton圈．     

广义四元数群上正规弧传递凯莱图

研究了广义四元数群上正规弧传递凯莱图,通过对这些图的正规商图的研究,刻画了这些图的度数,完全分类了4倍素数阶2倍素数度的情形,并得到了广义四元数群上凯莱图的一些性质.     

群的Cayley图

用一些例子阐述了Ｃａｙｌｅｙ图的概念，论述了Ｃａｙｌｅｙ图的自同构群及相关结论，为进一步研究了Ｃａｙｌｅｙ图的同构五正则总是作好了了准备．。     

FCn的路径问题

路径问题是网络理论研究的一个重要课题.我们讨论了FCn这类网络模型中节点间的内点不相连最短路径的数目.由于FCn是凯莱图,利用凯莱图的点传递性计算了FCn中任意点到单位元点之间的所有内点不相连的最短路,并且证明了FCn在内点不相连的最短路径方面达到最大可能,是最优的.     

有向强正则图

有向的强正则图以及参数和特征值性质,与无向的强正则图有很多类似的地方.而强正则图的性质学者们早已进行了深入的研究.第二节运用群的理论,点的传递性提出了一类特殊的有向强正则图Cayley图,构造源于shaw的工作.并描述了Cayley图成为有向强正则图的必要条件.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

单群的点传递图的GI-性质

针对点传递图的同构问题,类似于Babai关于Cayley图为CI图的充分必要条件,给出了点传递图为GI-图的判别准则,并研究了单群的点传递图的GI-性质.     

图同构判定的新方法

图的同构问题由来已久,并且它的应用十分广泛。例如:确定一个图的自同构群的构造的问题和它有紧密联系;在有机化学上我们可以利用图的同构判定方法来确定同分异构物。因此,寻求图同构的判定方法是一项引人入胜的工作。提出了一个新的判定方法(定理1)可以方便的确定两个图是否同构。此外,还得到了某一类图的同构判定的一个较强的条件(定理2)。     

几类4-正则平面图的最小折数纵横扩张

主要讨论了4类4-正则图的最小折数纵横扩张,对任意阶这样的的4-正则图都给出了它的一个最小折数纵横扩张,并给出了最小折数与阶数之间的关系.     

一类新的优美图的构造及其证明

优美图是图论中极为有趣的重要研究课题之一,有着广泛的应用价值和研究前景．讨论了一类新的构造优美图的方法,并且给出了它们都是优美图的严格的数学证明,从而得到了图Gn=TVkn具有优美标号算法并且都是优美图等结论．所给的新的优美标号不同于现有的文献的结果．     

Heawood图的s-正则循环覆盖分类

一个图称为s-正则的,如果它的自同构群作用在它的s-弧集上是正则的.运用电压图及提升理论,对Heawood图的循环覆盖进行了分类.证明了:Heawood图的循环覆盖是1-正则的或2-正则的,当循环群的阶数不等于7或21时,覆盖是1-正则的,并且给出了这个1-正则无限类的构造;当循环群的阶数等于7或21时,覆盖是2-正则的.     

一类4-正则图的最小折数纵横扩张

提出了一类新的4-正则图,并讨论了其最小折数纵横扩张,设计出求最小纵横扩张的线性时间算法,给出了最小折数与阶数之间的关系.     

求解单圈多部图的匹配算法

给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。