计算机考研408数据结构-图专题2009-2020年真题

2009年

【2009年题7】 下列关于无向连通图特性的叙述中，正确的是______。
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减 1
III. 至少有一个顶点的度为 1

A. 只有 I   B. 只有 II   C. I 和 II   D. I 和 III

解析：
每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次（出度和入度），故所有顶点的度之和为边数的两倍，I 正确。$n$ 个顶点、$n-1$ 条边可以构成无向连通图，比如树，II 错误。顶点数为 $N$（$N \geqslant 1$）的无向完全图中不存在度为 1 的顶点，III 错误。

2010年

【2010年题7】 若无向图 G = (V, E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是______。

A. 6   B. 15   C. 16   D. 21

解析： 要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通。首先考虑极限不连通情况：6 个顶点构成完全连通子图 G1，需 $$ 条边，此时第 7 个顶点为孤立点；然后再添加一条边将第 7 个节点与 G1 连接起来，图必连通，共需 16 条边。