共查询到20条相似文献,搜索用时 406 毫秒
1.
小直径图的导出匹配覆盖 总被引:1,自引:1,他引:0
设G是一个图,而M1,M2,…,Mk是G的k个导出匹配.称{M1,M2,…,Mk}是图G的一个k-导出匹配覆盖,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解. 相似文献
2.
3.
4.
5.
《数学的实践与认识》2015,(12)
在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性. 相似文献
6.
本文针对从图的k-边覆盖问题引出的合作对策模型,利用线性规划对偶理论得到了其核心非空的一个充分条件和构造核心分配的多项式时间算法,并将这一结果推广到了一般的k-集合覆盖对策模型中. 相似文献
7.
8.
本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子;其次,黄光鑫曾先后给出了当g<f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件;最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件. 相似文献
9.
令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,Kt)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,Ks,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r2+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1). 相似文献
10.
本文就数学建模课的教学过程中 ,在“图的方法建模”一章中 ,关于图的最小覆盖法提出启发式算法 .用书中所给方法推出一个反例 ,分析了其产生错误的原因 ;通过对图的最小覆盖的概念的理解、结合分析图的关联矩阵的特点 ,给出了图的最小覆盖的启发式算法 . 相似文献
11.
12.
度量空间的序列商,k-映象 总被引:1,自引:1,他引:0
本文给出了度量空间序列商.肛映象的-些内部刻画。证明了空间X是度量空间的序列商。肛映象当且仅当X具有紧有限k-闭cs*-覆盖列的点星sn-网,当且仅当X具有紧有限k-闭覆盖列的点星网.作为上述结果的-个推论.不仅得到了空间X是度量空间序列商,k-映象当且仅当X是度量空间的k-映象,而且还证明了空间X是度量空间当且仅当X具有局部有限(紧有限)闭(肛闭)覆盖列的点星弱邻域网.这里“闭”(“k闭”)不能省略. 相似文献
13.
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数被完全确定. 相似文献
14.
图的划分问题曾引起图论界的广泛关注,在文献[4]中讨论了k-单圈划分,本文进一步研究基于k-单圈划分的优化问题,即在一个赋权图中求一个最小权可k-单圈划分的支撑子图,以及对一个不存在k-单圈划分支撑子图的图,如何添最少的边使得它有k-单圈划分的支撑子图。 相似文献
15.
《数学的实践与认识》2017,(23)
最小点覆盖问题是NP难问题,传统的计算复杂性理论认为,当规模n较大时,问题是难计算的,但大量的实例表明,即使规模相同的实例,由于其结构的不同,求最优解时也会花费不同的计算时间,所以建立一种度量具体实例求解难度的方法是必要的.介绍了一种度量最小点覆盖问题任一实例求解所需计算成本的方法,度量方法是以计算时间复杂度为O~*(2.314~(k-vc~*)(G))的参数算法为参照的,参数算法可用来求解点覆盖问题的判定问题,在参数算法中,当参数k为常数时,点覆盖问题可在多项式时间内求解,当k表现为n的函数时,点覆盖问题的难解性就表现出来了,结合最小点覆盖问题的近似算法—线性规划松弛来估计每个实例对应的参数k的取值范围,可在多项式时间内实现对最小点覆盖问题实例的计算成本的预测.对于平面点覆盖问题,则以EPTAS算法为工具实现更精确的度量. 相似文献
16.
17.
18.
箱覆盖问题是NP困难问题中的经典问题,得到了广泛地研究,九十年代以来,半定松驰策略被用来求解组合优化问题,取得了很好的结果[13],本文首次给箱覆盖问题的半定松驰算法,算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。 相似文献
19.
给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的. 相似文献
20.
陈锡平 《数学物理学报(A辑)》1990,10(1):69-73
设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。 相似文献