5
矩阵计算结果
v4
6 5
v5
4
v1
5
1
7
3 4
v6
v2
2
v3
习题
第一版：

P. 265，第四章习题1、2。
第二版：

P. 284，第四章习题3、5。
5
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T
T T T T
v2 5 0 2 1 7 v3 2 0 3 4 v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
5
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T v2 5 0 2 1 7 v3 2 0 3 4 v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
5
5
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T
T T T
v2 5 0 2 1 7 v3 2 0 3 4 v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
第二节 最小生成树
什么是树？ 构造生成树的方法 最小生成树问题 寻找最小生成树的方法
一、什么是树？
树：不含圈的连通图 树的基本性质
任意两点之间有且只有一条链 若树有p个顶点，则共有q=p-1条边 若图是连通的，且q=p-1，则该图不含圈， 因此是树 若图不含圈，且q=p-1，则该图联通，因此 是树。
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T v2 5 0 2 1 7 T v3 2 0 3 4 T v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
x
ij
n 1 S 1, S A
( i , j )S
x
ij
xij 0,1
四、寻找最小生成树的方法
Kruskal方法 破圈法 矩阵计算法
Kruskal方法
v4
6 5
v5
4
v1
5
1
7
3 4
v6
v2
2
v3
矩阵计算方法
v1 v2
T v1 0
v3 v4v5 v6 v2 5 0 2 1 7 v3 2 0 3 4 v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
矩阵计算方法
v1 v2
T v1 0
v3 v4
v5 v6
T v2 5 0 2 1 7 v3 2 0 3 4 T v4 6 1 0 5 v5 7 3 5 0 4 v6 4 4 0 6
5

二、构造生成树的方法
破圈法 避圈法
v4
2
v5
v1
1 3
4
v6
v2
v3
避圈法
v4
v1
v5
v6
v2
v3
三、最小生成树
最小生成树的定义 最小生成树的定理
v4
v1
水塔 6 1 5 7
5
v5
4 3 4
v6
v2
2
v3
最小生成树的数学模型
min
( i , j ) A
w
ij
xij
( i , j ) A