κ-连通图中最长圈上可收缩边数目

来源 :山东大学 | 被引量 : 0次 | 上传用户:qianxiaoping
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的连通性是图的最基本的性质之一,是图论中重要的研究课题。探讨连通图的结构特征,寻求连通图的构造方法一直是图论研究的前沿课题之一。为了寻找连通图的构造方法,人们的主要研究手段是引入一些能够保持图的连通性特性的运算。基于此,图的可收缩边运算成为研究复杂连通图的有力工具之一。  本文主要探讨了k-连通图中最长圈上的可收缩边的数目,并得到如下结果:  引理2.1 设P:x=x1x2…xn=y是k-连通图G中的一条最长的(x,y)-路,xixi+1(i=1,2,…,n-1)是P上一条不可收缩的边,且S={xi,xi+1,u1…uk-2}是其对应的k-点割。则G-S的每个连通分支至少包含P上的一点。  引理2.2 设P:x=x1x2…xn=y是k-连通图G的一条最长的(x,y)-路,且G的任意断片的阶至少为[k/2]+1。则P上至少包含两条可收缩边。  定理3.1 设G是一个k-连通图且G的任意断片的阶至少是[k/2]+1,C=x1x2…xnx1是G的任意最长圈,则C上至少有三条可收缩边。  更进一步,若该k-连通图中存在哈密顿圈,有如下结果:  定理3.2 设G为k-连通图(k≥2),G的任意断片的阶至少为[k/2]+1,若G中存在哈密顿圈C,则C上至少有六条可收缩边。
其他文献
本文首先研究了在BR=B(0,R)(?) RN,N≥3的球域上,形如的半线性椭圆方程在D’(BR)中解的存在性,其中常数β>0,q>1,0≤c≤c0,这里c0是Hardy不等式中的最佳常数.我们用变分法、山路引理
本文切合目前微分方程分支理论的研究状况,对连续的高维非线性动力系统分支理论中尚很少涉及却更一般的异维环分支问题进行了较深入的理论分析,并运用分支理论解释了一类癌症模
在传统排序问题中,总是假设工件信息在排序之初都已经全部知道.这些问题称之为离线(off-line)排序问题.在实际应用中,有些工件的信息在一开始往往是不知道的,而是随着时间的
在双参数量子群Ur,s(SO5)中,引入Harish-Chandra同态并用它确定B2型双参数量子群的中心,证明了Ur,s(SO5)的中心同构于两个未定元的多项式代数.  
令k是代数闭域,A表示k上的有限维代数,modA表示全部有限生成右A模组成的范畴。有关倾斜模的理论和反变有限子范畴在代数表示论中有着重要的作用,令T是modA中投射维数有限且有限
本文研究了简单无向图的拉普拉斯矩阵的主特征向量的分量的值的分布情况.给出了模最大以及模最小的分量的可达上下界,并分析图的结构特征,刻画了模最大分量达到上界时的极图.
在医学成像技术和计算机视觉领域不断发展的背景下,医学图像处理与分析技术在现代医疗系统中的作用越来越突出。近年来,由于基于图论的图像分割技术具有良好的分割特性,因此
张家川回族自治县在开展农村保持共产党员先进性教育活动期间,共有1086名农村青年递交了入党申请书,其中渠子乡八卜子村的马金虎、马凤英夫妇,双双同时申请入党。翻开他们的
n-正合范畴与n-阿贝尔范畴是2014年由Jasso(见[12])引进,是阿贝尔范畴与正合范畴的自然推广.本硕士学位论文主要研究n-正合范畴,n-阿贝尔范畴,以及新定义的n-稳定正合列的相关性
本文从文献入手,讨论了线性非标准奇摄动系统的一般情况。本文先在第二章中对线性非标准系统做了一坐标变换,从而得到了一些初步结论,而这些结论在具体讨论高指标系统时会有