Halin图上的k条不相交路径问题

摘要

给定一个图G=(V，E)，以及图G中的k对顶点(u1，v1)，(u2，v2)，…，(uk，vk)，所谓的k条不相交路径问题就是，找到图G中的k条不相交路径分别连接这k对顶点，即路径P1连接u1和v1，…，路径Pk连接uk和vk，并且这k条路径必须互不相交。k条不相交路径问题总共有四种不同的版本，即考虑图G是有向图或无向图的情形，以及考虑路径是顶点不相交的或边不相交的，从而可以得到四种不同的组合情形，该问题在布线问题、VLSI设计等方面有着广泛的应用。
　　 普通图上的k条不相交路径问题目前还没有很好的研究成果，而Halin图最先是作为极小3-连通平面图被研究的，它本身有着很多良好的连通性质。本文提出一个线性时间算法来解决Halin图上的k条顶点不相交路径问题，整个算法主要基于Cornuéjols、Naddef和Pulleyblank所提出来的扇收缩方法。算法的大概思想是，先对Halin图的特征树进行后序遍历，在遍历的过程中不断对Halin图上的扇区进行收缩处理，同时保存大量有用的信息。当后序遍历完特征树后，算法利用刚才所保存的有效信息，来寻找问题所要求的那k条顶点不相交路径。
　　 k条不相交路径问题的难点在于，这k条不相交路径所有可能的情形是非常复杂的。由于Halin图进行扇收缩后仍然是Halin图，但是图的规模却比原来变小了，因此只要在扇收缩的过程中保存足够多的信息，就可以运用类似动态规划的思想来解决这个问题。算法通过不断地对Halin图进行扇收缩处理，直到最后判定题目是否有解。有解的话再根据扇收缩过程中保存的信息，来还原出那k条顶点不相交路径，从而完成对Halin图上k条不相交路径问题的解决。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 研究背景

1.2 Halin图的研究现状

1.3 k条不相交路径问题的研究现状

1.4 论文的主要工作和组织结构

第2章 算法简介

2.1 问题陈述

2.2 算法的主要思想

2.3 算法中需要说明的定义

2.4 算法的大概流程

第3章 算法详述

3.1 预处理给定顶点对

3.2 确定给定顶点的状态等信息

3.3 确定某对给定顶点对之间的路径

3.4 对受路径影响的扇区进行更新

3.5 确定全部的k条顶点不相交路径

3.6 主程序

第4章 算法分析

4.1 算法的正确性分析

4.2 算法的复杂度分析

第5章 总结和展望

5.1 总结

5.2 展望

参考文献

致谢