检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

几类乘积图的圈覆盖

福州大学学报（自然科学版） 1995年第1期23卷 8-14页

作者：江莹茵李剑敏罗由学福州大学数学系

文献［１］提出猜想：每个２─连通ｎ阶简单图都有一个圈覆盖Ｃ，使得｜ｃ｜≤（２ｎ－１）／３。此猜想至今尚未完全证实。本文对路、圈、完全图的若干笛卡尔乘积图和张量乘积图证实了猜想是正确的。

关键词：乘积图圈覆盖图论

在线全文

学校读者我要写书评

暂无评论

完全图Kv的最小偶圈覆盖

完全图Kv的最小偶圈覆盖

作者：张文军苏州大学

学位级别：硕士

完全图K的一个m—圈覆盖是指一个序偶(V,D)，其中V是K的顶点集，D是K的一簇长为m的圈，使K的每条边至少出现在D的一个圈中。当v为奇数且v(v-1)/2≡-1(modm)时，定义 b(v,m)=[v/m[(v-1)/2]]+1,否则，b(v,m)=[v/m[(v-1)/2]]。如果|D|=b(... 详细信息

完全图K的一个m—圈覆盖是指一个序偶(V,D)，其中V是K的顶点集，D是K的一簇长为m的圈，使K的每条边至少出现在D的一个圈中。当v为奇数且v(v-1)/2≡-1(modm)时，定义 b(v,m)=[v/m[(v-1)/2]]+1,否则，b(v,m)=[v/m[(v-1)/2]]。如果|D|=b(v,m)，则称此覆盖(V，D)为K的最小覆盖。本文中，我们就m是偶数及所有整数v≥m，研究了完全图K的最小m—圈覆盖的存在性问题。首先，我们运用递归构造的方法，把v的研究范围归结到归结到下面两种情形：(1)m≤v≤2m-1，当v是偶数时;(2)m≤v≤3m－1，当v是奇数时。进一步地，我们直接构造了v∈{m,m+1,m+2,2m-2,2m-1}时的最小m—圈覆盖。特别地，对m∈{6,8,10}及所有整数v≥m，给出了问题的完全解。

关键词：完全图覆盖圈覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

双圈覆盖猜想的拟度研究

双圈覆盖猜想的拟度研究

作者：张彰清华大学

学位级别：硕士

上世纪七十年代Szekeres和Seymour提出了著名的双圈覆盖猜想：每个无桥图均存在一系列偶子图使得原图每条边都恰好被覆盖两次。本文推广了普通偶图的定义,引入了符号偶图,从而建立了符号偶图覆盖的概念。作为核心成果,本文证明了符号双... 详细信息

上世纪七十年代Szekeres和Seymour提出了著名的双圈覆盖猜想：每个无桥图均存在一系列偶子图使得原图每条边都恰好被覆盖两次。本文推广了普通偶图的定义,引入了符号偶图,从而建立了符号偶图覆盖的概念。作为核心成果,本文证明了符号双圈覆盖的存在性,并试图将之转换为原猜想。由此将存在性问题转换为优化问题。文章最后讨论了所建立的符号覆盖与其它重要圈覆盖猜想之间的关系。本文在给出了关于符号覆盖的一些重要基本结果之后又引入了三种运算,用以将符号覆盖转换为原猜想。本文所提出的重要的完备性定理,保证了这种转换的可行性,从而建立了一种研究双圈覆盖猜想的新方法。

关键词：圈覆盖整数流符号偶图符号覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

关于DRC圈覆盖问题

关于DRC圈覆盖问题

作者：韩娜河北师范大学

学位级别：硕士

本文考虑的是由WDM网络的生存性设计所引发的满足DRC条件的圈覆盖问题．所谓DRC条件是将WDM网络中的”需求”在子网络上分配路径，使这些子网络保持相互独立．这个问题可被叙述如下：对于一个给定的图G，找到λK(λK)的边集的圈覆盖,其... 详细信息

本文考虑的是由WDM网络的生存性设计所引发的满足DRC条件的圈覆盖问题．所谓DRC条件是将WDM网络中的”需求”在子网络上分配路径，使这些子网络保持相互独立．这个问题可被叙述如下：对于一个给定的图G，找到λK(λK)的边集的圈覆盖,其中V(λK)=V(G)(V(λK)=V(G))，覆盖中的每个圈相对于G来说满足DRC条件，也就是说;对λK(λK)中的每条边对应G中一条路径，覆盖中的每一个圈中的边集所对应的路是顶点不交的．我们的目的是将覆盖中的圈数最小化．Jean-Claude Bermond等人在文献[1]中提出两个公开问题:当物理图G=C是—个大小为n的环并且逻辑图为λK或λK时,λK或λK的DRC覆盖的最小圈数为何值?对于这个问题，我们给出了最优解决方案，并且解决了有向图λK(λK)的DRC覆盖问题．

关键词： DRC 圈覆盖圈保护 WDM网

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

求欧拉图所有初级圈覆盖的一个算法

兰州大学学报 1982年第4期 9-15页

作者：林国宁张福基林诒勋兰州大学新疆大学郑州大学

本文利用深探法设计了一个求欧拉图一切无公共边的初级图覆盖(简称覆盖)的算法它由两个子算法组成:算法(Ⅰ):求欧拉图中过一边 e 的所有初级级图.算法 (Ⅱ):求欧拉图的一切无公共边的初级图覆盖.文中定理和算法对有向欧拉图也完全适用。

关键词：圈覆盖公共边算法欧拉图所有

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

关于图的圈覆盖

青岛大学学报（自然科学版） 1994年第1期7卷 44-48页

作者：刘建农山东经济学院

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对... 详细信息

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．

关键词：圈覆盖欧拉子图平面图图论

在线全文

学校读者我要写书评

暂无评论

完全图的最小6-圈覆盖和8-圈覆盖

山东理工大学学报（自然科学版） 2008年第4期22卷 15-18页

作者：张文军连云港职业技术学院基础课部江苏连云港222006

提出了完全图最小圈覆盖的覆盖数下界,运用递归构造的方法,把顶点数v的研究范围归结到区间[m,3m-1]中的部分数值上来,并就圈长m=6,8的情形给出了完全解.

关键词：组合数学递归构造完全图覆盖圈覆盖

在线全文

学校读者我要写书评

暂无评论

均衡路径覆盖和连通子图划分问题

均衡路径覆盖和连通子图划分问题

作者：姚会影杭州电子科技大学

学位级别：硕士

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容... 详细信息

本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容如下。第一章介绍了图论、计算复杂性和近似算法的一些基础知识,并阐述了{1,2}-边赋权完全图上最小最大k-路径（圈）覆盖问题和连通图上的均衡k-连通划分问题的研究现状。第二章研究了{1,2}-边赋权完全图上最小最大k-路径覆盖与k-圈覆盖问题。利用经典NP-哈密顿路问题和哈密顿圈问题进行多项式时间归约,证明了两个问题均是NP-难的。对最小最大2-路径覆盖问题,基于旅行售货商问题的一个近似算法,提出了一个近似比不超过11/7的算法,并给出了一个算例;然后将此算法推广到了一般最小最大k-路径覆盖问题,证明了算法的近似比不超过24/7-2/k。对于最小最大k-圈覆盖问题,基于上述最小最大k-路径覆盖问题算法,得到了一个近似比不超过19/7-1/k的算法。第三章研究了2-连通图上的均衡2-连通划分问题,基于局部搜索技术,提出了一个近似比不超过6/5的算法。第四章对全文的内容进行了总结,并对未来的研究方向给出了相关分析和展望。

关键词：路径覆盖圈覆盖图划分诱导子图 2-连通近似算法 NP-难

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

偶圈对完全图最小覆盖的若干同余类

淮阴工学院学报 2009年第1期18卷 5-9页

作者：张文军连云港职业技术学院基础课部江苏连云港222006

完全图Kv的m-圈覆盖是指一个序偶(V,D),其中V是Kv的顶点集,D是一族长为m的圈,使得Kv的各边至少在D的一个圈中。完全图的m-圈覆盖问题研究的关键在于确定最小覆盖的覆盖数。提出了完全图的最小圈覆盖的覆盖数的下界;进一步地直接构造了v... 详细信息

完全图Kv的m-圈覆盖是指一个序偶(V,D),其中V是Kv的顶点集,D是一族长为m的圈,使得Kv的各边至少在D的一个圈中。完全图的m-圈覆盖问题研究的关键在于确定最小覆盖的覆盖数。提出了完全图的最小圈覆盖的覆盖数的下界;进一步地直接构造了v∈{m,m+1,m+2,2m-2,2m-1}时的最小m-圈覆盖。最后,运用递归构造的方法,把顶点数v的研究范围归结到区间[m,3m-1]中的部分数值上来。

关键词：偶圈递归构造完全图覆盖圈覆盖