题16
题目
【2009 统考真题】下列关于无向连通图特性的叙述中, 正确的是 ( ).
I. 所有顶点的度之和为偶数
II. 边数大于顶点个数减 1
III. 至少有一个顶点的度为 1
A. 只有 I
B. 只有 II
C. I 和 II
D. I 和 III
分析
完全无向图有 n 个节点，那么它就有 n(n-1)/2 条边
连通无向图是指图中任意两个节点之间都存在路径连接的无向图
无向图的度: 指的是一个节点连接的边数。
一个无向图中所有节点的度数之和等于边数的两倍
在无向图中，每条边连接着两个节点，因此每条边会对这两个节点的度数各贡献 1。
完全无向图是指在一个图中，任意两个顶点之间都直接相连的无向图
注意，连通无向图和完全无向图的区别
要注意无向连通图变成了环这个考点
解
无向连通图每条边都连接了两个顶点, 在计算顶点的度之和时每条边都被计算了两次, 所以所有顶点的度之和偶数。
无向连通图对应的生成树也是无向连通图, 但此时边数等于顶点数减 1, II 错误。
考虑 2 个或以上的顶点恰好构成一个环的情况, 此时每个顶点的度都是 2, III 错误。