其他
称矩阵A为网络G的权矩阵。
V5
7
6
4 5
V1
9
V4
2
4
V2
3
0 9 V3 权矩阵A＝ 2 4 7
8
9 2 4 7 0 3 4 0 3 0 8 5 4 8 0 6 0 5 6 0
对于图G=(V,E)，|V|=n，构造一个矩阵 A=(aij)n×n，其中：
第六章 图与网络分析
• 1735年，瑞士数学家欧拉(Leonhard Euler)发表图论方面的第一篇论文， 解决了著名的哥尼斯堡七桥问题 (Koenigsberg bridges problem)。 • 哥尼斯堡城，普雷格尔河，两岛， 七桥 • 能否一次走过全部七桥，不重复地 回到出发点？
Königsberg (Koenigsberg)
步骤
(7)所有T标号中，T(v5)最小，故令P(v5)=8。记录路径(v2,v5)
(9)所有T标号中，T(v4)最小，故令P(v4)=9。记录路径(v2,v4) (10)T(v6)=min[T(v6),P(v4)+l46]=min[13,9+9]=13 T(v7)=min[T(v7),P(v4)+l47]=min[14,9+7]=14 (11)所有T标号中，T(v6)最小，故令P(v6)=13。记录路径(v5,v6) (12)T(v7)=min[T(v7),P(v6)+l67]=min[14,13+5]=13 T(v8)=min[T(v8),P(v6)+l68]=min[+∞,13+4]=17 (13)所有T标号中，T(v7)最小，故令P(v7)=13。记录路径(v5,v7) (14)T(v8)=min[T(v8),P(v7)+l78]=min[17,14+1]=15 (15)因只有一个T标号T(v8),令P(v8)=15，记录路径(v7,v8)，完毕
v1 v2 v 3 v 4 v5 v6 v7 v8 0 2 5 -3 4 6 0 0 -3 0 7 2 0 4 0 0 0 0
v1 v2
v3 v4 v5 v6 v7
0
2 0
0
2 0
0 -2 0 4
2
5
2
0
2 2
0 0
-3 -3 -3 -3 -3 -3
6 6 3 3 6 3 6 9
11 6 6
14 9
例：已知九个人v1, v2,…v9,v1和 两人握过手，v2,v3,v4各和四个人 握过手，v8和六个人握过手，证 明这九个人中一定可以找出三个 人互相握过手。
图的矩阵表示： 网络(赋权图)G=(V,E)，其边(vi,vj)有权wij， 构造矩阵A=(aij)n×n，其中： aij=
wij
0
(vi,vj)∈E
1
v8 5 v7
2 4 5 3
1
3 v0 4 4 2
1
v4
2
v6
5
v5
避圈法：开始选一条最小权的边，以后每一步中，总 从未被选取的边中选一条权最小的边，并使之与已选 取的边不构成圈。
v1 1 v8 5
4 2 4 5 3 1
v2 v0 2
1 3 4 4 2
v3 1 v4 5
v7
v6
v5
将图中的边按由小至大的顺序排列：
奇点
次为奇数的点, 如 v5
图G=(V,E)，若E’是E的子集，V’是V的子集，且E’中 的边仅与V’中的顶点相关联，则称G’=(V’,E’)是G的 一个子图。特别是，若V’=V，则G’称为G的生成子 图(支撑子图)。
v4 (G) v1 v4 (G’) v1
v3
v2
v3
v2
v1 e1
e4
v4 e3
Dijkstra算法步骤： (1)给vs以P标号，P(vs)=0,其余点均给T号, T(vi)=+∞ (2)若vi点为刚得到P标号的点，考虑这样的点 vj:(vi,vj)属于E，且vj为T标号。对vj的T标号 进行如下更改： T(vj)= min[T(vj), P(vj)+lij]
(3)比较所有具有T标号的点，把最小者改为P标 号，即： P(vi)= min[T(vi)]
(6)T(v4)=min[T(v4),P(v3)+l34]=min[9,6+4]=9 T(v5)=min[T(v5),P(v3)+l35]=min[8,6+7]=8
(8)T(v6)=min[T(v6),P(v5)+l56]=min[+∞,8+5]=13 T(v7)=min[T(v7),P(v5)+l57]=min[+∞,8+6]=14
• 破圈法：任取一个圈，从中去掉一条边，再 对余下的图重复直到不再含圈时为止。
• 在图中任取一条边，找到一条与之不构成 圈的边，再找一条前两边不构成圈的边 • 重复直到不再能进行为止
一个乡有九个村，其间道路及各道路长度如图，各边上 的数字表示距离，问如何铺设电线连结各村，用线最短？ v1 v2 v3 1 4
59 40 28 19
30 21
14 15
v1
12 v2
13
20
v3
v4
29 41
v5
22
15
v6
这样问题就变为求从v1到v6的最短路问题。 计算结果：序列{v1,v3,v6}为最短路，路长为49。
aij=
1
0
(vi,vj)∈E
其他
称矩阵A为网络G的邻接矩阵。
V4
V1 V2
V5
0 0 0 A 0 0 0
V6
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0
V3
邻接矩阵
当G为无向图时，邻接矩阵为对称阵。
Dijkstra算法采用标号法。 可用两种标号：T标号和P标号，T标号为试探性标号， P标号为永久性标号。 给vi点一个P标号时，表示从vs到vi点的最短路权，vi 点的标号不再改变。 给vi点一个T标号时，表示从vs到vi点的估计最短路权 的上界，是一种临时标号。凡没有得到P标号的点都有 T标号。 算法的每一步都把某一点的T标号改为P标号，当终点 vt得到P标号时，全部计算结束。
v4 e3 v1 v4 e3 v1
端点及关联边 若边e=(u,v)∈E，则称u,v为e的 端点，也称u,v是相邻的，称e是 点u(及点v)的关联边。
e7 v4 e5 v3 e6
e3
e2 e4
v1
e1 v2
环 若图G中，某个边的两个端点相同，则称e是环。如e7 多重边 若两个点之间有多于一条的边，称这些边为多重边。 如 e1,e2
e5 e6
v5 链 e9 v7 初等链
v2
e2
v6
v3 e7
e8
点边列中没有重复的点和重复边者为初等链。 在上图中{v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6 , e8,v7} 是一条链, 但不是初等链。 {v1,e1,v2,e2,v3,e7,v6,e8,v7} 是一条初等链。
a1
v2
v4
路
当链(圈)上的边方向相同时，称为路。
在上图中，1 , a2 , v3 , a4 , v4 , a7 , v6 }是从v1到v6的一条路。 {v
基本定理
定理1： 任何图中，顶点次数的总和等于边数的2倍。
即
vV
d (v ) 2 E
定理2： 任何图中，次为奇数的顶点必为偶数个。
若全部点均为P标号则停止。否则
二、逐次逼近算法 该算法可用于图中带有负权的边时，求某指定点v1到 图中任意点的最短路。 例：求下图中v1点到各点的最短路。 v2 2 v1 5 -2 v3 4 -3 6 7 v6 v5 3 4 -1 v7 v8
-3
v4
4
2
j i
lij
P1 P2 P3 P4 P5 P6
哥尼斯堡，原为东 普鲁士 (Prussia) 首 府，现属俄罗斯(飞 地)，名为加里宁格 勒(Kaliningrad)
Story in Kö nigsberg
现德国拜仁 的哥尼斯堡
A
Pregel River
C
D
B
A
欧拉将七桥问题归结为如图所示 的一笔画问题，并证明这是不可 能的
C B
D
6.1、图与网络的基本概念
(v0,v2)=1,
(v0,v6)=2, (v0,v5)=4, (v4,v5)=5
(v2,v3)=1,
(v5,v6)=2, (v0,v8)=4,
(v3,v4)=1,
(v0,v3)=3, (v1,v2)=4,
(v1,v8)=1,
(v6,v7)=3, (v0,v7)=5,
(v0,v1)=2
(v0,v4)=4 (v7,v8)=5
v8
3
-1 0
15 10 10 10
例：某工厂使用一台设备，每年年初都要做出决定，如 果继续使用旧的，要付维修费；若购买一台新设备，要 付购买费。试制定一个五年计划，总支出最少。
该设备在各年年初的价格为： 项目 购买费 第1年 11 第2年 12 第3年 13 第4年 14 第5年 14
机器不同役龄的维修费与残值： 使用年数 维修费 残值 0-1 5 4 1-2 6 3 2-3 8 2 3-4 11 1 4-5 18 0
贾代善 贾赦 贾琏 贾政 贾珠 贾宝玉 贾环 贾兰
若图G的生成子图是一棵树，则称该树为G的生 成树(支撑树)。 连通图G=(V,E)，每条边上有非负权L(e)。一 棵生成树所有树枝上权的总和，称为这个生成 树的权。具有最小权的生成树称为最小生成树 (最小支撑树)。 求最小生成树的两种算法： (1)避圈法； (2)破圈法。