三阶限制边连通度的优化问题的任务书.docx

该【三阶限制边连通度的优化问题的任务书 】是由【niuww】上传分享，文档一共【3】页，该文档可以免费在线阅读，需要了解更多关于【三阶限制边连通度的优化问题的任务书 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。三阶限制边连通度的优化问题的任务书任务书题目:三阶限制边连通度的优化问题一、题目背景图论是现代数学的一个基础分支,一个图(Graph)G由一些点(Vertex或Node)和它们之间的边组成。这个概念可以很自然地应用到许多现代应用中,比如社交网络、网络拓扑、交通系统等领域。在这些应用中,组成图中的点和边通常表示不同的实体或概念,并且它们之间的连通性非常重要。连通度(Connectivity)是一个图的重要衡量指标之一,它描述了图中其任意两个点之间的连通性。有许多种不同类型的连通度,其中一种非常重要的类型是k-边连通度(k-EdgeConnectivity)。它描述了删除其中任意k条边之后图的连通性是否仍然保持不变。这个性质在许多应用中非常重要,比如通讯网络、交通网络等。但是,有时候对于一些现代应用而言,单纯的k-边连通度已经不能完全描述其需要的连通性特性。比如,对于一个基站网络,由于基站的硬件特性等原因,任意两个基站之间都应当相距一定距离,而这个距离可以通过边权来表示。那么,如果一个图中任意两个点之间的距离都比一个预先设定的r值要小,则认为这两个点之间是连通的。在这种情形下,可以引入第三个衡量单元——三阶限制边连通度(3-ECC),来进一步描述图的连通性。二、任务描述本任务旨在设计算法,解决三阶限制边连通度的优化问题。给定一张有权无向图G=(V,E,w),其中V表示节点集合,E表示边集合,w:E→R+表示边权函数,即每条边的权值,且k和r是预先设定的整数。要求设计算法,得到G中一个权值和最小的子图G′,使得G′中的每个连通块的直径都不大于r,且G′的k-边连通度不小于3。三、输入输出格式输入:第一行为四个整数n、m、k、r,其中n表示节点数,m表示边数,k表示k-边连通度,r表示限制直径。接下来的m行,每行包含三个整数u、v、w,表示编号为u和v的两个节点之间有一条无向边,边权为w。输出:一行,包含两个用空格隔开的整数W和S,其中W表示满足要求的子图G′的权值和,S表示G′中的节点数。四、算法和思路本题需要结合许多图论算法和思想,比如::可以用来得到G中一个联通子图。-边连通图:可以用来得到G中k-边连通性最强的子图。:可以用来计算图中任意两点之间的距离。:可以用来对G做递归划分。下面给出一个基本的算法思路:,得到T的所有连通块。,如果C的直径不大于r,则将C保留下来。,如果C的k-边连通度小于3,则继续按照r的限制,将C递归划分成更小的子图。,以其为端点,计算图G中任意两点之间的距离,并构造以保留下来的子图节点为顶点的图H。,计算其最小k-边连通图T',并得到T'的权值和W和节点数S。。五、、边双连通分量及其算法[J].ActaMathematicaScientia,1988,8(4):349-,-timealgorithmforaspecialcaseofdisjointsetunion[J].puterandSystemSciences,1985,30(2):209-,[J].puterandSystemSciences,1991,43(3):292-,[J].ActaMathematicaAcademiaeScientiarumHungaricae,1973,23(2):217-,-timealgorithmforaspecialcaseofdisjointsetunion[J].puterandSystemSciences,1985,30(2):209-221.