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

《Halin图上的k条不相交路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文Halin图上的k条不相交路径问题姓名：夏春汛申请学位级别：硕士专业：计算机应用技术指导教师：娄定俊20100602论文题目：Halin图上的k条不相交路径问题专业：计算机应用技术硕士生：夏春汛指导教师：娄定俊教授摘要给定一个图G=(V，E)，以及图G中的k对顶点(“。，h)，@：，v2)，⋯，(心，％)，所谓的k条不相交路径问题就是，找到图G中的k条不相交路径分别连接这k对顶点，即路径丑连接甜l和vl，⋯，路径丑连接蚝和K，．并且这k条路径必须互不相交。k条不相交路径问题总共有四种不同的版本，即考虑图G是有向图或无向图的情形，以及考虑

2、路径是顶点不相交的或边不相交的，从而可以得到四种不同的组合情形，该问题在布线问题、vLSI设计等方面有着广泛的应用。普通图上的k条不相交路径问题目前还没有很好的研究成果，而Halin图最先是作为极小3．连通平面图被研究的，它本身有着很多良好的连通性质。本文提出一个线性时间算法来解决Halin图上的k条顶点不相交路径问题，整个算法主要基于Cornuejols、Naddef和Pulleyblank所提出来的扇收缩方法。算法的大概思想是，先对Halin图的特征树进行后序遍历，在遍历的过程中不断对Halin图上的扇区进行收缩处理，同时保存大量有用的信息。当后序遍历

3、完特征树后，算法利用刚才所保存的有效信息，来寻找问题所要求的那k条顶点不相交路径。k条不相交路径问题的难点在于，这k条不相交路径所有可能的情形是非常复杂的。由于Halin图进行扇收缩后仍然是Halin图，但是图的规模却比原来变小了，因此只要在扇收缩的过程中保存足够多的信息，就可以运用类似动态规划的思想来解决这个问题。算法通过不断地对Halin图进行扇收缩处理，直到最后判定题目是否有解。有解的话再根据扇收缩过程中保存的信息，来还原出那k条顶点不相交路径，从而完成对Halin图上k条不相交路径问题的解决。关键词：Halin图，扇收缩，不相交路径Title：ga

4、jor：Name：Supervisor：Thek-DisjointPathsProblemonHalinGraphsComputerApplicationTechnologyXiaChunxunProf．LouDin西unAbstractGivenagraphG=Ⅳ，E)andkdisjointvertexpairs(％，v1)，似2，v2)，⋯，(％，vk)ofG．Thek-disjointpathsproblemis，tofindoutkpathsinGsuchthatpath置connectsuaandh，⋯，path丘connectsukandK，

5、andthesekpathsmustbedisjoint．Disjointmaymeanvertex-disjointoredge—disjoint,andthegraphGmaybedirectedorundirected，SOthekdisjointpathsproblemhasfourversionsasweCallsee．Thekdisjointpathsproblemhasapplicationin‘‘wirerouting”，whichisallimportant．processofthelayoutdesignofVLSI’s．Thek-di

6、sjointpathsproblemisdifficultinthegenerasituation．TheHalingraphsarefirststudiedbyR．Hal．inasminimally3-connectedplanargraph，andtheirfeaturesaboutconnectivityaresobeautifulthatalinearalgorithmispresentedinthispapertosolvethek-disjointpathsproblemonHalingraphs．Thealgorithmisbasedonth

7、e“fancontracting”methodwhichisfirststudiedbyComudjols，NaddefandPulleyblank．Thebaseideaaboutthealgorithmisthat，firstapostorderwalkisperformedOnthecharacteristictreeoftheHalingraph，thenUSe“fancontracting’’methodtodealwitheveryfanoftheHalingraphbetweenthewalk．Whilecontractingthefan,a

8、plentyofusefulinformationmustbest