7-连通图最长圈上的可收缩边及3-连通图可收缩非边的分布

摘要

在图论研究中，对连通图的研究主要集中于对其结构特征进行分析和讨论，而采取的主要手段是采用构造连通图的方法，这使得我们可以从某些简单连通图造出满足要求性质的各种复杂连通图。为了寻找连通图的构造方法，人们的主要研究手段是引入一些能够保持图的连通性特性的运算，通过对各类连通图进行递归运算，达到使任意的连通图都可以由一些简单连通图重复进行这些运算而得到的结果。基于此背景，构造连通图并且能保持连通性的可去边、可收缩边和可收缩非边等运算便应运而生了，它们是目前研究连通图构造的有力工具。
　　 本文主要进行了两个方面的讨论:一是7-连通图最长圈上的可收缩边，结论有:
　　 引理0.1设P(∶)x=x1x2…xn=y是7-连通图G的一条最长（x，y）-路，xixi+1是一条不可收缩边，且S={xi，xi+1，u1，u2，u3，u4，u5}是其对应的7-点割，则G-S的每个连通分支至少包含P上一点。
　　 引理0.2设P(∶)x=x1x2…xn=y是7-连通图G的一条最长（x，y）-路，且G的任意断片阶都大于3，则P上至少包含一条可收缩边。
　　 定理0.1设G是7-连通图且G的任意断片阶都大于3，C=x1x2…xnx1是G的任意最长圈，则C上至少有两条可收缩边。
　　 二是讨论了3-连通图中特殊构造图Gv、无三角形的3-连通图中可收缩非边的分布情况。结论有:
　　 定理0.2(1)Gv是3-连通的;
　　 (2)Gv中的任一条非边(x，y)，x≠v，y≠v，（x，y）可收缩当且仅当(x，y)在G中可收缩;
　　 (3)所有Gv中，不存在非边收缩当且仅当Gv是车轮。
　　 定理0.3图G是无三角形、非完全的3-连通图，T是最小点割，F是T的断片，当｜F｜=3时，F与T之间的非边{（u，v）|u∈F,v∈T}不可收缩。

目录

声明

摘要

符号说明

第一章 绪论

1．1 图论概述

1．2 已有成果

第二章 7-连通图最长圈上的可收缩边

2．1 引言

2．2 本章主要引理

2．3 本章主要定理

第三章 某些3-连通图上的可收缩非边的分布

3．1 引言

3．2 主要结果及证明

3．2．1 特殊构造图Gv

3．2．2 无三角形3-连通图

参考文献

致谢