组合计数的群论与计算机方法

本文综述组合数学和图论中解决计数问题的群论与计算机方法及其最新发展。传统的计数方法得到有限的计数公式或递推公式等，然而许多复杂的问题很难得到有限的表达式，即使能得到，公式也往往非常复杂。由于计算机技术的发展不仅使复杂的计数公式有了实际意义，而且可以设计恰当的计算方法进行数值计算，使计数问题有更为广阔的发展领域。另一方面，为了计算不同构的图或组合结构，最有效的方法是群论方法，因此把群论方法与计算机方     

计算组合学和计算图论

本文从搜索与优化、计数问题、构造与同构检验等三个方面介绍计算组合学、计算图论的内容和发展情况.     

竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制.     

21阶亚循环群的弱3-DCI性

本文证明21阶亚循环群G不是弱3-DCI群,否定了Babai和Frankl的一个猜测.此外还决定了群G的所有3元生成子集的CI-性.     

求整标函数的差分方程法

在一些计算问题中常常会遇到求某一个整标函数f(n)的问题,其中自变量n取整数值。例如,求数列的前n项和的问题:     

GROUP THEORY METHODFOR ENUMERATION OFOUTERPLANAR GRAPHS

1.IntroductionAplanargraphiscalledanouterplanargraph[']ifinitsplaneembeddingitsvenicescanbeplacedontheboundaryofaface.Thisfaceisusuallycalledanouterface.Anouterplanargraphissaidtobemaximumifwecannotaddanyedgetokeepitsouterplanarity.Wesupposethatallouterplanargraphsinvestigatedinthispaperaretwoconnected.Theedgesontheboundaryoftheouterfacearecalledouteredgesandotheredgesarecalledinneredgesorchords.Apathu--vconsistedofouteredgeswithd(u)23andd(v)23iscalledasinglechain.Asinglechainissaidtobetrivi…     

ON THE CONSTRUCTION AND ENUMERATION OF HAMILTONIAN GRAPHS

In this paer we give a farmula for enumerating the equivalent classes of orderly labeled Hamiltonian graphs under group D.and two algorithms for constructing these equivalent classes and all nonisomorphic Hamiltonian graphs.Some computational results obtained by microcomputers are listed.     

应用群论方法对极小2-连通图计数

§1.引言在通讯网络和其它一些网络问题中需要研究保证一定的连通度而造价最低的网络设计问题,极小连通图的理论正是以这类实际问题为背景的.设 G=(V,E)是点集为V、边集为 E 的图,称|V|=n 为 G 的阶.若(?)v∈V,G-v 仍是连通的,则称 G 是2-连通图.一个2-连通图 G 若去掉其中任何一条边就不再是2-连通了,则称 G 是一个极小2-连通图,又称极小块.极小块早于60年代由 Dirac 和 Plummer 所研究,其后很多著作([4],[5])都对它的性质作了论述.Hobbs 于1973年用逐次加点法构造出10阶以下的全部极小块,Read 和 Hu 于1985年用压缩图法计算出12阶以下的全部极小块的数目.下面我们先给出极小块的一些性质和它的压缩图的概念.     

一种最优C—匹配问题

本文以学校招生录取问题为背景提出了一种最优C-匹配问题,证明了关于一个二分图中存在完全C-匹配的充要条件的一个定理,针对问题的不同要求设计了两个最优C-匹配模型和算法,并编制了计算机程序,在招生工作中进行了试验,表明理论和方法都是可行的。