第七章习题答案 - 副本

⑴ 分析并回答下列问题：

① 图中顶点的度之和与边数之和的关系

② 有向图中顶点的入度之和与出度之和的关系

③ 具有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 ：出度2，入度2

b ：出度1，入度3

c ：出度2，入度1

！

d ：出度1，入度2

e ：出度3，入度1

正邻接链表

1

2

3

4

逆邻接链表

a2

b3

c1

d2

e1

1

2

3

4

1?

4

?

4

?

3

0?

4

2

0?

2

⑶对图7-27所示的带权无向图。

① 写出相应的邻接矩阵表示。

② 写出相应的边表表示。

￥

③ 求出各顶点的度。

邻接矩阵：

∞9 6 3 ∞∞

9 ∞∞ 5 8 ∞

6 ∞∞ 2 9 5

3 5 2 ∞∞7

∞8 9 ∞∞4

∞∞ 5 7 4 ∞

边表表示：

#

1

2

3

4

5

1

2

3

4

6

5

顶点表

0 1 9

0 2 6

0 3 3

1 3 5

1 4 8

2 3 2

边表

2 4 9

2 5 5

3 5 7

4 5 4

各顶点的度：

顶点1的度：3 顶点2的度：3 顶点3的度：4顶点4的度：4 顶点5的度：3 顶点6的度：3

⑷已知有向图的逆邻接链表如图7-28所示。

① 画出该有向图。

② 写出相应的邻接矩阵表示。

③ 写出从顶点V1开始的深度优先和广度优先遍历序列。

、

④ 画出从顶点V1开始的深度优先和广度优先生成树。

有向图：

V1

V2

V4V5 V3

邻接矩阵表示：

0 1 0 1 0

1 0 0 0 0

1 1 0 0 1

1 0 1 0 0

0 1 1 1 0

深度优先遍历序列：V1 V4 V3 V5 V2 (

广度优先遍历序列：V1 V2 V4 V3 V5或V1 V4 V2 V3 V5深度优先生成树

广度优先生成树