论文部分内容阅读
图的连通性是图最基本的性质之一,是图论中重要的研究课题,连通图与网络模型和组合优化联系密切,使它具备很强的应用背景.特别是近二十年来,随着计算机与网络技术的迅速发展,这一联系日益密切.连通图中的可收缩变与可去边是探讨图的结构特征,寻求以递归方式证明图的某些性质的重要工具,对它们的研究具有重要的理论价值和应用价值.随着数学归纳法在图论中的广泛应用,图的“简约”日益受到重视.它足指在保持图的某种性质的前提下使图的阶数或边数减少的一系列运算的综合.图的可缩边与可去边就是在这种背景下产生的.
本文主要研究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.
(有关图的构造方法详见正文部分)