（应用数学专业论文）欧几里德距离下的最短2连通steiner网络.pdf

摘要 摘要 设 p是一个有限点集， n=( v , e ) 是一个顶点集为v， 边集为e的网 络 如果 vdp， 则称n为p的s t e i n e : 网络. 特别地， 如果 v=p， 则称 n为p的生成网 络. 称p中 的点 为正 则点， 称v p中 的点 为s t e i n e r 点. 网 络n的长度定义为它的各条边的长度的和 欧几里德2 一 连通s t e i n e r 网络问 题 可以描述为:给定欧几里德平面上的一个有限点集 尸，确定尸的最短 2 一 连通 s t e i n e : 网络. 这里， 任意两点之间的长 度定义为它们之间的欧几里德距离， 该 网络允许添加欧几里德平面上给定点集以外的点. 该问题在构造可靠经济的通讯 网络方面有重要的应用价值. l u e b k e 和 p r o v a 。证明了欧几里德 2 一 连通 s t e i n e r 网 络问 题是 n p 一 困难 的 这意味着对一般的平面有限点集而言， 不大可能存在求解这个间题的多项式 时间算法， 1 9 9 8 年，h s u 和h u 引入基本2 一 连通s t e i n e r 网络的 概念、 给出 了( 基本 最短 2 一 连通 s t e i n e r 网络的一些结构性质和两种特殊的多项式可解 情形. 李美丽在她的硕士论文中，以块图为工具， 给出了 ( 基本) 最短 2 一 连通 s t e in e r 网络的进一步的一些性质，对 h s u 和 h u的一个已有结论进行了清楚的 证明.本论文对该问题进行进一步的研究. 论文第一章介绍了论文中涉及的一些基本概念和术语，欧几里德 2 一 连通 s t e i n e r 网络问 题的 研究现状以 及论文中所得到的主要 结果. 利用 m o n m a 等人给出的2 一 连通网络的一个性质， 在论文的第二章中，我 们给出了( 基本) 最短 2 - 连通s t e i n e r ( 或生成) 网络的一些新的结构性质， 对 李美丽给出的( 基本) 最短2 - 连通s t e i n e : 网络的三个性质给出了新的、 简单的 证明 第三章主要讨论了一类特殊点集 i p i = 6 或7 时的 最短2 一 连通s t e i n e r 网 络与其最短2 一 连通生成网络和最短 h a m i l t o n圈之间的关系. 欧几里德 2 一 连通 s t e i n e r 网络问题是度量空间上的 2 一 连通s t e in e r 网络问 题的特殊情况. 第四章将关于最短 2 一 连通s t e i n e r 网络的几个结论推广到一般的 度量空间上 在第五章中，我们给出了广义欧几里德s t e i n e : 问 题的描述， 提出了该问题 的进一步研究的一些问题. 关键词: s t e i n e r 网络， 生成网络， 欧几里德 2 一 连通s t e i n e : 网络问题， 基本 2 一 连通s t e i n e r 网络，广义欧几里德 s t e i n e r 问题 ab s t r a c t abs t r a c t l e t p b e a fi n i t e s e t o f p o i n t s . a n e t w o r k n=( 认e ) i s c a l l e d a s t e i n e r n e t w o r k o n p i f p c v , a n d p a r t i c u l a r l y a s p a n n i n g n e t w o r k o n p i f p=v . f o r a s t e i n e r n e t w o r k n o n p , p o i n t s i n p a r e c a l l e d r e g u l a r p o i n t s , w h i l e p o i n t s i n v p a r e c a l l e d s t e i n e r p o i n t s . t h e l e n g t h o f a n e t w o r k is d e fi n e d t o b e t h e t o t a l l e n g t h o f a l l i t s e d g e s . g i v e n a fi n i t e s e t p o f p o i n t s i n t h e e u c l i d e a n p l a n e , t h e e u c l i d e a n 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m i s t o fi n d t h e s h o r t e s t 2 - c o n n e c t e d s t e i n e r n e t w o r k o n p , w h e r e t h e l e n g t h o f a n e d g e p q i s d e fi n i e d a s t h e e u c l i d e a n d i s t a n c e b e t w e e n t h e p o i n t s p a n d q , a n d s o m e e x t r a p o i n t s n o t i n p ma y n e e d . t h i s p r o b l e m h a s i m p o r t a n t a p p l ic a t i o n s i n t h e d e s ig n o f e c o n o mi c a l a n d r e l i a b l e c o mmu n i c a t i o n n e t w o r k s . l u e b k e a n d p r o v a n p r o v e d t h a t t h e e u c l i d e a n 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m i s n p - h a r d , w h i c h m e a n s t h a t t h e r e a r e f e w p o s s i b i l i t i e s o f e x i s t i n g a p o l y n o mi a l t i m e a l g o r i t h m f o r a g e n e r a l fi n i t e s e t p o f p o i n t s i n t h e e u c l i d e a n p l a n e . i n 1 9 9 8 , h s u a n d h u i n t r o d u c e d t h e c o n c e p t o f b a s i c 2 - c o n n e c t e d s t e i n e r n e t w o r k s , a n d g a v e s o m e s t r u c t u r a l p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d s t e i n e r n e t w o r k s a n d t w o p o l y n o m i a l ly - s o l v a b l e c a s e s . l i me i l i , i n h e r t h e s i s s h o w e d s e v e r a l s t r u c t u r a l p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d s t e in e r n e t - w o r k s b y u s in g b l o c k g r a p h s a s t o o l s a n d g a v e a c l e a r p r o o f o f a r e s u l t o f h s u a n d h u . i n t h i s t h e s i s , w e g i v e a f u r t h e r r e s e a r c h o n t h e e u c l i d e a n 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m i n c h a p t e r 1 , a f t e r a n i n t r o d u c t i o n o n t e r m i n o l o g y a n d n o t a t i o n s , w e g i v e a s u r v e y o n t h e e u c l i d e a n 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m a n d a g e n e r a l i n t r o d u c t i o n o f t h e ma i n r e s u l t s o f t h e t h e s i s . i n c h a p t e r 2 , w i t h a p r o p e r t y o f 2 - c o n n e c t e d n e t w o r k s g i v e n 饰m o n m a e t a l . , w e g i v e s e v e r a l n e w s t r u c t u r a l p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d s t e i n e r ( o r s p a n n i n g ) n e t w o r k s , a n d m o r e s i m p l e a n d c l e a r p r o o f s o f t h r e e p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d s t e i n e r n e t w o r k s p r e s e n t e d b y l i m e i l i i n c h a p t e r 3 , w e ma i n l y d i s c u s s t h e r e l a t i o n s h i p a mo n g t h e s h o r t e s t 2 - c o n n e c t e d s t e i n e r n e t w o r k o n p , t h e s h o r t e s t 2 - c o n n e c t e d s p a n n i n g n e t w o r k o n p a n d i t s s h o r t e s t h a m i l t o n c y c le w h e n jp j =6 o r 7 . i v 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m i n m e t r i c s p a c e . i n c h a p t e r 4 , w e g e n e r a l i z e s e v e r a l r e s u l t s o n s h o r t e s t 2 - c o n n e c t e d s t e i n e r n e t w o r k s t o g e n e r a l m e t r i c s p a c e . a t t h e e n d o f t h i s t h e s i s , w e g i v e a d e s c r i p t io n o f t h e g e n e r a l i z e d e u c l i d e a n s t e i n e r p r o b l e m a n d p r o p o s e s o m e p r o b l e m s f o r f u r t h e r r e s e a r c h . k e y w o r d s : s t e i n e r n e t w o r k , s p a n n i n g n e t w o r k , e u c l i d e a n 2 - c o n n e c t e d s t e i n e r n e t w o r k p r o b l e m, b as i c 2 - c o n n e c t e d s t e i n e r n e t w o r k , g e n e r a l i z e d e u - c l i d e a n s t e i n e r p r o b l e m 第一章绪论 第一章绪论 1 . 1 引言 由于通讯网络在现代生产、 生活中有着非常广泛的应用， 因此通讯网络设计 问 题具有非常重要的应用价值. 在通讯网 络的设计中， 一般说来， 有两个因素必 须加以考虑: 一是希望费用尽可能小， 即构建和维护网络各条通讯线路的费用和 尽可能小，二是希望网络的可靠性 尽可能高， 这样.当出现定时维修、 超载等故 障而导致某些通讯线路或通讯站不能正常工作时， 剩余通讯站之间的通讯仍然可 以通过其他通讯线路与通讯站正常进行. 我们用图或者赋权图表示通讯网络， 其中顶点表示网络的通讯站， 边表示网 络的通讯线路， 边上的权指的是构建和维护其所对应的通讯线路的费用. 人们对 于通讯网络设计问题的研究主要包括两个方面: 网络中的通讯网络设计问题和欧 几里德平面上的通讯网络设计间题 网络中的通讯网络设计问题是指给定一个网 络和它的一个顶点子集， 确定它的一个费用最小的子网络， 使得给定顶点子集中 的任意两个顶点满足特定的连通性要求. 值得注意的是， 该子网络可以包含网络 中给定顶点子集以外的顶点. 欧几里德平面上的通讯网 络设计问 题是指确定连接 欧几里德平面上一 组给定点的 满 足特定 连通 性要求的 最短网 络问 题( 两点之间 的 长度定义为它们之间的欧几里德距离， 该网络允许添加欧几里德平面上给定点集 以外的点)在仅仅要求网络连通的条件下， 称以上两个问题分别为网络s t e i n e r 问 题和欧 几里德s 七 e i n e r 问 题.wi n t e r l , 2 和h w a n g 与r i c h a r d s 3 给出了 以 上两种s t e i n e : 问题的详细综述 本文只讨论欧几里德平面上的通讯网络设计问 题 欧几里德s t e i n e r 问 题是 s t e i n e r 问 题中 最早研究的领域， 也是发展最快的 一个分支. c a r e y 等人闪证明了 这个问 题是n p 一 困 难的. 这意味着 对一般的 平面有限点集而言， 不大可能存在求解这个问题的多项式时间算法. 近年来， 关 于欧几里德s t e i n e r 问题的m e l z a k 几何思想、 算法理论以及一些有关的猜想， 尤其是s t e i n e r 比 率的研究取得了 很大进展 关于欧几里德s t e i n e r 问 题的综述 见 文献! 5 , 6 越民 义闭与 姚恩 瑜等 人8 也 对欧几 里德s t e i n e r 间 题进行了比 较深入的讨论. 根据欧几里德 s t e i n e r 问题确定的网络是树状结构， 在仅仅要求网络连通的 条件下费用最小， 但是这样的网络可靠性非常弱. 因为当 其中任意一条通讯线路 或一个通讯站出现故障而不能正常工作时， 都有可能导致其他-9a讯站夕间f- r 第一章绪论 第一章绪论 1 . 1 引言 由于通讯网络在现代生产、 生活中有着非常广泛的应用， 因此通讯网络设计 问 题具有非常重要的应用价值. 在通讯网 络的设计中， 一般说来， 有两个因素必 须加以考虑: 一是希望费用尽可能小， 即构建和维护网络各条通讯线路的费用和 尽可能小，二是希望网络的可靠性 尽可能高， 这样.当出现定时维修、 超载等故 障而导致某些通讯线路或通讯站不能正常工作时， 剩余通讯站之间的通讯仍然可 以通过其他通讯线路与通讯站正常进行. 我们用图或者赋权图表示通讯网络， 其中顶点表示网络的通讯站， 边表示网 络的通讯线路， 边上的权指的是构建和维护其所对应的通讯线路的费用. 人们对 于通讯网络设计问题的研究主要包括两个方面: 网络中的通讯网络设计问题和欧 几里德平面上的通讯网络设计间题 网络中的通讯网络设计问题是指给定一个网 络和它的一个顶点子集， 确定它的一个费用最小的子网络， 使得给定顶点子集中 的任意两个顶点满足特定的连通性要求. 值得注意的是， 该子网络可以包含网络 中给定顶点子集以外的顶点. 欧几里德平面上的通讯网 络设计问 题是指确定连接 欧几里德平面上一 组给定点的 满 足特定 连通 性要求的 最短网 络问 题( 两点之间 的 长度定义为它们之间的欧几里德距离， 该网络允许添加欧几里德平面上给定点集 以外的点)在仅仅要求网络连通的条件下， 称以上两个问题分别为网络s t e i n e r 问 题和欧 几里德s 七 e i n e r 问 题.wi n t e r l , 2 和h w a n g 与r i c h a r d s 3 给出了 以 上两种s t e i n e : 问题的详细综述 本文只讨论欧几里德平面上的通讯网络设计问 题 欧几里德s t e i n e r 问 题是 s t e i n e r 问 题中 最早研究的领域， 也是发展最快的 一个分支. c a r e y 等人闪证明了 这个问 题是n p 一 困 难的. 这意味着 对一般的 平面有限点集而言， 不大可能存在求解这个问题的多项式时间算法. 近年来， 关 于欧几里德s t e i n e r 问题的m e l z a k 几何思想、 算法理论以及一些有关的猜想， 尤其是s t e i n e r 比 率的研究取得了 很大进展 关于欧几里德s t e i n e r 问 题的综述 见 文献! 5 , 6 越民 义闭与 姚恩 瑜等 人8 也 对欧几 里德s t e i n e r 间 题进行了比 较深入的讨论. 根据欧几里德 s t e i n e r 问题确定的网络是树状结构， 在仅仅要求网络连通的 条件下费用最小， 但是这样的网络可靠性非常弱. 因为当 其中任意一条通讯线路 或一个通讯站出现故障而不能正常工作时， 都有可能导致其他-9a讯站夕间f- r 第一章 绪论 正常通讯中断. 所以， 研究费用小而可靠性更高的通讯网络设计问题具有非常重 要的 意义c h r i s t o fi d e s 和wh i t l o c k 9 与g r o t s c h e l 等人 1 0 对网 络设计中 的 可靠性要求进行了细致的讨论，并给出了一些解决技巧. 一般说来， 一个网络的连通度越高， 则它所对应的通讯网络就越可靠 但我 们又不能无限制地增加通讯线路， 因为这样费用也会相应地增加 况且， 欧几里 德平面上的通讯网络设计间题的一般情况是很复杂的 到目 前为止， 关于这个问 题主要是对于一些特殊情况， 尤其是欧几里德平面上的2 一 连通和3 一 连通通讯网 络设计间题进行了比 较多的研究. 其实， 对于实际问题， 特别是对于光纤通讯网 络设计而言，这些特殊情况确实也是非常重要的.贝尔实验室的科学家 mo n m a 和5 h a l lc r o s s 在 【 1 1 中曾 经指出: .对于光纤通讯网络来说， 可靠性是一个尤其重要的因素. 这主要是因为光纤 通讯网络具有费用高和传输量大的特点， 大部分光纤通讯网络都是稀疏网 络. 这样、 某一条通讯线路或某一个通讯站出现故障， 有可能导致整个网络 失效，并带来非常大的损失; . 对于光纤通讯网络来说，2 一 连通就很可靠了. 这主要是因为一旦网络中的某 条通讯线路或某个通讯站出现故障: 一般可以在比 较短的时间里得到修复， 并且在得到修复之前，其他通讯线路或通讯站再出现故障的可能性很小. 鉴于以上原因， 本文只讨论 2 一 连通通讯网络设计间题. 在下面的两节里， 我们 将依次介绍本论文所用到的一些基本概念和术语以及 欧几里德平面上 2 一 连通通讯网络设计问题的研究现状， 在本章的第四节，我们 将介绍本论文中所得到的研究结果 1 . 2 基本概念与术语 我们约定本文用到的网络和图是等同的， 边的权、 长度和费用也是等同的. 论文中 未加 说明的 概念和术 语参见【 1 2 为了 便于阅 读， 在以 后各章中 我们 可能 重复这里介绍的一些概念和术语. 定义 1 . 1 . 设尸是一 个有限点集，n=( u司 是一 个项点集为v， 边集为e 的网 络. 如果 vd尸， 则称n为p的s t e i n e r 网 络. 特别地， 4.果v=p， 则 称n为尸的生成网 络. 称尸中的点为正则点， 称v 尸中的点为及 。 二: 查 、 . 定义 1 . 2 . 设 尸是一个有限点集，n是 p的一个 s t e i n e r 网络. 如果n是一裸 树，且 n 中正则点的度均为 1 ，则称 n 为满 s t e i n e r 树 定义 1 . 3 . 设 i 和j是网络 n 中两个的顶a .如果 : ， ，之问至少存在 k条内邵 2 第一章 绪论 正常通讯中断. 所以， 研究费用小而可靠性更高的通讯网络设计问题具有非常重 要的 意义c h r i s t o fi d e s 和wh i t l o c k 9 与g r o t s c h e l 等人 1 0 对网 络设计中 的 可靠性要求进行了细致的讨论，并给出了一些解决技巧. 一般说来， 一个网络的连通度越高， 则它所对应的通讯网络就越可靠 但我 们又不能无限制地增加通讯线路， 因为这样费用也会相应地增加 况且， 欧几里 德平面上的通讯网络设计间题的一般情况是很复杂的 到目 前为止， 关于这个问 题主要是对于一些特殊情况， 尤其是欧几里德平面上的2 一 连通和3 一 连通通讯网 络设计间题进行了比 较多的研究. 其实， 对于实际问题， 特别是对于光纤通讯网 络设计而言，这些特殊情况确实也是非常重要的.贝尔实验室的科学家 mo n m a 和5 h a l lc r o s s 在 【 1 1 中曾 经指出: .对于光纤通讯网络来说， 可靠性是一个尤其重要的因素. 这主要是因为光纤 通讯网络具有费用高和传输量大的特点， 大部分光纤通讯网络都是稀疏网 络. 这样、 某一条通讯线路或某一个通讯站出现故障， 有可能导致整个网络 失效，并带来非常大的损失; . 对于光纤通讯网络来说，2 一 连通就很可靠了. 这主要是因为一旦网络中的某 条通讯线路或某个通讯站出现故障: 一般可以在比 较短的时间里得到修复， 并且在得到修复之前，其他通讯线路或通讯站再出现故障的可能性很小. 鉴于以上原因， 本文只讨论 2 一 连通通讯网络设计间题. 在下面的两节里， 我们 将依次介绍本论文所用到的一些基本概念和术语以及 欧几里德平面上 2 一 连通通讯网络设计问题的研究现状， 在本章的第四节，我们 将介绍本论文中所得到的研究结果 1 . 2 基本概念与术语 我们约定本文用到的网络和图是等同的， 边的权、 长度和费用也是等同的. 论文中 未加 说明的 概念和术 语参见【 1 2 为了 便于阅 读， 在以 后各章中 我们 可能 重复这里介绍的一些概念和术语. 定义 1 . 1 . 设尸是一 个有限点集，n=( u司 是一 个项点集为v， 边集为e 的网 络. 如果 vd尸， 则称n为p的s t e i n e r 网 络. 特别地， 4.果v=p， 则 称n为尸的生成网 络. 称尸中的点为正则点， 称v 尸中的点为及 。 二: 查 、 . 定义 1 . 2 . 设 尸是一个有限点集，n是 p的一个 s t e i n e r 网络. 如果n是一裸 树，且 n 中正则点的度均为 1 ，则称 n 为满 s t e i n e r 树 定义 1 . 3 . 设 i 和j是网络 n 中两个的顶a .如果 : ， ，之问至少存在 k条内邵 2 旦 1 .3欧几里德 2 - 连通 s t e i n e r 网络问题的研究现状 项点不相交( 或边不相交) 的路，则称 和.7 是局部 k - 连通 ( 或局部 k - 边连 通 )的. 定义1 . 4 . 设n是一 个 v ( n ) l k 十1 的网 络， 如果网络n中 任意两 个顶点都 是局部 k - 连通 ( 或局部 肛边连通) 的，则称网络 n 是 k - 连通 ( 或 k - 边连 通 )的 定义 1 . 5 . 网络 n 的长度定义为它的各条边的长度的和.对于给定有限点集 尸 及正整数 k，称 尸的最短 k - 边连通 s t e i n e r 网络的长度与 尸的最短 k 一 边连通 生成网 络的长度的比值为k - s t e i n e : 比率， 记为l k ( p ) . 定义 1 . 6 . 设 n=( v , e ) 是一个顶点集为v， 边集为e的网 络， v i 和v 1 为 v的非空不文子集，c为n 中的一个圈.称一条路 尸为从 v 到v 2 的路， 记 为( v, v 2 ) 一路，知果尸满足1%, ( 下两个条件: ( 1 ) 尸的起点和终点分别为二 ; 和v 2 ，且v i ev, v 2 e姚; ( 2 ) v ( p ) n v i = v 1 , v ( p ) f l v=1 v 2 ， 称一条( 。 ， 。 ) 一 路q为弦路， 如果v ( q ) n v ( c ) = 二 ， v i . 牡. 3 欧几里德2 一 连通s t e i n e r 网络问题的研究现状 如果仅要求网络是 2 - 连通的，则称欧几里德平面上的通讯网络设计问题为 欧几里德2 一 连通 s t e i n e r 网络问题. 该问题可以描述为: 给定欧几里德平面上的 一个有限点集 p， 确定p的最短2 一 连通s t e i n e r 网络 这里，任意两点p 和4 之间的长度定义为它们之间的欧几里德距离， 记为p 9 ， 该网络允许添加欧几里 德平面上给定点集以外的点. 本文以下部分所说的平面指的是欧几里德平面， 最短2 一 连通s t e i n e r 或生 成) 网络均为位于平面上的网络， 且不考虑 尸中的点共线的情况. l u e b k e 和p r o v a n 1 3 证明了 欧几里 德2 一 连通s t e i n e r 网 络问 题 也是n p - 困难问题 以下将从最短 2 一 连通s t e i n e r 网 络的结构特征及求解算法( 包括多 项式可解情形与启发式算法) 和 2 - s t e i n e r 比 率三个方面介绍欧几里德2 一 连通 s t e i n e r 网络间题的研究现状. 1 9 9 8 年，h s u 和h u 1 4 给出l 下 面的 结果: 结论 1 . 1 . ( h s u 和h u 1 4 ) 设尸是平面 上的一个有限点集.则尸的最短2 一 边 连通 s t e i n e r ( 或生成) 网络也是 尸的最短 2 - 连通 s t e i n e r ( 或生成) 网络，反 之亦然. 旦 1 .3欧几里德 2 - 连通 s t e i n e r 网络问题的研究现状 项点不相交( 或边不相交) 的路，则称 和.7 是局部 k - 连通 ( 或局部 k - 边连 通 )的. 定义1 . 4 . 设n是一 个 v ( n ) l k 十1 的网 络， 如果网络n中 任意两 个顶点都 是局部 k - 连通 ( 或局部 肛边连通) 的，则称网络 n 是 k - 连通 ( 或 k - 边连 通 )的 定义 1 . 5 . 网络 n 的长度定义为它的各条边的长度的和.对于给定有限点集 尸 及正整数 k，称 尸的最短 k - 边连通 s t e i n e r 网络的长度与 尸的最短 k 一 边连通 生成网 络的长度的比值为k - s t e i n e : 比率， 记为l k ( p ) . 定义 1 . 6 . 设 n=( v , e ) 是一个顶点集为v， 边集为e的网 络， v i 和v 1 为 v的非空不文子集，c为n 中的一个圈.称一条路 尸为从 v 到v 2 的路， 记 为( v, v 2 ) 一路，知果尸满足1%, ( 下两个条件: ( 1 ) 尸的起点和终点分别为二 ; 和v 2 ，且v i ev, v 2 e姚; ( 2 ) v ( p ) n v i = v 1 , v ( p ) f l v=1 v 2 ， 称一条( 。 ， 。 ) 一 路q为弦路， 如果v ( q ) n v ( c ) = 二 ， v i . 牡. 3 欧几里德2 一 连通s t e i n e r 网络问题的研究现状 如果仅要求网络是 2 - 连通的，则称欧几里德平面上的通讯网络设计问题为 欧几里德2 一 连通 s t e i n e r 网络问题. 该问题可以描述为: 给定欧几里德平面上的 一个有限点集 p， 确定p的最短2 一 连通s t e i n e r 网络 这里，任意两点p 和4 之间的长度定义为它们之间的欧几里德距离， 记为p 9 ， 该网络允许添加欧几里 德平面上给定点集以外的点. 本文以下部分所说的平面指的是欧几里德平面， 最短2 一 连通s t e i n e r 或生 成) 网络均为位于平面上的网络， 且不考虑 尸中的点共线的情况. l u e b k e 和p r o v a n 1 3 证明了 欧几里 德2 一 连通s t e i n e r 网 络问 题 也是n p - 困难问题 以下将从最短 2 一 连通s t e i n e r 网 络的结构特征及求解算法( 包括多 项式可解情形与启发式算法) 和 2 - s t e i n e r 比 率三个方面介绍欧几里德2 一 连通 s t e i n e r 网络间题的研究现状. 1 9 9 8 年，h s u 和h u 1 4 给出l 下 面的 结果: 结论 1 . 1 . ( h s u 和h u 1 4 ) 设尸是平面 上的一个有限点集.则尸的最短2 一 边 连通 s t e i n e r ( 或生成) 网络也是 尸的最短 2 - 连通 s t e i n e r ( 或生成) 网络，反 之亦然. 第一章 绪论 因此， 对于欧几里德平面上的2 一 连通和2 一 边连通通讯网络设计问题来说， 只讨论欧几里德 2 一 连通s t e i n e r 网络间题就足够了， 同时， 对于给定平面有限点 集p , 2 - s t e i n e r 比 率 记为1 2 ( p ) ) 可以定义为p的最短2 一 连通s t e i n e : 网络 的长度与 尸的最短2 一 连通生成网络的长度的比 值. 以下是关于最短 2 - 连通s t e i n e r 或生成) 网络结构性质的几个结论: 结 论1 . 2 . ( h s u 和h u 1 叨设p是 平面 上 的一 个有 限点集，n是尸的最 l se . 2 - 连通 s t e i n e r ( 或生成) 网络.则 ( 1 ) n中任意一个顶点的度为2 或3 ; ( 2 ) 删除n中 的任意一条或一对边， 所得导出网 络的某一个连通分支包 含割 边. 结论1 . 3 . ( h s u 和h u 1 4 ) 设尸是平面 上的 一 个有限点集，n是p的最 短2 - 连通s t e i n e r ( 或生成) 网络 则n不包 含重边. 结 论1 .4 . 禅、和h u 1 叼 ) 设p是 平面 上 的 一 个有 限 点 集 ，n是p的 最 短2 - 连通 s t e i n e r 网络， . 则 ( 1 ) n中 任意一个 s t e i 、二 点的 度为3 ， 且与 之关 联的三条 边中 任意两条 边的夹 角为1 2 4 0 ; ( 2 ) n不包 含仅含s t e i n e : 点的圈 . 结论 1 . 5 . ( l u e b k e 和p r o v a n 1 3 ) 设p是平面上的一 个有限点集，n是尸的 最短 2 - 连通 s t e i n e r 网络.则n中的任意一条张路的内部顶点至少包含一个正 则点. 结论 1 . 6 . ( l u e b k e 和p r o v a n 1 3 1 ) 设p是平面上的一个有限点集，n是尸的 最- s 2 - 连通 s t e i n e r网络.则 n 为边不相交的满 s t e i n e r 树的并 定义 1 . 7设 尸是平面上的一个有限点集，n是尸的一个位于平面上的2 一 连通 s t e i n e r ( 或生成) 网 络. 显然，n包 含一 个圈 ， 记为c ( n ) ， 使得n为c ( n ) k 及 c ( n ) 内 部一些连通子网 络的并. 我们称c ( n ) 为n的 外圈 . 如果n一 v ( c ( n ) ) 不包 含圈，则称 n为基本的.否则:则称 n为非基本的.如图 1 . 1 所示. 图1 . 1 : ( 1 ) 基本的;( 2 ) 非基本的 互 1 . 3欧几里德2 - 连通s t e i n e r 网络问题的研究现状 定义 1 . 8 . 设 尸是平面上的一个有限点集，n是尸的最短2 - 连通s t e i n e r或 生成)网络.如果 n 是墓本的，则称 n 为 p的基本最短 2 - 连通 s t e i n e r ( 或 生成)网络. h s u 和h u 在文献 1 4 中给出了 基本最短2 一 连通s t e in e r ( 或生成) 网络的 以下性质: 结论 1 . 7 . ( h s u 和h u 1 4 ) 设尸是平面 上的一 个有限点集，n是尸的最短2 - 连通 s t e i n e r 网络.如果 n是基本的，则 ( 1 ) n一v ( c ( n ) ) 中的任意两个s t e i n e r 点都不相邻; ( 2 ) n一v ( c ( n ) ) 为3 阶 s t e i n e r 极小 树的并; ( 3 ) n一 v ( c ( n ) ) 中 的 任意 一 个 正则 点 至 多 和一 个s t e i n e r 点 相 邻. 结论 1 . 8 . ( h s u 和h u 1 4 ) 设尸是平面 上的一个有限点集，n是尸的最短2 - 连通生成网络.如果 n是基本的，则 n一v ( c ( n ) ) 中的任意两个 3 度顶点都 不相冲 卜 . h s u 和h u 在文 献 1 4 中 证明 了以 下 结果: 结论1 . 9 . ( h s u 和h u 1 4 ) 设尸是平面 上的 一 个有限点集.则尸的 最% 2 一 连 通 s t e i n e r 网络也足 尸的最短 2 - 连通生成网络，均为 尸的 h a m i l t o n圈， 扣果 以下条件中任何一个成立: ( 1 ) 尸中至多有一个点位于它的凸包的 边界的内 部; ( 2 ) i p i -是 ， 并 且 用 实 例 说明 了 这 个 界 可 以 任 意 接近. 显然， 这个结论对于欧几里德2 一 连通s t e i n e : 网 络问 题也是成立的. 进一 步地，h s u和 h u 1 引发现对于欧几里德 2 一 连通 s t e i n e r 网络问题. 这个界环可 第一章 绪论 以 改 进 他 们 证 明 了乎4 ,则s m n不包 含边数为3 的圈 wi n t e r 和z a c h a r i a s e n 2 4 对s m n中的弦路和圈进行了 研究， 证明了以下 一些结论: 结论 1 . 1 1 . ( wi n t e r 和z a c h a r i a s e n 2 4 ) 设g 为 任意一 个s m n.则 互 1 . 4本论文的主要结果 ( 1 ) 理 中的 任意一条弦路的 边数至少为3 ; ( 2 ) g 中的 任意一条 弦 路的内 部顶点中 至少包 含一对相邻2 度正则点. 结论 1 . 1 2 . ( wi n t e r 和z a c h a r i a s e n 2 4 ) 设g ， 为 任意一个s m n.a ll ( 1 ) 设 c为g 中的一个包 含3 度顶点的圈.则c包 含两对相邻 2 度正则点， 使得它们分别位于 g的被两个 3度项点分成的两邵分上; ( 2 ) 若 例4 ,则g ， 中 的任意一个圈 至少包 含4 个2 度正则点 ; ( 3 ) 理不包 含仅含正则点 的 个数大于等于3 的 满s t 。 二: 树的 边的圈 . 与 此同 时， 如 果 z i 6 , wi n t e r 和z a c h a r i a s e n 在文 献2 4 中 证明了s iv 1 n 不包含3 度顶点. 进一步 地， 如果! z i =6 ， 他们 给出了s m n包含3 度顶点的 一个例子. 1 .4 本论文的主要结果 我们现在来介绍本论文的主要研究结果. 在第二章第二节， 我们 根据已 有结论和欧几里德距离三角不等式性质， 给出 了最短2 一 连通s t e i n e r ( 或生成) 网络的进一步的一些结构性质: 结论 1 . 1 3 . 设 尸是平面上的一个有限点集，n是尸的最短 2 一 连通 s t e i n e r 网 络.则 ( 1 ) 尸中 位于其凸包 的边界上的.屯 都位于n的外圈 上; ( 2 ) s t e i n e r 点必位于尸的凸包的 边界的内 部. 结论 1 . 1 4 . 设 尸是平面上的一个有限点集，n是 尸的最短 2 一 连通 s t e i n e r 网 络则n 中的任意两条边都不会相交于正则点与 s t e r n e r 点以外的其他点. 李 美丽在她的 硕士论文【 巧 中 证明 了2 一 连通网 络的 一 个 性质 . 利用 该性 质， 她给出了结论 1 . 1 4 的一种证明 方法 本文应用m o n m a 等人! 1 8 给出的2 一 连通 网络的一个性质， 给出了 结论1 . 1 4 的一种不同于 1 5 简洁的证明 方法. 结论 1 . 1 5 . 设 尸是平面上的一个有限点集， n是 尸的最短 2 一 连通 s t e i n e : 网 络.则 ( 1 ) n不包 含同 构于图1 . 2 t ( 1 ) 所 示网 络的子网 络， 其中。 o , u i , u 2 , u s 和。 ; 是 n的5 个不同 顶点，u o u i , u o u 2 , u z u a , u 2 u 4 e e ( n ) , p , 和p 2 分别是两条t a 点不相交的( u l , u 2 ) - 路和( u 3 , u 4 ) 一 路; ( 2 ) n不包 含同构于图1 .2中( 2 ) 所示网 络的子网 络，其中v i , v 2 , v 3 和4 j4 是n 的 4 个不同顶点， v i v a , u 2 u 4 e e ( n) , q i 和 q 2 是两条内 部顶点不相交的 ( v i , v 2 ) - 路，且 v ( q l ) i _ 3 , iv ( q 2 ) 1 4 ,则g ， 中 的任意一个圈 至少包 含4 个2 度正则点 ; ( 3 ) 理不包 含仅含正则点 的 个数大于等于3 的 满s t 。 二: 树的 边的圈 . 与 此同 时， 如 果 z i 6 , wi n t e r 和z a c h a r i a s e n 在文 献2 4 中 证明了s iv 1 n 不包含3 度顶点. 进一步 地， 如果! z i =6 ， 他们 给出了s m n包含3 度顶点的 一个例子. 1 .4 本论文的主要结果 我们现在来介绍本论文的主要研究结果. 在第二章第二节， 我们 根据已 有结论和欧几里德距离三角不等式性质， 给出 了最短2 一 连通s t e i n e r ( 或生成) 网络的进一步的一些结构性质: 结论 1 . 1 3 . 设 尸是平面上的一个有限点集，n是尸的最短 2 一 连通 s t e i n e r 网 络.则 ( 1 ) 尸中 位于其凸包 的边界上的.屯 都位于n的外圈 上; ( 2 ) s t e i n e r 点必位于尸的凸包的 边界的内 部. 结论 1 . 1 4 . 设 尸是平面上的一个有限点集，n是 尸的最短 2 一 连通 s t e i n e r 网 络则n 中的任意两条边都不会相交于正则点与 s t e r n e r 点以外的其他点. 李 美丽在她的 硕士论文【 巧 中 证明 了2 一 连通网 络的 一 个 性质 . 利用 该性 质， 她给出了结论 1 . 1 4 的一种证明 方法 本文应用m o n m a 等人! 1 8 给出的2 一