共查询到10条相似文献,搜索用时 31 毫秒
1.
研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,D1是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若Di(i=1,2,…,f)有1一路一圈因子,则D中必存在泛连通性点对。午且找到泛连通性点对的时间复杂度为0(n^0.5).(b)设D是由连通但非强连通竞赛图r的强分支t(1y(t)1≥3)平衡扩张而成的,(当Iy(t)I=1时,Ti不变),则D中必存在泛连通性点对。 相似文献
2.
郭巧萍等人证明了每个2-强连通竞赛图至少包含了3个外弧泛圈点.文章在增加一些前提条件的情况下,将对2-强连通竞赛图作进一步的研究. 相似文献
3.
文章研究了圆局部竞赛图的最小控制集.通过对非强连通圆的纯粹局部竞赛图、强连通的圆的纯粹局部竞赛图,以及圆的竞赛图三个子图类的分析,完全刻画了圆局部竞赛图最小控制集的结构. 相似文献
4.
圆可分解的局部竞赛图中的点外弧泛圈问题 总被引:1,自引:0,他引:1
Yao Tianxing(Discrete Appl.Math.,2000,99:245-249)已经证明了每一个强连通竞赛图都包含点,它的每条外弧都是泛圈的.将此结论推广到强连通的圆可分解的严格局部竞赛图,并证明了每一个强连通的圆可分解的严格局部竞赛图D,它的圆分解是D=R[D1,D2,…,Da],其中Di,i=1,2,…,a是强连通竞赛图,那么D包含一个点v,它的每条外弧是(g 1)-泛圈的,g=max{l(Ca)|Ca是包含a的最长诱导圈,a∈V(R),l(Ca)是Ca的长度}。 相似文献
5.
证明了在一些限制条件下的2-强连通竞赛图包含3个外孤泛圈点,并且讨论了一些强连通竞赛图的外弧泛圈点的个数。 相似文献
6.
7.
具有最小连通点对图的C-超图的染色讨论 总被引:1,自引:1,他引:0
主要讨论C-超图的染色与点的点对图的连通性之间的关系,证明了对任意给定的不小于3的正整数n,都存在上色数为n且具有最小连通点对图的3一致C-超图. 相似文献
8.
均匀多部竞赛图的分量共轭圈问题 总被引:1,自引:1,他引:0
GUO Yubao和Volkmann证明了一个2-强连通多部竞赛图包含两个分量共轭圈,使得每部至少有一个点在其中的一个圈中.得到的结论是Guo和Volkmann的定理的进一步推广. 相似文献
9.
在传统的竞赛矩阵理论基础上进行扩展,建立一种基于强连通竞赛图和竞赛矩阵的分析模型.讨论以篮球比赛为模型的篮球竞赛图,采用该模型计算比赛得分,对双循环的竞赛进行了排名.结果证明了该分析模型的合理性,当比赛对应的竞赛图为强连通时,用相应的竞赛矩阵理论进行排名,可以克服传统的竞赛矩阵理论只用于单循环赛事排名的局限性,适合更广泛的赛制. 相似文献
10.
郭巧萍 《山西大学学报(自然科学版)》2023,(1):126-130
为了在强连通多部竞赛图中寻找顶点和弧的外路,采用对原图去顶点或去弧的方法。通过在新得到的有向图中寻找哈密尔顿圈,进而找到顶点和弧的外路。研究结果表明强连通多部竞赛图中顶点和弧泛外路的两个充分条件被获得。 相似文献