刘滨[1]2004年在《任意无向图的R点连通扩充》文中认为随着近代工业的发展，图论的应用已渗透于系统工程、建筑工程、通信工程、运筹学、电路网络、计算机科学及经济学、社会学、心理学等各个领域。而图论中的优化问题是近代图论领域研究的焦点问题之一。连通扩充问题是图论中连通性理论的一个重要组成部分，也是一个组合优化问题，在电网络可靠性分析与设计等领域具有重大理论指导意义。本文研究了无向不加权连通图的R点连通扩充问题，即给定一个无向图，和一个连通要求矩阵，在中增加一个最小边集，使得中的任意两点之间的点连通度均满足。本文提出了一个复杂度为的算法RUCA，能扩充为R点连通图。在一些情况下，得到的R点连通图是最小的；而在其他一些情况下，可以保证所得到的R点连通图是极小的。算法的主要设计思想是：首先利用UTD变换将无向图转化为有向图，再把有向图经SPLIT构造把点连通扩充问题转化为边连通扩充问题。在对有向图的边连通扩充中，采用先增广扩充再检验的方法，如果不满足要求，再将其分解成一系列不可压缩子图，分别对这些子图进行扩充，最后再将扩充好的子图合并成一个总有向图，扩充后的总有向图经可行删除及SPLIT和UTD逆变换便可得到所求的无向图的R点连通扩充图。文中给出了增广扩充的最优准则及算法RUCA的最优性分析。通过本文所给的算法RUCA及算法复杂度估计和最优性分析，表明了不加权无向图R点连通最小扩充问题在一定条件下存在最优算法，这对彻底解决该问题具有重大的指导意义。此研究成果具有广阔的应用前景，在本文所提出的算法基础上，针对网络设计的具体问题及进行加权改造，可研制出具有自动设计可靠性网络的计算机辅助设计软件，诸如现行网络的可靠性改造问题和可靠联网或并网等实际问题都将得到比以往更加合理的架线方案，特别是对于较大规模的网络优化设计问题，其经济效益将非常显着。
孙雨耕, 刘滨, 杨郁[2]2006年在《任意无向图的R点连通扩充》文中进行了进一步梳理为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题,通过将无向图点连通问题转化为有向图边连通问题,采用增广扩充的方法,提出了一个复杂度为O(|V|5)的算法．利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度．它发展了K点连通最优扩充的研究,从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义．
参考文献：
[1]. 任意无向图的R点连通扩充[D]. 刘滨. 天津大学. 2004
[2]. 任意无向图的R点连通扩充[J]. 孙雨耕, 刘滨, 杨郁. 天津大学学报. 2006