图中的圈不可分离性(英文)

如果对图中的两条边或两个顶点,存在两个顶点不交圈分别包含他们,那么这两条边或两个顶点叫做可用圈分离。不能用圈分离的边对或点对叫做圈不可分离的。定义了包含一对不可用圈分离的边的图的一个无穷类。给出了两个顶点或两条边不可用圈分离的一个简单的充分条件。这个无穷类包含Wagner图作为元素。提出了关于所定义的概念和图类的一些尚未解决的研究问题。

可定向曲面上的一类闭曲线系统

利用组合数学的思想、拓扑的方法研究在可定向曲面上,一类含有个数最多的不可收缩的、两两不相交、互不同伦的圈(闭曲线)系统及其性质,得出了关于这些圈的一些拓扑定性性质,并给出这些圈在曲面上的位置分布.

Ford-Fulkerson算法与嵌入图中的短圈

关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于一个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于一般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈.