第七章习题答案 - 副本.doc

《第七章习题答案 - 副本.doc》由会员分享，可在线阅读，更多相关《第七章习题答案 - 副本.doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流第七章习题答案 - 副本.精品文档. 分析并回答下列问题： 图中顶点的度之和与边数之和的关系? 有向图中顶点的入度之和与出度之和的关系? 具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少? 具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么? 在一个图中, 所有顶点的度数之后等于所有边数的2倍无向图中，顶点的度数之和是边数的两倍。有向图中，任意一条边AB（A-B）都会给A提供一个出度，给B提供一个入度，所以顶点的度之和 = 2 * 顶点入度之和 = 2*顶点出度之和 =

2、顶点入度之和+顶点出度之和=边数的两倍。对任意有向图顶点出度之和等于入度之和，且等于边的条数至少应有n-1条边。大小是n*n n 。在有向图G中，如果对于任何两个不相同的点a,b，从a到b和从b到a都存在路径，则称G是强连通图，强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路。 设一有向图G=(V,E)，其中V=a,b,c,d,e ， E=, , , , , , , 请画出该有向图，并求各顶点的入度和出度。 分别画出有向图的正邻接链表和逆邻接链表。有向图：a ：出度2，入度2 b ：出度1，入度3 c ：出度2，入度1d ：出度1，入度2 e ：出度3，入度1正邻接链表逆邻接链

3、表 对图7-27所示的带权无向图。 写出相应的邻接矩阵表示。 写出相应的边表表示。 求出各顶点的度。邻接矩阵： 9 6 3 9 5 8 6 2 9 53 5 2 7 8 9 4 5 7 4 边表表示：各顶点的度：顶点1的度：3 顶点2的度：3 顶点3的度：4顶点4的度：4 顶点5的度：3 顶点6的度：3 已知有向图的逆邻接链表如图7-28所示。 画出该有向图。 写出相应的邻接矩阵表示。 写出从顶点V1开始的深度优先和广度优先遍历序列。 画出从顶点V1开始的深度优先和广度优先生成树。有向图：邻接矩阵表示：0 1 0 1 01 0 0 0 01 1 0 0 11 0 1 0 00 1 1 1 0深度优先遍历序列：V1 V4 V3 V5 V2广度优先遍历序列：V1 V2 V4 V3 V5或V1 V4 V2 V3 V5深度优先生成树广度优先生成树