第七章图论-3rd-li课件.pptVIP

*/41 例如，已知程序Prg中的过程集合VPrg={p1，p2，p3，p4，p5}，其过程的调用关系可表成下图所示的有向图，该图的邻接矩阵A为。 A= 可达性矩阵判断递归过程 图16.4.6 */41 于是可求得A+: A+= 由此可知，p2，p4和p5是递归的。 可达性矩阵判断递归过程 */41 三、关联矩阵 给定无环的有向图D=V，E，V={v1，v2，…，vm}，E={e1，e2，…，en}，令 则称B=(bij)m×n是D的关联矩阵。 */41 例题 例如，求下图所示的有向图的关联矩阵B(D)。 B(D)= */41 B(D)有如下性质： =0，j=1，2，…，n，表明矩 阵中每列元素之和为0，从而矩阵所有 元素之和为0。 ∑(+1)=∑(-1)=|E|，表明有向图的握手定理。 */41 B(D)有如下性质： 第i行中，∑(+1)=d+(vi)， |∑(-1)|=d-(vi)。 平行边所对应的列相同。 类似地可定义无向图的关联矩阵，略去了，有兴趣读者请参阅有关书籍。 */41 作业 P152， 1，3， 6，10 * 对于V中各元素间不同的次序关系，能够求得同一个图G的任何一个邻接矩阵。首先交换矩阵中的一些行，而后交换相对应的各列，就能够由图G的任何一个邻接矩阵，求得同一个图G的另外一个邻接矩阵。 第七章 图论 */41 7.4图的矩阵表示 一、邻接矩阵 定义： 设 是一个简单有向图，其中的结点集合 ，并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A，使得其中的元素 则称这样的矩阵A是图G的邻接矩阵。 */41 邻接矩阵 定义：元素或为0或为1的任何矩阵，都称为比特矩阵或布尔矩阵。 邻接矩阵也是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。 */41 邻接矩阵 图的邻接矩阵不具有唯一性。 对于给定简单有向图 来说，其邻接矩阵依赖于集合V中的各元素间的次序关系。 给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。 */41 邻接矩阵 例：写出下图的邻接矩阵，并计算各个节点的出度和入度。 解：首先给各结点安排好一个次序，譬如说是 。得出邻接矩阵如下： */41 邻接矩阵 上例中，如果重新把各结点排列成 ，就能写出另外一个矩阵如下： 如果首先交换第一行和第三行，而后交换第一列与第三列，接着交换v2和v3所对应的行，而后交换v2和v3所对应的列，那么就能够由邻接矩阵A2求得邻接矩阵A1。 */41 邻接矩阵 对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的n！个邻接矩阵都是相似的。 今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。 */41 邻接矩阵 由邻接矩阵判断有向图的性质： 如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。 如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。 对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。 如果给定有向图是反对称的，则对于所有的i和j和i≠j而言，aij=1 蕴含aji=0。 */41 邻接矩阵 可以把简单有向图的矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵，在多重边图或加权图的情况下，可以令 其中的wij，或者是边 的重数，或者是边 的权。另外，若 ，则 。 在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。 */41 邻接矩阵 逆图的邻接矩阵： 如果给定的图 是一个简单有向图，并且其邻接矩阵是A，则图G的逆图的邻接矩阵 是A的转置 。对于无向图或者对称的有向图来说，应 有 。 */41 在图上的意义 定义矩阵 。设 是邻接矩阵中的第i行和第j列上的 元素