离散数学离散数学 (12).pdf
Computer Science&Technology0Computer Science&Technology1定理2s(R)=R R-1定理3321)(RRRRRtiiiniRRt1)(定理4Computer Science&Technology2例题1:A=1,2,3,4,5R=,求解:r(R),s(R),t(R),用三种方法。（集合，矩阵，关系图）解:r(R)=R A=,Computer Science&Technology3s(R)=RR-1=,R 2=R R=,=,R 3=R 2R=,=,Computer Science&Technology4R4=R3 R=,=,=R2R5=R4 R=R2 R=R3t(R)=RR2R3R4R5=RR2R3=,Computer Science&Technology50000000000110000100100010RM100000100011100010110001110000010000010000010000010000000000110000100100010AIRr(R)MMMComputer Science&Technology60000000000110000100100010RM001000011011000010010001000100001100000000001000100000000000110000100100010TRRs(R)MMMComputer Science&Technology7Mt(R)=MRMR2MR3MR4MR55432)(RRRRRRtMMMMMMnnRRMM2010000100010010100101001001000000110001100000000000000000000000000000000000RRRMMM关系复合的矩阵表示可以关系复合的矩阵表示可以转换为关系矩阵的逻辑乘转换为关系矩阵的逻辑乘Computer Science&Technology832100100100001000010001001010010000000001100000000000000000000000000000000000RRRMMM43010000100010010100101001001000000000001100000000000000000000000000000000000RRRMMM=2RMComputer Science&Technology95423RRRRRRMMMMMM0000000000110000101101011325432)(RRRRRRRRRtMMMMMMMMMComputer Science&Technology101253451234R(2)r(R)s(R)t(R)1253412534Computer Science&Technology11 t(R)12534R“间接到达的直接到达”。12534Computer Science&Technology12ALGORITHM1 求解传递闭包的一般算法；依据定理4 利用关系的矩阵表示Procedure transitive closure MR(nn)0-1 matrix 1.A:=MR2.B:=A2.FOR i=2,n DO3.begin 4.A:=A MR 求取5.B:=B A 矩阵的逻辑加求闭包6.end B is the 0-1 matrix for R*:矩阵的逻辑乘；：矩阵的逻辑加矩阵乘算法的时间复杂度：计算闭包的时间复杂度：O（n3）O（n4）iniRRt1)(nnRRMMComputer Science&Technology13125340000000000000000001001001000000000011000010010001000000000001100001001000102RRRMMM111三个1说明存在长度为2的通路有三条0 1 0 0 0*0 1 0 0 0 0 1 0 0 0*0 1 1 0 0 1到1 长度为2的通路,1到4 长度为2的通路,Computer Science&Technology141253432100100100001000010001001010010000000001100000000000000000000000000000000000RRRMMM 111三个三个1说明存在长度说明存在长度为为3的的通通路有三条路有三条*1 0 0 0 0 0 1 0 0 02到1 长度为3的通路,2到4 长度为3的通路,Computer Science&Technology1542RRMM53RRMM325432)(RRRRRRRRRtMMMMMMMMMComputer Science&Technology16m1,2=1 表示从1到2 长度为1的通路存在0000000000110000100100010RMnRM表示从i到j长度为n的通路存在1)(,njimComputer Science&Technology17325432)(RRRRRRRRRtMMMMMMMMM325432)(RRRRRRRRRtMMMMMMMMM1201011020000110000000000)(RtM表示从i到j或者直接有通路存在,后者经过若干个中间结点(内点内点)有通路存在1)(,RtjimComputer Science&Technology18aiajakComputer Science&Technology19Computer Science&Technology20Computer Science&Technology21Warshall算法计算闭包的时间复杂度：O（n3）Computer Science&Technology220000000000110000100100010RM0000000000110000100100010W12534RComputer Science&Technology230000000000110000100100010W1001010000110000000000?101000010001001010010*000110001100000000000000000000 1：w1,1=w1,1 w1,k wk,1=w1,1 (w1,1 w1,1)(w1,2 w2,1)(w1,3 w3,1)(w1,4 w4,1)(w1,5 w5,1)=0 (0 0)(1 1)(0 0)(0 0)(0 0)=1w1,2=w1,2 w1,k wk,2=w1,2 (w1,1 w1,2)(w1,2 w2,2)(w1,3 w3,2)(w1,4 w4,2)(w1,5 w5,2)=1 (0 1)(1 0)(0 0)(0 0)(0 0)=1W1,1 w1,1 (w1,k wk,1);W1,2 w1,2 (w1,k wk,2);W1,3 w1,3 (w1,k wk,3)12534w1,3=0Computer Science&Technology240000000000110000100100010W01000010001001010010*000110001100000000000000000000 125341*：w1,4=w1,4 w1,k wk,4=w1,4 (w1,1 w1,4)(w1,2 w2,4)(w1,3 w3,4)(w1,4 w4,4)(w1,5 w5,4)=0 (0 0)(1 1)(0 1)(0 0)(0 0)=1w1,5=01001010000110000000000*?11W1,1 w1,1 (w1,k wk,1);W1,2 w1,2 (w1,k wk,2);W1,3 w1,3 (w1,k wk,3)Computer Science&Technology250000000000110000100100010W01000010001001010010*000110001100000000000000000000 1*：w2,2=w2,4 w2,k wk,2=w2,2 (w2,1 w1,2)(w2,2 w2,2)(w2,3 w3,2)(w2,4 w4,2)(w2,5 w5,2)=0 (1 1)(0 0)(0 0)(1 0)(0 0)=1125341001010000110000000*000*111Computer Science&Technology261001010000110000000000111WW12534t(R)0000000000110000101101011325432)(RRRRRRRRRtMMMMMMMMMComputer Science&Technology27算法的时间复杂度从O（n4）降为 O（n3）Computer Science&Technology28Computer Science&Technology29
