题目
2.一个无向图[1]有10个顶点,每个顶点的次均为3,则该图的边数为A. 10B. 15C. 20D. 30
2.一个无向图[1]有10个顶点,每个顶点的次均为3,则该图的边数为
A. 10
B. 15
C. 20
D. 30
题目解答
答案
B. 15
解析
本题考查无向图的基本性质,解题思路是利用握手定理来计算无向图的边数。握手定理指出,在无向图中,所有顶点的度数之和等于边数的两倍。
下面进行详细的解答:
- 首先明确握手定理的公式:设无向图 $G=(V, E)$,其中 $V$ 是顶点集,$E$ 是边集,$\sum_{v\in V}d(v) = 2|E|$,这里 $d(v)$ 表示顶点 $v$ 的度数,$|E|$ 表示边的数量。
- 已知该无向图有 $n = 10$ 个顶点,且每个顶点的度数 $d(v)=3$。
- 计算所有顶点的度数之和:根据上述条件,所有顶点的度数之和 $\sum_{v\in V}d(v)=n\times d(v)$,将 $n = 10$,$d(v)=3$ 代入可得,$\sum_{v\in V}d(v)=10\times3 = 30$。
- 由握手定理 $\sum_{v\in V}d(v) = 2|E|$,可得边数 $|E|=\frac{\sum_{v\in V}d(v)}{2}$。
- 将 $\sum_{v\in V}d(v)=30$ 代入上式,可得 $|E|=\frac{30}{2}=15$。