离散数学基础
•单元内容提示
−求道路矩阵的 Warshall 算法
•定义. 无向图的邻接矩阵
−对无向图 G =(V,
E),n =|V|,构造矩阵 A=(a ij )n ×n ,其中称 A 是图 G 的邻接矩阵。
•定理1.
−设 A 1、
A 2 分别为图 G 1、G 2 的邻接矩阵,则 G 1≅G 2 当且仅当存在置换矩阵 P,使得 A 1=PA 2P T 。
•定理2.
−设 A n ×n 是有向图 G 的邻接矩阵,则连接 v i 与 v j (i ≠j ) 的长度为 l 的有向道路的条数等于 A l 的第 i 行第 j 列的元素的数值。−这里的道路是有方向的,但不一定指初等道路。−证明: −设图 G=(V, A),V={v 1, v 2, …, v n }。对 l 作数学归纳法。−归纳基始: »l =1 时,邻接矩阵 A 描述了 G 中任意两点 v i 与 v j 一步可达的的邻接关系。
−归纳假设:
»设 l =k 时,矩阵 A k 的元素 A k [i , j ] 的值是从 v i 到 v j (i ≠j ) 的长度为 k 的有向道路的条数。
−归纳过程:当 l =k +1 时, A k +1 = A k × A −此时:现代心理学史
2017-11-19
1
1[,][,][,]n
k k p A i j A i p A p j +==×∑ − 由归纳假设,A k
[i , p ] 是从 v i 到 v p 的长度为 k 的有向道路的条数。当 A[p , j ]=1 时,可以将这些有向道路扩展为从 v i 到 v j 的经过 v p 的长度为 k +1 的有向道路。取遍所有的可能性后,A k+1[i , j ] 的值就是从 v i 到 v j (i ≠j) 的长度为 k +1 的全部有向道路的条数。
• 定义. 有向图的道路矩阵
− 对有向图 G =(V, R),n =|V|,构造矩阵 P=(p ij )n ×n ,其中
称矩阵 P 是图 G 的道路矩阵或可达矩阵。
− 讨论:有向图 G =(V, R) 的道路矩阵 P 给出了关系 R 的传递闭包 t(R) 的关系矩阵。
• 算法. 求给定有向图 G 的道路矩阵 P
− 对有向图 G =(V, R),n =|V|∈Z +,设 A 为 G 的邻接矩阵,B = A+A 2+A 3+…+A n ‐1,则由[定理2],b ij 表示由 v i 至 v j 的长度为1,或2,或…,或 n ‐1 的路径数目,即为由 v i 至 v j 的全部路径总和。令
即可求得 G 的道路矩阵 P 。算法复杂度 O(n 4)。
• 定义. 二值元素的逻辑运算
− 0∨0 = 0,0∨1 = 1∨0 = 1,1∨1 = 1
− 0∧0 = 0,0∧1 = 1∧0 = 0,1∧1 = 1
• 定义. 二值矩阵的逻辑运算
− 设有 n ×n 阶矩阵 A = (a ij ),B = (b ij ),矩阵元素值域为 {0, 1},定义运算 A ∨B 和 A ⊗B :
1(),(),
()()ij ij ij ij ij ij n ij ik kj k A B a b A B a b A B a b =∨=∨∧=∧⊗=∨∧
• 定义.
− A (1) = A
− A (k ) = A (k −1) ⊗ A ( k ≥2 )
− 注意 A (k ) 与 A k 的区别。
• 定理3.
米兰昆德拉− 设 A n ×n 是有向图 G 的邻接矩阵,若从 v i 到 v j 存在长度为 l 的路,则 [A (l )]ij = 1,否则 [A (l )]ij = 0。
− 证明:对 l 作归纳;或直接引用[定理2]。
• 算法. 求给定有向图 G 的道路矩阵 P
− 对有向图 G =(V, R),n =|V|∈Z +,设 A 为 G 的邻接矩阵,则 G 的道路矩阵 P = A ∨A (2)∨A (3)∨ … ∨A (n ‐1),算法复杂度 O(n 4)。
• Warshall 算法. 设 A n ×n 是图 G 的邻接矩阵,求 G 的道路矩阵 P 。
(1) P ← A
(2) i ← 1
(3) j ← 1
(4) p jk ← p jk ∨ (p ji ∧ p ik ), k = 1 ... n
(5) j ← j +1, if j ≤n goto 4
(6) i ← i +1, if i ≤n goto 3
(7) Stop
• 定理4.
− Warshall 算法以计算复杂度 O(n 3) 在图 G 的道路矩阵 P 上结束。 − 证明:(略)
• 例:
− 有向图 G 的邻接矩阵 A 如下,使用 Warshall 算法求G 的道路矩阵 P 。
− 解:
P ← A ,i=1。
矩阵元素 p jk 处理次序:p 11, p 12, p 13, p 14, p 21, p 22, …, p 31,…, p 41,…, p 44。
断离伤− 按照 p jk ← p jk ∨ (p ji ∧ p ik ), j = 1 ... n , k = 1 ... n
p 11 = p 11∨(p 1i ∧p i1) = p 11∨(p 11∧p 11) = 0 ⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠01000011A = 11011000
p12 = p12∨(p2i∧p i2) = p12∨(p21∧p12) = 1
p13 = p13∨(p3i∧p i3) = p13∨(p31∧p13) = 0
…………
结果:
凝胶谱法
绍兴越秀外国语职业学院−考察第 i 次循环。第 i 列的0元对应的第 j 行有 p ji=0,故
p jk=p jk∨(p ji∧p ik)=p jk∨(0∧p ik)=p jk;第 i 列的1元对应的第 j 行有 p ji=1,故
p jk=p jk∨(p ji∧p ik)= p jk∨p ik , 即将该行与第 i 行做“或”运算。
i =2 的迭代结果:
−(表上作业法) 第 i 次循环时,将第 i 行分别“叠加”到第 i 列的非0元对应的那些行,“叠加”运算是一对行向量各个对应元素的逻辑“或”运算。如上例:
•例:
•进一步的讨论