3连通图的某些子图上的可去边

摘要

图的连通性是图最基本的性质之一，是图论中重要的研究课题。连通图与网络模型和组合优化联系密切，使它具备很强的应用背景．随着计算机与网络的迅速发展，这一联系日益密切，使连通图拥有了重要的理论价值和应用价值。探讨连通图的结构特征，寻求连通图的构造方法一直是图论研究的前沿课题之一。随着数学归纳法在图论中的广泛应用，图的“约简”日益受到重视。它是指在保持图的某种性质的前提下使图的阶数或边数减少的一系列运算的综合。图的收缩边和可去边就是在这种背景下产生的。 本文主要研究连通图中可去边和可收缩边的性质，以及它们在3连通图中的分布情况。如无特别说明，文中的图G均为简单图。下面简单介绍一下本文的主要结果。 首先我们给出可去边与不可去边的定义。定义如下： 对于3连通图中的一条边e=xy进行如下运算： （1）从图G中删除边e=xy，得到G—e． （2）如果存在一点u∈{x，y}，使得u，在G—e中的邻域NG—e（u）={w，v），则用边wv代替G—e中的路wuv． （3）经过（1）（2）运算所得的图G'如果有重边，则删除G'的重边，使G'成为简单图。 用Gθe表示G经过（1）（2）（3）运算所得到的图。如果GθP是3连通图，则称e是G的可去边，或称e可去，否则称e是G的不可去边或称e不可去。用ER（G）表示G的可去边集，eR（G）表示G的可去边数，EN（G），eN（G）分别表示G的不可去边集和不可去边数。 对于3连通图中圈上的可去边的分布，本文对已有的部分研究成果进行了改进，得出了： 结论1 G是3连通图，C是G中一个6圈。如果C上至多存在一组3个连续3度顶点，则|E（C）∩ER（G）|≥1． 结论2 G是3连通图，υ（G）≥6，Cn是G中一个n圈。如果Cn上至多存在一组3个连续3度顶点，则|E（Cn）∩ER（G）|≥1． 对于3连通图中生成树外可去边的分布，本文通过对3正则图的研究，得出了： 结论3 G是一个3连通图，υ（G）≥6，如果G上不存在2个连续3度顶点，则G的生成树T外至少存在2条可去边．

目录

文摘

英文文摘

论文说明：符号说明

声明

第一章引言

§1.1研究背景

§1.2基本定义与符号

§1.3本文的主要结果

第二章3连通图中圈上的可去边

§2.1基本定义和已知结果

§2.2 3连通图中圈上的可去边

第三章3连通图中生成树外的可去边

§3.1基本定义和已知结果

§3.2 3连通图中生成树外的可去边

参考文献

致谢

攻读硕士期间发表及完成的论文