论文部分内容阅读
本文主要研究了图的割空间理论及相关性质,这是图论研究领域中的一个重要方面。但是与相对较为成熟的圈空间理论相比,对割空间的研究则显得较少。作为相互正交的两个空间,它们之间有着密切的联系。我们首先证明了最小割基在结构上的唯一性。然后,通过研究割的性质,得到拓扑图论中的一个重要性质,即不可分离圈不能由若干可分离圈生成。最后,给出了一个找最短割的多项式算法,并以此部分解决了Thomassen[18]关于是否存在多项式算法寻找短圈的问题。另外,我们还研究了2-边着色的完全图中单色三角形的最小数目,并确定了该最小值。具体内容如下:
1.通过建立一个基变换的Hall型定理,得到一个判定最小割基的充分必要条件,以此证明了最短割基在结构上的唯一性(即:任两个最短割基之间,一定存在一个1-1映射使得所对应的割的长度相等)。
2.通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于一个圈,那么该圈一定可分离。由此结论,证明了不可分离圈不能由若干可分离圈生成。
3.通过改进网络最大流的Ford-Fulkerson算法,得到最短割的多项式算法。并以此在射影平面上解决了Thomassen[18]关于是否存在多项式算法寻找短圈的问题。
4.利用邻接矩阵方法,确定了2-边着色的完全图K<,n>中单色三角形最少数目的精确值,并给出了该下界的一个特例。