（应用数学专业论文）网络中的均匀度问题和比值问题.pdf

里堕型兰茎查查兰 型堑兰堕兰堡 堕壅 摘要 网络最优化的理论和方法已经广泛地渗透于运筹学 信息论 控制论 管理科学 和计算机科学等领域 并在工程技术 军事等方面有着极为重要的应用 因此 研究 各类网络最优化问题的有效算法一直是网络最优化的主旋律 本文对如下几个有很好的实际背景的网络问题进行了研究 1 均匀支撑树问题 即基于最小树和最大树的性质和求它们的算法 讨论无向网 络中的最均匀支撑树 带有边集限制的最均匀支撑树 最大最小树 以及最小最大树 的基本性质和求法的问题 2 均匀选址问题 即平面上的限制在星图拓扑f 的最均匀选址问题和无向网络中 的最均匀选址问题 3 最大最小树形图问题 即基于实际背景 建立求网络的最大最小树形图的模型 研究最大最小树形图的基本性质 并以最小入弧回路与最大最小树形图的关系为基 石 介绍求网络的最大最小树形图的有效算法 4 比值问题 即如何求网络中的最小比值树形图的问题和如何在无向网络中以最 小比值为目标进行选址的问题 关键字 网络多项式算法均匀度最均匀支撑树最均匀点最大最小树 形图最小比值树形图 第1 页 里堕型堂垫查尘兰竺垄竺堕堂堡笙苎 a b s t r a c t t h e o r i e sa n dm e t h o d so fn e t w o r ko p t i m i z a t i o nh a v ei n f i i t r a t e do p e r a t i o n a l r e s e a r c h i n f o r m a t i o nt h e o r y c y b e r n e t i c s m a n a g e m e n ts c i e n c ea n dc e m p u t e r s c i e n c ew i d e l y a n dh a v ev e r yi m p o r t a n ta p p l i c a t i o n sj ne n g i n e e r i n gt e c hr f iq u e a n di i l j1 i t a r ya f f a i re t c s oc a r r y i n go n a ni n v e s t i g a t i o ni nt h ee f f e c t i v e a l g e r l t h m so ft h ed i v e r s i f l e dn e t w o r ko p t i m i z a t i o np r o b l e m sh a sb e e nat h e m e o fn e t w o r ko p t i m i z a t i o n i nt h i sp a p e r s o m en e wt y p en e t w o r ko p t i m i z a t i o np r o b l e m sa r ep u tf o r w a r d a n dr e s e a r c h e da c c o r d in gt ot h ep r a c tic a lb a c k g r o u n d f i r s t l y t h eb a l a n c e dd e g r e es p a n n i n gt r e ep r o b l e mi sd js c u s s e d w e i n v e s t i g a t et h em i n i m u mb a l a n c e dd e g r e es p a n n i n gt r e ep r o b l e ma n dt h es a m e p r o b l e mc o n t a i n e ds e t t l e de d g es e tb a s e do nm i n i m u ms p a n n i n gt r e e t h e nt h e m a x m i ns p a n n i n gt r e ep r o b l e ma n dt h em i n m a xs p a n n i n gt r e ep r o b l e ma r ea ls o d i s c h s s e d s e c o n d l y w ep u tf o r w a r dt w on e wt y p ef a c i l i t yl o c a t i o np r o b l e m s o n ejs t h em i n i m u mb a l a n c e dd e g r e ef a c i l i t yl o c a t i o np r o b l e mu n d e rs t a rt o p o i o g yo n p l a n ea n dt h eo t h e ri st h em i n i m u mb a l a n c e dd e g r e ef a c i l i t yl o c a t i o np r o b l e m o nan e t w o r k t h e n w ec o n s t r u c tan e t w o r km o d e lo ft h em a x m i ns p a n n i n ga r b o r e s c e n c e p r o b l e m w ed i s c u s st h ee s s e n t i a lc h a r a c t e ro ft h em a x m i ns p a n n i n g a r b o r e s c e n c ea n dd e d u c ea ne f f e c t i v ea l g o r i t h mt os o l v et h i sp r e b le mb a s e d o nt h er e l a t i o n s h i db e t w e e nt h em i n i m u mi n 一 r cc i r c u i ta n dt h em a xm n p a n n a p a n n n ga r b o r e s c e n c e 1 a s t t w or a t i op r o b l e m sa r ed i s c u s s e d t h ef i r s ti st h em i n i m u mr a t i o n ga r b o r e s c e n c ep r o b l e m a n dt h es e c o n di st h em i n i m u mr a t i of a c ilil y l o c a tt o np r o b l e mo n a nu n d i r e c t e dn e t w o r k k e y w o r d s n e t w o r k p o i y n o m ia i b aia n e e dd e g r e es p a n nin gt r e e m s p a n n i n gar b o r e s o e n c e m in i m u mr a t a i g o ri t h m b a i a n c e dd e g r e e m i n i m u m n i m u mb a ia n c e dd e g r e ep o i n tm a x m i n os p a n nin ga r b o r e s c e n c e 第1 l 页 国防科学技术大学研究生院学位论文 陶 2 1 图 2 2 图 2 3 图 2 4 图 3 1 图 3 2 图 4 1 图 5 1 图 5 2 图 6 1 图 6 2 图 6 3 图表目录 例2 1 的图 定义2 3 的直观示意图 例2 2 的图 无向网络g 的示意图 定理3 1 的图 定理3 2 的图 例4 1 的图 算例的图 网络d 2 a w 的示意图 例6 1 中网络d v a w 的图 网络见 v a 办 的示意图 例6 3 中网络d 的示意图 b 8 1 1 1 2 1 6 1 9 2 3 2 9 2 9 3 2 3 3 3 4 第i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含 其他人已经发表和撰写过的研究成果 也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目 圆垒主鲍塑鱼廑闷基垄出焦间题 学位论文作者签名 圣茎日期 2 叫年 f 月f f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留 使用学位论文的规定 本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档 允许论文被查阅和借阅 可以将学位论文的全部或部分内容编入有关数据 库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密学位论文在解密后适用本授权书 学位论文题目 圆终生鲍塑鱼廛回塑垄出焦闺题 学位论文作者签名 上 育 计 作者指导教师签名i 箍丛 日期 即铲年1 1 月心日 日期 砂牛年 月矽日 里堕型兰垫查奎堂竺茎生堕兰生笙苎 第一章预备知识 1 1图与有向图的基本概念 个图g 是指一个有序三元组 v g e g p 其中v g o 并且 y g n e g o 称v g 中的元素为图g 的顶点 而矿 g 则称为g 的顶点集 e g 称 为g 的边集 其中的元素称为g 的边 y 称为关联函数 它是使g 中的每条边对应于g 的 无序顶点对的函数 若e e g 且 p v 则称e 连接 和v 或称p 与甜及v 关联 而 和v 称为e 的端点 也称为 与v 是相邻的 若图的顶点和边集都只含有限的元素 则称 之为有限图 否则称之为无限图 称与同一个顶点关联的两条边为相邻的两条边 称两个 端点重合的边为环 端点不重合的边为连杆 连接同一对顶点的边称为重边 简单图是一 个既没有环也没有重边的图 当只讨论一个图时 我们常常省略g 并且用矿 e 来代替 v 6 e g 而且把g v g e 6 y 简记为g v e 此时e g 中的边只需要 用它的两个端点的无序对来表示 在以后的讨论中如果不特别指明 我们所说的图一般为 有限简单图 图g 中顶点v 的度定义为和v 关联的边的数目 与v 关联的环算作两条边 汜为 d v 称靠 是偶数的顶点为偶点 称d o v 为奇数的顶点为奇点 若图g 和图h 满足v h 矿 g e h e g 则称日为g 的子图 记为h g 特 别地 若矿 日 y g e 日 e g 则称日与g 相等 记为h g 两个图不相等但 具有相同的图形 差别只是它们的顶点和边的标记不同 则这两个图同构 一般说来 如 果能够在图g 和图h 的顶点集之间建立一一对应关系 使得连接g 中任何一对顶点的边数 等于连接h 中与之对应的 对顶点的边数 则称g 和h 是同构的 记作g 兰h 若h g 且h g 则称日是g 的真子图 记作h c g 若矿 日 矿 g e 日 点 g 则称日是 g 的支撑子图 从图g 中删去所有的环 并且对连接任何一对顶点的重边只保留一条 这 样得到的图称为g 的基础简单图 假设矿7 为v g 的非空子集 则以矿 为顶点集 v e g l v v 为边集的g 的子 图称为g 的由v 导出的子图 记为g v 简称为g 的导出子图 导出子图g l 矿 v l 记为 g 一矿 它是从g 中删去v 中的顶点及其所关联的边后所得到的子图 若v v 1 则把 g 一 v 简记为g v 设e 为e g 的非空子集 则称以e 为边集 v iv 为e 中某条边的端点 为顶点集的g 的子图为g 的由e7 导出的子图 d 为g t e 简称为g 的边导出子图 边集为e e7 的图g 的生成子图简记为g e 它是从g 中删去 e 中的边后所得的子图 图g 的一条途径是指一个有限非空序列矿 v o e l v l e 2 v 2 e k v t 其中v v o i s 第l 页 国防科学技术火学研究生院学位论文 p v v e 1 j k v 称为w 的起点 v 称为w 的终点 其它的顶点称为w 的内部 点 并把 称为g 的 v v 途径 k 称为形的长 有时把 简记为w v v v 若途径 的边互不相同 则称 为迹 若途径 的顶点互不相同 则称矿为链 单个顶点也称为 链 若途径 的长至少为1 又起点与终点重合 则称之为闭途径 若某迹的长至少为1 且起点与终点重合 则称之为闭迹 起点 内部点互不相同的闭迹称为圈 k 圈足指长为k 的圈 不含圈的图称为无圈图 图g 的两个顶点 和v 是连通的 若g 中存在一条 v 链 连通 是顶点集y 上的 一个等价关系 于是 存在v 的非空划分 k 圪 使得两个顶点连通当且仅当它们 属于同一个 导出子图g p g g v o 称为g 的连通分支 若g 只有一个连通分 支 则称g 是连通图 否则称为非连通图 用曲表示g 的连通分支数 g 为连通图当且仅 当g 中任何两个顶点都有链连接 下面介绍几类重要的图 完全图 任何两个相异顶点都相邻的简单图 空图 边集为空集的图 二部图 顶点集可以划分成两个子集 和y 使得每条边的一个端点在x 中 另一 个 端点在l 中 二部图g 记作g x y e 若 中每个顶点与l r 中每个顶点之间恰有一条 边 且x a y o 则称二部图g x y e 为完全二部图 设g 矿 e 是一个图 s 为矿的一个非空真子集 s v s 记 s s v v e lv s v s 若f s 豆 o 则称 s 蚕 是g 的一个边割 若e 是g 的一个边割 但点 的任何真子集都 不是g 的边割 则称e 是g 的极小边割 g 的极小边割又称为g 的补圈 一个图的边割与圈有如下的关系 定理1 11 2 设c 和 s 可 分别是图g 的圈和补圈 则 i e c n s s i 0 m o d 2 口 接下来简单介绍一下有向图的基本概念 有向图d 是指由一个非空的有限集合v d 和y d 中的某些元素的有序对的集合 a d 构成的二元组 矿 d 爿 d v d 称为d 的顶点集 其中的元素称为d 的顶 点 a d 称为d 的弧集 其中的元素称为d 的弧 在不混淆时 记v v d a a d d v a 如果v v v v 那么a d 中的元素a 与v d 中某两个元素构成的有 序对 v v 相对应 记口 v v 其中v 称为口的尾 v 称为a 的头 a 称为v 的出弧 也称为v 的入弧 尾和头重合的弧称为环 若两条弧有相同的头和相同的尾 则称这两条 弧为重弧 既没有环也没有重弧的有向图称为简单有向图 把有向图d 中每条弧上的箭头 去掉 即把d 的每条弧 v v 用边v v 代替 得到的图称为d 的基础图 第2 页 国防科学技术大学研究生院学位论文 有向图中的许多概念可以通过它的基础图去描述 我们不再一一赘述 赋权的有向图d 称为网络 赋权的图g 称为无向网络 一般情况下 我们所说的赋权 指的是弧被赋权或边被赋权 若顶点被赋权 我们会特别指明 设d v a w 是一个网络 若d k a 是d 的 个子图 则d k a w 称 为d 的子网络 并且称w d y w 口 为子网络的权 口 a l 同样可以定义无向网络的子网络和子网络的权 这里不再 列出 l 2 树与树形图的基本性质 首先 我们介绍一下树的基本性质 连通的无圈图称为树 若7 是图g 的一个支撑子图 且丁是树 则称丁为图g 的支撑 树 下面的结论揭示了一个图的支撑树与该图的连通性之间的关系 定理1 2 1图g 有支撑树的充要条件是g 连通 口 无向网络中权最小的支撑树被称为最小树 权最大的支撑树被称为最大树 最大树有 着与最小树完全类似的结论 并且可以用类似于求最小树的算法来求无向网络的最大树 这里不再具体列出 其次 看一下树形图的有关知识 不含圈的有根图称为树形图 设丁是有向图d 的一个支撑子图 如果丁是树形图 则称丁是d 的支撑树形图 网络d 中权最小的支撑树形图称为d 的最小树形图 权最大的支撑树形图称为d 的最大树形图 文中使用但未定义的概念和记号参见文献 1 和文献 3 第3 页 垦堕型兰垫查盔堂旦塑兰堕兰堡笙兰 第二章均匀支撑树问题 2 1 最均匀支撑树问题 2 1 1 背景的介绍和模型的建立 某贫困地区有若干优美的自然风光 为了充分利用这些自然资源促进该地区经济发 展 国家有关部门准备投资修建连接各景区的公路网 已知修建连接任何两个景区之问公 路的工期 假定所有需要修建的公路同时开工 试设计一个公路网将各个景区连通起来 在满足尽可能同时完工的前提下 使得总修建工期最短 如果把各个景区看作图的顶点 景区间的公路用相应顶点之间的边表示 每条边上赋 一个权表示相应公路的工期 那么上述问题就可以转化为求无向网络的最大权与最小权之 差最小的支撑树中权最小的支撑树的问题 其数学模型的建立如下 考虑简单连通无向网络g 矿 e w 其中i yj 挖 i e i 州 定义2 1 2 1 设 是一棵树 丁的均匀度b t 定义为丁中边的最大权与最小权的差值 即 6 丁 2 m f a 7 x j w p 一 m f i i n 7j w p 定义2 2 记t r l 丁为g 的支撑树 若存在f t 满足6 f 嚷啦6 r 则称f 为g 的最均匀支撑树 于是 上述问题就是在简单连通无向网络中求最均匀支撑树的问题 2 1 2 问题的求解 本小节里 我们将给出求解问题所需的理论依据以及解决问题的算法步骤 首先 给 出几个引理和推论 引理2 1 网络g 的任意两个最小树的边可以建立1 1 对应 使得对应的边权相等 推论2 1网络g 的最小树的均匀度是惟一的 引理2 2 如果网络g 的边权各不相同 则g 的最小树是惟一的 基于上述结论 可以得到如下的重要定理 定理2 1 设g v e w 是一个简单连通的无向网络 其中f 矿i n j ej 1 1 l 并l k w e 1 w e 2 w e 记 t o t l 为g 的含有边p 的支撑树 并设w z m i n w t i t t 1 1 贝0 v t t 有b t 6 z 第4 页 国防科学技术大学研究生院学位论义 证明易知 z 是g 的最小树 下面用反证法证明定理的结论成立 假设存在丁 t 使得b r 6 匝 记 e 正 e e e k 其中w e w g 蔓w e k e r p e j 2p 如 p 如 其中w e j l w 已 2 w e 一1 并且p e l 由假设可知w 0 w 0 即边p 的权大于支撑树7 1 中任意一条边的权 由此可 得 j e 不在丁 中 考虑基本圈c 8 和基本补圈力 8 k 出定理1 1 可知 存在 p c r p n 纯 p k 并且p7 口 于是可得 w 口 w p k l 显然 t 2 一 p 一p k 是g 的支撑树 并且丁 t 于是 有w r w z 这与 z 是g 的最小树 矛盾 因 此 v t tn 有b t 6 正 口 上述几个结论给出了求解简单连通无向网络g v e w 的最均匀支撑树问题的算 法思想 设g 有个n 顶点和m 条边 并j i w e 1 w e 2 w e 首先 求出g g 中 含有边q 的最小树 并计算其均匀度 其次 求g 2 g 一e 中含有边e 的最小树 并计算 其均匀度 依次下去 直到某个g i 2 是不连通的 最后 比较所得的不同的均匀度 最小者对应的支撑树即为所求 根据这个算法思想我们可以得到一个算法 记为a 具体 步骤如下 s t e p1 将g 中的边按权由小到大排列 不失一般性 设w e 1 w e 2 w e 置 k j l g t g s t e p2 若g 中不存在支撑树 即q 不连通 转s t e p 5 否则 求出嚷中含有边咯的 最小树l 转s t e p 3 s t e p3 计算6 t s t e p4 置嚷 q e 女 k k 1 返回s t e p 2 s t e p5 比较6 7 f 1 2 七一1 记6 巧 2 卿 6 i 则i 为所求 并且其 均匀度为6 r 算法终止 接下来 分析一下算法a 的正确性 在算法进行的过程中 关键是求一些带有限制条件的最小树 由引理2 1 可知 网络 g 的最小树可能是不惟一的 但最小树的边权所组成的序列是惟一的 结合引理2 2 其 不惟一性在于网络g 中某些边的权是相等的 当将这些边选入最小树时 有多种选择 选 取的边不同时 便可以得到不同的最小树 于是 在做了边的限制之后 算法的难确性可 以由定理2 1 来保证 最后 我们来估计算法五的复杂性 第5 页 国防科学技术大学研究生院学位论文 易知 算法中s t e p l 的计算量为0 m l o g m s t e p 2 至s t e p 4 至多循环聊一n 2 次 在 每次循环中 对于s t e p 2 应用d i j k s t r a 算法求伉的支撑树 其计算量为o n 2 s le p 3 与s t e p 4 的计算量均为1 又s t e p 5 的计算量至多为o m l o g m 因此 算法a 的复杂性 为 一 2 o n 2 o m l o g m o n 2 m 在算法a 的基础上 我们可以很容易的得到求解简单连通无向网络g 的权最小的最均 匀支撑树问题的算法思想 由s t e p 5 可以看出 g 中至多有k 一1 个最均匀支撑树 于是 由定理2 1 可得 第一条边的下标最小的最均匀支撑树就是g 的权最小的最均匀支撑树 从 而 只需将算法五中的s t e p 5 稍作修改就可以来求g 的权最小的最均匀支撑树 修改如下 若满足6 f m i nb r 的五是惟一的 则正为就是g 的权最小的最均匀支撑树 否则 i e 盘一 记满足6 i 望咖 6 i 的支撑树的集合为 死 l 乃 则第一条边的下标最小者即 为所求 其具体算法不再列出 易知 求解g 的权最小的最均匀支撑树问题的算法的复杂性也是o n z m 2 1 3 一个算例 例2 1给定简单无向网络g 矿 e w 如图 2 1 所示 求g 的权最小的最均匀 支撑树 7 毛 2 3 父 刊 5 呸 4 图 2 1 例2 1 的图 解易知 g 中的l o 条边满足w e w e w e 下面我们首先在网络gh 执行算法五来求g 的最均匀支撑树 具体结果如下 g 1 g 中含有p 1 的最小树为正 e t o p 1 p 2 9 3 e e 7 并r b r o 3 g 2 g i e i 中含有e 2 的最小树为己 e t p 2 e 3 p 4 e 5 e 7 并r b r 3 g g 2 一e 中含有巳的最小树为五 e i o 巳 e 4 8 5 e 6 e 7 并且6 五 2 g g 3 一巳中含有e 4 的最小树为瓦 e l e 4 e 5 e 6 e 7 口9 并r b l 3 g g 一e 4 中含有e 5 的最小树为e e t 5 8 5 8 e e 8 e 并且6 t 2 g 6 g 5 一e 5 中含有 的最小树为7 6 e 瓦 e 6 e 7 e 8 e 9 e l o 并且6 瓦 5 g 7 g 6 一e 中只含有4 条边 显然该图是不连通的 故算法转至s t e p 5 即比较6 一 第6 页 国防科学技术人学研究生院学位论文 i 1 2 6 易知 五和瓦均为g 的最均匀支撑树 其均匀度都是2 并且正是g 的权最小的最均 匀支撑树 口 2 1 4 进一步的探讨 文献 5 中曾给出下面的结论 设丁是g 的一棵支撑树 记 中边的最大权与最小权分别为m t 和 丁 则 是g 的最均匀支撑树当且仅当图g v e e 和g 一 v e e 一 都是非连通图 其中 e e e f l 以g m 丁 e 一 e e 1 w p m t 由2 1 3 节的算例可知 瓦为g 的最均匀支撑树 并且e t s p p p e 于 是可得e e e 1 e 2 e 3 口4 e 5 p 6 e 7 e e 一 p 6 e 7 9 8 p 9 e l o 显然 图 g y e e 和图g 一 矿 e e 都是连通的 因此 文献 5 中所给出的结论是错 误的 但是 我们可以得到如下两个结论 定理2 2 若r 是g 的最均匀支撑树 则g 矿 e e 一e 一 是非连通图 证明用反证法 假设g 是连通的 则由定理1 2 可知 图g 有支撑树 不妨设 是g 的支撑树 显然 丁 也是g 的支撑树 即t t 又在g 中 有m t 1 r n 7 因此 有6 丁 m c 一m t m t 一m t b t 这与已知条件 是g 的最均匀支撑树 矛盾 故定理的结论成立 口 定理2 3 若r 是g 的支撑树 并且g v e e 和g 一 v e e 一 都是非连通 图 则r 是g 的最均匀支撑树 证明用反证法 假设存在r7 满足丁 是g 的支撑树并且b t 6 丁 f 面基于b t b t 即m t 一m t m t 则r 是图g 一 v e e 一 的支撑树 从而 g 一 v e e 一 是连通的 这与题设 g 一 矿 e e 一 是非连通图 矛盾 因此 有m t r e t 于 是可得m c 一m t7 m t 一坍 r 又因为m t 一m t m c 一m t 所以 m 叮 一m t m t 一m t 即m c7 m t 于是 丁 是图g 矿 e e 的支撑 树 从而 g v e e 是连通的 这与题设 g v e e 是非连通图 矛盾 2 若m c7 m t 于是 r 是g 一 矿 e e 一 的支撑树 从 而g 一 f 矿 e e 一 是连通的 矛盾 综上可知 假设不成立 从而 定理的结沦成立 口 第7 页 里堕登兰丝查盔兰塑塞生堕兰堡丝兰 2 2 带有边集限制的最均匀支撑树问题 2 2 1问题的介绍和模型的建立 在2 1 1 小节的背景基础上 我们要求某些景区是直接连接的 试设计一个尽可能同 时完工 并且满足附带要求将各景区连通起来的公路网 易知 上述这 问题可以转化为求无向网络中带有边集限制的最均匀支撑树问题 其 数学模型的建立如下 考虑简单连通无向网络g v e w iv 净疗 f e l m 其中w 表示工期向量 e o e 为指定的边集 g 陋 是由e o 导出的g 的子图 不妨设g 陋 中不包含圈 于是 上述问题就是求g 的包含毛的最均匀支撑树的问题 2 2 2 理论依据 本小节里 我们给出求解上述问题的理论依据 定义2 3 设丁是一棵树 在g 中收缩 是指把r 的顶点连同边合并在一起成为一个新 的顶点 除e t 中的元素外 g 中其他一切与矿 中的元素关联的边都改为与新顶点关 联 并且g 中其他的顶点和边以及它们的关联关系保持不变 为了方便 将在g 中收缩7 1 记为g t 并称收缩r 后新增加的顶点为人造顶点 定义2 3 的直观解释 如图 2 2 所示 v l v p v 3 a b 图 2 2 定义2 3 的直观示意图 我们把图 a 视为图g 那么图 b 就是g 收缩树丁 其中e t v v v v 之后得 到的图 由图 2 2 可以看出 树的收缩与边的收缩有着本质的差别 因此 当应用图的 收缩的方法时 必须指明对哪种图进行收缩 本小节中 我们用的是对树进行收缩的方 法 与树的收缩相对应的是树的展开 即将人造顶点展开成原型 并且图g 中其他的 顶点和边以及它们的关联关系保持不变 下面分析一下具体问题 设g 陋 有f 个连通分支 由于g 瓯 不包含圈 因此 t i e 的每个连通分支均为树 在 第8 页 并且不改变边的权后得到的网络 设简单连通无向网络g 收缩图g l 磊l 后得到的网络为 g 因支撑树中不含环 故可以将g 中的环去掉 设将g 中的环去掉后所得的网络为 g v e w 其中i 矿 f n je i m 显然 有嘲 m n 1 w t 设g 中与丁 相对应 即把r 展开 的支撑树为巧 则有 w 巧 w t w e w 琢 w 凰 w 瓦 显然 巧是g 的包含凰的支撑树 这与 瓦是g 的包含e 0 的最小树 矛盾 因此 w 写 w t 充分性得证 同理可证必要性 口 基于引理2 3 可以得到本小节中的重要结论 定理2 4 对于无环的连通网络g v e w 设w e m i n w e fe e 记 t 柙 rr 为包含e 且含有边e 的g 的支撑树 并设w 一 m i n w t i t t o 贝0 v t t 有b t 6 互 证明记集合t o 中的每个元素收缩g l e 0 1 后所对应的元素的集合为f 易知 f 是g 的含有边q 的支撑树的集合 记互收缩g e 0 后所对应的g 的支撑树是1 7 显然 t t 1 并且正 亍 因为互是包含毛且含有边q 的g 的最小树 所以 由引理2 3 可知 i 是含 有边e 的g 的最小树 用m e 和m e 分别表示晶中权最大的边的权值和权最小的边 的权值 m t 和m 口 t t o 以及m t 和m t t7 t 的含义与m 和m e 的含义类似 由定理2 1 可知 vt t 有 b t 6 正 即m t 彳 一 又易知v t t 有m t m 互 因此 要比较6 r 和6 互 的大小 只需比较m t 和 m 正 的大小即可 vt t 设f 中与7 1 对应的为r 下面分三种情况来讨论 1 若m e o m t 则m 互 m t 吖 e o 于是 b 肘 e o 一m 丁 b 正 第9 页 璺堕型兰垫查盔兰竺塑兰堕兰垡笙三兰 综上所述 v t t 有b t 6 正 口 2 2 3 算法步骤和复杂性分析 由引理2 3 可以看出 带有边集限制的最均匀支撑树问题与带有边集限制的最小树问 题有着十分密切的关系 即前者以后者为基石 因此 我们需要先来解决带有边集限制的 最小树问题 文献 2 中第二章的第三小节介绍了几种求最小树的算法 下面以这些算法 为基础 给出求g 的带有边集限制的最小树的算法 为了叙述方便 记此算法为a 具体 步骤如卜 s t e p1 在g 中收缩图g 旧 l 并去掉环 设所得无向网络为g s t e p2 求g 的最小树碍 s t e p3 将t o 展开 形成网络g 的包含e 的最小树 算法终止 易知 算法a 的正确性由引理2 3 来保证 接下来 我们分析一下算法a7 的复杂性 算法中 s t e p l 是在g 中收缩图g e o 并去掉环 因为g i e o 有f 个连通分支 并且 g 中不含圈 所以收缩g e o 的计算量为d m 而去掉环至多需要对每条边进行搜索 故s t e p l 的计算量为0 肌 s t e p 2 是求最小树 由文献 2 知 d i j k s t r a 算法的复杂性最好 故用d i j k s t r a 算法求g 的最小树 又d i j k s t r a 算法中要求无向网络为简单无向网络 而g 中往往含有重边 此时 我们只需将g 稍作修改即保留这些重边中权最小的 其他的都删 去 得到另外一个简单无向网络睇 对睇应用d i j k s t r a 算法求出的最小树就是g 的最 小树 因此 s t e p 2 的计算量至多为o n s t e p 3 需要对g 中的边进行搜索 故s t e p 3 的计算量为o m 因此 算法a 的时间复杂性为 o m o 0 沏1 o n 有了上述基础 我们就可以给出带有边集限制的最均匀支撑树问题的求解过程了 基 于定理2 4 先给出求解这一问题的算法思想 已知图g l 凰l 有t 个连通分支 首先 在g 中收缩g i 民i 著且去掉环 得到网络为g 然后将g 中的边按权w 由小到大排歹0 不妨 设为w e w e 蔓w e 其次 求出g g 7 中含有边p 的最小树1 7 设g 中与 对应的支撑树为一 计算其均匀度6 i 再次 求g 2 g 1 一q 的含有边p 的最小树巧 设g 中与z 对应的支撑树为五 计算其均匀度b t 0 依次下去 直到某个g i 2 不再 连通 由这一算法思想我们可以得到求解带有边集限制的最均匀支撑树问题的算法 记此 算法为a 具体步骤如下 s t e p1 在g 中收缩g l 毛i 并去掉环 得到网络g v e w s t e p2 将g 中的边按权由小到大排列 不妨设为w e 1 墨w e 2 w e 第1 0 页 国防科学技术大学研究生院学位论文 s t e p3 置g g k 1 s t e p4 若g 女是不连通的 转s t e p s 否则 求出g k 中含有e k 的最小树巧 转s t e p 5 s t e p5 求g 中与巧相对应的支撑树瓦 s t e p6 计算均匀度6 t s t e p7 置嚷 g 一e k k k l 返回s t e p 4 s t e p8 比较6 i i 1 2 k 一1 记6 i 2 卿 6 z 则一为g 的包含民的最 均匀支撑树 其均匀度为6 z 算法终止 易知 算法a 的难确性由引理2 3 和定理2 4 共同保证 下面估计一下算法a 的复杂性 算法a 中 s t e p l 的计算量至多为o m s t e p 2 是将g 中的边按权由小到大排序 其计算量为o m ll o g m l s t e p 3 是赋值运算 其计算量为o 1 s t e p 4 至s t e p 7 至多循环 粥一一十2 次 在每次循环中 s t e p 4 的计算量至多为o n s t e p 5 的计算量为o m 1 s t e p 6 的计算量至多为o n s t e p 7 的计算量为0 0 s t e p 8 的计算量为o m 因此 算法a 的复杂性为0 h 卅 2 2 4 一个算例 例2 2 给定简单无向网络g 矿 e w 如图 2 3 所示 应用算法a 求g 的包 含边集e v 叱 v 3 v v v 的最均匀支撑树 酬 2 3 例2 2 的例 解首先 在g 中收缩g l 凰l 并去掉收缩后所得网络中的环 设所得到的网络为 g 矿 e w 如图 2 4 所示 因g e 0 l 有两个连通分支 故g 中有两个人造顶点 按 下来 对g 应用算法a 的s t e p 2 s t e p 8 为了叙述方便 我们给g 中的边以编号 并 标记在图 2 4 上 下面给出计算的具体结果 g g 中含有e 的最小树为正 其边集为e 五 e e g 中与之对应的支撑树正 的边集为占 五 v l v 2 也v 4 v 4 v 5 v l v 3 v 2 v 6 并且6 正 5 g 2 g 一e 中含有e 的最小树为巧 其边集为e 乏 e 色 g 中与之对应的支撑 第1 1 页 国防科学技术人学研究生院学位论文 树疋的边集为e 正 f v v 2 v 3 v 4 v 4 v 5 v 5 v 6 v 2 v 6 并且6 e 4 g g 一e 中含有e 的最小树为巧 其边集为e 巧 p e 4 g 中与之对应的支撑 树e 的边集为e e h v 2 v 3 v 4 v 4 v 5 v 5 v 6 v l v 5 并且6 五 3 y i v 6 圈 2 4 无向网络g 的示惹图 g 4 g 一e 中含有e 的最小树为巧 其边集为e e e g 中与之对应的支撑 树五的边集为e l v l v 2 v 3 v 4 v 4 v 5 v l v 5 v 4 v 6 并h h l 2 g g 4 一e 中含有e 的最小树为巧 其边集为e 巧 e e g 中与之对应的支撑 树e 的边集为e e p l v 2 v 3 v 4 v 4 v 5 v 4 v 6 v l v 6 并且6 e 3 g 6 g 一巳只含有一条边e 故该图不连通 因此 g 的包含边集凰的最均匀支撑树为l 其均匀度为2 口 2 3 最大最小树与最小最大树 设g 矿 e w 为简单连通的无向网络 其中f v 降聆 i e m v te t 令 谛 r m a x e e e t w p 谛 7 1 e m e e i 强w p lj 定义2 4 若存在于 t 满足访 f 卿茹 r 则称f 为g 的最大最小支撑树 简 称最大最小树 定义2 5 若存在于 t 满足谛 于 m 登c v t 则称于为g 的最小最大支撑树 简 称最小最大树 f 面的两个结论揭示了最小树与最大最小树 以及最大树与最小最大树之间的关系 定理2 5g 的最小树一定是g 的最大最小树 证明设z 是g 的任意一个最小树 下证谛 r 话 正 反证法 若罚 r 话 互 设订 丁 w 虿 茹 五 w e 1 则w y w e 1 于是 边e 1 1 i 在丁 上 考虑c r p 1 和马 e 1 由定理1 1 可知 l c r p 1 n 纯 8 1 0 r o o d 2 因此t 存在 边p c r 8 1 n 嘞 8 1 从而w p w e 1 并 a t e e l 仍然为g 的支撑树 于是可得 第1 2 页 国防科学技术大学研究生院学位论文 w 巧 e e e 时 必存在区域力 使得 无穷远点是r2 力巾均匀度最小的点 证明在f7 上取一点p f 设p 与f 1 的距离为x 如图 3 1 所示 令 一一 p1 一 x 尸 p b 一p p c 口2 d x 2 一 p 2 x 2 易知 当z 充分大时 总有 厂 x 0 并且b p7 f x 又因为 f x 型竺 兰 一 兰 p 了丽丽 瓜a 再2 历 所以 当a p 时 有 厂 x 0 即f x 是关于x 的严格单调递增函数 又l i m f x d d b d g 一 c 石 p 7 图 3 1 定理3 1 的图 因此 无穷远点不是最均匀点 当a e 时 对充分大的x x 旦 总有 x 0 于 a p 是 必存在区域力 使得f x 在r2 妇上是关于z 的严格单调递减函数 又l i m j x 屯 因此 无穷远点是r2 力中均匀度最小的点 于是 定理的结论成立 口 3 3 求解问题的算法 定理3 1 的证明是构造性的 由此我们可以得到求平面上的最均匀点的算法思想 给 定平面上h h 4 个点a 4 a 首先 判断这托个点是否共线 如果共线 那么无 穷远点是最均匀点 如果不共线 那么我们就需要求出由这 个点生成的凸包 其次 计 算无穷远点的均匀度 并找出与其对应的方向 然后 求出区域口 并在口中计算出均匀 度最小的点 最后 将得到的两个数值作比较 最小者所对应的点即为所求 下面根据上 述算法思想给出求平面上的最均匀点的算法 记为a 具体步骤如下 s t e p1 若给定的点a a 彳 是共线的 则无穷远点是最均匀点 算法终l l 否 则 转s t e p 2 s t e p2 求由a a 4 生成的凸包h s t e p3 分别计算与h 的各边垂直的方向上的无穷远点的均匀度 并求出无穷远点的 第1 6 页 四防科学技术大学研咒生阮学位论文 均匀度炙 s t e p4 设d b 1 求出区域力 s t e p5 求出区域力中均匀度最小的点 记为尸 并且记下b p 的值 s t e p6比较d 与b p 最小者对应的点即为所求 算法终止 易知 算法五中 关键的步骤是s t e p 5 即如何求出区域力中均匀度最小的点 为 此 我们给出下面的定理 定理32 设尸是最均匀点 则a t 1 2 与p 的距离中达到最大值与最小值的 点均是不惟一的 证明首先 证明4 f 1 2 胛 与p 的距离中达到最大值的点是不惟一的 用反 证法 假设a t 1 2 胛 与p 的距离中达到最大值的点是惟一的 不失一般性 假设 p p a 1 s p 尸 a2 尸 p a 0 在连接尸与爿 的线段上选取一点 使得p j p p 霎 即 p p a p p a 宴 下面分两种情况讨论 1 v f 1 2 n 一1 点p a 4 均不共线 因j p p a 一p p a 故j p p 4 昙一p p a 又因为点p a a 不共 线 所以点p 4 p 也不共线 于是 有不等式 p p a p p a 昙 成立 从而可得 j p p 一 手一p 尸 爿 萼 即0 昙 p p a 一p p7 4 也即p p a p p7 4 f 1 2 门一1 因此 a f l 2 n 与p 的距离中达到最大值的点是惟一的 又因为 p p7 a 一p p 爿 p p a 一要一p p 爿 t 且p p a p p 爿 霎 所以 第1 7 页 国防科学技术大学石j f 究生院学位论文 尸 p a 一尸 p a p e a 一p e a 又p j p a p p a 故 p p a p p a p e a 一p 尸 a 1 于是 有6 p 6 p 这与已知条件 p 是最均匀点 矛盾 2 存在某个i i 1 2 聆一1 使得点p 爿 a 共线 记 1 i l 点p a a 共线 点p a a 不共线 其中1 羔f 疗一1 易知 1 a 并且v i 1 有 p p a 一p 尸 a p e a 一尸 p a 又因为p p a p e a i 所以 p j p a 一p p a p p a 一p p a 由 1 的证明过程可知 v j 有 p p 7 a 一p 尸 a p e a 一p p a 1 从而 若v i i 有 p p a 一p p a p p a 一p p a i 则可得6 p 0 所以p 尸 a p p 爿 又因v k u 有 p p a 一尸 p 以t p p 一 于是 p p a 是4 f 1 2 与p 7 的距离中惟一的最小 值 并且由 1 的证明过程可知 v 7 有p p a 亨 o 所以v i i 有p p 爿 p p7 4 从而vi 1 2 n l 有p p a p e 4 于 是 p p7 爿 是a 1 2 h 与p 的距离中惟一的最大值 因此 有 b p b p p p a 一p j p a 下面以a 为圆心 以p p 4 为半径作一段充分小的圆弧 于是 在圆弧上一定存 在充分靠近尸 的点尸 它满足在a f 1 2 h 与p 的距离中 p p a 和尸 p a 仍然是惟一的最大值和最小值 如图 3 2 所示 在图 3 2 中 我们只画出了部分点之问 的关系 p 图 32 定理3 2 的图 由图 3 2 可知 p p a p a a p p a p p 爿 从而 有b p b p 这与已知条件 p 是最均匀点 矛盾 于是 综合 1 和 2 的证明可知 4 f 1 2 与p 的距离中达到最大值的点是 不惟一的 其次 同理可证 a 扛1 2 与p 的距离中达到最小值的点也是不惟一的 故 定理的结论成立 口 易知 算法a 的正确性由定理3 1 和定理3 2 共同保证 最后 我们估计一下算法五的复杂性 算法中 s t e p l 判断点4 4 4 是否共线