题目

在图 G= 中，V 为结点的集合，E 为边的集合，则 sum_(v in V) deg(v)=A. 2|V|B. |V|^2C. 2|E|D. |E|^2

在图 $G=$ 中，$V$ 为结点的集合，$E$ 为边的集合，则 $\sum_{v \in V} \deg(v)=$

A. $2|V|$

B. $|V|^2$

C. $2|E|$

D. $|E|^2$

题目解答

答案

C. $2|E|$

解析

本题考查图论中的握手定理（Handshaking Lemma），核心在于理解边与顶点度数之间的关系。关键点在于：每条边连接两个顶点，因此每条边会为两个顶点各贡献1度。通过这一基本关系，可以推导出所有顶点度数之和等于边数的两倍。

握手定理的应用

  1. 边与度数的关联：在图中，每条边连接两个顶点。例如，边$(u, v)$存在时，顶点$u$的度数加1，顶点$v$的度数也加1。
  2. 总度数的计算：假设图中共有$|E|$条边，每条边为两个顶点各贡献1度，因此所有顶点的度数之和为$2 \times |E|$。
  3. 排除干扰项：
    • 选项A（$2|V|$）：仅在所有顶点度数均为2时成立，但题目未限定此条件。
    • 选项B、D（$|V|^2$或$|E|^2$）：与边或顶点的平方无关，明显不符合逻辑。

综上，正确答案为C. $2|E|$。