4-连通图中最长圈上弦的存在性与可去边的关系

来源 :山东大学 | 被引量 : 0次 | 上传用户:qweasd123qweqwe
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1976年,Thomassen提出一个关于弦的猜想:在3-连通图中,每个最长圈上都至少存在一条弦.到目前为止,这个猜想在几类特殊的3-连通图中已被证明成立,不仅如此,此猜想已被拓展到4-连通图中,本文的主要内容就是通过可去边找到一类4-连通图,并证明此猜想在这类图中是成立的.主要定义及结论:  4-连通图中的可去边:  对于4-连通图G,及其中一条边e,从图中去掉边e,得到图G-e,  (1)若图G-e中所有点的度均大于等于4,则令G(☉)e=G-e.  (2)若图G-e中出现度等于3的点,则去掉此点,并用一个三角形连接它的3个邻点,新得到的图记为G(☉)e(若出现重边,去掉).若图G(☉)e仍为4-连通图,则称e为图G的可去边;否则为不可去边.  主要定理:  图G为4-连通图,令C表示图G中的最长圈.如果满足条件|E(C)∩ER(G)|≤7,那么圈C上存在弦.
其他文献
随着人类基因组计划的顺利实施,海量的基因和蛋白质数据随之产生,再加上互联网的发展与普及,生物信息学在近些年来得到了迅猛发展。DNA是遗传信息的携带者,蛋白质是生物体的基本
数据包络分析(Data Envelopment Analysis,简称DEA)是著名运筹学家A.Charnes和W.W.Cooper等学者以"相对效率评价"概念为基础发展起来的一种新的行之有效的系统分析方法.自197
学位
在实际生活中,我们遇到的问题一般都是多目标问题。而文献[15]证明了这些多目标问题基本上都可以直接写成多目标半定规划问题,或者对变量的约束进行一定的放宽,间接化成多目标半