| Ford-Fulkerson算法与嵌入图中的短圈 |
| |
| 引用本文： | 张燕,任韩. Ford-Fulkerson算法与嵌入图中的短圈[J]. 应用数学学报, 2008, 31(5) |
| |
| 作者姓名： | 张燕 任韩 |
| |
| 基金项目： | 国家自然科学基金，上海市重点学科建设资助项目 |
| |
| 摘 要： | 关于嵌入图中最短圈的多项式算法的存在性问题,是由Thomassen最早提出的.本文通过改进的Ford-Fulkerson算法,可以得到最短割算法.另一方面,通过定义嵌入图的几何对偶图及其相应的嵌入系统,得到几何对偶图中的可分离圈就对应于原图中的割;反之,若几何对偶图中的割在原图中对应于-个圈,那么该圈一定可分离.从而在射影平面上解决了Mohar与Thomassen关于是否存在多项式算法寻找短圈的问题.对于-般曲面上嵌入图,只要它的面宽度充分大,那么同样有多项式算法发现最短可收缩圈.
|
| 关 键 词： | 割 可分离圈 可收缩圈 双侧圈 |
Ford-Fulkerson Algorithm and Short Cycles in Embedded Graphs |
| |
| ZHANG YAN,REN HAN. Ford-Fulkerson Algorithm and Short Cycles in Embedded Graphs[J]. Acta Mathematicae Applicatae Sinica, 2008, 31(5) |
| |
| Authors: | ZHANG YAN REN HAN |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
