04第11章习题答案

《04第11章习题答案》由会员分享，可在线阅读，更多相关《04第11章习题答案（2页珍藏版）》请在装配图网上搜索。

1、第11章习题答案3. 对图11.3的有向图，找出从u1到u4的长度为2,3,4的所有通路，并找出顶点u4上的长度为2,3,4的所有回路。用M2，M3，M4，来验证这些结果。解：从u1到u4长度为2的通路有1条：（u1,u2,u4）从u1到u4长度为3的通路有2条：（u1,u2,u3，u4），（u1,u4,u2，u4）从u1到u4长度为4的通路有3条：（u1,u2,u3，u2，u4），（u1,u2，u4,u2，u4），（u1,u4,u2，u3，u4）顶点u4上的长度为2的回路有1条：（u4,u2,u4）顶点u4上的长度为3的回路有1条：（u4,u2,u3，u4）顶点u4上的长度为4的回路有2条：

2、（u4,u2,u3，u2，u4），（u4,u2，u4,u2，u4）M= M2= M3=M4= 由M2，M3，M4中的第1行第4列的元素可见，从u1到u4长度为2，3，4的通路分别有1条，2条，3条。由M2，M3，M4中的第4行第4列的元素可见，u4上的长度为2,3,4的回路分别有1条，1条，2条，说明所找的上述通路和回路正确。6. 试用图11.4的有向图的邻接矩阵求出可达性矩阵，并利用可达性矩阵求其强分图。解：M= M2= M3= M4=I+M+M2+M3+M4=+ + = R=B（I+M+M2+M3+M4）=RT = RRT =由矩阵RRT可知，该有向图的强分图有：v1， v2，v4，v5， v3