数据结构与算法 - 图

第1关：图的定义和术语

任务描述
本关任务：掌握图的定义和基本术语，并完成相应的选择题。

相关知识
图的定义
图 G 是由顶点集 V 和边集 E ，记为 G=(V,E) ，其中 V(G) 表示图 G 中的顶点的有限非空集合； E(G) 表示图 G 中顶点之间的关系集合。若 则用 ｜V｜ 表示图 G 中顶点的个数，也称为图 G 的阶， E={(u,v)∣u∈V,v∈V} ，用 ∣E∣ 表示图 G 中边的条数。

图的基本术语
下面是一些关于图的基本术语，在后面我们会经常碰到。

1. 有向图
   若 E 是有向边的有限集合时，则图 G 是有向图。弧是顶点的有序对，记为 , 其中 v,w 是顶点， v 称为弧尾， w 称为弧头， 称为从顶点 v 到顶点 w 的弧，也称为 v 邻接到 w ，或 w 邻接自 v 。

第1题

正确答案为 A 。

第2题

正确答案为 B 。

第3题

正确答案为 C 。

第4题

正确答案为 A 。无向连通图对应的生成树也是无向连通图，但此时边数等于顶点数减 1 ，故 Ⅲ 错误。考虑一个无向连通图的顶点恰好构成一个回路的情况，此时每个顶点的度都是 
1
2
3
4
5
6
7
8
9
10
11
12
13
14