关于5连通图中可去边的一些性质

来源 :山东大学 | 被引量 : 0次 | 上传用户:chen_d031
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的连通性是图的最基本的性质之一,是图论中重要的研究课题,近二十年来更是图论的研究热点。连通图与网络模型和组合优化联系密切,使它拥有很强的应用价值和理论价值。连通图中的可去边和可收缩边是探讨图的结构、递归的证明图的某些性质的重要工具,对它们的研究具有重要的理论价值和应用价值。本文选择连通图中的可去边作为研究对象,就是希望通过努力能够对进一步了解连通图的结构以及找出其构造方法的研究工作有所帮助。本文主要研究连通图中可去边的性质以及它们在特定子图上的分布情况。下面简单介绍一下本文的主要结果。 首先,我们给出几个子图的定义:定义令G是一个5连通图,H是图G的一个子图,且图H由点集V(H)={x,y,a,b,c,z,w)和边集E(H)={xy,xa,xb,xc,xz,ab,ac,az,aw}组成,其中点x和a的邻点都只有5个,我们称这样一个子图为*1。类似的,我们给出其它子图的点集和边集分别如下,它们对应的被称为*2,*3: 结论:1设图G是一个5连通图,且阶数|G|≥10,对于其中一条不可去边e=xy,设其对应的分离组为(e,S;A,B)。A是一个2边点割原子,x∈A,y∈B。若存在另一条不可去边,f=xz(z≠y),我们给出它的分离组(f,T;G,D)),其中x∈C,z∈D,则图G必然包含*1,*2之一作为其子图。 结论:2设图G是一个5连通图,它的阶数|G|≥10,若图G的一个圈C满足,|E(C)∩ER(G)|=0,则图G必然包含木*1,*2,*3之一作为其子图。 结论:3设图G是一个5连通图,图G不包含*1,*2之一作为其子图并且是树,则||≤|G|-4。 结论:4设图G是一个5连通图,φ≠Eo∈En(G),边xy∈Eo,对应的分离组为(xy,S;A,B),其中z∈A,Y∈B,A是E0-边点割端片且图G中边点割原子的度都不小于3。则必然有以下结论之一成立: (1)(E(A)∪(A,S))E0=φ; (2)(E(A)∪(A,S))∩ER(G)≠φ。
其他文献
摘要:近些年来,随着建筑物的服务功能不断增加和扩大,提高了建筑电气化、自动化、智能化的标准,这就使得建筑电气专业在建设工程中的复杂程度越来越大,对电气系统的质量要求也越来越高。建筑电气工程的质量,对于建筑工程的使用功能、竣工后运行的安全可靠程度、投资效益的体现等都起着举足轻重的作用,对于一项建筑电气工程而言,从开工到竣工,施工现场质量管理工作自始至终都起着至关重要的作用。为此,本文结合实践工作经验
期刊
提要: 结合强夯片石桩在青岛滨海公路南段一期工程中的实践应用,介绍了强夯片石桩的设计原理及施工方法,提出了实际施工过程中的部分经验总结,为类似工程施工提供参考。  Abstract: combined with PianShi pile dynamic compaction in Qingdao southern coastal highway project practice of applic
期刊
半群理论是一门年轻的学科,一直以来人们都在对它进行深入的研究。它在许多领域都有着广泛的用途,比如计算机科学,自动机理论,编码和密码理论等等。随着时代的发展,半群理论越来越
摘要:现浇混凝土梁板结构裂缝是混凝土工程质量通病,也是当前工程界关注的热点问题之一。本文简单阐述了产生混凝土裂缝产生的成因,接着提出对砼裂缝的预防措施,最后对裂缝的补救治理措施进行了总结。  关键词:现浇混凝土;梁板;裂缝;成因;预防措施;治理措施  Abstract: the cast-in-situ concrete beam slab structure crack is the concr
期刊
网络流问题是网络最优化问题中至关重要的部分,它在生活和各个科学领域的应用也愈加广泛。随着计算机科学技术的进步和人们对其深入的研究,形成了较完善的理论体系,从而建立了一
本文在对 MCMC 算法的起源,应用以及其相关的基本问题(随机样本生成法,静态 Monte Carlo 算法)做了介绍后,一方面讨论了 MCMC 算法的构造方法,另一方面讨论了 Markov 链的定性收