离散数学 7.图

设G 为线图，V={v1 , v2…vn}，A = （aij）nxn为G的邻接矩阵，Am = (aijm)nxn，m = 1,2,n ;Bn = (bijn)nxn = A+ A2+A3+…+An 。则有当vi ≠ vj时，如果bijn > 0，那么vi到vj可达，否则不可达。 把Bn中可达变为1，不可达变为0 ，得的矩阵P=(pij)nxn 为图G的可达性矩阵。

可达矩阵的简洁求法： 设G=< V,E>为线图, A、P分别是G的邻接矩阵和可达性矩阵,则有最短通路P= AV A(2)V A(3)V …V A(m),这里, A(i)表示做矩阵布尔乘法的i次幂.

如果vi到vj可达，则称长度最短的通路为从vi到vj的短程线。距离记为d(i,j)。

结点间距离的判定 无向图相关

若无向图G中的任何两个结点都是可达的，则称G是连通图。 无向完全图Kn都是连通图。 非平凡无向线图G是连通图当且仅当它的可达矩阵P的所有元素均为1。

无向图G = 结点之间的可达关系R = {| u,v ∈V}则R是V上的等价关系。R是自反的，对称的，传递的。

无向图G=< V,E>中结点之间的可达关系R的每个等价类导出的子图都称为G的一个连通分支。用p(G)表示G中的连通分支个数。