| 【中文题名】 | 任意无向图的R点连通扩充 |
| 【英文题名】 | R-Vertex-Connectivity Augmentation of any Graph |
| 【学科专业】 | 电工理论与新技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-7-19 |
| 【中关键词】 | 图论,连通度,无向图,扩充,, |
| 【英关键词】 | Graph Theory,connectivity,graphs,augmentation, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 随着近代工业的发展，图论的应用已渗透于系统工程、建筑工程、通信工程、运筹学、电路网络、计算机科学及经济学、社会学、心理学等各个领域。而图论中的优化问题是近代图论领域研究的焦点问题之一。
连通扩充问题是图论中连通性理论的一个重要组成部分，也是一个组合优化问题，在电网络可靠性分析与设计等领域具有重大理论指导意义。本文研究了无向不加权连通图的R点连通扩充问题，即给定一个无向图，和一个连通要求矩阵，在中增加一个最小边集，使得中的任意两点之间的点连通度均满足。本文提出了一个复杂度为的算法RUCA，能扩充为R点连通图。在一些情况下，得到的R点连通图是最小的；而在其他一些情况下，可以保证所得到的R点连通图是极小的。算法的主要设计思想是：首先利用UTD变换将无向图转化为有向图，再把有向图经SPLIT构造把点连通扩充问题转化为边连通扩充问题。在对有向图的边连通扩充中，采用先增广扩充再检验的方法，如果不满足要求，再将其分解成一系列不可压缩子图，分别对这些子图进行扩充，最后再将扩充好的子图合并成一个总有向图，扩充后的总有向图经可行删除及SPLIT和UTD逆变换便可得到所求的无向图的R点连通扩充图。文中给出了增广... |
| 【论文题纲】 |
|
第一章 绪论 |
8-12 |
|
1.1 图论与可靠通信网研究 |
8-9 |
|
1.2 本文的工作及意义 |
9-12 |
|
第二章 不加权无向图的R点连通扩充 |
12-36 |
|
2.1 引言 |
12-16 |
|
2.2 基本定义和定理 |
16-18 |
|
2.3 连通性理论简介 |
18-21 |
|
2.3.1 Menger定理及其推论 |
19 |
|
2.3.2 Mader定理及其推论 |
19-21 |
|
2.4 点连通度的最小扩充问题 |
21 |
|
2.5 无向图R点连通扩充问题与有向图R边连通扩充问题的等效 |
21-24 |
|
2.6 增广扩充图 |
24 |
|
2.7 最小增广z-SR扩充图的判据 |
24-26 |
|
2.8 算法RDCA:有向图的最小增广z-SR扩充 |
26-29 |
|
2.8.1 增广扩充 |
26-27 |
|
2.8.2 划分 |
27 |
|
2.8.3 合并 |
27-29 |
|
2.9 可行删除 |
29-33 |
|
2.10 算法RUCA:无向图R点连通扩充 |
33-34 |
|
2.11 算法RUCA的复杂度分析 |
34-36 |
|
第三章 算法最优性证明及程序说明 |
36-41 |
|
3.1 算法RUCA的最优性证明 |
36-39 |
|
3.1.1 算法RDCA最优性证明 |
36-37 |
|
3.1.2 算法RUCA最优性分析 |
37-39 |
|
3.2 程序RUCA的说明 |
39-41 |
|
3.2.1 程序的功能与特点 |
39 |
|
3.2.2 程序结构与框图 |
39-41 |
|
第四章 例题 |
41-49 |
|
4.1 例题一 |
41-45 |
|
4.2 例题二 |
45-49 |
|
第五章 结论 |
49-51 |
|
5.1 全文总结 |
49-50 |
|
5.2 工作展望 |
50-51 |
|
参考文献 |
51-55 |
|
发表论文和科研情况说明 |
55-56 |
|
致 谢 |
56 |
|
| 【DOI】 | LunWen.ID:2.2008.11472 |
