恰含6条非基本边的极小3连通图

来源 :山东大学 | 被引量 : 0次 | 上传用户:javaoak
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的连通性是图的最重要的性质之一,也是图论中的一个重要研究课题.由于连通图跟网络模型和组合优化的联系日益密切,从而使连通图理论拥有更加重要的理论价值和应用价值.连通图中的非基本边是研究3连通图结构特征的重要归纳工具,它作为有力的归纳工具,具有独特的优势:   第一,非基本边的处理简单方便,不会出现重边;   第二,非基本边的改变不影响其他任何边的存在.   因而,非基本边在探讨连通图的结构上应用的十分广泛.正因如此,近年来,关于连通图中非基本边的研究已成为一个热点问题.   本文通过研究连通图中的非基本边来刻画极小3连通图的结构特征.在本文中我们刻画恰含有6条非基本边的极小3连通图.   第1章主要叙述极小3连通图非基本边的研究背景和研究意义.   第2章回顾图论的一些基本概念,并介绍极小3连通图的一些重要性质.   第3章首先确定了恰含6条非基本边的极小3连通图中所含扇的数目.我们将简单极小3连通图中的所有基本边组成的边集进行等价划分,即一条基本边与另一条基本边等价当且仅当这两条基本边在同一个扇中.并且我们假设极小3连通图中不存在只有一条基本边且该基本边是两个平凡扇的公共边的这种等价类.若极小3连通图中存在这样的等价类,则可用一Ⅱ-型扇代替等价类中的一个平凡扇,使这样处理后的所得到的新图仍为极小3连通图,并且非基本边的数目保持不变.通过收缩新图中的某些Ⅱ-型扇就可以得到原图.所以我们通过研究处理后所得到的新图的结构就能得到原图的结构特征.由上述假设我们知道,每一个等价类在极小3连通图中对应唯一的一个扇,所以极小3连通图中等价类的数目就等于扇的数目.我们证明恰有6条非基本边的极小3连通图中的扇的数目k,3≤k≤5.   然后,分别刻画当k=3,4,5即扇的数目为3,4,5时恰含有6条非基本边的极小3连通图.   本文结论如下:   设G为不是轮的简单极小3连通图,则G恰含6条非基本边当且仅当G含有3个,4个或者5个扇,且G∈(p),其中(p)={A1,A2,…,A10,B1,B2,…,B27,C1,C2,…,C11},图A1,A2,…,A10,B1,B2,…,B27,C1,C2,…,C11见图7,图8,图9,图10,图11.   第4章结本文的结果并展望未来的研究工作.
其他文献
学位
细分方法因其计算方式简单高效、适用于任意拓扑结构等优点,备受图形学家的欢迎,并已成为计算机辅助几何设计(CAGD)和计算机图形学(CG)领域中的一个国际性研究热点。细分方法
抛物方程是在工程学,物理学等实际问题中提出来的一类重要的偏微分方程.因此,数值分析和求解该类方程具有重要意义和潜在应用价值.目前学者们对偏微分方程数值解法的研究很多,大
本篇硕士毕业论文由四部分构成。   第一章为预备知识,简要介绍了非线性Sobolev方程、混合有限元方法和混合体积元方法的背景知识。具体地,§1.1简要介绍了文中所讨论的一类
近几年我国经济发展迅速,各产业迅猛发展,油田产业也不例外,大规模的生产中也出现了很多问题,油井事故频频发生,尤其是在油井落入复杂物时难以处理,影响油井的工作,严重时会使油井报
三对角对的概念起源于代数图论中的Q-多项式距离正则图理论.1999年Bannai和Ito在文献[1]中给出了这一概念,并进行了系统的研究.涉及这个概念的重要文献有[2][3][4][5]等.设V
Using input-output tables of China and the U.S.,this paper has calculated the pollution embodied in trade and structure of pollution,the balance of emissions em
广告天然就带有召唤大众,整合社会,塑造未来的功能。1927年,戈公振在《中国报学史》中讲道,“广告为商业发展之史乘,亦即文化进步之记录”。广告在追求商业目的的同时,还蕴藏