《集合论与图论》第22讲1 第22讲图的矩阵表示 ?1. 关联矩阵M(D), M(G) ?2. 用基本联矩阵M f (G)求所有生成树 ?3. 邻接矩阵A(D), 相邻矩阵A(G) ?4. 用A的幂求不同长度通路(回路)总数 ?5. 可达矩阵P(D), 连通矩阵P(G) ?6. 单源最短路径问题, Dijkstra算法 《集合论与图论》第22讲2 有向图关联矩阵 ?设D=<V,E>是无环有向图,V={v 1 ,v 2 ,…,v n }, E={e 1 ,e 2 ,…,e m } ?关联矩阵(incidence matrix): M(D)=[m ij ] n×m , 1, v i 是e j 的起点 m ij = 0, v i 与e j 不关联 -1, v i 是e j 的终点 《集合论与图论》第22讲3 有向图关联矩阵(例) ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ?? = 110000 111100 001011 000111 )( 654321 4 3 2 1 eeeeee v v v v DM v 1 v 2 v 4 v 3 e 1 e 2 e 3 e 5 e 4 e 6 《集合论与图论》第22讲4 有向图关联矩阵(性质) ?每列和为零: Σ n i=1 m ij =0 ?每行绝对值和为d(v): d(v i )=Σ m j=1 m ij , 其中 1的个数为d + (v), -1的个数为d - (v) ?握手定理: Σ n i=1 Σ m j=1 m ij =0 ?平行边: 相同两列 ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ?? = 110000 111100 001011 000111 )( 654321 4 3 2 1 eeeeee v v v v DM 《集合论与图论》第22讲5 无向图关联矩阵 ?设G=<V,E>是无环无向图,V={v 1 ,v 2 ,…,v n }, E={e 1 ,e 2 ,…,e m } ?关联矩阵(incidence matrix): M(G)=[m ij ] n×m , 1, v i 与e j 关联 m ij = 0, v i 不与e j 关联 《集合论与图论》第22讲6 无向图关联矩阵(例) ? ? ? ? ? ? ? ? ? ? ? ? = 100100 111000 010011 001111 )( 654321 4 3 2 1 eeeeee v v v v GM v 1 v 2 v 4 v 3 e 1 e 2 e 3 e 4 e 6 e 5 《集合论与图论》第22讲7 无向图关联矩阵(性质) ?每列和为2: Σ n i=1 m ij =2 ( Σ n i=1 Σ m j=1 m ij =2m ) ?每行和为d(v): d(v i )=Σ m j=1 m ij ?每行所有1对应的边构成断集: [{v i }, {v i }] ?平行边: 相同两列 ?伪对角阵: 对角块是连通分支 ? ? ? ? ? ? ? ? ? ? ? ? = 100100 111000 010011 001111 )( 654321 4 3 2 1 eeeeee v v v v GM ? ? ? ? ? ? ? ? ? ? ? ? = )( )( )( )( 2 1 k GM GM GM GM O 《集合论与图论》第22讲8 无向图关联矩阵的秩 ?定理10.1: G连通?r(M(G))=n-1 (F={0,1}) ?证明: (1) M(G)每行对应1个断集, 断集空 间C 断 的维数是n-1, 所以r(M(G))≤n-1. (2) M(G)的前n-1行M 1 ,M 2 ,…,M n-1 线性无 关, 所以r(M(G))≥n-1. (反证)若前s行 线性相关, M 1 ⊕M 2 ⊕…⊕M s =0 1×m , 则 每列有2个1或全是0. 令V 1 ={v 1 ,v 2 ,…,v s }, 则(V 1 ,V 1 )=?, 即G不 连通, 矛盾! # ? ? ? ? ? ? ? ? ? ? ? ? = S M M M M M 2 1 ' 《集合论与图论》第22讲9 无向图基本关联矩阵 ?设G=<V,E>是无环无向图,V={v 1 ,v 2 ,…,v n }, E={e 1 ,e 2 ,…,e m } ?参考点: 任意1个顶点 ?基本关联矩阵(fundamental incidence matrix): 从M(G)删除参考点对应的行, 记 作M f (G) 《集合论与图论》第22讲10 无向图基本关联矩阵的秩 ?定理10.2: G连通?r(M f (G))=n-1. # ?推论1: G有p个连通分支?r(M f (G))=n-p, 其中M f (G)是从M(G)的每个对角块中删除 任意1行而得到的. # ?推论2: G连通?r(M(G))=r(M f (G))=n-1. # 《集合论与图论》第22讲11 基本关联矩阵与生成树 ?定理10.3: G连通, M’ f 是M f (G)中任意n-1 列组成的方阵, M’ f 中各列对应的边集是 {e i1 ,e i2 ,…, e i(n-1) }, T是导出子图G[{e i1 , e i2 ,…,e i(n-1) }], 则 T是G的生成树? M’ f 的行列式|M’ f |≠0 ?证明: M f (T)=M’ f , T是G的生成树?T连通 ?r(M f (T))=n-1?r(M’ f )=n-1?M’ f 满秩? |M’ f |≠0. # ?说明: 上述运算是在F={0,1}上进行的 《集合论与图论》第22讲12 用关联矩阵求所有生成树 ?忽略环, 求关联矩阵 ?任选参考点, 求基本关联矩阵 ?求所有n-1阶子方阵,计算行列式,行列式 非0的是生成树 《集合论与图论》第22讲13 求所有生成树(例) ? ? ? ? ? ? ? ? ? ? ? ? = 100100 111000 010011 001111 )( 654321 4 3 2 1 eeeeee v v v v GM v 1 v 2 v 4 v 3 e 1 e 2 e 3 e 4 e 6 e 5 《集合论与图论》第22讲14 求所有生成树(例,续) ? ? ? ? ? ? ? ? ? ? ? ? = 100100 111000 010011 )( 654321 4 3 2 eeeeee v v vGM f v 1 v 2 v 4 v 3 e 1 e 2 e 3 e 4 e 6 e 5 《集合论与图论》第22讲15 求所有生成树(例,续) ? ? ? ? ? ? ? ? ? ? ? ? = 100100 111000 010011 )( 654321 4 3 2 eeeeee v v vGM f v 1 v 2 v 4 v 3 e 1 e 2 e 3 e 4 e 6 e 5 13,5,611,4,6 12,3,501,2,4 14,5,611,5,6 13,4,511,3,6 12,4,611,3,4 12,3,601,2,5 03,4,601,4,5 12,5,611,3,5 02,4,501,2,6 12,3,401,2,3 《集合论与图论》第22讲16 有向图邻接矩阵 ?设D=<V,E>是有向图,V={v 1 ,v 2 ,…,v n } ?邻接矩阵(adjacence matrix): A(D)=[a ij ] n×n , a ij = 从v i 到v j 的边数 v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA 《集合论与图论》第22讲17 有向图邻接矩阵(性质) ?每行和为出度: Σ n j=1 a ij =d + (v i ) ?每列和为入度: Σ n i=1 a ij =d - (v j ) ?握手定理: Σ n i=1 Σ n j=1 a ij =Σ n i=1 d - (v j )=m ?环个数: Σ n i=1 a ii v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA 《集合论与图论》第22讲18 邻接矩阵与通路数 ?设A(D)=A=[a ij ] n×n , A r =A r-1 ?A,(r≥2), A r =[a (r) ij ] n×n , B r =A+A 2 +…+A r = [b (r) ij ] n×n ?定理4: a (r) ij =从v i 到v j 长度为r的通路总数∧ Σ n i=1 Σ n j=1 a (r) ij =长度为r的通路总数∧ Σ n i=1 a (r) ii =长度为r的回路总数 ?推论: b (r) ij =从v i 到v j 长度≤r的通路总数∧ Σ n i=1 Σ n j=1 b (r) ij =长度≤r的通路总数∧ Σ n i=1 b (r) ii =长度≤r的回路总数. # 《集合论与图论》第22讲19 定理4(证明) ?证明: (归纳法) (1)r=1: a (1) ij =a ij , 结论显然. (2) 设r≤k时结论成立, 当r=k+1时, a (k) it ?a (1) tj =从v i 到v j 最后经过v t 的长度为 k+1的通路总数, a (k+1) ij =Σ n t=1 a (k) it ?a (1) tj =从v i 到v j 的长度为 k+1的通路总数. # k1 《集合论与图论》第22讲20 用邻接矩阵求通路数(例) v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA ? ? ? ? ? ? ? ? ? ? ? ? = 2100 1100 1000 1200 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 3100 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 5300 3200 2100 4300 4 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 1320 2 B ? ? ? ? ? ? ? ? ? ? ? ? = 6400 4200 2200 4420 3 B ? ? ? ? ? ? ? ? ? ? ? ? = 11700 7400 4300 8720 4 B 《集合论与图论》第22讲21 用邻接矩阵求通路数(例,续) ? v 2 到v 4 长度为3和4的通路数: 1, 2 ? v 2 到v 4 长度≤4的通路数: 4 ? v 4 到v 4 长度为4的回路数: 5 ? v 4 到v 4 长度≤4的回路数: 11 ? ? ? ? ? ? ? ? ? ? ? ? = 2100 1100 1000 1200 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 3100 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 5300 3200 2100 4300 4 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 1320 2 B ? ? ? ? ? ? ? ? ? ? ? ? = 6400 4200 2200 4420 3 B ? ? ? ? ? ? ? ? ? ? ? ? = 11700 7400 4300 8720 4 B 《集合论与图论》第22讲22 用邻接矩阵求通路数(例,续) ?长度=4的通路(不含回路)数: 16 ?长度≤4的通路和回路数: 53, 15 ? ? ? ? ? ? ? ? ? ? ? ? = 2100 1100 1000 1200 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 3100 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 5300 3200 2100 4300 4 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 1320 2 B ? ? ? ? ? ? ? ? ? ? ? ? = 6400 4200 2200 4420 3 B ? ? ? ? ? ? ? ? ? ? ? ? = 11700 7400 4300 8720 4 B 《集合论与图论》第22讲23 可达矩阵 ?设D=<V,E>是有向图,V={v 1 ,v 2 ,…,v n }, ?可达矩阵: P(D)=[p ij ] n×n , 1, 从v i 可达v j p ij = 0, 从v i 不可达v j 《集合论与图论》第22讲24 可达矩阵(性质) ?主对角线元素都是1: ?v i ∈V, 从v i 可达v i ?强连通图: 所有元素都是1 ?伪对角阵: 对角块是连通分支的可达矩阵 ? ?i≠j, p ij =1 ? b (n-1) ij > 0 ? ? ? ? ? ? ? ? ? ? ? ? = )( )( )( )( 2 1 k DP DP DP DP O 《集合论与图论》第22讲25 可达矩阵(例) v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 1100 1000 0100 0120 )( 4321 4 3 2 1 vvvv v v v v DA ? ? ? ? ? ? ? ? ? ? ? ? = 2100 1100 1000 1200 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 3100 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 5300 3200 2100 4300 4 A ? ? ? ? ? ? ? ? ? ? ? ? = 3200 2100 1100 1320 2 B ? ? ? ? ? ? ? ? ? ? ? ? = 6400 4200 2200 4420 3 B ? ? ? ? ? ? ? ? ? ? ? ? = 11700 7400 4300 8720 4 B ? ? ? ? ? ? ? ? ? ? ? ? = 1100 1100 1110 1111 P 《集合论与图论》第22讲26 无向图相邻矩阵 ?设G=<V,E>是无向简单图,V={v 1 ,v 2 ,…,v n } ?相邻矩阵(adjacence matrix): A(G)=[a ij ] n×n , a ii =0, 1, v i 与v j 相邻,i≠j a ij = 0, v i 与v j 不相邻 v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 0011 0010 1101 1010 )( 4321 4 3 2 1 vvvv v v v v GA 《集合论与图论》第22讲27 无向图相邻矩阵(性质) ?A(G)对称: a ij =a ji ?每行(列)和为顶点度: Σ n i=1 a ij =d(v j ) ?握手定理: Σ n i=1 Σ n j=1 a ij =Σ n i=1 d(v j )=2m v 2 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 0011 0010 1101 1010 )( 4321 4 3 2 1 vvvv v v v v GA 《集合论与图论》第22讲28 相邻矩阵与通路数 ?设A r =A r-1 ?A,(r≥2), A r =[a (r) ij ] n×n , B r =A+A 2 +…+A r = [b (r) ij ] n×n ?定理5: a (r) ij =从v i 到v j 长度为r的通路总数∧ Σ n i=1 a (r) ii =长度为r的回路总数. # ?推论1: a (2) ii =d(v i ). # ?推论2: G连通?距离d(v i ,v j )=min{r|a (r) ij ≠0}. # 《集合论与图论》第22讲29 用相邻矩阵求通路数(例) ? ? ? ? ? ? ? ? ? ? ? ? = 2111 1101 1031 1112 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 2142 1031 4324 3142 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 7466 4324 62116 6467 4 A v 1 v 2 v 4 v 3 ? ? ? ? ? ? ? ? ? ? ? ? = 0011 0010 1101 1010 )( 4321 4 3 2 1 vvvv v v v v GA 《集合论与图论》第22讲30 用相邻矩阵求通路数(例,续) ? v 1 到v 2 长度为4的通路数: 6 14142,14242,14232,12412,14212,12142 ? v 1 到v 3 长度为4的通路数: 4 12423,12323,14123,12123 ? v 1 到v 1 长度为4的回路数: 7 14141,14241,14121,12121, 12421,12321,12141, ? ? ? ? ? ? ? ? ? ? ? ? = 2111 1101 1031 1112 2 A ? ? ? ? ? ? ? ? ? ? ? ? = 2142 1031 4324 3142 3 A ? ? ? ? ? ? ? ? ? ? ? ? = 7466 4324 62116 6467 4 A v 1 v 2 v 4 v 3 《集合论与图论》第22讲31 连通矩阵 ?设G=<V,E>是无向简单图,V={v 1 ,v 2 ,…,v n }, ?连通矩阵: P(G)=[p ij ] n×n , 1, 若v i 与v j 连通 p ij = 0, 若v i 与v j 不连通 《集合论与图论》第22讲32 连通矩阵(性质) ?主对角线元素都是1: ?v i ∈V, v i 与v i 连通 ?连通图: 所有元素都是1 ?伪对角阵: 对角块是连通分支的连通矩阵 ?设B r =A+A 2 +…+A r = [b (r) ij ] n×n , 则?i≠j, p ij =1 ? b (n-1) ij > 0 ? ? ? ? ? ? ? ? ? ? ? ? = )( )( )( )( 2 1 k GP GP GP GP O 《集合论与图论》第22讲33 连通矩阵(例) v 1 v 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 100000 011000 011000 000111 000111 000111 P v 3 v 2 v 6 v 5 《集合论与图论》第22讲34 单源最短路径问题 ?单源最短路径(single-source shortest paths)问题: 给定带权图G(有向或无向)和 顶点s, 求从s到其余顶点的最短路径 ?所有顶点之间最短路径(all-pairs shortest paths)问题: 给定带权图G(有向或无向), 求G所有顶点对之间的最短路径 ?带权图路径长度: W(P)=Σ e∈E(P) W(e) ?E.W.Dijkstra,1959, 理论O(m+nlogn), O(m+n√logC),实践O(m+nC),C=maxW(e) 《集合论与图论》第22讲35 Dijkstra算法 ?输入: 带权图G=<V,E,W>, W非负, s∈V ?输出: 以s为根的最短路径树 ?算法: d(s)=0; pred(s)=0; d(j)=∞ for all j∈V-{s}; LIST=V; 《集合论与图论》第22讲36 Dijkstra算法(续) while LIST≠? {Vertex selection} let i be a vertex for witch d(i)=min j∈LIST d(j); LIST=LIST-{i}; {Distance update} for each (i,j)∈E if d(j)>d(i)+W(i,j) then d(j)=d(i)+W(i,j); pred(j)=i; 《集合论与图论》第22讲37 Dijkstra算法(例1-1) 1 2 3 4 5 7 4 2 1 3 4 2 5 s 1 2 3 4 5 7 4 2 1 3 4 2 5 0 ∞∞ ∞∞ 1,2,3,4,5 LIST 3 2 d(2)=7,d(3)=410,∞,∞,∞,∞1 更新选标号遍 《集合论与图论》第22讲38 Dijkstra算法(例1-2) 1 2 3 4 5 7 4 2 1 3 4 2 5 s 1 2 3 4 5 7 4 2 1 3 4 2 5 0 7 ∞ 4 ∞ 2,3,4,5 1,2,3,4,5 LIST d(2)=min{7,4+2}=6, d(5)=9 30,7,4,∞,∞2 d(2)=7,d(3)=410,∞,∞,∞,∞1 更新选标号遍 《集合论与图论》第22讲39 Dijkstra算法(例1-3) 1 2 3 4 5 7 4 2 1 3 4 2 5 s 1 2 3 4 5 7 4 2 1 3 4 2 5 0 6 ∞ 49 d(4)=9, d(5)=min{9,6+1}=7 22,4,50,6,4,∞,93 2,3,4,5 LIST d(2)=min{7,4+2}=6, d(5)=9 30,7,4,∞,∞2 更新选标号遍 《集合论与图论》第22讲40 Dijkstra算法(例1-4,5) 1 2 3 4 5 7 4 2 1 3 4 2 5 s 1 2 3 4 5 7 4 2 1 3 4 2 5 0 69 47 d(5)=min{7,9+4}=7440,6,4,9,75 d(3)=min{4,7+2}=454,50,6,4,9,74 d(4)=9, d(5)=min{9,6+1}=7 22,4,50,6,4,∞,93 LIST 更新选标号遍 《集合论与图论》第22讲41 d(2)=min{7,4+2}=6, d(4)=9, 32,3,4,50,7,4,∞,∞2 d(4)=9, d(5)=min{9,6+1}=7 22,4,50,6,4,∞,93 d(5)=min{7,9+4}=7440,6,4,9,75 d(3)=min{4,7+2}=454,50,6,4,9,74 d(2)=7,d(3)=411,2,3,4,50,∞,∞,∞,∞1 LIST 更新选标号遍 Dijkstra算法(例1-1~5) 《集合论与图论》第22讲42 Dijkstra算法(例1-结果) 1 2 3 4 5 7 4 2 1 3 4 2 5 s 1 2 3 4 5 7 4 2 1 3 4 2 5 0 69 47 《集合论与图论》第22讲43 Dijkstra算法(例1) 1 2 3 4 5 7 4 2 1 3 4 2 5 0 ∞∞ ∞∞ 1 2 3 4 5 7 4 2 1 3 4 2 5 0 7 ∞ 4 ∞ 1 2 3 4 5 7 4 2 1 3 4 2 5 0 6 ∞ 49 1 2 3 4 5 7 4 2 1 3 4 2 5 0 69 47 《集合论与图论》第22讲44 例14.1 6 5 3 6 2 5 4 1 5 2 2 2 2 6 5 3 6 2 5 4 1 5 2 2 2 2 0 0 1 6 5 3 6 2 5 4 1 5 2 2 2 2 01 4 5 1 3 3 3 3 6 6 5 3 6 2 5 4 1 5 2 2 2 2 01 3 3 6 9 6 6 5 3 6 2 5 4 1 5 2 2 2 2 01 3 3 6 9 6 6 9 11 6 5 3 6 2 5 4 1 5 2 2 2 2 01 3 3 6 8 6 8 6 5 3 6 2 5 4 1 5 2 2 2 2 01 3 3 6 8 6 8 6 5 3 6 2 5 4 1 5 2 2 2 2 《集合论与图论》第22讲45 总结 ?关联矩阵M(D), M(G) ?用基本联矩阵M f (G)求所有生成树 ?邻接矩阵A(D), 相邻矩阵A(G) ?用A的幂求不同长度通路(回路)总数 ?可达矩阵P(D), 连通矩阵P(G) ?单源最短路径问题, Dijkstra算法 《集合论与图论》第22讲46 作业(#18) ? p271, 习题十, 2,4 ? p368, 习题十四, 2 《集合论与图论》第22讲47 习题讲解(#14) ?p234, 习题八, 7,9,13 ?7. 《集合论与图论》第22讲48 习题讲解(#14) ?p234, 习题八, 7,9,13 ?9. |E(K n )|=n(n-1)/2, m=(n-1)(n-2)/2+2, |E(K n )|-m=n-3, G是从K n 删除n-3边. ?u,v∈V(G), (u,v)?E(G)?d(u)+d(v)≥ 2(n-1)-2-(n-4)=n, ∴ G是哈密顿图. 反例: G是从K n 删除n-2边, δ(G)=1. # 《集合论与图论》第22讲49 习题讲解(#14) ?p234, 习题八, 7,9,13 ?13. G=<V,E>,E={ (u,v) | u和v认识}, ?u,v∈V(G), d(u)+d(v) ≥ n-2, n≥4 ? d(u)+d(v)≥ n-2 ≥ n/2 , ∴ n≥4时G是哈密顿图(?). n=3时, 只有2种 可能: K 3 或K 3 删除1边, G是半哈密顿图. # 《集合论与图论》第22讲50 习题讲解(#15) ? p256, 习题九, 2,3,6,11 ? 2. 设有x个4度顶点, 由握手定理 9+3×3+4x=2(9+3+x-1), x=2. 度数列1 9 3 3 4 2 , 考虑3 3 4 2 , d(T)=T直径 d(T)=6: 33344, 33434, 34334, 43334, 33443, 34343 d(T)=5: 3443, 4433, 4343, 4333, 4333, 3433, 3433, d(T)=4: 344, 14种非同构的. # 《集合论与图论》第22讲51 习题讲解(#15) ?p256, 习题九, 2,3,6,11 ?3. 设有x个树叶, 由握手定理 2(x+n 2 +…+n k -1)=x+2n 2 +3n 3 +…+kn k x= n 3 +2n 4 +…+(k-2)n k +2. # ?6. (反证)假设G和G都无圈, 即都是森林, 所以|E(K n )|=|E(G)|+|E(G)|≤2(n-1), n≥5?|E(K n )|=n(n-1)/2>2(n-1), 矛盾! # 《集合论与图论》第22讲52 习题讲解(#15) ?p256, 习题九, 2,3,6,11 ?11. 设有x个树叶, 由握手定理 2(n-1)=2m =Σd(v)=Σ d(v)=1 d(v)+Σ d(v)=Δ d(v)+Σ 其余v d(v) ≥x+k+2(n-x-1) ∴ x≥k. #