环和环形树负载问题一些结果

《环和环形树负载问题一些结果》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、、。“分类号习单位代码‘，“学号伽丫功第尤寒硕士学位论文孚介曰刀口口口打，，吮犷，卜，阳”甸一论文题目补令“形树灸粉叭胜，‘呆专作者姓名专甲节业妙匀全种匕一送指导教师姓名—。专业技术职务香司刀条轰枷‘年乒月日山东大学硕士学位论文目录中文摘要··············“·············…···················“”英文摘要……第一章环负载问题的有关结果····························一第一节问题的背景··················一········“”第二节有关的

2、结果……第二章一个解决一类环形树负载问题的多项式时间近似方案……第······················一节问题的背景一··················“““”第二节预备工作一第三节环形树负载问题的多项式时间近似方案························……第四节示意图···“·········“········一·························“第三章有向双环的路径选择问题…第一节引言···············································

3、···················……第························································……二节有关的结果第四章有向环形树的路径选择的多项式时间算法和转换器安排方案…第一节引言··································································……第二节必要的定义和预备知识·············································……第三节有向······

4、·········……环形树的路径选择的多项式时间算法第四节转换器安排方案················································……第五章改进的有向双环负载问题的多项式时间近似方案······……········、········“””“”“第一节问题的提出一第二节相关的算法·························································……参考文献八几，致谢……山东大学硕士学位论文环和环形树负载问题的一些结果李畅，，山东大学

5、数学与系统科学学院山东济南摘要，，，论文分三部分第一部分讨论无向环和无向环形树的负载问题包括第一，，。二章第二部分讨论有向环和有向环形树的路径选择问题包括第三四章第三部分提出改进的有向环负载问题的多，包括第五章。项式时间近似方案环形树在通讯网络中有着广泛的应用。一个环形树是一个由一棵树得，，到的图把树的每个顶点换成一个环叫做顶点环然后收缩树的边使得两个时应，于一边的两个顶点的环有且只有一个相同的顶点且没有三个顶点环共用一点一个更广的定义允许三个环共用一点川。第一，二章的问题是，给定一，，，，个要求的集合任每个要求是定

6、义在一对顶点之间的一个，非负实数在同一个环上每对顶点之间的所有要求必须且只能在两条可能道路，，中选择同一条道路来输送算法的目的是找出一个路径选择方案衬每个要求，且使得环形树上的各边的最大负载最，在环形树上找出一条路来满足它小化在这里一条边的负载指的是通过这条边的所有路的要求值之和。我们提出一个多项式时间近似方案来解决此问题，主要有对于这个问题以下结果算法环形树负载问题的多项式时间近似算法定理算法是一个多项式时间近似方案定理程序结束时每个要求所对应的两点之间的路径是唯一的。，第三四章讨论有向环和有向环形树的负载问题有向

7、环形树由有向双环构，成构造方法与环形树的构造方法相同只是把原来无向环形树上的每个无向环，，一换成有向双环即两个方向相反的有向环和对有向环形树的路径选择，问题主要有以下结果算法有向环形树的路径选择的多项式时间算法定理算法是一个多项式时间算法有当的位置安装波长转换器。对有向环形树的转向环和有向环形树需要在适，换器安排方案主要有如下结果定理所有枢纽点集合对有向环形树是足够的山东大学硕士学位论文定理改进的安装方法的安装点集合对有向环形树是足够的，第五章提出改进的有向环负载问题的多项式时间近似方案主要有如下结果算法改进的有向双

8、环的路径选择问题的近似的多项式时间算法算法改进的有向双环的路径选择问题的多项式时间近似方案本文的安排如下第一章介绍环负载问题的背景和有关结果第二章提出环形树负载问题的一个多项式时间近似方案第三章介绍有向双环的路径选择问题的主要结果和相关知识第四章提出有向环形树的路径选择的多项式时间算法和转换器安排方案第五章提出改进的有向环负载问题的多项式时间近