第八章----图和网络分析

⑤
6
32
9
11
① 10
③
7
6
8
⑦
12
5
④
5
16 ⑥
解 设xij为选择弧(i，j)的状 态变量，选择弧(i，j)时xij＝1， 不选择弧(i，j)时xij＝0，得到 最短路问题的网络模型：
m in Z
cij xij
(i , j ) E
x12 x13 x14 1


e1{v1,v2} e2 {v1,v2}
e10
e3 {v2,v3} e4 {v3,v4}
e5 {v1,v3} e6 {v3,v5}
v6 e9
e7 {v3,v5} e8 {v5,v6}
e9 {v6,v6} e10{v1,v6}
e1
e2
v2
e5 e3 e4 v4
e8
e6
v5 e7 v3
用μ表示。{ v1, ( v1, v2), v2, ( v2, v5,) v5}
2. 简单链：没有重复边的链。
V1 V3
V4 V7
V5 V8
对于简单链可由顶点表示，如上链 v1 → v2 → v5
3．初等链：顶点也不相同的简单链。v1 → v2 → v5→
v4 → v3
4．圈（闭链）：起点终点一致的链。（与环不同，环
（或发点），记作v1 ，一个称为终点（或收点），记作 vn ，其余的点称为中间点。对每一条弧 (vi ,vj)A，对 应一个数 w i j ，称为弧上的“权”。通常把这种赋权
的图称为网络。
v1 6
7 3
4
v2
v5 15
1 v1 36
v5 2
7
v2
4 5
v4 5
v3
v4 5
v3
赋权 无向图
赋权 有向图
v2
e1 v1
e6 e7
e2
v3
e8 e9
e3
v7
e10 v4 e11 e4
v6 e5 v5
(a)
v2
e1
Hale Waihona Puke e8v1e6 e7 v7
v6 e5
v5
(b)
v2 e1 v1 e6 e7
v6
v3 e9
e10 v7 e11
v4
v5
(c)
子图
支撑子图
（二）、连通图
1. 链：点、边交替或点弧交替的序列。V2
V6
（三）、 图的矩阵表示 对于网络（赋权图）G=（V，E），其中边 (vi , v j ) 有权 w i j ，构造矩阵 A(ai j)nn ，其中：
aij wij
(vi ,vj)E (vi ,vj)E
称矩阵A为网络G的权矩阵。
设图G=（V，E）中顶点的个数为n，构造一个
矩阵 A(ai j)nn ，其中：
为图中任意两点，求一条路 ，使它为从v s 到 v t 的所有
路中总权最短。即：
L() wi j 最小。 (vi , vj )
例 图中的权cij表示vi到vj的距离(费用、时间)，从v1修一条 公路或架设一条高压线到v7，如何选择一条路线使距离最短，建 立该问题的网络数学模型。
②
14
用 d (vi ) 表示；vi 点的出次和入次之和就是该点的次。 所有顶点的入次之和等于所有顶点的出次之和。
9、设 G1=（ V1 , E1 ），G2 =（ V2 ,E2 ）
如果 V2 V1 , E2 E1 称 G2 是G1 的子图； 如果 V2 = V1 , E2 E1 称 G2 是 G1 的支撑子图。
6、一个无环，无多重边的图称为简单图，一个无环， 有多重边的图称为多重图。
7、每一对顶点间都有边相连的无向简单图称为完全图。
有向完全图则是指任意两个顶点之间有且仅有一条有
向边的简单图。
8、以点v为端点的边的个数称为点v 的度（次），记
作 d(v) 。
下图中 d(v1)= 4，d(v6)= 4（环计两度）

4


2
0
3
v 6 3 3 3 0
v1 0 1 0 1 1 1
v
2

1
0
1
1
0
0

B

v3 v4
0

1
1 1
0 1
1 0
0 1
1
0

