论文部分内容阅读
图的连通性是图的最基本的性质之一,是图论中重要的研究课题,近二十年来更是图论的研究热点。连通图与网络模型和组合优化联系密切,使它拥有很强的应用价值和理论价值。连通图中的可去边和可收缩边是探讨图的结构、递归的证明图的某些性质的重要工具,对它们的研究具有重要的理论价值和应用价值。本文选择连通图中的可去边作为研究对象,就是希望通过努力能够对进一步了解连通图的结构以及找出其构造方法的研究工作有所帮助。本文主要研究连通图中可去边的性质以及它们在特定子图上的分布情况。下面简单介绍一下本文的主要结果。
首先,我们给出几个子图的定义:定义令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)≠φ。