二部竞赛图与超竞赛图的(1,2)步竞争图

来源 :山西大学 | 被引量 : 0次 | 上传用户:LAP281482184
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
竞争图的概念是由Cohen在研究食物链网络模型时提出的,被广泛应用于生态系统的研究.除此之外,它还被应用在噪声信道下通信的研究和设定无线电或电视发射机频道等问题.因而,有向图的竞争图越来越受到科研工作者的广泛关注.而随着Factor等人于2011年提出有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图后,关于类竞赛图的(i,j)步竞争图问题也成为学者们研究的热点之一.  本文研究二部竞赛图的竞争图及其与(1,2)步竞争图之间的关系,并在竞赛图的(1,2)步竞争图的基础上,刻画了超竞赛图的(1,2)步竞争图.  本文共分为四章.  第一章,绪论.介绍了应用背景,研究现状和基本概念,并提出本文主要内容.  第二章,针对两个部集分别具有m和n个顶点的二部竞赛图,研究了它的竞争图的独立数,得出最大独立数αmax(m,n)和最小独立数αmin(m,n),通过证明得到如下结论:  1.αmax(m,n)={4,m=n=2;max{m,n}+1,其它.  2.αmin(m,n)={2,m=1,n任意,或者n=1,m任意;2,m=5,n≥10,或者n=5,m≥10;2,m≥6且n≥6;3,其它.  3.若m,n满足(m,n)≠(1,1),则对任意整数k∈{3,4,…,max{m,n}+1},总存在某个二部竞赛图H=(X,Y),满足|X|=m,|Y|=n,使得H的竞争图G的独立数α(G)=k.  第三章,研究了二部竞赛图的竞争图与(1,2)步竞争图的边集关系,得到这两个图的边数之差的下界ε1,2min(m,n)和上界ε1,2max(m,n),并举例说明了上下界的紧性,通过证明得到如下结论:  1.设m≥2,n≥2是正整数,则ε1,2min(m,n)=0.此外,若H∈H(m,n)满足ε1,2(H)=ε1,2min(m,n)=0当且仅当H是下面情形之一:  (a)X→Y或Y→X;  (b)H是一个4圈.  2.设m≥4,n≥4是正整数,则ε1,2max(m,n)=mn.且若H∈H(m,n)满足ε1,2(H)=ε1,2max(m,n)=mn当且仅当H的每个顶点的出度不小于2.  第四章,刻画了超竞赛图的(1,2)步竞争图,并且将一些结论推广到超竞赛图的(i,j)步竞争图,通过证明得到了:  1.设3≤k≤n-1,顶点数为n的图G是某个强连通k超竞赛图T的(1,2)步竞争图当且仅当G为Kn;Kn-E(P2),或者Kn-E(P3).  2.设3≤k≤n-1,顶点数为n的图G是某个k超竞赛图T的(1,2)步竞争图当且仅当G为Kn,Kn-1∪K1,Kn-E(P2),或者Kn-E(P3).  3.设T是一个顶点数为n的k超竞赛图,满足3≤k≤n-1.设i≥1,j≥2是整数,则Ci,j(T)=C1,2(T).
其他文献
在图论中,有关哈圈和哈路的问题一直是图论学者研究的重点之一.随着Dirac和Ore将哈圈与度约束条件联系起来后,有关哈密尔顿性的度约束条件成为了学者们研究的热点.二部有向图是
随着世界经济一体化的加快,多式联运作为国际物流服务中的一个重要环节,以其灵活、方便、安全等特点而倍受货主的亲睐。关于多式联运优化问题的研究,即如何对运输路径和运输
“蒙山红”是山楂品种“甜红子”芽变新品种。2010年通过山东省农作物品种审定委员会审定。该品种果实扁圆形,纵径2.02 cm,横径约2.70 cm。果个大,平均单果重14.15 g,大小整
最小费用最大流问题作为网络流问题的组成部分,主要研究的是网络最优化问题,它在工程、经济及科学等领域有着重要意义。其主要涉及最短路、最大流及最小费用流等方面的问题,随着
本文研究竞赛图中满足一定最小出度条件的点不交4-圈问题.这篇文章只考虑有向图,除非特殊说明,否则下文提到的圈都是有向圈.令G是一个有向图,V(D)表示它的顶点集,A(D)表示它的弧集.称圈C是一个q-圈,如果|V(C)==q.令T是一个有向图,如果对T中任意两个不同顶点χ和y.恰有(χ,y)或者(y.χ)中的一条弧属于A(T),则称T是一个竞赛图,设v e V(T).则点v在T中的出度表示为d+(
学位
期刊
设N,F为有限群.若存在有限群G,它具有正规子群N~使得N~()N且G/N~()F,则称群G为群F的扩张.若N~≤Z(G),则称群G为群F的中心扩张.特别地,若∣N∣=2,称G为群F的2次中心扩张.本文利用中心扩
分析了油井气锁形成原因,同时进行油井正常生产与发生气锁时的生产数据对比,并探讨了油田气锁的分析与处理,以期为油井气锁的分析与处理提供一些参考,确保油井的正常生产.
随着科学信息计算的发展,在各个工程技术领域中(如医学、军事等)出现大量的数字图像(包括造影图像、红外图像等),需要有效、快速的提取数字图像中的有用信息,因此图像分割、目标特征
广义线性模型在经济、生物、医学等领域中有着广泛地运用。然而随着实验样本的增加,特别是当维数p远大于样本数量n时,传统的估计方法选不出真实的模型。在这样的高维问题中,我们