[s,t]-图及其Hamilton性

一个图G叫[s ,t] -图,如果G中任意s个点的导出子图中至少含有t条边.本文讨论了某些[s,t] -图的Hamilton性质.

Cayley色图中的Hamilton路

Joseph B.Klerlein 在文[1]中证明了有限 Abell 群Γ具有极小生成元集△使Cayley 色图 D_△(T)为有向 Hamilton 图.本文证明了当Γ是 Abell 群时,连通的cayley 色图D_△(Γ)具有有向 Hamilton 路对任意的△成立,并举例说明一般的D_△(Γ)未必是 Hamilton 图.

Hamilton图的一个注记

本文的主要结果是：设G是D－圈图，若存在某个t≤δ，使得对任何t＋1个点的独立集，X＝｛x0，x1，…，xz），有，则G是Hamilton图。

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此,设计了一个在Edmonds意义下的有效算法———自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2)。最后通过应用实例说明该算法的有效性和实用性。

2~n和2p^2阶群上Cayley图的Hamilton图的分解

主要给出几类非交换群对Alspach猜想(当Cay(G,S)的度小于等于4时)成立,进一步对2n和2p2阶群Cayley图的Hamilton圈的分解进行了讨论.

有向图存在Hamilton圈的必要条件

应用随机过程理论——马尔柯夫链,我们得到有向图存在Hamilton圈的必要条件。一个不可约有向图(?)=(V,E)具有周期d,|V|=n,V能分解成V=C_1+C_2+…+C_d且C_k,K=1,2,…,d,是不相交的非空循环类。如果|C_k|不等于n/d,那么有向图不是一个有向的Hamilton图。

图的直接和的Hamilton圈研究

本文定义了图的直接和的概念,讨论了图的直接和中Hamilton圈的存在性。当图本身存在Hamilton圈时,它的直接和中的Hamilton圈也存在;设图G是n阶图,如果它的极大Hamilton子圈与Cn-1同构,那么它的直接和存在Hamilton圈;本文还研究了极大Hamilton子圈同构于Cn-2的n阶图并得到了三个充分条件。本文最后用超立方体Q4为例展示了这些命题的应用。

闭包是完全图的求Hamilton圈的新算法

Hamilton圈问题是一个典型的NP-完全问题,文章设计和研究了闭包是完全图的求Hamilton圈的新算法,其基于Bondy-Chvátal算法,与原来算法相比,新算法存在易于程序设计、可读性强等优点,且不失其好算法的特性。

基于图形展开及图形归约的过程模型验证方法

工作流过程模型是业务过程的形式化定义,在业务过程的分析、运行和重组方面起着关键性的作用.为了实现预期的业务目标,需要正确地定义工作流过程模型,它的正确性直接影响业务目标的实现,WfMS开始调度执行之前必须对其进行分析.针对大规模复杂应用的特点和业务过程执行的实际需要,对复杂工作流过程模型的正确性验证进行了研究;基于有向有环图(DCG图)详细讨论工作流过程模型的局部错误以及过程逻辑错误;给出了过程建模中避免错误的相关约束规则;另外了提出了一种新型的图形归约和图形展开相结合的验证方法及过程模型验证算法.

有向圈的矩阵算法及有关性质

用矩阵方法讨论了有向图的连通性 ,阐述了计算有向圈的矩阵方法及有向图为Hamilton图的充要条件 。

有向圈的行列式算法及HAMILTON图条件

本文引入有向路乘法、弧行列式等概念 ,讨论了弧行列式的性质 ,阐述了二种计算有向圈的行列式方法及有向图 D为 Hamilton图的充要条件 。

用有向图法确定报表系统中的公式计算顺序

首先提出了报表系统中的公式计算顺序问题,然后描述了公式计算顺序的形式定义,最后给出了用有向图法解决公式计算顺序的算法。

树枝形专用线取送车问题哈密尔顿图模型及算法

合理安排铁路专用线取送车顺序,对提高调车机车作业效率、加速货车周转具有重要的意义.在已知条件下,以机车在装卸点间走行时间为权,把树枝形专用线取(送)车作业优化问题转换成哈密尔顿图最短路问题,并松弛为指派问题,采用匈牙利算法求出指派问题的最优解,可得到最短回路路长的下界或最优解.若未得到最优解,再利用破圈连接法求出满意的取(送)车顺序,此算法的复杂度为O(n2).同时对送兼调移、取兼调移、取送结合、送调取结合作业形式进行了深入地讨论.最后举例说明了模型的构造及求解过程.大量小规模案例表明,该算法的平均复杂度及性能是比较优越的.

用有向图法解决公式循环依赖问题

用户使用报表系统时,在自定义的公式集合中可能存在公式循环依赖问题,用一种有效的方法发现这一隐藏错误是设计报表系统的一项关键技术。研究了用有向图法解决报表系统中的公式循环依赖问题,提出了报表系统中的公式循环依赖问题;引用有向图和集合论上的关系等概念对公式循环依赖进行了形式定义,证明了公式循环依赖的判定方法;给出了公式依赖关系图的构造算法和用有向图法解决公式循环依赖的算法。

关联矩阵的一些特殊性质

文章应用代数学中的置换理论,得出了关联矩阵的一些性质,这些性质为讨论关联矩阵的计数提供便利.

逐点循环递归法求哈密顿回路

给出了求解任意图的所有哈密顿回路逐点循环递归算法,用于处理复杂的旅行商问题,证明了一个图是否是哈密顿图。在算法中,用结点标号数组存储一个回路,无向图的正向表存储初始图。

用“遗传”算法求任意图的所有哈密顿回路

给出求解任意图所有哈密顿回路的"遗传"算法.首先,使用"继承"法,求完全图的所有哈密顿回路,既从Kk的哈密顿回路求Kk+1的哈密顿回路,直到Kn的哈密顿回路;然后,使用"选择"算法,将Kn中所有哈密顿回路在实际图中有不存在边的哈密顿回路去掉,最后得到任意图Gn的所有哈密顿回路,如果全部去掉,则该图不是哈密顿图.

用“递增”算法求完全图的所有哈密顿回路

本文给出求解完全图的所有哈密顿回路“递增”算法。即从Kn 的哈密顿回路求Kn +1 的哈密顿回路。任意给出一个图 ,可以根据结点数先求其完全图的所有哈密顿回路 ,在所有哈密顿回路中去掉那些在实际图中有不存在边的哈密顿回路 ,最后得到任意图的所有哈密顿回路 ,如果全部去掉 。

拓扑图的一种双向搜寻法

关于图G的节点(数码对)所作的双向搜寻产生一种搜寻树.由叠套结构组合出码,构成算法,基于节点关联矩阵的数码比较运算,逐层产生搜索树.用搜索树可系统地产生任意图的全部Hamilton回路,也可产生两节点间全部路径的完整系统.本算法易于编制程序,其速度快,内存小的优点是显而易见的.

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图