数 学 建 模
题目： A
队号： 2014045A
2014年5月25
题目A：通信网络设计问题
摘
文研究通信网络铺设线路遇总铺设成网络结点链路性问题建模建立某通信公司建立80结点铺设线路提出优铺设方案
问题1网络设计常见成低化问题通简化问题转寻找权值生成树问题利避圈法破圈法生成树（结果见8页图2）终求省铺设费29478万元通仿真计算该方案性检验结果表明意条链路破坏时够保证通信畅通结点数低结点数5375网络链路太稳定通模拟结点出现障发现22号结点出现障够保证通信畅通结点数结点数46（结果见14页表2）见利生成树模型涉网络铺线优点成低缺点保证结点通信畅通性低
问题2根邻接矩阵计算达矩阵根达矩阵链路连通性关系结点出现障时生成树分解干组联通子树然保证90结点通信畅通条件分解图进行连接修复结点出现障时保证通信畅通90％建立01整数规划规划模型（12页）考虑整数规划模型求解复杂性设计贪婪算法中17结点出现障结点具体连接方法见（详见14页表2）结点出现障网络身保持90％需连链路表2中未进行考虑表2知贪婪算法结果保证925％结点通信畅通
问题3求意条链路破坏时保证90结点通信畅通分两种情况进行考虑果意条链路破坏90％结点保持通信畅通链路需追加链接（详15页见表3）外链路破坏保证90％结点通信畅通需追加链接加边加边时允许某结点连2条边需原生成树某结点连两条样边（复制某生成树某两结点间破坏边形成回路）该链路然总铺设费省方案果允许意结点连两条边破坏边整树分二需计算两组结点间短距离连条新短路性90情况总铺设费方案（详17页见表4）
问题四综合考虑网络性铺设费根问题2问题3结果结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型(见19页图8)该模型意结点出现障结点保持畅通性低90％（详18页见表5）考虑该模型成高需增加铺设费75075万元次移成高边（处移图8中条边71－76）成更低稳定性友模型模型(见20页图9)时需增加成5032万元意结点出现障结点保持畅通性低90％（详21页见表6）边类似结果分见表7方案合理
关键词：生成树破圈法网络模型图
问题重述
着科学技术进步计算机网络技术取快速发展成信息交流手段渗透社会方面发展断推动类社会逐渐走信息时代网络技术发展生活社会生产力提高提供巨贡献时存着许安全隐患信息漏洞出现网络OpenSSL心血漏洞等工作生活造成影响
系统性重整体指标通信网络例外通信网络性仅通信设备链路关网络结构关网络结构复杂变通信网络性分析直棘手问题
某通信公司拟建具80结点通信网络需结点间铺设线路进行数传输结合结点间距离铺设线路单位费见附件1文需具体完成问题：
问题1：通信网络总铺设费省请建立问题数学模型设计求解算法出铺设方案讨方案性
问题2：考虑通信网络结点性求意结点出现障时结点间然够保持通信畅通性达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
问题3：考虑通信网络链路性求意条链路破坏时够保持通信畅通结点够达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
问题4：综合考虑网络性铺设费试确定合理铺设方案
二模型假设
1假设结点结点间连接存先序均直线连接
2假设考虑结点
3假设考虑线路铺设费线路连通影响
4假设通信网络中结点间距离固定变数
5假设链路结点障正常两种状态
6假设网络中链路障概率统计独立
7考虑网络线路结点容量问题
三定义符号说明
：链路权值结点间距离×结点间铺设线路单位费
：结点数
：结点名
：边
：树
四问题分析
计算机网络通信现代流行尖端新颖通信技术手段现代信息技术发展极致发展现已进入智化宽带化综合化阶段发展前景广泛[1]保证网络通信安全前提网络性系统中较重整体指标网络性评估网络性相关研究基础目前网络性研究领域热点基性网络设计针网络性网络构建费等网络设计目标提供种优化方案供网络理者参考[2]
问题重述知题属网络路线优化问题网络通信时数需结点间传输需结点间铺设线路理位置距离等素 结点间架设网线费 公司想结点间网络畅通费降低 应该样设计结点间线路文关键
线路建设中仅需考虑成问题考虑方案性保证意结点链路出现障时通信畅通参考附件1结点间距离铺设线路单位费面问题进行分析：
问题1：网络设计方案中常见问题成低化结合附件1中出结点间距离铺设线路单位费链路权值问题简化寻找生成树问题棵生成树代价树边代价时颗生成树总权值题中省总铺设费条产生回路边连接网络中顶点构造生成树[3]
问题2：题1结知生成树网络连通基础考虑少总铺设费意结点线路出现障时种解决方案优解通信网络中仅需考虑铺设费问题考虑性问题问题二中求结点性90基础求解少总铺设费问题存两需考虑素：性达90时优先考虑省总铺设费二性达90情况优先考虑提高性计算少铺设费时间问题算法复杂性文前者素建立模型求解
问题3：连通性定义性定义见题2题做定义直接运题2连通性性定义运MATLAB破坏意条链路时结点间连接关系根题1知：生成生成树已网络总铺设费省方案现考虑意条链路破坏时网络性达90基础省铺设费问题
问题4：述三题解决方案知综合考虑网络性铺设费三方面着手：意结点出现障时网络性二意条链路破坏时网络性三总铺设费
五模型建立求解
51 问题1模型建立求解
511 模型建立
建模准确性面引入生成树概念般设V{ν1ν2ν3…νp}P点集合E{e1e2e3…eq}q条边集合中
νi νj ∈V
VE组成图形称图记果G0包含G 中顶点回路连通子图G0G棵生成树Gn顶点生成树n顶点n1条边图生成树中条边权值生成树生成树
根生成树定义性质结（设图G1图G生成树）
（1）G1中条边权值
（2）G1中n 顶点n1条边
（3）G1必须连通回路
连通带权图里找时满足述三条件图找该图生成树
研究方便题中通信网络简化结点结点间连线计结点文中律连线做链路生成树模型中链路权值F详见附件1结点编号
假该公司建立部分结点位置简化图1示顶点代表结点编号边代表架设网线链路样构成带权连通图 费问题转化求带权连通图生成树问题
图1 部分结点通信网络简化图
512 模型求解
常生成树算法—破圈法避圈法题采两种方法分模型求解
（1）避圈法
避圈法计算步骤：
Step1：网络中选点vi令
Step2：连接边中选取边 妨设边（vivj）该边必优化路线中条
Step3：重新修正集合组成元素集合中增加顶点显然集合中减少该顶点
Step4：果（空集）停止已找优化路线否返回第2 步
面该网络中结点简单说明通信网络避圈法求解生成树方法通信网络铺设优方案问题避圈法求解程：
① 假设结点开始
② 链接中79种情况计算较出结点结点间铺设费费连接起标记部分树边
③ 重新修正集合
④ 前回第二步时通计算发现连接156条边中结点结点间铺设费费连接起程中没重复次第二步通计算铺设费较出边连接成生成树实现通信网络总铺设费省铺设方案铺设费29478百元中生成树图图2结点间铺设费表1
（2）破圈法
破圈法相避圈法思路简单谓破圈法取圈掉圈权值边反复执行步骤直没圈止[4]通前文知已通信网络建立连通图时问题简化破圈法求解生成树问题
Step1：网络图中找圈 掉圈中长条边
Step2：检查网络图中否圈果重复第1步否停止表明已找优路线
结点数较MATLAB编程实现具体说明终输出结果避圈法样
通两种方法均网络线路铺设生成树
表1：结点间链路铺设费
序号
链接
费百元
序号
链接
费百元
序号
链接
费百元
1
1–34
154
28
40–63
558
55
33–73
230
2
26–34
545
29
63–79
300
56
51–30
279
3
34–61
273
30
35–27
320
57
30–31
43
4
61–50
532
31
27–3
160
58
31–59
231
5
50–32
132
32
3–7
348
59
59–60
1729
6
61–70
115
33
7–13
102
60
59–48
783
7
70–36
160
34
27–42
420
61
30–38
217
8
36–8
468
35
42–53
148
62
38–4
303
9
8–14
901
36
53–22
432
63
4–58
141
10
70–62
84
37
53–37
752
64
22–45
308
11
70–66
426
38
22–56
254
65
45–76
420
12
66–67
98
39
22–54
72
66
76–77
288
13
62–47
372
40
22–16
198
67
77–23
230
14
47–69
690
41
16–52
140
68
23–6
145
15
47–2
198
42
16–55
320
69
23–75
336
16
2–29
483
43
55–25
792
70
23–64
387
17
2–19
114
44
52–21
468
71
64–57
703
18
19–28
368
45
52–43
555
72
77–71
195
19
19–49
345
46
43–9
420
73
71–72
534
20
2–5
336
47
52–18
284
74
71–74
187
21
5–78
342
48
18–51
302
75
74–17
77
22
5–35
101
49
51–12
100
76
17–10
157
23
35–20
489
50
12–68
300
77
10–44
36
24
20–80
1914
51
12–46
207
78
44–15
510
25
20–24
586
52
46–65
636
79
71–11
472
26
24–39
484
53
46–33
80
27
35–40
348
54
33–41
811
52 方案性
根生成树特点网络连接特性两方面考虑方案性网络中连通性树生成法性
网络连接性说（详见题2）意结点出现障破坏题2 MATLAB程序运行破坏结点性结果知（附件2）网络性04625高性意条链路破坏时网络性05375题2 MATLAB程序运行破坏链路性结果知（附件3）高性09875
方案方法分析避圈算法空图出发逐步加边生成树似求解算法然数生成树问题求优解相部分求似优解具体应时定方便作种树算法概括理定意义破圈法图出发逐步边破圈生成树适合图工作图较时时子图工作破圈法实方便
综合两方面说方案中生成树两种算法适题计算复杂度方面需改进实际生活中网络连通种较适方案
图2 生成树图
52 问题2模型建立求解
521 模型建立
（1）连通性
A达矩阵
判断网络链路否连通引入布尔代数布尔矩阵达矩阵概念
定义1 二阶布尔代数元素元素阶矩阵中称布尔矩阵定阶布尔矩阵规定矩阵合成运算取运算
1)
2)
3)
4)
式中表示元素取运算
定义2 图中矩阵
称达矩阵
布尔矩阵定义：矩阵中元素属01矩阵题1邻接矩阵概念知图邻接矩阵达矩阵种典型布尔矩阵
定理 令
B求达矩阵新算法
①达矩阵常求法
中阶单位阵简单图邻接矩阵中
简单图
②新算法（布尔代数算达矩阵）
根定理
采逐次方法
令达矩阵少步数[5]
C达矩阵连通性
达矩阵表明图中意两结点间否少存条链结点处否回路通达矩阵判断链路间 连通性例已知邻接矩阵
述布尔矩阵求达矩阵新算法知需求步求达矩阵时进行3步达矩阵
根达矩阵知互相连通互连通连通中链路权值F详见附件1
根题意意结点出现障需查点间连通性令邻接矩阵中意结点出现障邻接矩阵中第行第列均定0时新邻接矩阵通新邻接矩阵布尔代数求达矩阵通达矩阵判断出结点连通性具体算法MATLAB实现
（2）连通性
分析问题2前考虑问题中性方便准确定义连通性：生成树中意结点者链路损坏剩余拥结点树结点数生成树总结点数衡量生成树连通性
文中生成树方法时连通性通信网络性
设点数
时意结点链路发生障碍性90
时意结点链路发生障碍性等90
例：6结点生成树中结点链接发生障碍形状变化分图3图4具体种情况：
A断结点1：1结点出现障形成2354连通结点孤立6结点时两结点间通信畅通性型
B断链路12：链路12发生障碍形成236154两连通结点性
图3
图4
出连通性基础根连通性定义性定义运MATLAB程序直接计算结点出现障时连通性通信网络链接性详细运算结果见附件2
522 模型求解
问题分析题1优解基础考虑意结点出现障问题根通信网络结点特性结点出现障该结点算性范围相连通结点连通性受破坏性降低障点外链路均已优解提高网络性需意结点破坏（网络结点连通性状态详见附件2）统计破坏结点性90结点生成树状态互连通生成树分组进行步建模面例子说明图5示
图5
破坏结点1网络性90生成树总铺设费省方案省破坏结点2性90需MATLAB编程计算出结点2破坏结点连通性根连通性分1组2组等根分组建立数学模型
（1）01整数规划
破坏结点性90通建立模型性90总铺设费少铺设方案
互连通结点分形(137)组命名阿拉伯数字123等模型中表示考虑组组间存连接连接问题定义
建立01整数规划模型
目标函数
中第组结点间链路铺设费总组组间铺设费表示第组第组间否存链路定义：
实现目标规划文中实现01整数规划编程程中排时成圈情况
中表示第组结点数
01整数规划中成圈隐含条件LINGOMATLAB软件难计算采述贪婪算法进行建模求解
（2）贪婪算法模型
意破坏结点时生成树分组编号连线均成中初始选组均结点设第组第组间短铺设费链接第组总铺设费第组结点数规定初始组结点数结点数
性90基础意结点出现障MATLAB编程详细分组情况（见附件2）选择连线均成组计算组组连线均成选择相连连线均成组令计算组性性90停止运算性90继续计算组剩余组连线均成直计算性90计算停止具体算法程：
例图64组初始组（编号1）（连线均成组）分计算三组连线均成出（编号2）组连通连线均成计算性性90停止连通组否计算组（时编号12组重新组组）两组连线均成4组连线均成性90停止连通组否继续组连通
图6
文中结点数较算法相复杂运MATLAB方法计算结果表2示
表2 结点出现障解决情况
出现障结点
出现障系统性
重新连接结点
连接系统性
成百元
未接入结点
2
07500
47连4940连66
09750
24192
229
5
07250
40连66
09750
44917
578
16
07000
71连76
09625
16766
16{2555}
18
07875
46连71
09875
12708
18
22
04625
2连1055连62
09625
24532
225456
27
05750
3连742连10
09875
13524
27
35
06250
2连10
09000
34954
35{20293480}{406379}
42
05625
2连10
09875
13316
42
45
08000
23连54
09875
24958
45
47
08125
40连66
09750
49095
4769
51
08000
46连7131连33
09875
10127
51
52
07375
46连71
09500
13312
5221{943}
53
05375
2连10
09750
13736
3753
62
08375
66连40
09875
50781
62
70
08500
40连6661连68
09500
4066
{81436}70
76
08125
23连54
09875
25266
76
77
08250
2连10
09250
4041
{623576475}77
53 问题3模型建立求解
根链路情况现分两种情况讨铺设方案中允许出现两结点间重复铺路需破坏链路铺设条链路保证性达90基础总铺设费省允许出现两结点间重复铺路需考虑组间短距离着手面两方面分讨
（1）允许结点间重复铺路
根网络连接特性发现条链路破坏生成树（代表结点数）条链路会影响生成树连通性影响性提高网络性兼顾铺设费基础链路破坏性达90情况铺设费然省（加边）需考虑链路破坏性90情况（加边）
通分析知题意条链路破坏题1生成树方案基础生成树中点间铺设费已值需性90链路间铺设条链路样保证意条链路破坏性90情况总铺设达少例图7生成树中链路12破坏性9012间铺设条链路（见红色虚线边）
图7
通MATLAB编程意条链路破坏性统计出性90链路铺设条相链路
（2）允许结点间重复铺路
题1生成树基础允许结点间重复铺路链路破坏 生成树分干组组总铺设费已省铺设方案里需保证性90考虑组组短距离题中MATLAB程序分组情况性统计性90解决方案总费少铺设方案表4示：
表3系统出现障性高90情况
破坏链路
链路破坏系统性
剩余结点
铺设费（百元）
系统性
3051
09
430313848585960
26098
09
7177
09
10111517447174
27310
09
1251
09125
12334146686573
27114
09125
6170
0925
12632346150
27727
0925
1246
09375
3341466573
27514
09375
2377
09375
623576475
27677
09375
7174
09375
1015174474
28511
09375
1774
095
10151744
28698
095
2035
095
20243980
26005
095
3031
095
31485960
26692
095
3038
09624
43858
28817
09624
219
09625
192849
28651
09625
327
09625
3713
28868
09625
1017
09625
101544
28775
09625
3159
09625
485960
26735
09625
3346
09625
334173
28357
09625
3461
09625
12634
28506
09625
3540
09625
406379
28272
09625
3670
09625
81436
27949
09625
37
0975
713
29028
0975
438
0975
458
29034
0975
836
0975
814
28109
0975
1044
0975
1544
28932
0975
1655
0975
2555
28366
0975
2024
0975
2439
28408
0975
2364
0975
5764
28388
0975
4063
0975
6379
28620
0975
4352
0975
943
28503
0975
5061
0975
3250
28814
0975
6670
0975
6667
28954
0975
134
09875
1
29324
09875
229
09875
29
28995
09875
458
09875
58
29337
09875
578
09875
78
29136
09875
623
09875
6
29333
09875
713
09875
13
29376
09875
814
09875
14
28577
09875
943
09875
9
29058
09875
1171
09875
11
29006
09875
1268
09875
68
29178
09875
1544
09875
15
28968
09875
1928
09875
28
29110
09875
1949
09875
49
29133
09875
2080
09875
80
27564
09875
2152
09875
21
29010
09875
2254
09875
54
29406
09875
2256
09875
56
29224
09875
2375
09875
75
29142
09875
2439
09875
39
28994
09875
2555
09875
25
28686
09875
2634
09875
26
28933
09875
3250
09875
32
29346
09875
3341
09875
41
28667
09875
3373
09875
73
29248
09875
3753
09875
37
28726
09875
4665
09875
65
28842
09875
4769
09875
69
28788
09875
4859
09875
48
28695
09875
5764
09875
57
28775
09875
5960
09875
60
27749
09875
6379
09875
79
29178
09875
6667
09875
67
29380
09875
7172
09875
72
28944
09875
表4 链路出现障系统性低90情况
破坏链路
链路破坏系统性
连接
铺设费（百元）
系统性
2253
05375
2连10
29516
1
4253
05625
2连10
29800
1
2742
0575
2连10
29528
1
2735
0625
2连10
29628
1
1622
07
55连62
29805
1
535
0725
40连66
29812
1
1652
07375
46连7161连68
29866
1
25
075
40连66
29577
1
1852
07875
46连7161连68
29722
1
1851
08
46连7161连68
29704
1
2245
08
23连54
29635
1
247
08125
47连49
29640
1
4576
08125
23连54
29523
1
7677
0825
23连54
29655
1
4762
08375
40连66
29541
1
6270
085
40连66
29829
1
54 问题4模型建立求解
基述问题4提出三方面建立数学模型：
意条链路破坏保证性达90题1基础需连接链路令{}中代表第条边
意结点障保证性达90题1基础需连接链路令{}
时题1中生成树中加时网络性低09875方面性高外方面增加75075百元费符合量减少铺设费原
设定合理性定义方案合理
保证性90情况减少总铺设费切断铺设成高链路7176链路切断时时意链路破坏够保证通信畅通结点少095（详见表5）增加5032百元时考虑性相较高新增线路铺设费相题1 原费相增加少方案合理 意结点障够保证通信畅通结点少09（详见表6）增加5032百元方案合理
表5 结点出现障加条边网络性
结点
网络性
结点
网络性
结点
网络性
结点
网络性
1
09875
21
09875
41
09875
61
0925
2
0975
22
0975
42
09875
62
09875
3
09625
23
09375
43
0975
63
0975
4
0975
24
0975
44
0975
64
0975
5
0975
25
09875
45
09875
65
09875
6
09875
26
09875
46
0975
66
0975
7
0975
27
09875
47
0975
67
09875
8
0975
28
09875
48
09875
68
09875
9
09875
29
09875
49
09875
69
09875
10
09625
30
095
50
0975
70
09625
11
09875
31
095
51
09875
71
09625
12
09875
32
09875
52
095
72
09875
13
09875
33
09625
53
0975
73
09875
14
09875
34
09625
54
09875
74
09875
15
09875
35
09
55
0975
75
09875
16
09875
36
09625
56
09875
76
09875
17
09875
37
09875
57
09875
77
09875
18
09875
38
09625
58
09875
78
09875
19
0975
39
09875
59
09625
79
09875
20
095
40
09625
60
09875
80
09875
图8 结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型
图9 次移成高边（处移图8中条边71－76）成更低稳定性友模型模型
表6 结点出现障网络性
障点
网络性
障点
网络性
障点
网络性
障点
网络性
1
09
21
0975
41
09875
61
09875
2
0925
22
0975
42
09875
62
09875
3
09375
23
0975
43
09875
63
09875
4
095
24
0975
44
09875
64
09875
5
095
25
0975
45
09875
65
09875
6
095
26
0975
46
09875
66
09875
7
095
27
0975
47
09875
67
09875
8
09625
28
0975
48
09875
68
09875
9
09625
29
0975
49
09875
69
09875
10
09625
30
0975
50
09875
70
09875
11
09625
31
0975
51
09875
71
09875
12
09625
32
0975
52
09875
72
09875
13
09625
33
0975
53
09875
73
09875
14
09625
34
0975
54
09875
74
09875
15
09625
35
0975
55
09875
75
09875
16
09625
36
09875
56
09875
76
09875
17
09625
37
09875
57
09875
77
09875
18
0975
38
09875
58
09875
78
09875
19
0975
39
09875
59
09875
79
09875
20
0975
40
09875
60
09875
80
09875
表7 移成长边测切断条边模型稳定性
切断条边
切断边网络性
切断条边
切断边网络性
切断条边
切断边网络性
10—17
1
23—77
1
4—58
09875
10—44
0975
24—39
09875
46—65
1
11—71
09875
2—47
1
47—49
1
12—46
1
2—5
1
47—62
1
12—51
1
25—55
09875
47—69
1
12—68
1
26—34
09875
48—59
1
1—34
09875
27—35
1
50—61
0975
15—44
09875
27—42
1
55—62
1
16—22
1
30—31
1
57—64
09875
16—52
1
30—38
09625
5—78
09875
16—52
1
30—51
1
59—60
09875
17—74
1
31—33
1
61—68
1
18—51
1
31—59
09625
61—70
1
18—52
1
32—50
09875
6—23
09875
18—52
1
3—27
1
62—70
1
19—28
09875
33—41
09875
63—79
09875
19—49
1
33—46
1
66—67
09875
20—24
0975
33—73
09875
66—70
1
20—35
095
34—61
09625
67—66
09875
20—80
09875
35—40
1
7—13
09875
2—10
1
36—46
1
71—72
09875
21—52
9875
36—70
1
71—74
1
2—19
1
3—7
0975
71—76
1
22—45
1
3—74
1
71—77
1
22—53
1
37—53
09875
7—3
0975
22—54
1
40—46
1
8—14
09875
22—56
09875
40—63
0975
8—36
1
2—29
09875
42—53
1
9—43
09875
23—64
1
43—52
0975
45—76
1
23—75
1
4—38
0975
六模型优缺点改进
优点：文中运达矩阵判断连通性通定义性01整数规划贪婪算法分析结点者链路破坏情况结点间然够保持畅通性未达90总费省方案模型题网络适应性良解均似优点
缺点：计算量较算法复杂
改进：破坏意结点链路网络性动筛选出性<90情况进行步运算
参考文献
[1] 徐星 浅议计算机网络通信技术特点发展前景[J] 线互联科技 2013 03 38
[2] 章筠 计算机网络性分析设计[D] 杭州 浙江学 2012
[3] 董跃华 李云浩 姜东 破圈法实现普里姆算法[J] 江西理工学学报 2008 29(4) 2022
[4] Lin WMTsay MT Wu SW Application of geographic information system for substain and feeder planning[J]International Journal of Electrical Power and Energy SystemIEEEMar 1996175183
[5] 杨秀文 严尚安 张洁 鹏 达矩阵新求法[J] 电子科技学学报 2000 29(6) 666668
附录
附录1：邻接矩阵计算达矩阵程序
function ykedajz(linjiejuzhenN)
linjiejuzhen表示邻接矩阵N表示迭代次数
clearclc
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
kedajuzhenlinjiejuzhen+eye(size(linjiejuzhen))
Nkedajuzheneye(size(linjiejuzhen))
N200
for i1N
Nkedajuzhen01Nkedajuzhen>0
tempNkedajuzhen>0
Nkedajuzhen Nkedajuzhen*kedajuzhen
Nkedajuzhen01Nkedajuzhen>0
ttttabs(Nkedajuzhen01temp)
ibianshui1
if sum(sum(tttt))<01breakend
NkedajuzhenNkedajuzhen
Nkedajuzhen01Nkedajuzhen01
end
yNkedajuzhen01
附录2：根达矩阵生成树分成干组走通组间走通子树（组）
function [zuidazudsjiedianzu]fenzu(kedajuzhen)
nlength(kedajuzhen)达矩阵行数结点数
index1n初始点
flagones(1n)
for i1n
temp[]
for j1n
if kedajuzhen(ij)>0&flag(j)>0
temp[tempij]flag(j)0
end
end
jiedianzu0{i}unique(temp)
end
zushu0zuidazuds0
for i1length(jiedianzu0)
if length(jiedianzu0{i})>0
zushuzushu+1
jiedianzu{zushu}jiedianzu0{i}
end
if length(jiedianzu0{i})>zuidazuds
zuidazudslength(jiedianzu0{i})
end
end
附录3：切断意条边计算网络性
clearclc
load data1mat
该文件切断条边网络性计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
for j01n
linjiejuzhenmintrM
clc
if linjiejuzhen(i0j0)>0
linjiejuzhen(i0j0)0
linjiejuzhen(j0i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇切断边dd计算系统性：＇i0j0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
end
end
附录4：破坏结点计算网络性
clearclc
load data1mat
该文件坏点网络性计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
linjiejuzhenmintrM
clc
linjiejuzhen(i0)0
linjiejuzhen(i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏dd计算系统性：＇i0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
附录5：条边截断性低90计算加边保网络性达90
clearclc
load data1mat
该文件坏点网络连接计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
fflag0
for i01length(Bianji)
linjiejuzhenmintrM
clc
linjiejuzhen(Bianji(i01)Bianji(i02))0
linjiejuzhen(Bianji(i02)Bianji(i01))0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏边dd计算系统性：＇Bianji(i01)Bianji(i02))
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
if kekaodu<09
fflag1
end
计算结算结点破坏新铺线
linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
[node1node2]find(sijfeiyong_zu)两组点间连线费结点
zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
结点i0破坏必须重结点集删i0
z0zilianjieidian[]
if fflag>0
feiyong00feiyongttt0feiyong00(Bianji(i01)Bianji(i02))
feiyong00(Bianji(i01)Bianji(i02))99999999999999
feiyong00(Bianji(i02)Bianji(i01))99999999999999
feiyong_zufeiyong00(jiedianzu{1}jiedianzu{2})zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
[node1node2]find(sijfeiyong00)zu_0zu_i两组点间连线费结点
z0zilianjieidian[node1node2]
zu_0zu_i两组点间连线费应结点
disp(＇＇)
fprintf(＇破坏边dd连接系统性：＇Bianji(i01)Bianji(i02))
100
fprintf(＇破坏边dd连接联网成：＇Bianji(i01)Bianji(i02))
clwcbdisitance+sijttt0
fprintf(＇破坏边dd重新连接结点：＇Bianji(i01)Bianji(i02))
z0zilianjieidianz0zilianjieidian
pause
end
end for 破坏结点i0
附录6：结点破坏性低90计算加边保证网络性90
clearclc
load data1mat
该文件坏点网络连接计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
fflag0
for i01n
linjiejuzhenmintrM
clc
linjiejuzhen(i0)0
linjiejuzhen(i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏dd计算系统性：＇i0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
if kekaodu<09
fflag1
end
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
计算结算结点破坏新铺线
linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
[node1node2]find(sijfeiyong_zu)两组点间连线费结点
zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
结点i0破坏必须重结点集删i0
if fflag>0
if length(jiedianzu{i0zu})0
jiedianzu(i0zu)[]
end
jiedianzujiedianzu
计算结点组均成
c[]avgc[]计算结点组均成
for i1length(jiedianzu)
if length(jiedianzu{i})0
c(i)99999999999 第i3组已铺线费
avgc(i)999999999 第i组已均结点铺线费
else
zu_ijiedianzu{i}
linjiezhen_zulinjiejuzhen(zu_izu_i)第3组邻接矩阵
feiyong_zufeiyong(zu_izu_i)第i组已单位铺线费
c(i)sum(sum(linjiezhen_zu*feiyong_zu))2 第i3组已铺线费
avgc(i)c(i)length(zu_i) 第i组已均结点铺线费
end
end
选取初始结点z0求成低结点数组10％
[tempindex0]sort(avgc)
jiedianzu00jiedianzuc00
for i1length(jiedianzu00)
if length(jiedianzu{index0(i)})>n*010
z0jiedianzu{index0(i)}已入网中结点
jiedianzu00(index0(i))[]jiedianzu00中移已入网中结点
c(index0(i))[]成c中移已入网中结点成
c0c0+c(index0(i))已入网中结点总成
break
end
riwangzuxu[riwangzuxuindex0(i)]
end
iter0
lianxian[]
while length(z0) iteriter+1
fprintf(＇第d次迭代－－－－－－－＇iter)
计算z0组组间短距离sij连接结点
s[]
z0zilianjieidian[]
重新计算jiedianzu00中
for i1length(jiedianzu00)
feiyong_zufeiyong(z0jiedianzu00{i})zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
s(i)sijzu_0zu_i两组点间连线费
[node1node2]find(sijfeiyong_zu)zu_0zu_i两组点间连线费结点
z0zilianjieidian[z0zilianjieidianz0(node1(1))jiedianzu00{i}(node2(1))]
zu_0zu_i两组点间连线费应结点
end
计算联入结点均总成
avgs[]
for i1length(jiedianzu00)
avgs(i)(s(i)+c(i))length(jiedianzu00{i})计算新连入结点均成
if abs(prod(jiedianzu00{i}i0))0
avgs(i)9999999999999
end
end
minavgsavgs(1)t01
for i1length(jiedianzu00)
if minavgs>avgs(i)
minavgsavgs(i)t0i选t0组联入z0时新连入结点均成低
end
end
z0[z0jiedianzu00{t0}]t0组合z0组
lianxian[lianxian z0zilianjieidian(t0)]
jiedianzu00(t0)[]删t0组
c0c0+c(t0)+s(t0)计算入网总成余组成重新计算c
c(t0)[]
disp(＇＇)
fprintf(＇破坏结点d连接系统性：＇i0)
kkdlength(z0)n
fprintf(＇破坏结点d连接联网成：＇i0)
clwcbc0
fprintf(＇破坏结点d重新连接结点：＇i0)
lianxianlianxian
end
pause
end
end for 破坏结点i0
附录7：问题四求解程序
clearclc
global linjiejuzhen00
load data1mat
linjiejuzhen00mintrM
kedajuzhenkedajz(linjiejuzhen00N)
[zuidazudsjiedianzu]fenzu(kedajuzhen)
linjiejuzhen_jianbian
linjiejuzhenlinjiejuzhen00
N40000设置迭代次数
nlength(mintrM)总结点数
fidfopen(＇wenti44txt＇＇w＇)
for i01n
for j01n
linjiejuzhenlinjiejuzhen00
clc
if linjiejuzhen(i0j0)>0
linjiejuzhen(i0j0)0
linjiejuzhen(j0i0)0
fprintf(fid＇＼n＇)
fprintf(fid＇切断边dd计算系统性：＼n＇i0j0)
fprintf(＇切断边dd计算系统性：＇i0j0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
fprintf(fid＇网络度：d＼n＇kekaodu)
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
end
end
fclose(fid)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
数 学 建 模
题目： A
队号： 2014045A
2014年5月25
题目A：通信网络设计问题
摘
文研究通信网络铺设线路遇总铺设成网络结点链路性问题建模建立某通信公司建立80结点铺设线路提出优铺设方案
问题1网络设计常见成低化问题通简化问题转寻找权值生成树问题利避圈法破圈法生成树（结果见8页图2）终求省铺设费29478万元通仿真计算该方案性检验结果表明意条链路破坏时够保证通信畅通结点数低结点数5375网络链路太稳定通模拟结点出现障发现22号结点出现障够保证通信畅通结点数结点数46（结果见14页表2）见利生成树模型涉网络铺线优点成低缺点保证结点通信畅通性低
问题2根邻接矩阵计算达矩阵根达矩阵链路连通性关系结点出现障时生成树分解干组联通子树然保证90结点通信畅通条件分解图进行连接修复结点出现障时保证通信畅通90％建立01整数规划规划模型（12页）考虑整数规划模型求解复杂性设计贪婪算法中17结点出现障结点具体连接方法见（详见14页表2）结点出现障网络身保持90％需连链路表2中未进行考虑表2知贪婪算法结果保证925％结点通信畅通
问题3求意条链路破坏时保证90结点通信畅通分两种情况进行考虑果意条链路破坏90％结点保持通信畅通链路需追加链接（详15页见表3）外链路破坏保证90％结点通信畅通需追加链接加边加边时允许某结点连2条边需原生成树某结点连两条样边（复制某生成树某两结点间破坏边形成回路）该链路然总铺设费省方案果允许意结点连两条边破坏边整树分二需计算两组结点间短距离连条新短路性90情况总铺设费方案（详17页见表4）
问题四综合考虑网络性铺设费根问题2问题3结果结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型(见19页图8)该模型意结点出现障结点保持畅通性低90％（详18页见表5）考虑该模型成高需增加铺设费75075万元次移成高边（处移图8中条边71－76）成更低稳定性友模型模型(见20页图9)时需增加成5032万元意结点出现障结点保持畅通性低90％（详21页见表6）边类似结果分见表7方案合理
关键词：生成树破圈法网络模型图
问题重述
着科学技术进步计算机网络技术取快速发展成信息交流手段渗透社会方面发展断推动类社会逐渐走信息时代网络技术发展生活社会生产力提高提供巨贡献时存着许安全隐患信息漏洞出现网络OpenSSL心血漏洞等工作生活造成影响
系统性重整体指标通信网络例外通信网络性仅通信设备链路关网络结构关网络结构复杂变通信网络性分析直棘手问题
某通信公司拟建具80结点通信网络需结点间铺设线路进行数传输结合结点间距离铺设线路单位费见附件1文需具体完成问题：
问题1：通信网络总铺设费省请建立问题数学模型设计求解算法出铺设方案讨方案性
问题2：考虑通信网络结点性求意结点出现障时结点间然够保持通信畅通性达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
问题3：考虑通信网络链路性求意条链路破坏时够保持通信畅通结点够达90请建立问题数学模型设计求解算法出总铺设费少铺设方案
问题4：综合考虑网络性铺设费试确定合理铺设方案
二模型假设
1假设结点结点间连接存先序均直线连接
2假设考虑结点
3假设考虑线路铺设费线路连通影响
4假设通信网络中结点间距离固定变数
5假设链路结点障正常两种状态
6假设网络中链路障概率统计独立
7考虑网络线路结点容量问题
三定义符号说明
：链路权值结点间距离×结点间铺设线路单位费
：结点数
：结点名
：边
：树
四问题分析
计算机网络通信现代流行尖端新颖通信技术手段现代信息技术发展极致发展现已进入智化宽带化综合化阶段发展前景广泛[1]保证网络通信安全前提网络性系统中较重整体指标网络性评估网络性相关研究基础目前网络性研究领域热点基性网络设计针网络性网络构建费等网络设计目标提供种优化方案供网络理者参考[2]
问题重述知题属网络路线优化问题网络通信时数需结点间传输需结点间铺设线路理位置距离等素 结点间架设网线费 公司想结点间网络畅通费降低 应该样设计结点间线路文关键
线路建设中仅需考虑成问题考虑方案性保证意结点链路出现障时通信畅通参考附件1结点间距离铺设线路单位费面问题进行分析：
问题1：网络设计方案中常见问题成低化结合附件1中出结点间距离铺设线路单位费链路权值问题简化寻找生成树问题棵生成树代价树边代价时颗生成树总权值题中省总铺设费条产生回路边连接网络中顶点构造生成树[3]
问题2：题1结知生成树网络连通基础考虑少总铺设费意结点线路出现障时种解决方案优解通信网络中仅需考虑铺设费问题考虑性问题问题二中求结点性90基础求解少总铺设费问题存两需考虑素：性达90时优先考虑省总铺设费二性达90情况优先考虑提高性计算少铺设费时间问题算法复杂性文前者素建立模型求解
问题3：连通性定义性定义见题2题做定义直接运题2连通性性定义运MATLAB破坏意条链路时结点间连接关系根题1知：生成生成树已网络总铺设费省方案现考虑意条链路破坏时网络性达90基础省铺设费问题
问题4：述三题解决方案知综合考虑网络性铺设费三方面着手：意结点出现障时网络性二意条链路破坏时网络性三总铺设费
五模型建立求解
51 问题1模型建立求解
511 模型建立
建模准确性面引入生成树概念般设V{ν1ν2ν3…νp}P点集合E{e1e2e3…eq}q条边集合中
νi νj ∈V
VE组成图形称图记果G0包含G 中顶点回路连通子图G0G棵生成树Gn顶点生成树n顶点n1条边图生成树中条边权值生成树生成树
根生成树定义性质结（设图G1图G生成树）
（1）G1中条边权值
（2）G1中n 顶点n1条边
（3）G1必须连通回路
连通带权图里找时满足述三条件图找该图生成树
研究方便题中通信网络简化结点结点间连线计结点文中律连线做链路生成树模型中链路权值F详见附件1结点编号
假该公司建立部分结点位置简化图1示顶点代表结点编号边代表架设网线链路样构成带权连通图 费问题转化求带权连通图生成树问题
图1 部分结点通信网络简化图
512 模型求解
常生成树算法—破圈法避圈法题采两种方法分模型求解
（1）避圈法
避圈法计算步骤：
Step1：网络中选点vi令
Step2：连接边中选取边 妨设边（vivj）该边必优化路线中条
Step3：重新修正集合组成元素集合中增加顶点显然集合中减少该顶点
Step4：果（空集）停止已找优化路线否返回第2 步
面该网络中结点简单说明通信网络避圈法求解生成树方法通信网络铺设优方案问题避圈法求解程：
① 假设结点开始
② 链接中79种情况计算较出结点结点间铺设费费连接起标记部分树边
③ 重新修正集合
④ 前回第二步时通计算发现连接156条边中结点结点间铺设费费连接起程中没重复次第二步通计算铺设费较出边连接成生成树实现通信网络总铺设费省铺设方案铺设费29478百元中生成树图图2结点间铺设费表1
（2）破圈法
破圈法相避圈法思路简单谓破圈法取圈掉圈权值边反复执行步骤直没圈止[4]通前文知已通信网络建立连通图时问题简化破圈法求解生成树问题
Step1：网络图中找圈 掉圈中长条边
Step2：检查网络图中否圈果重复第1步否停止表明已找优路线
结点数较MATLAB编程实现具体说明终输出结果避圈法样
通两种方法均网络线路铺设生成树
表1：结点间链路铺设费
序号
链接
费百元
序号
链接
费百元
序号
链接
费百元
1
1–34
154
28
40–63
558
55
33–73
230
2
26–34
545
29
63–79
300
56
51–30
279
3
34–61
273
30
35–27
320
57
30–31
43
4
61–50
532
31
27–3
160
58
31–59
231
5
50–32
132
32
3–7
348
59
59–60
1729
6
61–70
115
33
7–13
102
60
59–48
783
7
70–36
160
34
27–42
420
61
30–38
217
8
36–8
468
35
42–53
148
62
38–4
303
9
8–14
901
36
53–22
432
63
4–58
141
10
70–62
84
37
53–37
752
64
22–45
308
11
70–66
426
38
22–56
254
65
45–76
420
12
66–67
98
39
22–54
72
66
76–77
288
13
62–47
372
40
22–16
198
67
77–23
230
14
47–69
690
41
16–52
140
68
23–6
145
15
47–2
198
42
16–55
320
69
23–75
336
16
2–29
483
43
55–25
792
70
23–64
387
17
2–19
114
44
52–21
468
71
64–57
703
18
19–28
368
45
52–43
555
72
77–71
195
19
19–49
345
46
43–9
420
73
71–72
534
20
2–5
336
47
52–18
284
74
71–74
187
21
5–78
342
48
18–51
302
75
74–17
77
22
5–35
101
49
51–12
100
76
17–10
157
23
35–20
489
50
12–68
300
77
10–44
36
24
20–80
1914
51
12–46
207
78
44–15
510
25
20–24
586
52
46–65
636
79
71–11
472
26
24–39
484
53
46–33
80
27
35–40
348
54
33–41
811
52 方案性
根生成树特点网络连接特性两方面考虑方案性网络中连通性树生成法性
网络连接性说（详见题2）意结点出现障破坏题2 MATLAB程序运行破坏结点性结果知（附件2）网络性04625高性意条链路破坏时网络性05375题2 MATLAB程序运行破坏链路性结果知（附件3）高性09875
方案方法分析避圈算法空图出发逐步加边生成树似求解算法然数生成树问题求优解相部分求似优解具体应时定方便作种树算法概括理定意义破圈法图出发逐步边破圈生成树适合图工作图较时时子图工作破圈法实方便
综合两方面说方案中生成树两种算法适题计算复杂度方面需改进实际生活中网络连通种较适方案
图2 生成树图
52 问题2模型建立求解
521 模型建立
（1）连通性
A达矩阵
判断网络链路否连通引入布尔代数布尔矩阵达矩阵概念
定义1 二阶布尔代数元素元素阶矩阵中称布尔矩阵定阶布尔矩阵规定矩阵合成运算取运算
1)
2)
3)
4)
式中表示元素取运算
定义2 图中矩阵
称达矩阵
布尔矩阵定义：矩阵中元素属01矩阵题1邻接矩阵概念知图邻接矩阵达矩阵种典型布尔矩阵
定理 令
B求达矩阵新算法
①达矩阵常求法
中阶单位阵简单图邻接矩阵中
简单图
②新算法（布尔代数算达矩阵）
根定理
采逐次方法
令达矩阵少步数[5]
C达矩阵连通性
达矩阵表明图中意两结点间否少存条链结点处否回路通达矩阵判断链路间 连通性例已知邻接矩阵
述布尔矩阵求达矩阵新算法知需求步求达矩阵时进行3步达矩阵
根达矩阵知互相连通互连通连通中链路权值F详见附件1
根题意意结点出现障需查点间连通性令邻接矩阵中意结点出现障邻接矩阵中第行第列均定0时新邻接矩阵通新邻接矩阵布尔代数求达矩阵通达矩阵判断出结点连通性具体算法MATLAB实现
（2）连通性
分析问题2前考虑问题中性方便准确定义连通性：生成树中意结点者链路损坏剩余拥结点树结点数生成树总结点数衡量生成树连通性
文中生成树方法时连通性通信网络性
设点数
时意结点链路发生障碍性90
时意结点链路发生障碍性等90
例：6结点生成树中结点链接发生障碍形状变化分图3图4具体种情况：
A断结点1：1结点出现障形成2354连通结点孤立6结点时两结点间通信畅通性型
B断链路12：链路12发生障碍形成236154两连通结点性
图3
图4
出连通性基础根连通性定义性定义运MATLAB程序直接计算结点出现障时连通性通信网络链接性详细运算结果见附件2
522 模型求解
问题分析题1优解基础考虑意结点出现障问题根通信网络结点特性结点出现障该结点算性范围相连通结点连通性受破坏性降低障点外链路均已优解提高网络性需意结点破坏（网络结点连通性状态详见附件2）统计破坏结点性90结点生成树状态互连通生成树分组进行步建模面例子说明图5示
图5
破坏结点1网络性90生成树总铺设费省方案省破坏结点2性90需MATLAB编程计算出结点2破坏结点连通性根连通性分1组2组等根分组建立数学模型
（1）01整数规划
破坏结点性90通建立模型性90总铺设费少铺设方案
互连通结点分形(137)组命名阿拉伯数字123等模型中表示考虑组组间存连接连接问题定义
建立01整数规划模型
目标函数
中第组结点间链路铺设费总组组间铺设费表示第组第组间否存链路定义：
实现目标规划文中实现01整数规划编程程中排时成圈情况
中表示第组结点数
01整数规划中成圈隐含条件LINGOMATLAB软件难计算采述贪婪算法进行建模求解
（2）贪婪算法模型
意破坏结点时生成树分组编号连线均成中初始选组均结点设第组第组间短铺设费链接第组总铺设费第组结点数规定初始组结点数结点数
性90基础意结点出现障MATLAB编程详细分组情况（见附件2）选择连线均成组计算组组连线均成选择相连连线均成组令计算组性性90停止运算性90继续计算组剩余组连线均成直计算性90计算停止具体算法程：
例图64组初始组（编号1）（连线均成组）分计算三组连线均成出（编号2）组连通连线均成计算性性90停止连通组否计算组（时编号12组重新组组）两组连线均成4组连线均成性90停止连通组否继续组连通
图6
文中结点数较算法相复杂运MATLAB方法计算结果表2示
表2 结点出现障解决情况
出现障结点
出现障系统性
重新连接结点
连接系统性
成百元
未接入结点
2
07500
47连4940连66
09750
24192
229
5
07250
40连66
09750
44917
578
16
07000
71连76
09625
16766
16{2555}
18
07875
46连71
09875
12708
18
22
04625
2连1055连62
09625
24532
225456
27
05750
3连742连10
09875
13524
27
35
06250
2连10
09000
34954
35{20293480}{406379}
42
05625
2连10
09875
13316
42
45
08000
23连54
09875
24958
45
47
08125
40连66
09750
49095
4769
51
08000
46连7131连33
09875
10127
51
52
07375
46连71
09500
13312
5221{943}
53
05375
2连10
09750
13736
3753
62
08375
66连40
09875
50781
62
70
08500
40连6661连68
09500
4066
{81436}70
76
08125
23连54
09875
25266
76
77
08250
2连10
09250
4041
{623576475}77
53 问题3模型建立求解
根链路情况现分两种情况讨铺设方案中允许出现两结点间重复铺路需破坏链路铺设条链路保证性达90基础总铺设费省允许出现两结点间重复铺路需考虑组间短距离着手面两方面分讨
（1）允许结点间重复铺路
根网络连接特性发现条链路破坏生成树（代表结点数）条链路会影响生成树连通性影响性提高网络性兼顾铺设费基础链路破坏性达90情况铺设费然省（加边）需考虑链路破坏性90情况（加边）
通分析知题意条链路破坏题1生成树方案基础生成树中点间铺设费已值需性90链路间铺设条链路样保证意条链路破坏性90情况总铺设达少例图7生成树中链路12破坏性9012间铺设条链路（见红色虚线边）
图7
通MATLAB编程意条链路破坏性统计出性90链路铺设条相链路
（2）允许结点间重复铺路
题1生成树基础允许结点间重复铺路链路破坏 生成树分干组组总铺设费已省铺设方案里需保证性90考虑组组短距离题中MATLAB程序分组情况性统计性90解决方案总费少铺设方案表4示：
表3系统出现障性高90情况
破坏链路
链路破坏系统性
剩余结点
铺设费（百元）
系统性
3051
09
430313848585960
26098
09
7177
09
10111517447174
27310
09
1251
09125
12334146686573
27114
09125
6170
0925
12632346150
27727
0925
1246
09375
3341466573
27514
09375
2377
09375
623576475
27677
09375
7174
09375
1015174474
28511
09375
1774
095
10151744
28698
095
2035
095
20243980
26005
095
3031
095
31485960
26692
095
3038
09624
43858
28817
09624
219
09625
192849
28651
09625
327
09625
3713
28868
09625
1017
09625
101544
28775
09625
3159
09625
485960
26735
09625
3346
09625
334173
28357
09625
3461
09625
12634
28506
09625
3540
09625
406379
28272
09625
3670
09625
81436
27949
09625
37
0975
713
29028
0975
438
0975
458
29034
0975
836
0975
814
28109
0975
1044
0975
1544
28932
0975
1655
0975
2555
28366
0975
2024
0975
2439
28408
0975
2364
0975
5764
28388
0975
4063
0975
6379
28620
0975
4352
0975
943
28503
0975
5061
0975
3250
28814
0975
6670
0975
6667
28954
0975
134
09875
1
29324
09875
229
09875
29
28995
09875
458
09875
58
29337
09875
578
09875
78
29136
09875
623
09875
6
29333
09875
713
09875
13
29376
09875
814
09875
14
28577
09875
943
09875
9
29058
09875
1171
09875
11
29006
09875
1268
09875
68
29178
09875
1544
09875
15
28968
09875
1928
09875
28
29110
09875
1949
09875
49
29133
09875
2080
09875
80
27564
09875
2152
09875
21
29010
09875
2254
09875
54
29406
09875
2256
09875
56
29224
09875
2375
09875
75
29142
09875
2439
09875
39
28994
09875
2555
09875
25
28686
09875
2634
09875
26
28933
09875
3250
09875
32
29346
09875
3341
09875
41
28667
09875
3373
09875
73
29248
09875
3753
09875
37
28726
09875
4665
09875
65
28842
09875
4769
09875
69
28788
09875
4859
09875
48
28695
09875
5764
09875
57
28775
09875
5960
09875
60
27749
09875
6379
09875
79
29178
09875
6667
09875
67
29380
09875
7172
09875
72
28944
09875
表4 链路出现障系统性低90情况
破坏链路
链路破坏系统性
连接
铺设费（百元）
系统性
2253
05375
2连10
29516
1
4253
05625
2连10
29800
1
2742
0575
2连10
29528
1
2735
0625
2连10
29628
1
1622
07
55连62
29805
1
535
0725
40连66
29812
1
1652
07375
46连7161连68
29866
1
25
075
40连66
29577
1
1852
07875
46连7161连68
29722
1
1851
08
46连7161连68
29704
1
2245
08
23连54
29635
1
247
08125
47连49
29640
1
4576
08125
23连54
29523
1
7677
0825
23连54
29655
1
4762
08375
40连66
29541
1
6270
085
40连66
29829
1
54 问题4模型建立求解
基述问题4提出三方面建立数学模型：
意条链路破坏保证性达90题1基础需连接链路令{}中代表第条边
意结点障保证性达90题1基础需连接链路令{}
时题1中生成树中加时网络性低09875方面性高外方面增加75075百元费符合量减少铺设费原
设定合理性定义方案合理
保证性90情况减少总铺设费切断铺设成高链路7176链路切断时时意链路破坏够保证通信畅通结点少095（详见表5）增加5032百元时考虑性相较高新增线路铺设费相题1 原费相增加少方案合理 意结点障够保证通信畅通结点少09（详见表6）增加5032百元方案合理
表5 结点出现障加条边网络性
结点
网络性
结点
网络性
结点
网络性
结点
网络性
1
09875
21
09875
41
09875
61
0925
2
0975
22
0975
42
09875
62
09875
3
09625
23
09375
43
0975
63
0975
4
0975
24
0975
44
0975
64
0975
5
0975
25
09875
45
09875
65
09875
6
09875
26
09875
46
0975
66
0975
7
0975
27
09875
47
0975
67
09875
8
0975
28
09875
48
09875
68
09875
9
09875
29
09875
49
09875
69
09875
10
09625
30
095
50
0975
70
09625
11
09875
31
095
51
09875
71
09625
12
09875
32
09875
52
095
72
09875
13
09875
33
09625
53
0975
73
09875
14
09875
34
09625
54
09875
74
09875
15
09875
35
09
55
0975
75
09875
16
09875
36
09625
56
09875
76
09875
17
09875
37
09875
57
09875
77
09875
18
09875
38
09625
58
09875
78
09875
19
0975
39
09875
59
09625
79
09875
20
095
40
09625
60
09875
80
09875
图8 结点出现障需加边链路破坏需加边全部加问题1 生成树性相高铺线模型
图9 次移成高边（处移图8中条边71－76）成更低稳定性友模型模型
表6 结点出现障网络性
障点
网络性
障点
网络性
障点
网络性
障点
网络性
1
09
21
0975
41
09875
61
09875
2
0925
22
0975
42
09875
62
09875
3
09375
23
0975
43
09875
63
09875
4
095
24
0975
44
09875
64
09875
5
095
25
0975
45
09875
65
09875
6
095
26
0975
46
09875
66
09875
7
095
27
0975
47
09875
67
09875
8
09625
28
0975
48
09875
68
09875
9
09625
29
0975
49
09875
69
09875
10
09625
30
0975
50
09875
70
09875
11
09625
31
0975
51
09875
71
09875
12
09625
32
0975
52
09875
72
09875
13
09625
33
0975
53
09875
73
09875
14
09625
34
0975
54
09875
74
09875
15
09625
35
0975
55
09875
75
09875
16
09625
36
09875
56
09875
76
09875
17
09625
37
09875
57
09875
77
09875
18
0975
38
09875
58
09875
78
09875
19
0975
39
09875
59
09875
79
09875
20
0975
40
09875
60
09875
80
09875
表7 移成长边测切断条边模型稳定性
切断条边
切断边网络性
切断条边
切断边网络性
切断条边
切断边网络性
10—17
1
23—77
1
4—58
09875
10—44
0975
24—39
09875
46—65
1
11—71
09875
2—47
1
47—49
1
12—46
1
2—5
1
47—62
1
12—51
1
25—55
09875
47—69
1
12—68
1
26—34
09875
48—59
1
1—34
09875
27—35
1
50—61
0975
15—44
09875
27—42
1
55—62
1
16—22
1
30—31
1
57—64
09875
16—52
1
30—38
09625
5—78
09875
16—52
1
30—51
1
59—60
09875
17—74
1
31—33
1
61—68
1
18—51
1
31—59
09625
61—70
1
18—52
1
32—50
09875
6—23
09875
18—52
1
3—27
1
62—70
1
19—28
09875
33—41
09875
63—79
09875
19—49
1
33—46
1
66—67
09875
20—24
0975
33—73
09875
66—70
1
20—35
095
34—61
09625
67—66
09875
20—80
09875
35—40
1
7—13
09875
2—10
1
36—46
1
71—72
09875
21—52
9875
36—70
1
71—74
1
2—19
1
3—7
0975
71—76
1
22—45
1
3—74
1
71—77
1
22—53
1
37—53
09875
7—3
0975
22—54
1
40—46
1
8—14
09875
22—56
09875
40—63
0975
8—36
1
2—29
09875
42—53
1
9—43
09875
23—64
1
43—52
0975
45—76
1
23—75
1
4—38
0975
六模型优缺点改进
优点：文中运达矩阵判断连通性通定义性01整数规划贪婪算法分析结点者链路破坏情况结点间然够保持畅通性未达90总费省方案模型题网络适应性良解均似优点
缺点：计算量较算法复杂
改进：破坏意结点链路网络性动筛选出性<90情况进行步运算
参考文献
[1] 徐星 浅议计算机网络通信技术特点发展前景[J] 线互联科技 2013 03 38
[2] 章筠 计算机网络性分析设计[D] 杭州 浙江学 2012
[3] 董跃华 李云浩 姜东 破圈法实现普里姆算法[J] 江西理工学学报 2008 29(4) 2022
[4] Lin WMTsay MT Wu SW Application of geographic information system for substain and feeder planning[J]International Journal of Electrical Power and Energy SystemIEEEMar 1996175183
[5] 杨秀文 严尚安 张洁 鹏 达矩阵新求法[J] 电子科技学学报 2000 29(6) 666668
附录
附录1：邻接矩阵计算达矩阵程序
function ykedajz(linjiejuzhenN)
linjiejuzhen表示邻接矩阵N表示迭代次数
clearclc
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
kedajuzhenlinjiejuzhen+eye(size(linjiejuzhen))
Nkedajuzheneye(size(linjiejuzhen))
N200
for i1N
Nkedajuzhen01Nkedajuzhen>0
tempNkedajuzhen>0
Nkedajuzhen Nkedajuzhen*kedajuzhen
Nkedajuzhen01Nkedajuzhen>0
ttttabs(Nkedajuzhen01temp)
ibianshui1
if sum(sum(tttt))<01breakend
NkedajuzhenNkedajuzhen
Nkedajuzhen01Nkedajuzhen01
end
yNkedajuzhen01
附录2：根达矩阵生成树分成干组走通组间走通子树（组）
function [zuidazudsjiedianzu]fenzu(kedajuzhen)
nlength(kedajuzhen)达矩阵行数结点数
index1n初始点
flagones(1n)
for i1n
temp[]
for j1n
if kedajuzhen(ij)>0&flag(j)>0
temp[tempij]flag(j)0
end
end
jiedianzu0{i}unique(temp)
end
zushu0zuidazuds0
for i1length(jiedianzu0)
if length(jiedianzu0{i})>0
zushuzushu+1
jiedianzu{zushu}jiedianzu0{i}
end
if length(jiedianzu0{i})>zuidazuds
zuidazudslength(jiedianzu0{i})
end
end
附录3：切断意条边计算网络性
clearclc
load data1mat
该文件切断条边网络性计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
for j01n
linjiejuzhenmintrM
clc
if linjiejuzhen(i0j0)>0
linjiejuzhen(i0j0)0
linjiejuzhen(j0i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇切断边dd计算系统性：＇i0j0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
end
end
附录4：破坏结点计算网络性
clearclc
load data1mat
该文件坏点网络性计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
linjiejuzhenmintrM
clc
linjiejuzhen(i0)0
linjiejuzhen(i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏dd计算系统性：＇i0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
附录5：条边截断性低90计算加边保网络性达90
clearclc
load data1mat
该文件坏点网络连接计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
fflag0
for i01length(Bianji)
linjiejuzhenmintrM
clc
linjiejuzhen(Bianji(i01)Bianji(i02))0
linjiejuzhen(Bianji(i02)Bianji(i01))0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏边dd计算系统性：＇Bianji(i01)Bianji(i02))
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
if kekaodu<09
fflag1
end
计算结算结点破坏新铺线
linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
[node1node2]find(sijfeiyong_zu)两组点间连线费结点
zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
结点i0破坏必须重结点集删i0
z0zilianjieidian[]
if fflag>0
feiyong00feiyongttt0feiyong00(Bianji(i01)Bianji(i02))
feiyong00(Bianji(i01)Bianji(i02))99999999999999
feiyong00(Bianji(i02)Bianji(i01))99999999999999
feiyong_zufeiyong00(jiedianzu{1}jiedianzu{2})zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
[node1node2]find(sijfeiyong00)zu_0zu_i两组点间连线费结点
z0zilianjieidian[node1node2]
zu_0zu_i两组点间连线费应结点
disp(＇＇)
fprintf(＇破坏边dd连接系统性：＇Bianji(i01)Bianji(i02))
100
fprintf(＇破坏边dd连接联网成：＇Bianji(i01)Bianji(i02))
clwcbdisitance+sijttt0
fprintf(＇破坏边dd重新连接结点：＇Bianji(i01)Bianji(i02))
z0zilianjieidianz0zilianjieidian
pause
end
end for 破坏结点i0
附录6：结点破坏性低90计算加边保证网络性90
clearclc
load data1mat
该文件坏点网络连接计算程序
linjiejuzhen[0 1 0 0 1 11 0 1 0 0 00 1 0 0 0 00 0 0 0 1 01 0 0 1 0 01 0 0 0 0 0]
linjiejuzhen(15)0linjiejuzhen(51)0
linjiejuzhen(1)0linjiejuzhen(1)0破坏结点1
linjiejuzhen(5)0linjiejuzhen(5)0破坏结点1
N40000设置迭代次数
nlength(mintrM)总结点数
for i01n
fflag0
for i01n
linjiejuzhenmintrM
clc
linjiejuzhen(i0)0
linjiejuzhen(i0)0
[iiiijjj]find(mintrMlinjiejuzhen>0)
fprintf(＇破坏dd计算系统性：＇i0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
if kekaodu<09
fflag1
end
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
计算结算结点破坏新铺线
linjiezhen_zulinjiejuzhen(zu_3zu_3)第3组邻接矩阵
feiyong_zufeiyong(zu_3zu_3)第i3组已单位铺线费
cilinjiezhen_zu*feiyong_zu 第i3组已铺线费
feiyong_zufeiyong(zu_2zu_3)zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_2zu_3两组点间连线费
[node1node2]find(sijfeiyong_zu)两组点间连线费结点
zu_2zu_3两组点间连线均费avgsij(c2+c3+s23)(d2+d3)中d2d3表示组结点数
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
结点i0破坏必须重结点集删i0
if fflag>0
if length(jiedianzu{i0zu})0
jiedianzu(i0zu)[]
end
jiedianzujiedianzu
计算结点组均成
c[]avgc[]计算结点组均成
for i1length(jiedianzu)
if length(jiedianzu{i})0
c(i)99999999999 第i3组已铺线费
avgc(i)999999999 第i组已均结点铺线费
else
zu_ijiedianzu{i}
linjiezhen_zulinjiejuzhen(zu_izu_i)第3组邻接矩阵
feiyong_zufeiyong(zu_izu_i)第i组已单位铺线费
c(i)sum(sum(linjiezhen_zu*feiyong_zu))2 第i3组已铺线费
avgc(i)c(i)length(zu_i) 第i组已均结点铺线费
end
end
选取初始结点z0求成低结点数组10％
[tempindex0]sort(avgc)
jiedianzu00jiedianzuc00
for i1length(jiedianzu00)
if length(jiedianzu{index0(i)})>n*010
z0jiedianzu{index0(i)}已入网中结点
jiedianzu00(index0(i))[]jiedianzu00中移已入网中结点
c(index0(i))[]成c中移已入网中结点成
c0c0+c(index0(i))已入网中结点总成
break
end
riwangzuxu[riwangzuxuindex0(i)]
end
iter0
lianxian[]
while length(z0)
fprintf(＇第d次迭代－－－－－－－＇iter)
计算z0组组间短距离sij连接结点
s[]
z0zilianjieidian[]
重新计算jiedianzu00中
for i1length(jiedianzu00)
feiyong_zufeiyong(z0jiedianzu00{i})zu_2zu_3两组点间连线费矩阵
sijmin(min(feiyong_zu))zu_0zu_0两组点间连线费
s(i)sijzu_0zu_i两组点间连线费
[node1node2]find(sijfeiyong_zu)zu_0zu_i两组点间连线费结点
z0zilianjieidian[z0zilianjieidianz0(node1(1))jiedianzu00{i}(node2(1))]
zu_0zu_i两组点间连线费应结点
end
计算联入结点均总成
avgs[]
for i1length(jiedianzu00)
avgs(i)(s(i)+c(i))length(jiedianzu00{i})计算新连入结点均成
if abs(prod(jiedianzu00{i}i0))0
avgs(i)9999999999999
end
end
minavgsavgs(1)t01
for i1length(jiedianzu00)
if minavgs>avgs(i)
minavgsavgs(i)t0i选t0组联入z0时新连入结点均成低
end
end
z0[z0jiedianzu00{t0}]t0组合z0组
lianxian[lianxian z0zilianjieidian(t0)]
jiedianzu00(t0)[]删t0组
c0c0+c(t0)+s(t0)计算入网总成余组成重新计算c
c(t0)[]
disp(＇＇)
fprintf(＇破坏结点d连接系统性：＇i0)
kkdlength(z0)n
fprintf(＇破坏结点d连接联网成：＇i0)
clwcbc0
fprintf(＇破坏结点d重新连接结点：＇i0)
lianxianlianxian
end
pause
end
end for 破坏结点i0
附录7：问题四求解程序
clearclc
global linjiejuzhen00
load data1mat
linjiejuzhen00mintrM
kedajuzhenkedajz(linjiejuzhen00N)
[zuidazudsjiedianzu]fenzu(kedajuzhen)
linjiejuzhen_jianbian
linjiejuzhenlinjiejuzhen00
N40000设置迭代次数
nlength(mintrM)总结点数
fidfopen(＇wenti44txt＇＇w＇)
for i01n
for j01n
linjiejuzhenlinjiejuzhen00
clc
if linjiejuzhen(i0j0)>0
linjiejuzhen(i0j0)0
linjiejuzhen(j0i0)0
fprintf(fid＇＼n＇)
fprintf(fid＇切断边dd计算系统性：＼n＇i0j0)
fprintf(＇切断边dd计算系统性：＇i0j0)
kedajuzhenkedajz(linjiejuzhenN)根邻接矩阵计算达矩阵
[zuidazudsjiedianzu]fenzu(kedajuzhen)jiedianzu中元素已分组组连通组间联通
disp(＇网络度：＇)
kekaoduzuidazudsn
fprintf(fid＇网络度：d＼n＇kekaodu)
for i1length(jiedianzu)
fprintf(＇第d组结点组结点连通组间连通＇i)
eval([＇zu_＇num2str(i)＇jiedianzu{i}＇])
end
disp(＇－－－－－统计结果请ENTER键继续－－－－－－＇)pause
end
end
end
fclose(fid)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档