图中点不交圈的相关问题

来源 :山东大学 | 被引量 : 0次 | 上传用户:jiaozhixuan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在此论文中,主要介绍图中一定条件的不交团及独立的圈在一些二分图中的相关结果.  本文令G代表一个图,它的顶点集和边集分别用V(G)和E(G)来表示.设v∈V(G),则点v在G中的度数表示为dG(v),图G的最大度和最小度分别表示为△(G)和δ(G).定义σ2(G)=min{d(x)+d(y)|x,y∈V(G),xy(∈)E(G)}.称k个图是可填装的,如果它们可嵌入到一个完全图中使得其中任意两个是边不交的.若k=2则称为2-填装,图中点不交的子图问题是一类特殊的2-填装问题.G的一个完全子图被称为团,若一个团中包含的顶点数为k,那么称其为k-团.1963年,Erd(o)s提出了一个关于图中包含k个点不交团的猜想.令G是一个顶点数为n的图,满足n=sk,s和k为正整数且s≥3,k≥1.若δ(G)≥(s-1)k,则G含有k个点不交的Ks.当s=4时,1978年Bollobós证明了:令G是一个顶点数为n的图,其中n=4k,k为正整数.若满足δ(G)≥3n/4,那么G包含k个独立的4-团.最近,Wang证明了:假设δ(G)≥[n/2],那么G包含k个独立的圈,其中k-1个为4-圈.此文将4-圈推广到4-团,研究了图中具有特定性质的不交团问题,证明结果如下:  结果1:令G是一个顶点数为n的图.如果n≥4k,k为正整数.并且δ(G)≥3n/4,那么G包含k-1个独立的4-团和一个弦圈,弦圈上的度大于等于3.  对于二部图G=(V1,V2;E),令G的两个部分的顶点集合分别为V1和V2.若|V1|=|V2|,则称G为均衡二部图.定义δ1,1(G)=min[d(x)+d(y)|x∈V1,y∈V2}.δ2,2(G)=min{d(x)+d(y)+d(u)+d(v)|x,y∈V1;u,v∈V2}.和σ1,1(G)=min{d(x)+d(y)|x∈V1,y∈V2,xy(∈)E(G)}.σ2,2(G)=min{d(x)+d(y)+d(u)+d(v)|x,y∈V1;u,v∈V2,e({x,y},{u,v})=0}.  如果一条路(或一个圈)被称为G的哈密顿路(或哈密顿圈),则图G中存在一条路(或一个圈)包含图G的所有点.著名的哈密尔顿圈理论的广义推广之一是图中独立的圈的问题.在1952年,Dirac证明了定理:令G是一个顶点数为n≥3的图,假若δ(G)≥n/2,则G中有一个哈密尔顿圈.在1963年,Corrádi和Hajnal证明了假设G是一个顶点数为n≥3k的图并且满足最小度δ(G)≥2k,则G包含k个独立的圈.对于二部图,1996,Wang证明了:令二部图G=(V1,V2;E)满足|V1|=|V2|=n≥2k+1,若δ(G)≥k+1,则G包含k个独立的圈.Enomoto提出是否可以用δ1,1或者σ1,1代替定理中的δ.2009,Yan和Gao证明了用σ1,1代替δ的情况.本文用σ2,2代替δ,进一步研究均衡二部图中点不交圈的相关问题,得到如下结果:  结果2:令k,n为两个正整数,G=(V1,V2;E)为一个二部图且满足|V1|=|V2|=n≥4k+4.如果σ2,2(G)≥4k+4,那么G包含k个点不交的圈.
其他文献
计算机辅助设计(Computer Aided Design,CAD)技术是一种应用计算机系统对产品进行分析、优化和修改的设计技术.  SDRC公司提出了变量化设计、参数化设计,它们是CAD技术的主要
本论文对于Hamilton算子理论进行了多方面的研究,得到了一些相应的结果.  一.建立了无界2×2算子矩阵的乘法运算和伴随运算的一般法则,得出了算子矩阵自伴的充分必要条件.对
流动党员存在的现状在流动人才和劳动力队伍中,有相当一部分共产党员,他们被称为“流动党员”。调查结果显示,德阳市直机关各级党组织以及和市直机关各级党组织有一定工作关
有限P群G的指数为沪的子群称为G的&极大子群. d(G)表示G的极小生成系中元素的个数,知(G)表示G的不含Frattini子群的k极大子群的个数.当k= l,d(G)- I和d( G)时,本文给出了 Sk(
模型和变量(特征)选择是现代统计学中最重要的问题之一。本文比较了-元线性回归模型中变量选择的Lasso方法及其相关方法的优良性,并提出了一个新的求解Lasso估计的算法——随
前馈神经网络中最常见的一种学习算法为误差反向传播算法(Back Propagation,BP),因此也称BP网络.BP网络虽然应用广泛,但却有一个缺点.实际应用中,常常没有一个很好的准则来选
“互联网+”时代催生了众多崭新的金融模式和金融产品,加之国内外政治和经济环境的不断变化,防范金融风险逐渐成为政府与实业界的工作重心。随着云计算、大数据等新技术的发展,对金融高频数据进行收集、分析的技术日益成熟,基于已实现测度的波动率预测和风险度量逐渐成为研究热点,但是基于Realized EGARCH模型对中国股市进行风险度量的研究亟待补充。本文对已实现EGARCH模型的残差分布进行拓展,尝试利用
学位
哈密顿函数在平衡点处的二次部分定号时,哈密顿函数在平衡位置有局部极值,可得这个平衡点是李雅普诺夫稳定。哈密顿系统在平衡点处非谱稳定时,必然非李雅普诺夫稳定,但谱稳定不能
行为金融学的发展,为我们研究金融市场中一些无法用传统金融学解释的情况,以及金融市场中存在的异象,提出了新的思路。投资者情绪属于行为金融学范畴,它会导致投资者对股票价格的认知偏差,从而导致股票价格偏离其基本价值,即投资者情绪对股票价格决策及其在股票市场上的变化产生重大影响。因此,对投资者情绪的研究有助于投资者更好地理解自己的情绪,使投资者能够更理性地面对金融市场的波动,从而做出合理的投资决策。本文将