29.图的矩阵表示.ppt

计算机数学 定理 7.3.1 设G是具有n个结点｛v1, v2, …, vn｝ 的图， 其邻接矩阵为A， 则Ak（k＝1， 2， …）的 （i， j）项元素 a(k)ij 是从vi 到vj 的长度等于k的路 的总数。 证明: 施归纳于k。 当k＝1时， A1＝A， 由A的定义，定理显然成立。 假设当 k＝l 时定理成立， 则当k＝l＋1时， A l+1＝Al ·A， 根据邻接矩阵定义arj是联结vr和vj的长度为1的路数目,a(l)ir是联结vi和vr的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr 经过1条边到vj的总长度为l+1的路的数目 。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。 由定理7.3.1可得出以下结论： 1) 如果对l＝1， 2， …， n-1， Al的（i， j）项元素（i≠j）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。 【例7.3.1】图G＝〈V ,E〉的图形如图7.3.2， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。 1) 由A中a(1)12＝1知， v1和v2是邻接的； 由A3中a(3)12＝2知， v1到v2长度为3的路有两条， 从图中可看出是v1v2v1v2和v1v2v3v2。 2) 由A2的主对角线上元素知， 每个结点都有长度为２的回路， 其中结点v2有两条： v2v1v2和v2v3v2， 其余结点只有一条。 3) 由于A3的主对角线上元素全为零， 所以G中没有长度为３的回路。 4) 由于 所以结点v3和v4间无路， 它们属于不同的连通分支。 5) d（v1， v3）＝２。 对其他元素读者自己可以找出它的意义。 2.有向图的邻接矩阵 与无向图一样， 有向图也能用相应的邻接矩阵表示. 定义 7.3.2 设D＝〈V ,E〉是一个有n 个结点的有向图， 则n阶方阵Ｐ＝（pij）称为图D的可达性矩阵。 其中 1) 令Bn＝A＋A2＋…＋An； 2) 将矩阵Ｂn中不为零的元素均改为１， 为零的元素不变； 3) 将主对角线元素都改为1。 所得的矩阵P就是可达性矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。 因可达性矩阵是一个元素仅为１或０的矩阵（称为布尔矩阵）， 而在研究可达性问题时， 我们对于两个结点间具有路的数目并不感兴趣， 所关心的只是两结点间是否有路存在。 因此， 我们可将矩阵A，A2,…, An,分别改为布尔矩阵A(1)， A(2)， …， A(n)。 【例7.3.2】求出图7.3.3所示图的可达性矩阵。 解: 该图的邻接矩阵为 练习：求下图的可达矩阵 例 右图所示的有向图D的可达矩阵为 有向图的关联矩阵的性质： 教师：田检 内 容 回 顾 √ √ √ √ √ 判 断 题 √ 定义 设有有向图G， 1)若G 的任意两个结点中,至少从一个结点可达另一个结点,则称图G 是单向连通的; 2)如果G的任意两个结点都是相互可达的,则称图G是强连通的; 3)如果略去边的方向后， G成为连通的无向图，则称图G是弱连通的。 定义 设无向图G =〈V,E〉的结点集为 边集为 则矩阵 称为G的邻接矩阵， 其中 图的矩阵表示 1.无向图的邻接矩阵 简单无向图的邻接矩阵具有下列性质： (1)简单无向图的邻接矩阵是对称矩阵； (2)主对角线元素皆为0； (3)每一行（以及每一列）各元素的和等于相应 结点的度。 例1 写出下图所示无向图G的邻接矩阵A(G)： 如图7.3.1所示的图G， 求其邻接矩阵A 下面的定理说明， 在邻接矩阵A的幂A2， A3， …等矩阵中， 每个元素有特定的含义。 图7.3.1 G 所以 2) 结点vi 到vj （i≠j）间的距离d（vi， vj） 是使Al（l＝1， 2， …， n-1 ）的（i， j）项元 素不为零的最小整数l。 3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。 图 7.3.2 但注意这里A 不一定是对称的。 定义 设有向图D=V,E, V={v1, v2,