检索结果-南通市图书馆

数学进展 2012年第3期41卷 356-360页

作者：刘春房王江鲁滨州学院数学与信息科学系滨州山东256603 山东师范大学数学科学学院济南山东250014

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|

关键词：顶点的度路可扩 Hamilton路

在线全文

学校读者我要写书评

暂无评论

两类图的度性条件和路圈性质

两类图的度性条件和路圈性质

作者：丛晓雨山东师范大学

学位级别：硕士

图的路和圈问题是图论中一个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题.图论中三大著名难题之一的Hamilton (?)可题本质上也是图的路和圈问题.国内外许多学者对此问题作了大量的研究工作.这方面的研究成果... 详细信息

图的路和圈问题是图论中一个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题.图论中三大著名难题之一的Hamilton (?)可题本质上也是图的路和圈问题.国内外许多学者对此问题作了大量的研究工作.这方面的研究成果和进展可参见文献[34]-[38].其中度条件和邻域并条件成为研究路和圈问题的重要途径,在这方面取得了很多优秀的成果.经过几十年的发展,图的路圈性质所涉及的内容日益丰富和具体.路的方面包括图的Hamilton路(可迹性),齐次可迹性,最长路,Hamilton连通,泛连通,路可扩等等;圈的方面包括图的Hamilton圈,最长圈,(点)泛圈,完全圈可扩,点不交的圈,圈覆盖等等.由于直接研究一般图的Hamilton问题往往比较困难,于是人们转而研究不含有某些禁用子图的图类.继Beineke1970年发表的关于线图性质的文章[18]之后,人们开始关注包含着线图的无爪图.70年代末80年代初,是研究无爪图的一个非常活跃的时期.关于无爪图方面的部分优秀成果可参考[1]-[3],[20]-[32].另外,无爪图的概念也被从不同角度推广到了更大的图类,半无爪图,几乎无爪图,(K1,4;2)-图等.本文主要对图的度条件(任意三个不相邻顶点的度和,邻域并的阶与最小度之和)与路圈性质(包括Hamilton连通,泛圈性等)之间的关系进行了一些探索,得出了无爪图和半无爪图的路圈性质的几个充分条件.在第一章中,我们主要介绍文章中所涉及的一些概念和术语符号,以及本文的研究背景和已有的一些结果.在第二章中,我们主要研究了无爪图在不同度条件下的路圈性质,得到下面的结果：定理2.1设G是n阶3-连通无爪图,如果σ3(G)≥n+1,则G是泛圈的.定理2.2设G是n阶3-连通无爪图,如果NC(G)+δ(G)≥n,则G是泛圈的.在第三章中,讨论了半无爪图在不同度条件下的路圈性质,得到下面的结果：定理3.1设G是2-连通的半无爪图,其阶为n,则当NC(G)+δ(G)≥n-1时,G是Hamilton图.定理3.2设G是n≥3的3-连通半无爪图,若NC(G)+δ(G)≥n+1,则G是Hamilton-连通图.

关键词：无爪图半无爪图顶点的度邻域并 Hamilton图泛圈

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的度和与圈可扩性

科学技术与工程 2008年第18期8卷 5220-5222页

作者：刘绪文潍坊教育学院潍坊262500

讨论了两个点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+1,则G是完全圈可扩的。

关键词：顶点的度完全圈可扩图连通图

在线全文

学校读者我要写书评

暂无评论

图的度和与扩圈

理论数学 2011年第2期1卷 64-67页

作者：王江鲁程建民山东师范大学数学科学学院济南

本文讨论了两顶点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶 ,如果G中任意一对不相邻的顶点u,v满足 ,则G中任意一个满足的圈C是可扩的。这里圈C的下界是最好可能的。由此进一步得到,如果G中任意一对不相邻的顶点u,v满足 ,则... 详细信息

本文讨论了两顶点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶 ,如果G中任意一对不相邻的顶点u,v满足 ,则G中任意一个满足的圈C是可扩的。这里圈C的下界是最好可能的。由此进一步得到,如果G中任意一对不相邻的顶点u,v满足 ,则G是完全圈可扩的。

关键词：顶点的度完全圈可扩图

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

图的最小度与路可扩性

