赋权无向图的双瓶颈问题

《赋权无向图的双瓶颈问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、扉页：独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人或集体己经发表或撰写过的研究成果，对本文的研究做出贡献的集体和个人均己在论文中作了明确的说明并表示了谢意。研究生签名：藜么盆当日期：垫丝雏§目麴目论文使用和授权说明本人完全了解云南大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文

2、。．(保密的论文在解密后应遵循此规定)研究生签名：象丝．盏导师签名：本人及导师同意将学位论文提交至清华大学“中国学术期刊(光盘版)电子杂志社”进行电子和网络出版，并编入Q水I系列数据库，传播本学位论文的全部或部分内容，同意按《中国优秀博硕士学位论文全文数据库出版章程》规定享受相关权益。研究生签名：⋯导师签名：——日期：摘要mPlilllll)lllUllllllJI)lllIJIIIPIIIIIY2378919瓶颈最短路Ih7题_(BSP)是一系列网络优化问题的核心，旨在寻找网络中两点之间容量最大的一条路。以这

3、个问题为基础，研究三个新的最优化问题：给定一个赋权连通无向图G=(VE；叫；s，t)，其中8，t是两个固定的顶点，W：E--+N+是边的长度函数。问题一是在这个图中找一条由顶点s到顶点t的路只t，使得笔篝矧达到最大。问题二是在这个图中找一棵支撑树T，使得笔篝黼达到最大。问题三是在这个图中找一个基数最大匹配M，使得笔瓮黼达到最大。本文对这三个问题分别都给出了一个多项式时间算法。本文由以下四个章节构成。在第一章中，回顾了问题的由来，给出了到目前为止的一些研究成果；在第二章中，给出本文所涉及的定义，概念和符号；在第三

4、章中，基本问题及其算法；在第四章中，讨论三个双瓶颈问题，给出了相应算法；最后，本文给出相关结论以及未来的研究方向。关键词：支撑树；最大匹配；双瓶颈；二分法；多项式时间算法AbstractThebottleneckshortestpathproblem(BSP)isthecoreofanumberofnetworkoptimizationproblem，thegoalistodeterminethelimitedcapacityofanypathbe—tweentwospecifiedverticesofthen

5、etwork．Basedonthisproblem，weconsiderthreenewproblems：givenaweightedconnectedundirectedgraphG=(VE；加；8，￡)，wheres，taretwofixednodes，andW：E_N+isthelengthfunction．Thefirstproblemistoconstructapathfr。mn。destonodet只t。fGsuchthat箍滁糯筹ismaximized。Thesecondproblemistoco

6、nstructaspanningtreeTofGsuchthatismaximized．Thethirdproblemistoconstructamaximumcardinal—itymatchMofGsuchthat笔黼ismaximized．Inthisthesis，Wedesignapolynomialtimealgorithmfortheeachproblemrespectively．Thisthesisconsistsofthefollowingfourchapters．InChapter1，wetr

7、acethehistoryoftheproblems，andgiverecentresults．InChapter2，wegivesomebasicconcepts，terminologyandnotations．InChapter3，wepresentsomebasicproblemandtheiralgorithm．InChapter4，westudyourthreedoublebottleneckproblemsandthendesignsomealgorithmstosolvethem．Atlast，w

8、egivesomeconclusionsandsomeplansforthefuture．Keywords：spanningtree；maximumcardinalitymatch；doublebottleneck；dichotomy；polynomialtimealgorithm11Abstract目录第一章引言11．1理论背景．．．．．．．。。．．．．．．．．．．．．．．．．。．．