寻找独立路径问题的一个关键顶点和一条关键弧-论文.pdf

《寻找独立路径问题的一个关键顶点和一条关键弧-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第3期应用数学学报Vo1．37No．32014年5月ACTAMATHEMATICAEAPPLICATAESINICAMay，2014寻找独立路径问题的一个关键顶点和一条关键弧孙智帅(国防科技大学理学院数学与系统科学系，长沙410073)(E—m~il：sunzhishuai@gmail．COiTI)谢政(国防科技大学理学院数学与系统科学系，长沙410073)摘要通信网络中不同的顶点和弧在多径路由中的作用具有差异陛，为此，提出了独立路径问题的关键顶点和关键弧问题．若由定义来求关键顶点和关键弧，算法效率太低．对于弧独立路径数问题，文中引入关键度的概念来量化每个顶点和每条

2、弧的关键程度，发现并证明了顶点的关键度与出度的关系，并由此设计了求关键顶点的算法．根据独立路径数问题本身的特点，提出了求弧独立路径数问题关键弧及顶点独立路径数问题关键顶点和关键弧的方法．对于K一弧独立路径问题，文中利用网络流理论构造替代路径来寻找关键顶点和关键弧．通过变换网络结构，用相似的方法求K一顶点独立路径问题的关键顶点和关键弧．关键词独立路径；关键顶点；关键弧MR(2000)主题分类05c38中图分类02251引言关键顶点是这样的顶点，在网络中删除该顶点时，网络最优解的目标值变化最大；关建弧是这样的弧，在网络中删除该弧时，网络最优解的目标值变化最大[1J_关键顶点和关

3、键弧的研究始于上世纪七八十年代[2-4]，由于在网络攻击和网络安全方面有重要应用，该问题逐渐成为网络优化问题的研究热点，吸引了大批学者，并取得了一系列成果．但是，这些成果主要集中于寻找最短路问题，最短路树问题及最小支撑树问题的关键顶点和关键弧[5-sl，对独立路径问题_gJ的关键顶点和关键弧的研究还比本文2012年1O月28日收到．2013年12月24日收到修改稿国防预研(513210704)资助项目．3期孙智帅，谢政：寻找独立路径问题的一个关键顶点和一条关键弧517较少．独立路径问题主要包括两个方面：求网络中最多同时存在多少条相互独立的路径L1o]；求权值和最小的K(K>

4、1，为整数)条独立路径．考虑独立路径问题的关键顶点和关键弧对网络通信有非常重要的意义．如果根据关键顶点和关键弧的定义来计算，计算量大，算法效率低，本文的主旨即设计效率比较高的求取独立路径问题的一个关键顶点和一条关键弧的算法．为叙述简便，不妨称求网络中最多同时存在多少条相互独立的路径的问题为独立路径数问题；称求权值和最小的(K>1，为整数)条独立路径的问题为一独立路径问题．独立路径数问题包含弧独立路径数问题和顶点独立路径数问题，一独立路径问题包含一弧独立路径问题和一顶点独立路径问题．对于这四类问题，我们在『10]中已经给出了相应的算法．在本文中，我们需要分别找出弧独立路径数问

5、题的一个关键顶点和一条关键弧，顶点独立路径数问题的一个关键顶点和一条关键弧，一弧独立路径问题的一个关键顶点和一条关键弧以及一顶点独立路径问题的一个关键顶点和一条关键弧．文章的其余部分是按以下组织的，第2部分，我们给出了一些定义和符号．第3部分讨论了怎样求弧独立路径数问题的关键顶点和关键弧以及顶点独立路径数问题的关键顶点和关键弧．第4部分，我们考虑了一弧独立路径问题的关键顶点和关键弧以及一顶点独立路径问题的关键顶点和关键弧．在第5部分，我们给出了一个算例．最后，我们对全文进行了总结．2定义与符号设D：(A，W)是一个带发点和收点V的赋权网络．其中，是顶点集，是弧集，W是定义在

6、弧上的非负权，或为时间，或为费用，任意(Vi，vj)∈A上的权值为W顶点个数和弧数分别为凡和m．除发点和收点之外的顶点，统称为中间顶点．D中去掉某个顶点之后的网络记为DD中去掉某条弧(V，”j)之后的网络记为DJ^1．定义某个顶点或弧删除前和删除后网络最优解目标值的改变量(由大减小，保证恒取非负值)为该顶点或弧的关键度，用g表示，顶点仇的关键度表示为gv，弧(V，vy)的关键度表示为Ig)．求关键顶点和关键弧即求关键度最大的顶点和弧．我们用Ⅳ，，Ⅳ(vivj)分别表示D，DD(Vi~Vj)的弧独立路径数，用Ⅳ，，)分别表示D，DD(Vi~Vj)的顶点独立路径数，用，，Vi~

7、Vj)分别表示D，DD(Vi~Vj)中权值和最小的K条弧独立路径的权值和，用，，1表示D，DD(，1中权值和最小的条顶点独立路径的权值和．在以下的讨论中，我们假定D不含负回路。3独立路径数问题的关键顶点和关键弧先考虑弧独立路径数问题的关键顶点．对于某个固定的网络，弧独立路径数Ⅳ是唯一的，但对应的Ⅳ条弧独立路径不一518应用数学学报37卷定是唯一的，将每组Ⅳ条弧独立路径生成的子网络称为一种路由方案．我们有下面的定理．定理1顶点的关键度g等于Vt在所有路由方案中的最小出度．证在各个路由方案中，与Vt相关的路径的数目等于