作者：张燕 任韩割可分离圈可收缩圈双侧圈
摘要：关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于一个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于一般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
