i到v
j的长为m

1的通路数
k 1
显然，atii是vi到自身的长度-吴扬为扬t-的回路数。
7
§11.3 图的矩阵表示 1. 邻接矩阵(3)
例2：求例1中v2到其他顶点的长为3的通路数。
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 0 1 0 0 2 0 1 0 0 2 1 0 0 0 A2 A A 0 1 0 0 0 0 1 0 0 0 2 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0
此时系统是否处于死锁状态？
-吴扬扬-
3
§11.2 通路回路和连通性 3. 赋权图最短通路问题
赋权图 设G=<V, E>, 若eE, 有一实数w(e)与之对应, 则称G为赋权图， 记为G=<V, E, W>, w(e)称为e的权。 在赋权图中，一条通路的长为该通路上边权之和，
顶点u, v的距离d(u, v)为从u到v的最短通路的长度。
{v1,v2,v3}
7 6 ∞ v5 6
{v1,v2,v3,v5}
7
10 v4 7
{v1,v2,v3,v5,v4}
9 v6 59
§11.3 图的矩阵表示 1. 邻接矩阵(1)
邻接矩阵性质
定义：设G=<V, E>是有向图，V={v1, v2, …,vn},
则G的邻接矩阵A=(aij)nn, 其中aij是vi邻接vj的边的条数。
例1：
v2 10 v4
v1
3 6
3
2 2 v6
4 24 v3 v5
d(v1,v4)=?
最短通路问题：设赋权图中的权值均为正数，求赋权图中两顶
点u, v的距离d(u, v)。
-吴扬扬-
4
§11.2 通路回路和连通性 3. 赋权图最短通路问题
Dijkstra算法: 设G=<V, E, W>是赋权图, u, vV, 求u到v的距离。
6
§11.3 图的矩阵表示 1. 邻接矩阵(2)
定理11.3.1设有向图G=<V, E>,V={v1,…,vn}, 邻接矩阵A=(aij)nn, At=(atij)nn, 则 atij 是 vi 到 vj 的长度为 t 的通路数, atii是vi到自身的长度为t的回路数。 证明：归纳法
(1) t=1时，由邻接矩阵的定义知结论成立。
∴ v2到v1的长为3的通路有4条，到v3的长为3的通路有1条…
-吴扬扬-
8
作业：P230 6, P234 1
-吴扬扬-
9
资源分配图 --强连通图的一个应用实例(2)
«资源图
例: 设Rt={r1,r2,r3,r4}，Pt={p1,p2,p3,p4}。 时刻t资源分配状态是：
p1占用资源r4且请求资源r1； p2占用资源r1且请求资源r2和r3； p3占用资源r2且请求资源r3； p4占用资源r3且请求资源r1和r4。 资源分配图Gt=<Rt,E>为：
资源分配图 令Pt={p1，…，pm}为计算机系统在时间t的程序集合， Rt={r1，r2，…，rn}为计算机系统在时刻t的资源集合， 资源分配图Gt=<Rt，E>是有向图，其中 <ri，rj>∈E iff 程序pk已分配到资源ri且等待资源rj。 时刻t计算机系统处于死锁状态 i-吴ff扬资扬-源分配图Gt包含强连通分图2
例1：
v1 v4
v2 v5
v3
v1 v2 v3 v4 v5
v1 1 0 0 0 0
v2

2
0
1
0
0

A v3 0 1 0 0 0
v4

0
0
0
0
1

v5 0 0 0 1 0 55
性质： 邻接矩阵可展示相应图的一些特征 通过对邻接矩阵元素的计算还可以得到对应图的结点度数
主要内容
强连通图的一个应用实例 赋权图、最短通路问题 图的矩阵表示
邻接矩阵
-吴扬扬-
1
资源分配图
--强连通图的一个应用实例(1)
例»
资源分配问题 计算机系统中的程序共享系统资源，如磁盘、CPU、主存等。 当一个程序要求使用某种资源，它需向操作系统发出请求。 资源请求可能发生冲突。如程序A控制着资源r1，又请求资源 r2；而程序B控制着资源r2，又请求资源r1(处于死锁状态)。
⑥ xT,ls(x):=min{ls(x),ls(t)+w(t,x)}, 转(3)。
v2 10v4
v1
3 4v36
3 2
2
2v6 4
v5
S
ls(v2) ls(v3) ls(v4) ls(v5) ls(v6) t ls(t)
{v1} {v1,v2}
3 4 ∞ ∞ ∞ v2 3 4 13 ∞ ∞ v3 4
(2) 设t=m时，结论成立。
(3) t=m+1时，Am1 Am A (
n
a
m ik

a
kj
)nn
n

a m1 ij

a
m ik
Hale Waihona Puke akjk 1
k 1
aimk是vi到vk长为m的通路数，akj 是vk到vj长为1的通路数,
n

a
m ik

a
kj，即a
m ij
1是v
① S:={u}, T:=V-S;
② xT, 若(u, x)E, 则ls(x):=w(u, x), 否则ls(x):=∞；
③ 求tT,使得ls(t)=min{ls(x)|xT}；
u到x的不含T-{x}顶点的 通路中最短通路长度
④ 若t=v, 则输出ls(t)，结束；
⑤ S:=S{t}, T:=T-{t};
0 0 0 1 0 0 0 0 1 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 1 0 0 0 2 0 1 0 0 4 0 1 0 0 A3 A2 A 2 0 1 0 0 0 1 0 0 0 2 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0