3连通图中圈上可去边的一些性质

来源 :山东大学 | 被引量 : 0次 | 上传用户:shinemun
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的连通性是图最基本的性质之一,是图论中重要的研究课题,连通图与网络模型和组合优化联系密切,使它具备很强的应用背景.特别是近二十年来,随着计算机与网络技术的迅速发展,这一联系日益密切.连通图中的可收缩变与可去边是探讨图的结构特征,寻求以递归方式证明图的某些性质的重要工具,对它们的研究具有重要的理论价值和应用价值.随着数学归纳法在图论中的广泛应用,图的“简约”日益受到重视.它足指在保持图的某种性质的前提下使图的阶数或边数减少的一系列运算的综合.图的可缩边与可去边就是在这种背景下产生的.   本文主要研究3连通图中可去边的性质,以及可去边在圈上的分布情况.下面简单介绍一下本文的主要结果.如无特别说明,文中的图G均为简单图.   首先我们给出可去边与不可去边的定义.定义如下:   对于3连通图中的一条边e=xy进行如下运算:   (1)从图G中删除边e=xy,得到G-e.   (2)如果存在一点u∈{x,y},使得“在G-e中的临域NG-e(u)={w,v},则用边Wv代替G-e中的路WUV.   (3)经过(1)(2)运算所得的图G’如果有重边,则删除G’的重边,使G’的每条边的重数都为一.   用GOe表示G经过(1)(2)(3)运算所得到的图,如果GOe是3连通图,则称e是G的可去边,或称e可去;否则称e是G的不可去边或称e不可去.用ER(G)表示G的可去边集,eR(G)表示G的可去边数,EN(G)和印(G)分别表示G的不可去边集和不可去边数.   对于3连通图中圈上的可去边分布,本文对已有的部分研究成果进行了推广,得出下述两条结论:   定理3.1如果C是不同构于W8的3连通图G的一个7圈,那么:   |E(C)nER(G)|≥l;   或者G中存在同构于W**s的子图,且C? W**.其中dG(xi)=dG(Yi)=3,i=2,3,4;dG(a)≥4;dG(b)≥4.   定理3.2如果C是不同构于W9的3连通图G的一个8圈,那么;   |E(C)nER(G)|≥l;   或者G中存在同构于暇中任意一种的子图,且c包含在子图中,其中dG(Xi)=dG(Yi)=3,i=2,3,4;dG(a)≥4;dG(6)≥4.   (有关图的构造方法详见正文部分)
其他文献
粗糙集理论,作为数据挖掘的一种重要方法,是在20世纪90年代由波兰数学家Palawk给出的一种能够对不精确和不完备信息系统进行处理的数学工具。属性约简是粗糙集理论研究的重点
本文主要研究的问题足一般型三维代数簇的3典范系统的双有理性。设X是一个一般型极小三维代数簇且只有Q-可分终极奇点,Kx是X上的典范除子。当X的几何亏格pg(X)≥2时,令d=dimφ|
本文研究了一类时滞神经网络模型的稳定性。全文共分三章:第一章研究了常时滞泛网络的全局渐近稳定性。利用李雅普诺夫泛函方法和拓扑度理论证明了该网络的全局渐近稳定性.实
本文将特征线法与有限体积元法结合起来应用到一维和二维大气污染模型中.第一部分,针对一维模型,选取试探函数空间和检验函数空间分别为二次元空间与分片常函数空间,得到了全
众所周知,关于秩为2的对角型Nichol代数,给出其生成子及关系,并计算它们的维数有着重要的意义。本文正是基于Heckenberger的秩为2的对角型Nichol代数的研究,它分类了秩为2的
近几年来,磁动力学成为科学技术研究的一个热门课题,而它在开关转换异常以及磁记忆工业中都有非常重要的应用.在微磁动力学的研究中,对Landau-Lifshitz方程的数值模拟最为广
由于其算术意义,自守形式的Fourier系数是有趣且重要的研究对象.很多问题都涉及到Fourier系数,包括著名的Ramanujan-Peterson猜想.同时,作为数论中的重要问题,Fourier系数的的平
学位