传递闭包R+的Warshall算法:
(1)置新矩阵A=M;(M为R对应的矩阵)
(2)置i=1;
(3)对所有j,如果A[j,i]=1,则对k=1,2,···,n,令
A[j,k]=A[j,k]+A[i,k];
(4)i=i+1;
(5)若i<n
设集合A=(a,b,c,d)上的关系:
R={< a,b>,< b,a>,< b,c>,< c,d>}
(i)用矩阵运算的方法求出R的自反、对称、传递闭包。
(ii)用Warshall算法,求出R的传递闭包。
证明定理17.18.
定理17.18:设G*是具有h(k≥2)个连通分支的平面图G的对偶图,n*m*,r*和n,m,r分别为G*和G的顶点数,边数,面数,则
(1)n*=r,(2)m*= m;(3)r*=n-k+1;
(4)设G*的顶点vt*,位于G的面Rt中,则dG*(vt*)=dcg(Rt).
设A是实对称矩阵,若Rayleigh商R(x)=xTAx/xTx的梯度对某个向量z为零,则z必是A的特征向量。