共查询到20条相似文献,搜索用时 234 毫秒
1.
图的完美控制集和有效控制集是两类特殊的控制集.通常要判断一个图是否存在有效控制集是困难的.该文证明了无向循环图一定存在有效控制集.此外,给出了单圈图的完美控制数与其阶数的关系. 相似文献
2.
给出了图的临界控制集和优控制的定义,研究了顶点集合的子集合构成非平凡控制集的存在性问题,讨论了优控制与完美控制的关系. 相似文献
3.
孙林 《山东大学学报(理学版)》2011,46(8):92-94
由超图与其线图的关系,分别证明了单模超图、平衡超图、树形超图的线图是完美图。定义了k-完美超图,使其成为完美图的推广。讨论了正规超图和拟正则超图的完美性,并得出相应的结果。 相似文献
4.
孙林 《新疆师范大学学报(自然科学版)》2011,30(1):88-90
由完美图知道,如果图G和它的每一个诱导子图均满足其色数x等于其最大团的基数ω,则图G是完美的。在这篇论文中,定义了弱k-完美超图和强k-完美超图。在这个定义之下,完美图是超图的一个特殊情况。进一步,讨论了弱k-完美超图和强k-完美超图的性质,并且得出了一个定理,该定理不能由Lovasz的相应定理直接推广而来。 相似文献
5.
给出p-完美凸集、绝对p-完美凸集的定义,讨论了Banach空间中p-凸集、p-完美凸集、绝对p-完美凸集三者之间的关系, 同时给出了p-完美凸集和绝对p-完美凸集的若干性质(0
相似文献
6.
若C=D,则混合超图H=(X,C,D)称为bi-超图.向量R(H)=(r1,r2,…,rχ珋)表示超图H的色谱,其中ri(i=1,2,…,χ珋)表示H的不同的严格i-染色的数目,χ珋表示H的上色数.证明了对于一个确定的可行集,存在一个bi-超图有任意多的边数和点数,部分解决了由Voloshin提出的公开问题. 相似文献
7.
研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法. 相似文献
8.
An表示n阶交错群,α是由An的某些三循环构成的集合,Hα是由α生成的一个3-均匀超图.证明了α是An的生成集当且仅当Hα是n阶连通超图. 相似文献
9.
G(V,E)是一个图且D包含于V,如果N[D]=V,则称D为图G的控制集,进一步,对任一个控制集D1而言均有γ((D))≤γ((D1))成立,则称D为图G的小控制集,且小控制数γL(G)=min{|D|:D包含于V且D是G的一个小控制集}。如果点集S包含于V,A↓X∈V均有N(X)∩S≠φ或∪↑x∈SN(x)=V,则称S为图G的全控制集,且全控制数γ1(G)=min{|S|:S是G的一个全控制集}。 相似文献
10.
研究平面图的选择控制集问题.通过PX3C(planar exact cover by 3-sets)到平面图控制集的变换,证明了平面图的控制集问题是NP完全的,从而得到平面图的选择控制集问题的NP完全性.同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法. 相似文献
11.
李毛亲 《山西大学学报(自然科学版)》2006,29(4):359-361
给出了多目标最优化中关于Pareto弱有效集表示的一种新型的方法,即把弱有效集表示成两个集合之差,从而得到了一系列与目标集及控制锥的和、差、交及并相关的弱Pareto有效集的性质. 相似文献
12.
田叶 《河北师范大学学报(自然科学版)》2012,(4):332-335,354
对于图G=(V,E),如果V\S中的每个顶点都和S中至少1个顶点相邻,且G[V\S]是连通的,则称V的子集S是图G的外连通控制集.外连通控制集的最小基数~γc(G)称为图G的外连通控制数.给出了树删去1条边后对应的外连通控制数的可达下界,定义了关于边删除的~γc-严格图及~γc-稳定图,并对其相关性质进行了讨论. 相似文献
13.
14.
基于网络优化的交通网络设计研究 总被引:1,自引:0,他引:1
张江华 《复旦学报(自然科学版)》2008,47(2):260-265
针对交通网络设计问题,首先定义了赋权二分图的单边控制集问题,给出了相应的算法;然后将上述算法和割集遍历算法相结合,构建了基于网络优化思想的两个启发式算法,并对两个算法进行了比较分析,证明了算法Ⅱ可在有限步终止.最后通过算例验证了两个算法的有效性. 相似文献
15.
研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。 相似文献
16.
17.
证明了关于图的支配数、上支配数、全支配数、连通支配数、点-边弱(强)支配数及边-点弱(强)支配数的一些不等式,并继而讨论了这些不变量的若干介值性质 相似文献
18.
通过对图G的边集分析的方法,对图的符号星k控制数进行研究,确定了几类图的符号星k控制数 相似文献
19.
侯新民 《中国科学技术大学学报》2006,36(6):604-606
设G为n阶连通图,集合S称为图G的全控制集,如果V(G)的每个顶点都和S中某点相邻。图G的全控制数,记为γt(G),是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1,n-1的树T,γt(T)=min{(2n/3),n-l,[n/2]+l-1},这里l表示树T中叶子的数目。 相似文献
20.
研究了图的 Fractional 控制问题,主要给出了关于联图的 Fractional 控制数的1个上界,由此确定了几类特殊联图的 Fractional 控制数,并推广了部分已知的结果。 相似文献