第七章习题答案 - 副本
⑴ 分析并回答下列问题:① 图中顶点的度之和与边数之和的关系? ② 有向图中顶点的入度之和与出度之和的关系? ③ 具有n个顶点的无向图,至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示,则
⑴分析并回答下列问题: ①图中顶点的度之和与边数之和的关系? ②有向图中顶点的入度之和与出度之和的关系? ③具有n个顶点的无向图,至少应有多少条边才能确保是一个连通图?若采用 邻接矩阵表示,则该矩阵的大小是多少? ④具有n个顶点的有向图,至少应有多少条弧才能确保是强连通图的?为什么? ①在一个图中,所有顶点的度数之后等于所有边数的2倍 无向图中,顶点的度数之和是边数的两倍。有向图中,任意一条边AB(A->B)都会给A提 供一个出度,给B提供一个入度,所以顶点的度之和=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,b>,<a,d>,<b,a>, <c,b>,<c,d>,<d,e>,<e,a>,<e,b>,<e,c>} ①请画出该有向图,并求各顶点的入度和出度。 ②分别画出有向图的正邻接链表和逆邻接链表。 有向图: a:出度2,入度2b:出度1,入度3c:出度2,入度1 d:出度1,入度2e:出度3,入度1 正邻接链表 逆邻接链表