v
5
1
0
0
1
0
1
v 6 1 0 1 0 1 0
v1 v2 v3 v4 v5 v6
v1 v2 v3 v4 v5 v6
求最短路有两种算法：
一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法； 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵（表格）算法。
最短路的一般提法为：设 G(V,E) 为连通图，图中各边 (vi , v j ) 有权 w （i j wi j 表示 v i , v j 之间没有边），v s , vt
v1 e2
e4 e7
e3
v4 e8
e5 e6
v3
v2
e4
v5
v1
v4 e8
v5
e2
e6
v3
用破圈法求图的最小树。 破圈法：任取一圈，去掉圈中
最长边，直到无圈。
v1
8
v3
7
v5
5
5
4
8
1
2
v2
3
v4
6
v6
最小树长为 C(T)=4+3+5+2+1=15。 注：当一个圈中有多个相同的最长边时，不能同时都 去掉，只能去掉其中任意一条边。最小树有可能不唯 一，但最小树的长度相同
？
？D
A
B
D
A
B
C
C
D3
A
3
B
5
C 3
4
1
3
3
1
2
2
实例2： 下图是一张石油流向管网示意图，A 表示石油开采 地，H 为石油汇集站，B，C，D，E，F 表示可供选择的石 油流动加压站，数字为两地距离（管长），问如何选择管线， 使将油从 A 送到 H 所需油管最短？
A
6B 12
2 2
C
1
6
4 D3
度的道路联结六个城市的电话线网，使电话线的总长度最
短。
v3 5 v5
6
4
v1
17 3
v6
v3
v1
1
v5 3
v6
5
2
4
v2
v4
5
2
v2
4 v4
v2
1
3
5
2
v4
v1
2
v5
4
1
3
v3
三 、最短路问题
最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距
离最短的一条路。
最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题， 还有些如设备更新、投资等问题也可以归结为求最短路问题
只有一条边） v1 → v2 → v3→ v4 → v1
5．连通图： 若图G中任意二点之间至少有一条链连接， 则图G称为连通图，否则称为不连通图。不连通图G每个
连通的部分称为G的一个连通分图。（两个连通分图）
（三）赋权图
在实际应用中，给定一个图G=（V，E）或有向
图D=（V，A），在V中指定两个点，一个称为始点
加边法：取图G的n个孤立点｛v1，v2，…， vn}作为一
个支撑图，从最短边开始往支撑图中添加，见圈回避，
直到连通（有n－1条边）
v1 4
5×
v3 5
2
v2
3
v4
Min C(T)=15
v5
v1 8 v3
7 v5
5
1
5 482
1
v6
v2 3
v4 6 v6
在图中，如果添加边[v1, v2]就形成圈｛v1, v2, v4｝，这时就 应避开添加边[v1, v2]，添加下一条最短边[v3, v6]。破圈法 和加边法得到树的形状可能不一样，但最小树的长度相等
中 V 中的元素 v j 叫做顶点，V 表示图 G 的点集合；E
中的元素 e k 叫做边，E 表示图 G 的边集合。
例
V v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6
E { e 1 ， e 2 ,e 3 ,e 4 ,e 5 ,e 6 ,e 7 ,e 8 ,e 9 ,e 1 } 0 v1
二、 树及最小树问题
已知有六个城市，它们之间 要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。
v1
v2
v6
v3
以点v为端点的边的个数
v5
v4
称为点v 的度（次），
1、一个连通的无圈的无向图叫做树。
树中次为1的点称为树叶，次大于1的点称为分支点。
树 的性质：
（1）树必连通，但无回路（圈）。
（2）n 个顶点的树必有n-1 条边。
（3）树 中任意两个顶点之间，恰有且仅有一条链（初
等链）。
（4）树 连通，但去掉任一条边， 必变为不连通。
（5） 树 无回路（圈），但不相邻的两个点之间加一条
边，恰得到一个回路（圈）。 v1
v2
v6
v3
v5
v4
简单链：没有重复边的链。 初等链：顶点也不相同的简单链。
3、最小生成树问题 如果图 T(V,E1)是图G的一个生成树，那么称E1上所 有边的权的和为生成树T 的权，记作S(T)。如果图G的生