给定一个图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条不相交路径问题的解决。