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

Ford-Fulkerson Algorithm and Short Cycles in Embedded Graphs

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

It is Thomassen who firstly asked if there is a polynomial bounded algorithm for finding a shortest contractible cycle,a shortest separating cycle and a shortest two sided cycle in an embedded graphs.By an improved Ford-Fulkerson algorithm,we obtain a polynomially bounded algorithm for finding the shortest co-cycle.This implies the existence of a polynomially bounded algorithm to find a shortest contractible cycle,a shortest separating cycle,and shortest cycle in an embedded graph in the projective plane and answers the open problems raised by Mohar and Thomassen in the case of projective plane embedded graph.We also show that for a fixed surface S,if the face-width of an embedded graph G in S is large enough,then there exists a polynomially bounded algorithm to find a shortest contractible cycle in G.