科学技术与工程 2010年第11期10卷 2690-2693页

作者：滕岩王江鲁山东师范大学数学科学学院济南250014

讨论了图的最小度与路可扩之间的关系,得到当δ(G)≥2/G+1,则图G是路可扩的。这里δ(G)的下界是最好可能的。

关键词：顶点的度路可扩最小度

在线全文

学校读者我要写书评

暂无评论

图的最小顶点覆盖问题的面上DNA解法

小型微型计算机系统 2004年第2期25卷 242-244页

作者：王淑栋许进董亚非华中科技大学控制科学与工程系

1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图... 详细信息

1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图的最小顶点覆盖问题 .构造了含有 6个顶点 10条边的图的顶点集子集对应的数据池之后 ,进行了一系列的合成、杂交、清洗、变性等生物操作 ,得到所有覆盖对应的 DNA序列 ,然后通过编址过程得到所要求的最小覆盖 .

关键词： DNA计算覆盖顶点的度

在线全文

学校读者我要写书评

暂无评论

改进的最小顶点覆盖问题的贪婪算法

内蒙古师范大学学报（自然科学汉文版） 2012年第2期41卷 206-210页

作者：张楠张升内蒙古师范大学计算机与信息工程学院内蒙古呼和浩特010022 内蒙古师范大学公共管理学院内蒙古呼和浩特010022

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完... 详细信息

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2).

关键词：最小顶点覆盖问题贪婪算法顶点的度访问标记减治法

在线全文

学校读者我要写书评

暂无评论

两类特殊图论问题

中等数学 1996年第6期 15-17页

作者：冯跃峰湖南师大附中 410006

给定自然数n,r,探求在什么情况下,n阶简单图G中必存在r阶完全图kr,是图论中一个极为有趣的问题。下面介绍这一问题的某些结果。例1.设n（n>1）阶简单图G中不含k3,则其边数的最大值为[n2/4]。

关键词：简单图图论中顶点的度最大值自然数完全图边数最小度极值问题 5阶图

在线全文

学校读者我要写书评

暂无评论

第33届IMO越南国家队选拔试题

中等数学 1995年第3期 30-31,37页

作者：苏淳中国科技大学

第一天（4小时） 1.给定两个自然数m和n,其中n>1,且nm,试求最小的整数k,使得任意k个满足条件:“对一切1≤ii-aj）”的整数a1,a2,…,ak中,都存在两个整数as和at（s≠t）,使得m+as-at可被n整除。 2.给定一个次数≥1的实系数多项式f（x）,... 详细信息

第一天（4小时） 1.给定两个自然数m和n,其中n>1,且nm,试求最小的整数k,使得任意k个满足条件:“对一切1≤ii-aj）”的整数a1,a2,…,ak中,都存在两个整数as和at（s≠t）,使得m+as-at可被n整除。 2.给定一个次数≥1的实系数多项式f（x）,证明,对每个c>0,存在一个正整数n0满足如下条件:对每个次数≥n0

关键词：哈密尔顿圈实系数多项式国家队正整数解相邻顶点首项系数相似变换越南顶点的度算术平均值

1992中国数学奥林匹克(CMO)试题及解答

在线全文

学校读者我要写书评

暂无评论

中等数学 1992年第1期 35-39页

1992中国数学奥林匹克(第七届全国中学生数学冬令营)于1992.1.11～1.15在北京举行.香港张百康先生、台湾孙文先先生参加了本届冬令营活动.16个省、市组队参加了本届冬令营的“陈省身杯”团体比赛.经过两天比赛,湖南、四川、北京、黑龙... 详细信息

1992中国数学奥林匹克(第七届全国中学生数学冬令营)于1992.1.11～1.15在北京举行.香港张百康先生、台湾孙文先先生参加了本届冬令营活动.16个省、市组队参加了本届冬令营的“陈省身杯”团体比赛.经过两天比赛,湖南、四川、北京、黑龙江、广东、江苏荣获团体前六名.上海建平中学张健、安徽安庆一中何斯迈、天津耀华中学唐宁等21名营员入选中国数学奥林匹克国家集训队.

关键词：中国数学奥林匹克 CMO 顶点的度