哈密尔顿圈相关论文
设α2(D)=max{|X|:X?V(D)且D[X]不含有向2-圈}是有向图D的α2(D)-独立数.在文献[Proc.London Math.Soc.,42 (1981) 231-251]中,Thomassen构......
本文仅考虑简单图.用G表示一个图.图中过每个顶点的圈,称为图的哈密尔顿圈.如果图中含有一个哈密尔顿圈,则该图是哈密尔顿的.哈密......
本文给出一个计算有向图上哈密尔顿圈个数的改进算法,该算法的基本思想是分步接受/拒绝。分步接受/拒绝方法已经成功地应用于渐进......
(n,k)-星图是Cayley图,具有许多优良的性质.(n,k)-星图作为一类重要的网络拓扑结构,可以用来设计大规模并行系统.设G是一个图,F (?)E(G).......
在本文中我们考虑的都是有限的无向简单图.一个图G的全图T(G)的顶点集是V (G)∪E(G),其中任意的两个点相邻当且仅当它们在G中相邻或关联.......
有向图是图论的一个重要分支,有向图的哈密尔顿性是图论的基本问题,在现实生活中有着非常广泛的应用.半个多世纪以来,人们对哈密尔......
有向图在图论的研究中非常重要.而有向图的哈密尔顿圈问题及与其相关的很多问题,已经被广泛地研究了半个多世纪,并且取得了较为显......
如果图G的一个子图F是G的一个支撑子图,则称F是G的一个因子.Akiyama和Kano将图的因子问题分为两类,分别称为:度因子问题和分支因子问题......
曲面Fullerene图是嵌入到曲面上的3-正则有限图,它的每个面的边界为5长或6长圈.这样的嵌入只能在球面、环面、克莱因瓶和射影平面......
图论的研究始于1736年,Euler用图的方法解决了哥尼斯堡(Konigsberg)七桥问题,并发表了第一篇关于图论的学术论文.从此,图论这门新的......
包含图中所有顶点的圈(或路)称为哈密尔顿圈(或哈密尔顿路).含哈密尔顿圈的图称为哈密尔顿图.判断一个给定的图是否哈密尔顿图的问题是......
星图是一种理想的Cayley图,其具有边对称性、很强的分层性、强容错性、可哈密尔顿性以及可嵌入性等特点。因此星图网络作为一个互......
哈密尔顿问题是结构图论中一个经典的研究课题,该问题与著名的四色问题存在着紧密联系.哈密尔顿问题在运筹学、通讯网络、社交网络......
随机图理论起源于Erdos和Renyi在1959-1968年间发表的一系列论文。该理论经过几十年的发展目前已成为一个独立且发展迅猛的离散数......
给出了图的基本运算,例如直和、笛卡尔积、强积、弱积等运算,并定义一种新的基于一个基的图运算,即图的基运算,通过图的基运算构造......
焦薄饼图是Cayley图,因而具有许多优良的性质.相同顶点数的焦薄饼图的度、直径等参数比超立方体的小.因此焦薄饼图作为一类重要的......
计算机或通信系统中各个元件之间不同的连接方式被称为该系统的互连网络。人们一般将互连网络看作一个图,图中顶点代表网络中的处......
平衡二部划分问题是图论的一个重要研究课题,本文研究了哈密尔顿平面图最小平衡二部划分上界的问题,主要证明了:哈密尔顿平面图G(V......
摘要:本文对生活中快递送货问题,应用哈密尔顿图、最佳推销员回路,建立模型,对完备加权图给出了近似算法、最小生成树算法和遗传算法三......
Cayley图在图论,群论,代数拓扑以及计算机科学中有广泛的应用。Babai已经证明了所有的图都可以被作为任何足够大的群上的Cayley图的......
该论文的主要结果论述如下:1、G是一个连通度不小于的n个顶点的图,H是G的一个顶点子集.2、借助于已知3-控制临界图的一般性理论及......
设G是n阶图,如果G中存在一个过所有顶点的圈,则称G为Hamilton图。若一个图的每一个分支是一条路,则称该图为一个路系统。定义-σ3......
设G=(V, E;w)为赋权图,定义G中点v的权度dwG(v)为G中与v相关联的所有边的权和,图G中圈的权值定义为圈中所有边的权和.范更华[7]中证明......
给定图G,G的全图T(G)是以V(G)∪E(G)为顶点集,对于x,y∈V(T(G)),如果x和y在G中是相邻的或相关的,则xy∈E(T(G))。令G--是全图T(G)的补......
在生态系统的研究中,人们最早以竞争图为数学模型表示物种之间的捕食关系.当捕食关系复杂时,竞争图这一数学模型受到了一定的局限性,......
版图设计已经成为电路设计的关键阶段。因而在物理层设计的早期阶段,一个好的版图设计是必须的。关于版图设计前人给出了很多设计方......
本论文在前人研究的基础上,进一步研究哈密尔顿圈问题及关于Vzing-猜想的某个特殊情况,主要内容包括:
·介绍了本文的研究背景和......
在图论中,有关哈圈和哈路的问题一直是图论学者研究的重点之一.随着Dirac和Ore将哈圈与度约束条件联系起来后,有关哈密尔顿性的度约......
图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象.一个连通图的树图能够反映该图的不......
本文研究了在超立方体Qn中通过给定三条边的所有圈的问题. 证明了: 设E0(∪)E(Qn)且|E0|=3≤n. 由E0导出的子图是线性森林, 则在Qn......
群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图.本文证明群作用......
本文研究了在超立方体Qn中通过给定三条边的所有圈的问题.证明了:设E0包含E(Qn)且|E0|=3≤n.由E0导出的子图是线性森林,则在Qn中E0的所有边......
飞机巡航最佳路线问题可归结为大型TSP问题。TSP问题是典型的NP完全问题,模拟退火算法是求解NP完全问题的一种理想方法。在构造了飞......
求解完全图上的哈密尔顿圈是典型的组合优化问题,遗传算法是解决此类NP问题的一种较理想的方法。对基本的遗传算法进行改进,在选择......
针对圆有向图的(1,2)步竞争图的结构,提出了竞争图中是否存在哈密尔顿圈;通过特殊到一般的方法得到如下结论:对于阶数n(n≥5)的强连通圆......
基于生活实例,引出问题讨论,建立了理论模型及实用简化模型,在BORLANDC环境中编程实现了最小生成树算法和递归穷举法.最后,分析了......
完全对换网络是互连网络设计中的一个重要的Cayley图模型,关于完全对换网络的一簇猜想如下:对任意整数n≥3,当n=0(mod 4)或1(mod 4)时,......
对简单图G=(V,E),Ore定理告诉我们:如果对G的每一对不相邻的顶点u,v都有d(u)+d(v)≥|V|,则G有哈密尔顿圈.证明了,若G仅包含一对不......
研究了有向图的两个方面:竞赛图的Hamilton-路数的计数及有关竞赛排名的相关问题,多部或n-部竞赛图是完全n-部图的一个定向。根据Bon......
第一天(4小时) 1.给定两个自然数m和n,其中n】1,且nm,试求最小的整数k,使得任意k个满足条件:“对一切1≤i【j≤k,n(a<sub>i</sub>-a<s......
提出了新概念:n阶图G的距离为2的任两点u,v及和这两点均不相邻且到这两点之一的距离为2的任一点w,若均满足|N(u)UN(v)|+d(w)≥n,则......
利用禁止子图给出了2-连通重爪图中哈密尔顿圈存在性的充分条件,并得到了2个结果:(1)G是一个含有n≥3个顶点的2-连通图,如果G是2-重图......