⑴分析并回答下列问题：①图中顶点的度之和与边数之和的关系②有向图中顶点的入度之和与出度之和的关系③具有
个顶点的无向图，至少应有多少条边才能确保是一个连通图若采用邻接矩阵表示，则该矩阵的大小是多少④具有
个顶点的有向图，至少应有多少条弧才能确保是强连通图的为什么
①在一个图中所有顶点的度数之后等于所有边数的2倍无向图中，顶点的度数之和是边数的两倍。有向图中，任意一条边AB（AB）都会给A提供一个出度，给B提供一个入度，所以顶点的度之和2顶点入度之和2顶点出度之和顶点入度之和顶点出度之和边数的两倍。
②对任意有向图顶点出度之和等于入度之和，且等于边的条数
③至少应有
1条边。大小是

④
。在有向图G中，如果对于任何两个不相同的点ab，从a到b和从b到a都存在路径，则称G是强连通图，强连通图必须从任何一点出发都可以回到原处每个节点至少要一条出路。
⑵设一有向图GVE，其中Vabcde，Eabadbacbcddeeaebec①请画出该有向图，并求各顶点的入度和出度。②分别画出有向图的正邻接链表和逆邻接链表。有向图：
a
b
e
d
c
a：出度2，入度2d：出度1，入度2
正邻接链表
b：出度1，入度3e：出度3，入度1
0a21b12c23d14e3
1
0
1
4
0
33
1
2
逆邻接链表
c：出度2，入度1
f0a21b32c13d24e1
10
4
0
3
4
2
2
4
⑶对图727所示的带权无向图。
①写出相应的邻接矩阵表示。
②写出相应的边表表示。
③求出各顶点的度。
邻接矩阵：
∞963∞∞
9∞∞58
∞
6∞∞29
5
3
52∞∞
7
∞89∞∞
4
∞∞574
∞
边表表示：
顶点表011223344556
各顶点的度：顶点1的度：3
边表019026033135148232249255357454
顶点2的度：3
顶点3的度：4
f顶点4的度：4
顶点5的度：3
⑷已知有向图的逆邻接链表如图728所示。
顶点6的度：3
①画出该有向图。②写出相应的邻接矩阵表示。③写出从顶点V1开始的深度优先和广度优先遍历序列。④画出从顶点V1开始的深度优先和广度优先生成树。有向图：
V2
V3V1
V5
V4
邻接矩阵表示：
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
深度优先遍历序列：V1V4V3V5V2
广度优先遍历序列：V1V2V4V3V5或V1V4V2V3V5
深度优先生成树
fV1V4V3V5V2
广度优先生成树
V1
V4
V2
V3
V5
fr