图中可缩边与可去边是探讨图的结构,寻求使用归纳法证明图的某些性质的一个有利工具。W. T. Tutte[22]在1961年给出3-连通图的结构特征定理时,实际上用到了可去边与可缩边的存在性,Tutte给出了极为出色的3连通图的结构为:G时3连通图当且仅当G是一个轮,或是从一个轮重复使用以下而种运算推得的图:(1).加边;(2).拆点。证明了每个阶大于或等于5的3-连通图必有可缩边,这是有关可去边与可缩边的最早的结果。Holton、Jackson、Wormald等在[3]中对3连通图中可去边的分布及数目进行了探讨。苏健基在[4]中得出了3连通图中可去边的下界,并描述了达到这一下界的图的结构特征。Fouquet、Thuiller和McCuaig在[5.17]中对3连通3正则图中的可去边进行了研究。 尹建华在[2]中证明了4连通图G(阶数为5和6的2循环图除外)中总存在可去边,并且利用4连通图存在可去边与可收缩边的事实,证明了一个4连通图总可以从一个2循环图经过以下步骤得到:(1).加边;(2).拆点;(3).加点去边;(4).扩点。 近二十多年来,有关可去边和可收缩边的研究已经有了很大进展,许多文献重点研究了一个图中可缩边与可去边的数目。 本论文主要研究了图论及其应用中连通度方面的问题,重点放在了3连通图与4连通图方面:其主要研究成果如下: (1) 在论文的第一部分(第二章),我们研究了3连通图的可去边在生成树上的分布。G是3-连通图,e是G中的一条边。若G-e是3连通图的一个剖分,则称e是3连通图的可去边。否则,e是G中不可去边。我们在前人研究的基础上,对3连通图的可去边作了进一步的研究,得到了以下结论:(1)3连通3正则图的生成树上至少有两条可去边;(2)设G是最小度至少为4的3连通图,则任一生成树上至少有两条可去边。(3)设G是围长至少为4的3连通图,则任一生成树上至少有两条可去边。 (2) 在论文的第二部分(第三章——第六章),我们主要对4连通图中的可去边作了一些研究。4连通图G中的可去边定义如下:(1)从G中去掉边e得图G-e。(2)如果e的某个端点在G-e中度数为3,则去掉此端点,再两两联结此端点在G-e中的3个邻点。(3)如果通过运算(2)后有多重边