首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   14篇
  免费   1篇
综合类   1篇
数学   14篇
  2023年   2篇
  2014年   1篇
  2010年   1篇
  2008年   1篇
  2007年   1篇
  2006年   2篇
  2005年   1篇
  2004年   1篇
  1996年   1篇
  1995年   2篇
  1991年   1篇
  1990年   1篇
排序方式: 共有15条查询结果,搜索用时 15 毫秒
1.
本文给出了配对控制集在AT-free图的BFS-树上分布的结构性质.利用这些性质,我们给出了求解AT-free图类最小配对控制集的多项式时间算法.  相似文献   
2.
原晋江  康丽英 《数学杂志》1995,15(4):401-404
一个给定的图是否存在用r种颜色的正常Pk着色?称该问题为图的(k,r)路色数问题。已知对于直径为2的图及任意给定的整数r≥3,图的(2,r)路色数问题是NP-完全的。本文给出直径为2的(2,2)路色图的一个好的刻划,并由此给出该问题的一个多项式时间算法,从而解决了以r为参数的直径为2的图的(2,r)路色数问题的计算复杂性分类。  相似文献   
3.
本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1.相交于一点的直线簇,2.除一条直线外,其余的直线都平行的直线簇,3.一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大.本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n t)时间内求解.  相似文献   
4.
本文证明了顶点数至少为4的单位区间图是边泛圈图当且仅当它是3连通的。  相似文献   
5.
函数f:V(G)→{-1,1}称为图G的符号全控制函数,如果对每一个开邻域集上的点的函数值的和都大于等于1.符号全控制函数的权值是指图中所有点的函数值的求和.图的符号全控制数为图中所有符号全控制函数的最小权值.令G表示图G的补图.在该文中,我们研究符号全控制数的Nordhaus-Gaddum型不等式,给出了路与其补图的符号全控制数和的上界,以及图与其补图的符号全控制数和的下界.  相似文献   
6.
7.
设D是图G的一个顶点子集, 若D含有G的每个团中至少一个顶点, 则D称为G的团横贯集. 图G的团横贯数是指它的最小团横贯集中顶点的数目, 记作τc(G). 本文研究正则图的团横贯数. 首先建立了正则图的团横贯数的上、下界, 且刻画了达到下界的极值图. 其次, 对无爪三次图, 得到了改进的可达上、下界并刻画了达到下界的极值图.  相似文献   
8.
设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.  相似文献   
9.
康丽英  单而芳 《应用数学》1996,9(4):526-528
关于图的积的Domination数康丽英,单而芳(石家庄铁道学院基础部石家庄050043)(石家庄师专数学系石家庄050041)关键词:图;θ-图;Dominating集AMS(1991)主题分类:05C35.本文所讨论的图均为无环、无重边的有限简单...  相似文献   
10.
1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.  相似文献   
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号